그리디 알고리즘, 그림으로 쉽게 이해하기

1. 그리디 알고리즘은 무엇인가요? 💡

Greedy Algorithm은 매 선택의 순간마다 당시에 고를 수 있는 최선의 선택지를 골라가는 것이 전체에서 봤을 때 최선의 선택이라고 가정하는 알고리즘이다.
예를 들어 다음과 같은 문제가 있다고 해보자.

현재 A의 시점에서 고를 수 있는 선택지 중 C가 최단거리이다. 그러므로 C를 선택한다.

C 시점에서 고를 수 있는 선택지 중 최단 거리로 갈 수 있는 노드는 G이다. 따라서 G를 선택한다. 두번의 선택 후 무조건 F를 비용 0으로 갈 수 있다고 할 때, 전체 노드는 다음과 같다.

매 순간 갈 수 있는 최선의 선택지를 골랐더니 전체에서 봤을 때도 최선의 선택이었다. 이와 같이 매 순간의 최선 = 전체의 최선 이 성립할 때, 이러한 논리를 Greedy 알고리즘이라 한다.

2. 왜 사용하죠? 🤷‍♂️

음... 저러한 가정이 성립하는 문제라면 굳이 구현으로 완전탐색을 하는 것은 시간 낭비이기 때문이다. 하지만 개념 설명에서 봤다시피, 매 순간의 최선 = 전체의 최선이 성립할때만 이용이 가능하다. 따라서 해당 가정이 성립하는지 문제를 풀며 유심히 봐야 한다.

3. 어떻게 구현하죠? 🔍

다음 3가지 가정을 따른다.

1. 재귀이든 Loop이든 선택의 순간이 오면 해당 시점에서 고를 수 있는 최선의 선택지를 고른다.
2. 해당 선택지가 문제의 조건을 위반하지 않는지 확인한다.
3. 전체 문제의 답이 나왔는지 확인한다. 답이 아직 나오지 않았다면 1번을 반복한다.

4. (추가) 문제 유형별 최선의 선택이 뭔지 수집 🤔💭

이 문제에서는 최선의 선택이 뭘까?

그리디 알고리즘 문제를 풀면 항상 드는 궁금증이다. 이러한 궁금증을 해결할 인사이트를 넓히기 위해서 Greedy 알고리즘 문제를 풀 때마다, 그 때의 최선을 수집하려 한다.

(1) 최대한 작은 값 고르기

x 선 위의 Thread에서 최대한 오른쪽의 값을 고른다. 그 이유는 해당 문제는 매듭 사이의 거리가 d 이상이 되는지 확인해야 하므로, 최대한 오른쪽의 (작은) 값을 골라서 후순위 매듭들 사이 거리가 d 이상이 될 수 있도록 여유 공간을 줘야 하기 때문이다.

Thread Knots 문제 링크