모종닷컴

그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘 ◆그리디 알고리즘의 특징 1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다. 2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다. ◆그리디 알고리즘으로 해결 가능한 대표적인 문제들 1)동전 거스름돈 :거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제 #유사코드 입력:거스름돈 액수W 출력:거스름돈 액수에 대한 최소 동전 수 change=W,n500=n100=n10=n1=0 //n500,n100,n50,n10,n1은 각각의 동전 수를 위한 변수이다. while(change>=500) change=change-500,n500++ while(chan..

분할 정복 알고리즘 = 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘 ◆대표적인 분할 정복 알고리즘 1)합병 정렬 문제를 계속해서 반으로 잘르고 다시 합병시키는 정렬. 자를 수 없을 때까지 자른 후 합병 과정에서 sorting함 #유사코드 MergeSort(A,p,q) 입력:A[p]~A[q] 출력: 정렬된 A[p]~A[q] if( pfloor MergeSort(A,p,k) MergeSort(A,k+1,q) A[p]~A[k]와 A[k+1]~A[q]를 합병한다. } #파이썬 소스 def merge_sort(a): print(a) n = len(a) # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음 if n