그리디 알고리즘

그리디 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근시안적(local)인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

그리디 알고리즘 설계

그리디 알고리즘을 설계하는 과정은 다음과 같다.

• 주어진 문제를 해결하는 것은 어떤 결정의 연속임을 알아내는 것이다.
• 최선의 결정을 하기 위해 greedy choice를 한다.
  • Greedy choice는 결정의 순간에 모든 경우를 보지 않고 근시안적(local)인 최선의 선택을 하는 것을 말한다.
  • 어떤 기준에 의해 그 시점에서 최선인 것 같은 것을 선택한다.
  • 이 선택은 전역적(global)으로 봤을 때는 최선이 아닐 수가 있다.

그리디 알고리즘 예시

• 그리디 알고리즘의 예시로 다음과 같은 문제를 설명할 수 있다.
  - 수강신청을 할 때, 특정 요일에 신청할 수 있는 과목 n개가 있을 경우, 최대한 많은 과목을 신청하기 위해서 각 과목의 시작, 끝 시각이 입력으로 주어질 때 어떤 과목들을 선택하면 최대한 해당 요일에 많은 과목을 신청할 수 있을까?
  

• 여기서 greedy choice를 사용하게 되는데 계산이 가능한 greedy choice는 다음과 같다.

  • 시작 시각(S[i])이 가장 이른 class를 먼저 선택하는 경우
  • 강의 길이(F[i] - S[i])가 가장 짧은 class를 먼저 선택하는 경우
  • 서로 겹치는 class 개수가 가장 적은 것을 먼저 선택하는 경우
  • 종료 시각(F[i])이 가장 이른 class를 먼저 선택하는 경우

• 각 greedy choice를 고려하여 가장 최선인 선택을 고르게 된다.

  한 번 각 greedy choice들을 계산해보아 가장 최적인 선택이 무엇인지 생각해 보자.

그리디 알고리즘의 조건

그리디 알고리즘이 잘 작동하는 문제는 대부분 greedy choice 조건과 최적 부분 구조 조건(local optimal solution)이라는 두 가지 조건이 만족된다. greedy choice 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이고, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 최적해라는 것이다.

하지만 그리디 알고리즘을 수행한다 하더라도 항상 global optimal solution이 되지는 않는다. 위의 조건이 성립하지 않는 경우에는 그리디 알고리즘으로 최적해를 구하지 못한다.

그럼에도 불구하고, 그리디 알고리즘은 근시안적인 알고리즘으로서 사용이 가능하며, 대부분의 경우 계산 속도가 빠르기 떄문에 실용적으로 사용할 수 있다. 이러한 경우에서도 어느 정도 최적해에 가까운 해를 구할 수 있는지를 보장하기 위해서 엄밀한 증명이 필요하다.

해답

위의 class 계산 문제에 대해서 가장 최선의 greedy choice는 종료 시각(F[i])이 가장 이른 class를 먼저 선택하는 경우이다.