그리디 읽기 자료 timer 1s memory 1MB

 그리디 또한, 올림피아드에서 가장 어려운 분야 중 하나입니다. 그리디는 마치 수학 문제와 같아서, KMO의 조합론 문제와 같은 수학문제에 익숙하지 않다면 어렵게 느껴질 수 있습니다. 특히, 그리디는 풀이가 올바른지 확인하기 위해 증명을 해야 하는 만큼, 수학 능력이 매우 중요한 분야입니다.

 그리디 문제에서는, 문제에서 풀이에 쓰일 특징을 찾아내는 것과, 문제가 풀릴 법한 풀이를 만드는 것, 그리고 만든 풀이를 증명하는 능력이 필요합니다. 특징을 찾는 능력은 일반적인 문제를 많이 푸는 것으로, 그리디 문제의 풀이를 만드는 능력은 그리디 문제를 많이 풀면 늘지만, 증명하는 것은 따로 연습하지 않으면 쉽게 늘지 않습니다. 때문에 그리디 문제를 풀 때는 증명 과정 또한 주의깊게 봐야 합니다.

 이번 주제에서는 그리디 문제의 풀이와, 증명 과정 하나를 설명할 것입니다. 그리디 문제를 풀 때는, 수학적으로 올바른지 꼭 증명을 하고 넘어가야 합니다.

2. Mountain Climbing

 하산하는데 걸리는 시간이 등산하는데 걸리는 시간보다 더 긴 소들은, 일단 빠르게 올려보내고 느리게 내려보내는 게 좋을 것 같습니다. 반대로 등산하는데 걸리는 시간이 더 길면, 하산하는 소가 있을 때 올려보내는 게 더 좋을 것 같습니다. 이런 생각을 해보면 다음과 같은 정렬 순서를 세울 수 있습니다.

1. 하산이 더 오래걸리는 소들은 등산하는데 더 오래걸리는 소들보다 먼저 출발시킨다.

2. 하산이 더 오래걸리는 소들끼리는, 등산 시간이 짧은 순서대로 등산시킨다.

3. 등산이 더 오래걸리는 소들끼리는, 하산 시간이 긴 순서대로 등산시킨다.

만약 1번 조건을 만족하지 않은 소가 있다면, 하산이 더 오래걸리는 소의 바로 앞에 등산이 더 오래걸리는 소가 있는 경우가 존재합니다. 경우를 직접 나눠보면, 이 둘의 순서를 바꾸는 것이 더 빠르다는 것을 알 수 있습니다. (직접 해보세요.)

 2번 조건을 만족하지 않은 소가 있다면, 등산 시간이 바로 앞의 소보다 더 짧은 소가 있을 것입니다. 이 경우도 둘의 순서를 바꾸는 것이 더 빠릅니다. 3번 조건도 똑같이 됩니다.

 그리디 문제에서 주로 사용되는 증명 방법은 여러가지가 있습니다. 정렬 순서를 결정하기 위해 인접한 2개의 원소를 바꿨을 때 더 좋아지는 경우가 언제인지 확인하는 방법이 있습니다. 다른 증명 방법으로, 임의의 최적해가 있다면, 답이 바뀌지 않도록 적절히 최적해를 바꿔 그리디로 찾은 해를 만드는 것이 있습니다. 회의실 배정 문제가 이런 방식으로 증명이 가능합니다. 이외에도 많은 증명 방법이 있을 수 있고, 익숙해지기 위해서는 많은 문제를 풀어보는 것이 좋습니다.