그리디 알고리즘
그리디 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이다. 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은것만 고르는 방법을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
그리디 알고리즘의 정당성
그리디 알고리즘은 모든 알고리즘 문제에서 최적의 해를 보장하진 못한다. 하지만 거스름돈 문제에서 ‘가장 큰 화폐 단위부터’ 돈을 거슬러주는 것과 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때에는 매우 효과적이고 직관적이다.
그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 검토해야 한다. 그리디 알고리즘의 정당성을 증명하는 것은 아래와 같다.
- Greedy choice property (탐욕적 선택 특성) : Greedy 방식으로 선택했을 때 손해볼 일이 없다는 것을 증명
- Optimal substructrue (최적 부분 구조) : 부분 문제에서 greedy 방식을 선택해서 구한 최적해가 전체 문제에 대한 최적해임을 증명
위 두 조건이 성립되어야만 greedy에서는 최적의 해를 보장한다.
문제 모음집
동적 계획법과 그리디
위 사진에서 보면 그리디는 매 순간 가장 큰 값을 찾아 가고있다. 매우 빠르다는 장점이 있지만 실제로 가장 큰 숫자를 보장하지 않는다는 단점이 있다.
이렇기 때문에 그리디는 dynamic programming과 서로 보완하는 개념으로 사용되고 있다.
동적 계획법
동적계획법은 전체 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.
매번 현재의 최대 가치를 저장하기 때문에 이전의 값보다 더 나빠지는 경우는 있을 수 없다. 동적 프로그래밍은 각 하위 문제들이 서로 관계가 없을 때, 즉 서로 의존하지 않는 경우에만 쓸 수 있다.
최적 값을 구하는 데 실패하는 문제들
- 배낭 문제, Knapsack Problem
- 외판원 순회 문제, 조합 최적화