탐욕 알고리즘이란?

• 탐욕 알고리즘 ( greedy algorithm )

탐욕 알고리즘은 문제를 해결하는 최적의 방법을 구하는데 사용되는 방법이다. 여러가지의 방법중 하나를 택할때마다 그 '순간'중 가장 최선이라고 생각되는 방법을 선택해 나가는 방식으로 최종적인 해답에 도달하는 방법이다. '순간' 선택의 최선이라고 정의 하는것은 local하게는 최선이지만, 전체적으로 global 하게 들여다 봤을땐 그것이 정확히 최선이 아닐수도 있다.

많은 사람들이 말하는 탐욕 알고리즘의 대표적인 문제에는 ' 분할 가능 배낭문제 ' 라는 것이 있다.

예를들어, 가상화폐 거래소에는 비트코인이 50만원 / 이더리움 20만원 / 리플 10만원 / 도지코인 5만원이라고 가정해보자.

• 한사람이 100만원을 입금하여 금액에 딱 맞게 코인을 구매하려 했을때 가장 최적의 방법은 무엇일까?
  ( 이때, greedy algorithm 을 이용하여 구매한다고 가정해보자 )

여기서 greedy algorithm 는 매 '순간' 마다 최적의 수를 고려한다. 이 사람이 100만원의 돈으로 가상화폐를 구매했을땐 50만원 * 2 인 비트코인 2개가 가장 최적의 방법이다. 이 방법은 global optimal 의 방법을 이용해 최적의 방법을 찾았다고 할수 있겠다.

그렇다면, 좀 더 복잡한 경우에는 어떨까.

가상화폐의 가격이 변동하여 비트코인이 60만원/이더리움50만원/리플코인10만원/도지코인5만원 이라고 가정해보자.

• 한사람이 100만원을 입금하여 금액에 딱 맞게 코인을 구매하려 했을때 가장 최적의 방법은 무엇일까?
  ( 이떄, greedy algorithm 을 이용하여 구매한다고 가정해보자 )

이 경우에는 가장 비싼 비트코인 60만원을 먼저 구매한다고 쳐보자. 100만원에서 60만원을 이용해 비트코인을 구매한뒤 남은돈은 40만원이다. 40만원으로는 10만원인 리플을 4개 구매할수 있는 가격이다.

따라서 , 이 경우엔 비트코인 1개, 리플 4개로 총 5개의 코인을 얻는다. 하지만, 처음부터 100만원으로 이더리움 2개를 샀다면 총 2개의 코인인것이다.

이처럼, greedy algorithm 은 최적의 방법을 찾기위해 매 순간( local ) 최적의 수를 찾을때도 있지만 , 위의 예시 같이 subproblem이 모여진 해답이 직관적이나 전체적으로 ( global ) 하게는 항상 최적이라는 보장을 하지 않는다.

결국, greedy algorithm 이 잘 동작하게 하기 위해서는 greedy choice property 와 optimal substructure 라는 두가지 속성을 만족해야 한다.

• greedy choice property = subproblem의 해답이 다음 subproblem 에 영향이 가지 않는다는 독립적인 연산 속성

• optimal substructure = 문제 전체 최적해(global optimal) 이 subproblem 에서도 최적해가 된다는 속성

쉽게 말하면, greedy algorithm은 매 순간마다 최적의 수를 계산한다 했으므로 각 순간은 독립적이며 그 결과가 어느 순간에도 영향을 끼치지 않는다는 속성과 매 순간마다 구한 최적의 수가 전체 문제에 대한 최적해와 같아야 된다는 속성이다.

그렇다면 greedy algorithm 이 저 두 속성을 만족하지 않는다면 안좋은것인가?

결론부터 말하자면 아니다. 위와 같이 greedy algorithm 이 최적해를 보장하진 않지만 근사 알고리즘으로 이용 할 수 있으며, 대부분의 경우 연산 속도가 빠르기 때문에 실용적으로 사용이 가능하다. ( 이 경우에도 역시 어느정도까지 최적해에 가까운 해를 구할수 있는지를 보장하려면 엄밀한 증명이 필요하다.) 최적해는 아니지만 최적해에 가까운 값을 사용하면서 어느정도의 loss 를 감안하고 빠른 실행시간 또는 다른 이득을 취할수 있다는 장점이 있다.

DP 와 greedy algorithm 비교.

dynamic programming ( dp ) 에 관한 설명 - https://rain-bow.tistory.com/entry/DPDynamic-Programming