탐욕법

August 26, 2021 1 분 소요

그리디 알고리즘이라고 불리는 탐욕법은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출할 때 쓰는 알고리즘 입니다.

현재 처한 상황에서 최적의 해를 구하는 것이기에, 적절한 값으로 인식하여 문제를 해결하는 기법입니다. 따라서 각 상황에서의 최적의 값이 무조건 종합적인 최적의 값을 보장하지는 않기에 문제의 성격을 잘 파악하여 대입하는 것이 중요합니다.

각 부분에서의 선택이 다른 부분에게 영향을 주지 않을때. 각 부분에서의 최적해결이 최종 해결방법일때 탐욕법을 사용합니다.

아래의 그림과 같이 출발점에서 도착점까지의 최단 경로를 찾을때 1번 선택의 결과가 2번 선택의 결과에 영향을 미치기에 1번 선택에서 더 짧은 3을 선택하는 것이 정답이 될 수 없습니다. 이때는 “동적계획법”을 활용하여 문제를 접근 할 수 있습니다.

그리고 아래의 그림과 같이 1번 선택이 2번 선택에 영향을 주지 않고 2번 선택이 3번 선택에 영향을 주지 않을때 순간순간 최적의 길을 선택할때 도착점점까지의 최단거리가 될 수 있습니다. 이때 바로 “탐욕법”을 사용 할 수 있습니다.

아래의 그림과 같이 1970원을 만들때 10원짜리 197개를 이용하여 만들 수 도 있지만 동전의 최소 갯수를 구함으로 아래와 같이 500원 3개, 100원 4개, 50원 1개, 10원 2개 총 10개로 만들때 최소 갯수가 됩니다.

이번에는 100원이 아닌 300원과 200원이 있다면 어떨까요? 이번에도 위와 같이 차례대로 구하면 9개가 됩니다.

하지만 이번에는 300원을 선택 하지 않고 200원을 2개 선택하면 50원을 1개만 선택할 수 있기 때문에 8개가 됩니다.

위와 같은 경우는 동전들이 서로간의 배수가 아니기 때문에 앞에서의 선택이 뒤에서의 선택에 영향을 미칩니다. 이런 경우에는 “동적계획법”을 활용하는 것이 좋습니다.

동전들이 서로간 배수인 일반적인 동전의 경우 반대로 “탐욕법”을 활용하는 것이 좋습니다.

하나의 회의실을 여러 팀이 사용할 경우 가능한 많은 수의 회의를 사용하기 위해서는 아래와 같이 검색합니다.

위와 같이 각 상황에 맞게 최적의 해를 구할때 탐욕법을 사용 합니다.

카드 게임을 할때 A가 B를 이길 수 있는 최대 횟수를 찾는 방법 입니다.

위와 같이 마찬가지로 각 상황에 맞는 최적의 해를 구할때 탐욕법을 사용합니다.

지금 까지 탐욕법의 예제를 통해 알아 보았습니다. 문제의 상황에 따라서 “탐욕법”과 “동적계획법”을 잘 파악하여 적합한 결과를 도출하는 연습이 필요해 보입니다.

(1) 인터넷