그리디(Greedy)는 각각의 상황에서 나중을 고려하지 않고 최선의 선택을 반복하는 방법으로 문제를 해결하는 것이다. 개념은 매우 간단하지만 적용하기가 만만치 않은 분야이기도 하다.
그리디로 문제를 해결하기 위해서는 각각의 상황에서 최선의 선택을 한 이후에 그 선택을 하기 전과 동일한 성질이 성립해야 한다. 그렇기 때문에 이후에도 같은 전략을 계속 사용할 수 있는 것이다. 또한 그리디는 보통 '가장 ~한 것'부터 처리하는 식으로 많이 구현되기 때문에 주어지는 값, 객체를 정렬해야 하는 경우가 많다.
그리디로 풀 수 있는 대표적인 문제 $2$개를 살펴보면 이해하기에 더 좋다.
모든 잔돈에 대해 큰 잔돈의 가치가 작은 잔돈의 가치이 배수라는 것을 알 수 있다. 즉 최대한 큰 가치의 잔돈부터 거슬러 주어도 아무 문제가 없음을 알 수 있다. 따라서 주어야 할 거스름돈 이하의 잔돈들 중 가장 가치가 큰 것부터 하나씩 선택하면 된다.
회의를 끝나는 시간이 빠른 순서대로 정렬한 후 이전에 선택한 회의들과 시간이 겹치지 않는 첫 번째 회의를 선택하는 과정을 반복하면 최적해를 구할 수 있음이 알려져 있다.
그밖에도 다양한 종류의 그리디 문제가 존재한다. 금방 드러나지 않는 문제들도 많기 때문에 많은 연습이 필요하다.
[연습문제]
그리디가 성립한다는 게 잘 안 보일 수 있지만 그리디 문제이다. 모든 편의시설 중 최소한 하나는 답이 될 수 있음이 보장된다. 왜 이걸 그리디라고 부르는가 하면, 임의의 좌표를 선택한 다음 거기서 답으로 가능한 편의시설로 좌표를 옮기는 것이 항상 이득이기 때문이다.
도둑이 중간에 방향을 바꿨을 때보다 원래의 진행 방향으로 계속해서 갔을 때 손해볼 것이 없기 때문에 도둑이 한쪽 방향으로 계속 도망가는 $4$가지 경우 중 경찰이 잡지 못하는 경우가 있는지 확인한다.
CF 1401B. Ternary Sequence (1100)
$a_i=1,b_i=2$이거나 $a_i=2,b_i=1$일 때만 $c_i$가 $0$이 아닌 수가 되기 때문에 저 두 경우 중 $a_i=2,b_i=1$인 쌍을 최대한 많이 만들면 $c_i$의 합을 최대로 할 수 있다.
CF 1189B. Number Circle (1100)
가장 큰 수가 그 다음으로 큰 $2$개의 수의 합보다 크다면 가능한 방법이 없고, 그렇지 않을 경우 값들을 오름차순으로 정렬한 후 가장 뒤의 두 수의 순서를 바꾸면 답이 된다.
CF 1271C. Shawarma Tent (1300)
텐트를 학교의 바로 옆 칸에 위치시키는 것이 최적의 방법이 된다. 학교와 인접한 $4$칸 중 답이 최대가 되는 위치를 찾는다.
CF 1466C. Canine poetry (1300)
앞에서부터 한 글자씩 확인하면서 그 글자가 바로 앞의 두 글자 중 하나와 같을 경우 그 글자를 알파벳이 아닌 다른 문자로 바꾼다. 바꾼 문자의 수가 답이 된다.
CF 1334C. Circle of Monsters (1600)
각각의 몬스터가 죽으면서 다음 몬스터에게 데미지를 주었을 때 다음 몬스터에게 얼마의 체력이 남는지 확인한다. 이때 남는 체력이 가장 많은 몬스터를 처음에 죽일 몬스터로 선택하면 최적해를 구할 수 있다.
CF 1153C. Serval and Parenthesis Sequence (1700)
$s$에 ( 또는 )가 절반보다 많은 경우 가능한 방법이 없다. 그렇지 않다면 (가 절반이 될 때까지 앞쪽 ?를 (로 채우고 나머지 ?는 )로 채운 다음 완성된 문자열이 문제의 조건을 만족하는지 확인한다.
?를 $000 \ldots 111$로 채우거나 $111 \ldots 000$으로 채우는 경우만 확인하면 최적해가 나온다.
CF 1305E. Kuroni and the Score Distribution (2200)
$a_i + a_j = a_k$인 쌍이 가장 많이 나오는 경우는 각각의 값이 $1$부터 차례로 나올 때이다. 여기서 마지막 값만 적절하게 크게 만들면 원하는 답을 찾을 수 있다.
'Algorithm > B. Basic Algorithms' 카테고리의 다른 글
| 23. Backtracking (0) | 2021.01.30 |
|---|---|
| 22. Recursion (0) | 2021.01.30 |
| 20. Simulation (0) | 2021.01.29 |
| 19. Brute Force (0) | 2021.01.28 |
| 18. Implementation (0) | 2021.01.28 |
