지나공 : 지식을 나누는 공간

그리디 알고리즘이란? 현재 시점에서의 최적의 선택을 하는 알고리즘입니다. 전체 시점에서는 그게 가장 좋은 답이 아닐 수 있습니다. 매 시점마다 당장 그 시점에서의 최선의 답을 찾는 방식이기 때문입니다. 아래 그림에서 거치는 노드의 숫자 합이 가장 큰 선택을 해야 한다고 합시다. 우리 입장에선 전체 노드가 보이기 때문에 당연히 왼쪽처럼 선택을 해야 숫자 합이 0+3+100 = 103이 되므로 최적의 선택이 된다는 걸 압니다. 하지만 그리디한 선택은 당시에 위치하는 노드에서 바라볼 때 가장 큰 숫자로 가는 것이므로 오른쪽 그림처럼 선택하게 됩니다. 그리디한 선택을 한 결과(0+10+8 = 18)는 실제 최적의 답(103)보다 좋지 않은 답일 수 있습니다. 즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 ..