영어로 적어놓으니까 뭔가 생소하고 어려울 것 같지만,
실제 개념은 그렇게 복잡하지 않다.
현재에서 최선의 선택을 따라가는 것이다. 로컬 미니멈 초이스를 통해 글로벌 미니멈에 도달한다는 생각인데,
즉 최종 결과가 최선일 수도, 아닐 수도 있다.
예로 동전 교환 문제를 들어보자.
17원을 10 5 1원 주화로 바꾸는 것을 생각해보자. 10원 1개, 5원 1개 1원 2개.
당장 작은수 코인 교환을 보장하는 큰 코인 부터 바꿨는데, 최선의 결과가 됐다.
17원을 7 6 5 4 1원 주화로 바꾸는 것을 생각해보자
같은 접근법으로 7원 2개 1원 3개라는 결과가 나온다. 하지만 최선의 결과는 따로 있다.
6원 2개 5원 1개.
즉 같은 접근 법임에도 최선이 아닐 수 있다.
탐욕알고리즘 풀이 이전에는 , 반례가 없는지 잘 살펴보고 없다면 적용해야한다.
댓글