Greedy: 탐욕법

 

개념

매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식. 각 단계에서 내린 결정이 전체로 봤을 때도 최적일 거라는 보장은 없다.

출처 : wikipedia

위 사진을 참고하여 세 숫자의 합이 가장 커질 수 있는 경우를 생각해보자. 실제로 가장 큰 수는 109지만 Greedy algorithm의 결과로 나온 값은 25가 된다. 여기서 첫 줄의 '매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식'을 떠올릴 수 있다. Greedy algorithm에 따른 숫자 선택 과정은 아래와 같다.

 

① 7에서 시작

② 3과 12를 만났을 때 더 큰 수인 12 선택(3을 선택할 경우 99로 갈 수 있지만 미래의 선택에 대해서 생각하지 않음)

③ 12에서 5, 6을 만났을 때 더 큰 수인 6 선택

---

하지만 탐욕법을 이용해 항상 부분 최적해를 구할 수 있는 것은 아니다. Greedy algorithm이 잘 작동하는 문제들을 다음과 같은 2가지 조건을 만족해야 한다.

 

- 탐욕 선택 속성(현재의 선택이 다음에 일어날 선택과 무관)

- 최적 부분 구조

 

 

최적 부분 구조

A라는 지점에서 P를 거쳐 B라는 지점까지 3가지 경로를 이용해 갈 수 있다고 가정할 때, A→B 최단 경로는 A→P 최단 거리와 P→B 최단 거리의 합이 될 것이다. 즉 A에서 P로 가는 순간의 최적해와 P에서 B로 가는 순간의 최적해가 전체의 최적해를 이끌어 낸다는 것을 알 수 있다. 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법이 되는 구조를 최적 부분 구조라고 한다. 

 

 

특징

무조건 큰 경우, 무조건 작은 경우, 무조건 긴 경우, 무조건 짧은 경우와 같이 극단적으로 문제에 접근하기 때문에 정렬 기법과 함께 사용된다.

 

 

사용 예

- 거스름돈 문제(주어진 돈의 단위가 서로서로 약수/배수 관계일 때)

- 활동 선택 문제(한정적인 자원을 최대한 많이 사용하기 위한 형태)

- Dijkstra(그래프 내의 한 정점에서 다른 정점으로 향하는 가장 짧은 경로 계산)

- Kruskal(사이클이 형성되지 않는 조건에서 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리)

- Prim(방향이 없는 연결 그래프가 주어질 때 MST를 찾기 위한 알고리즘)

- Fractional knapsack problem(짐을 나눌 수 있는 배낭 문제)

 

 

사용할 수 없는 예

Greedy algorithm을 이용해 최적해에 가까운 근사치만을 추정할 수 있다.

 

- 0-1 Knapsack Problem(짐을 나눌 수 없는 배낭 문제)

- 외판원 문제

 

 

🙏 틀린 부분, 오타가 있다면 편하게 댓글 남겨주세요 🙏