전체 글131 [Chapter4] 그리디 알고리즘(1) - 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘* 최적화 문제: 가능한 해들 중에서 가장 좋은 해(최소 비용, 최대 이익 등..)를 찾는 문제 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 - 근시안적 선택: 입력 데이터 간 관계 고려x 수행 과정에서 순간순간 최솟값 또는 최댓값 가진 데이터 선택 - 일단 한 번 선택하면 -> 절대로 번복하지 x=> 대부분의 그리디 알고리즘들은 매우 단순, 제한적인 문제만이 그리디 알고리즘으로 해결 가능 동전 거스름돈 문제 남은 액수를 초과하지 않는 조건 하에 욕심내어 가장 큰 액면의 동전을 취하는 것 CoinChange입력: 거스름돈 액수 W출력: 거스름동 액수에 대한 최소 동전 수change=W, n500=n100=n50=n10=n1=0while(.. 2025. 4. 26. 선택 문제 n개의 숫자들 중 k번째로 작은 숫자 찾기 1. 최소 숫자를 k번 찾는다.: O(kn) 2. 숫자들을 정렬한 후, k번째 숫자를 찾는다.: O(nlogn) 이진 탐색: 입력을 1/2로 나눈 두 부분 중에 한 부분만을 검색 선택 문제 : 입력 숫자들 중 피봇 선택하여 분할(마치 퀵 정렬)- small group: 피봇보다 작은 숫자 그룹=> k번째 작은 숫자를 small group에서 찾기- large group: 피봇보다 큰 숫자그룹=> (k=|Small group|-1)번째로 작은 숫자를 large group에서 찾기* 피봇 = 1개이므로 Selection알고리즘은 분할 정복 알고리즘이기도 하지만 랜덤 알고리즘이기도 하다.=> 피봇을 랜덤하게 정하기 때문 피봇이 입력을 너무 한쪽으로 치우치게 분할하면=.. 2025. 4. 24. 퀵 정렬 partition을 통해 일부 진행 -> 그거를 가지고 부분 분할즉, 대강 partition으로 기준을 정해놓고 큰지 작은지만 대략 분류하기-> 작으면 오른쪽, 크면 왼쪽-> 피봇은 어느쪽에도 포함x 1. partition(피봇 선정)2. 퀵 정렬(Quick Sort) 알고리즘 QuickSort(A,left,right)입력: 배열 A[left]~A[right]출력: 정렬된 배열 A[left]~A[right]if(left void quick_sort(int list[], int left, int right){ if(left pivot이 가장 왼쪽 pivot=list[left]; do{ do low++; while(low=left && list[high]>pivo.. 2025. 4. 24. 합병 정렬 : 분할 정복 알고리즘: 2개의 부분 문제로 분할 -> 부분 문제의 크기가 1/2로 감소 n개의 숫자들을 n/2씩 2개의 부분문제로 분할-> 각각의 부분 문제를 순환으로 합병 정렬-> 2개의 정렬된 부분을 합병하여 정렬(정복) 즉, 정복 과정이 합병이다. 알고리즘 A와 B를 앞 숫자부터 비교 -> 더 작은 것 선택 -> 반복MergeSort(A,p,q)입력: A[p]~A[q]출력: 정렬된 A[p]~A[q] if(p void merge_sort(int list[], int left, int right){ int mid; if(leftmid) //남아 있는 레코드 일괄 복사 for(l=j;l 시간복잡도 1. 분할: O(1)2. 합병: 입력의 크기에 비례- 최소비교횟수: 작은 것의 크기만큼(n)-.. 2025. 4. 23. 이전 1 2 3 4 5 6 ··· 33 다음
