분류 전체보기104 [알고리즘] 탐욕(그리디) 알고리즘 그리디 알고리즘이란? 탐욕적 알고리즘이라고도 하며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. A에서 C까지 가는 최단 경로는? A에서 B로 갈 때 가장 적은 비용인 20을 고른다. B에서 C로 갈 때 가장 적은 비용인 8을 고른다. A에서 C로 가는 최단 경로는 20+8=28인 것을 알 수 있다! 이 문제는 선택의 순간마다 가장 적은 비용이 드는 길을 찾아가는 방법으로 풀 수 있었다. 아래의 문제도 위와 같이 그때그때 가장 최적의 값을 고르는 방법으로 풀어야 할까? 총 합이 최대의 값을 얻는 방법은? 위의 방법처럼 그때그때 최적의 값을 골라보자. start에서 시작하여 최대의 값을 얻어야 하니 15로 가보자. .. 2021. 11. 1. [알고리즘] 병합 정렬 - C++ 병합 정렬 #include using namespace std; int temp[6]; int arr[] = { 4, 2, 6, 1, 5, 3 }; void merge(int start, int end) { int mid = (start + end) / 2; int i = start, j = mid + 1, k = start; while (i 2021. 9. 22. [알고리즘] 퀵 정렬 - C++ 퀵 정렬 #include using namespace std; int n, cnt; int arr[] = { 4, 2, 6, 1, 5, 3 }; void quickSort(int s, int e) { if (s >= e)//원소가 1개인 경우 return; int pivot = s;//피벗은 첫번째 원소 int left = s+1, right = e; int temp; while (left s)//피벗보다 작은 값을 만날 때까지 이동 right--; if (left > right) { temp = arr[right]; arr[right] = arr[pivot]; arr[pivot] = temp; } else { temp = arr[right]; arr[right] = arr[left]; arr[left].. 2021. 9. 22. [알고리즘] 삽입 정렬 - C++ 삽입 정렬 #include using namespace std; int arr[] = {4, 2, 6, 1, 5, 3}; int main() { for (int i = 1; i = 0 && arr[j - 1] > arr[j]){//왼쪽에 있는 값이 오른쪽에 있는 값보다 큰 경우 계속 swap int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; j--; } } for (int i=0; i < 6; i++) cout 2021. 9. 22. [알고리즘] 선택 정렬 - C++ 선택 정렬 #include using namespace std; int arr[] = { 4, 2, 6, 1, 5, 3 }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int idx = 0; for (int i = 0; i < 6; i++) { int min = 100;//배열의 값보다 큰 값으로 잡기 for (int j = i; j < 6; j++) { if (arr[j] < min) {//제일 작은 값 찾기 min = arr[j]; idx = j;//제일 작은 값이 저장되어 있는 인덱스 } } int temp = arr[i];//i와 제일 작은 값이 저장된 인덱스와 자리 바꾸기 arr[i] = arr[id.. 2021. 9. 22. [알고리즘] 버블 정렬 - C++ 버블 정렬 #include using namespace std; int arr[] = {4, 2, 6, 1, 5, 3}; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); for (int i = 0; i arr[j + 1]){//붙어있는 두 값을 비교하여 왼쪽보다 오른쪽이 작을 경우 int temp = arr[j];//자리 바꿈 arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } for (int i=0; i < 6; i++) cout 2021. 9. 22. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음
