탐욕 알고리즘이란 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다.
- 최적해를 구하는 데에 사용되는 근사적인 방법입니다.(언제나 최적해를 구하진 못하지만, 최적에 근사한 값을 구함)
- 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘입니다.
- 동적 계획법보다 구현이 쉽고, 시간복잡도가 우수한 장점이 있지만 항상 최적해를 보장하지 못합니다.
- 여러 경우의 수 중에서 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식입니다.
- 단, 순간마다 하는 선택은 그 순간에 대해서 지역적으로는 최적이지만, 이러한 지역적으로 최적인 선택을 수집하여 최종적인 해답을 만들었다고 해서, 이 방법이 전역적으로 최적이라는 보장은 없습니다.
- 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.
[해결방법]
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check) : 선택된 해가 전체 문제의 제약조건을 벗어나지 않는지 검사합니다.
- 해답 검사(Solution Check) : 현재까지 선택한 해의 집합이 전체적인 문제를 해결할 수 있는지 검사하고, 전체 문제를 해결하지 못한다면 1번부터 다시 반복합니다.
[적용방법]
- 탐욕 알고리즘이 적용할 문제의 조건은 탐욕스러운 조건(Greedy Choice Property)과 최적 부분 구조 조건(Optimal substructure)이라는 두 가지 조건이 만족되어야 합니다.
- 탐욕적 선택속성 : 이전에 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
위의 조건이 성립하지 않는 경우 탐욕 알고리즘으로 최적해를 구하지 못합니다. 하지만, 이러한 경우에는 탐욕 알고리즘이 근사 알고리즘으로 사용될 수 있으며 어느정도 최적해에 근사한 값을 도출할 수 있습니다. 근사 알고리즘으로 사용되는 것은 자동적을 되는 것이 아니며, 엄밀한 증명이 필요합니다.
어떤 특별한 구조가 있는 문제에 대해서는 탐욕알고리즘이 언제나 최적해를 찾을 수 있는데, 이를 매트로이드라고 합니다. 탐욕 알고리즘은
[결론]
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.
탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있습니다.
근사 알고리즘이란(Approximation Algorithm)?
- 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미합니다.
- 이 알고리즘은 가장 최적화 되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느정도 보장된 근사값을 계산할 수 있습니다.
[예시1] - 최적해를 구할 수 있는 경우
매트로이드(탐욕 알고리즘을 사용해도 언제나 최적해를 찾을 수 있습니다.)
편의점에서 물건을 구매했는데 가격이 4,040이 나왔다. 오천원을 지불했을 때, 거스름돈으로 받을 동전의 개수를 최소화하시오.
1. 선택절차
거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사
1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사
선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번부터 다시 반복한다.
[예시2] - 최적해 구하지 못하는 경우(local optimal과 global optimal을 구분해야합니다.)
다음 그래프에서 시작점이 주어지고 최소값을 구하시오.
위와 같이 보라색점으로 시작점이 주어졌을 때, 탐욕 알고리즘을 적용하면 왼쪽으로 갈지 오른쪽으로 갈지에 대한 선택의 순간에서 당연히 오른쪽으로 가면 값이 커지기 때문에 비탈면을 따라서 값이 작아지는 왼쪽으로 이동하다가 가장 작은 값, local optimal을 만나면 최적해로 판단합니다.
하지만 주어진 상황에 대해서 최적해는 오른쪽으로 가야 만날 수 있는 global optimal입니다.
이는 가장 처음 시작점에서 마주친 선택의 순간에서 선택한 답(local optimal)이 최적해가 되지 못했습니다. 즉, 두 가지 조건중에서 최적 부분 구조가 충족되지 못했습니다.
최종적인 해결방법이 부분 문제에 대한 해결방법과 다르기 때문입니다.
[예시3] - 최적해를 구하는 경우 & 최적해 구하지 못하는 경우
1) 동전을 조합하여 710원을 만들어야 합니다. -> 최적해 : (500:1개, 100:2개, 10:1개, 총 4개)
동전의 종류가 [500, 100, 50, 10]일 때 결과는 위와 같은 최적해를 구할 수 있습니다. 하지만 사실 이 최적해는 지역적인 최적해(선택의 순간에서 가장 좋은 방안)가 운이 좋게 전역적인 최적해(최종적인 해답)가 된 경우입니다. 동전의 종류만 바꾸어도 그 차이를 알 수 있습니다.
2) 동전을 조합하여 70원을 만들어야 합니다. -> 최적해 : (50:1개, 10:2개, 총 3개)
동전의 종류가 [50, 40, 30, 10]인 경우에는 동전의 가치가 가장 큰 50부터 시작해서 위와 같은 결과를 얻었지만. 위의 해는 지역적인 최적해입니다. 전역적인 최적해는 40원 1개, 30원 1개로 총 2개가 됩니다.
결론은 탐욕 알고리즘으로 해결한 최적해가 정답이 아니었다는 말입니다. (항상 최적해를 보장할 수 없음.)
[예시4] - 최적해 구하지 못하는 경우
도둑이 물건을 훔치는데, 35Kg까지의 물건만 담을 수 있고, 4개의 훔칠 물건이 있을 때, 가장 가치가 좋은 최적해를 구하시오. (그림 : 3000$ 30kg, 컴퓨터 : 2500$ 20kg, 반지 1000$ 10kg, 가방 500$ 8kg)
1. 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
2. 그 다음으로 넣을 수 있는 가장 비싼 물건을 넣는다.
- 도둑의 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 가방에 담는다.
- 남는 공간이 5kg밖에 남지 않아 더 이상 훔칠 수있는 물건이 없다. 총 가치는 3000$이다.
- 만약 그림 대신 컴퓨터와 반지를 가방에 담았다고 가정해보자
- 35kg이 넘지 않으면서 총 가치는 3500$로 그림 하나만 훔칠때보다 더 많은 가치의 물건을 훔칠수 있다.
[정리]
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라고 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결방식입니다.
하지만 위의 예시와 같이 두 가지 조건(탐욕적 선택 속성, 최적 부분 구조)을 만족하는 특정한 상황(매트로이드)가 아니면 최적의 해를 보장하지 못합니다.
문제에서 주어진 조건을 보고 탐욕알고리즘을 적용해도 되는 문제인지, 지역 최적해와 전역 최적해가 달라서 생기는 오류가 없는지를 정확히 판단하여 알고리즘을 적용해야 합니다.
'알고리즘 > 문제 풀이 비법' 카테고리의 다른 글
| 깊이 우선 탐색DFS(Depth-First_Search) (0) | 2022.06.16 |
|---|---|
| 정수론 (0) | 2022.05.12 |
| 구간 합 (0) | 2022.05.01 |
| 너비 우선 탐색_BFS(Breadth First Search) (0) | 2022.04.30 |
| 시간복잡도 (0) | 2022.04.24 |
