| 알고리즘 | 풀이 가능한 문제들의 특징 | 풀이 가능한 문제 및 알고리즘 |
|---|---|---|
| 다이나믹 프로그래밍 | 최적 부분 구조(Optimal Substructure) 중복된 하위 문제들(Overlapping Subproblems) | 0-1 배낭문제 피보나치 수열 다익스트라 알고리즘 |
| 그리디 알고리즘 | 최적 부분 구조(Optimal Substructure) 탐욕 선택 속성(Greedy Choice Property) | 분할 가능 배낭 문제 다익스트라 알고리즘 |
| 분할 정복 | 최적 부분 구조(Optimal Substructure) | 병합 정렬 퀵 정렬 |
분할 정복(Divide and Conquer)
분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될때까지 문제를 재귀적으로 쪼개 해결한 다음, 해결한 하위 문제들의 결과들을 조합하여 원래 문제의 결과를 도출하는 풀이법이다.
대표적인 분할 정복 알고리즘으로 병합 정렬이 있다.
문제를 축소해서 정복한다는 개념은 고대 그리스 수학자 유클리드(Euclid)의 저서,『원론』에서의 최대 공약수 알고리즘에서 최초로 정립되었으며, 이 알고리즘은 인류 최초의 알고리즘이라 일컬어진다.
병합 정렬을 통한 분할 정복 이해
위 그림과 같이 문제를 동일한 유형의 하위 문제들로 나누고, 가장 작은 단위의 하위 문제를 해결하여 정복 후, 해결한 하위 문제들의 결과를 조합하여 원 문제를 해결한다.
분할: 문제를 동일한 유형으로 나눔
정복: 가장 작은 단위의 하위 문제를 해결하여 정복
조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합
정리
위에서 언급했듯이 분할 정복을 재귀를 활용하는 대표적인 알고리즘이다.
중급 이상의 코딩테스트 문제로 빈번히 출제되며, 최적 부분 구조(Optimal Substructure)를 풀이하는 매우 중요한 기법 중 하나이다.
Reference)
파이썬 알고리즘 인터뷰
22.10.04 - 1차 작성
...