그리디, 분할 정복

탐욕(Greedy) 알고리즘

• 최적해를 구하는데 사용되는 방법
• 최적화(Optimization): 가능한 해들 중에서 가장 좋은 해(최대 or 최소)를 찾는 문제
• 선택 시점의 결정은 지역적으로는 최선이지만, 전체 최적이라는 보장은 없음
• 한번 선택한 것은 번복하지 않음

분할 정복

• 분할(Divide): 해결할 문제를 여러 개의 작은 부분으로 나눔
• 정복(Conquer): 나눈 작은 문제를 각각 해결
• 통합(Combine): 해결된 해답 모음(선택적)