그리디(탐욕 알고리즘)

개요

최적해를 고르는 근사적인 방법 이며, 지금 당장 좋은것만 고르는 알고리즘이다.
해당종류의 알고리즘은 응용이 많아 단순히 암기로 풀이하기 어렵다. 따라서 많은 문제를 풀어보는 것이 좋으며, 특히 다른 알고리즘과 접합하여 문제가 나오면 난이도가 높아진다. 특히 정렬 알고리즘과 접합하는 경우가 많은 것 같다.

또한 알고리즘 구현 과정에서 문제풀이에 아이디어를 제시하고 아이디어가 정당한가 검증할 수 있어야 한다.

마지막으로 최적해를 고르는 것이지 항상 그것이 최적인 방법은 아니다.
즉, 그리디를 이용해 문제를 풀이 할 수 있으려면 다음의 두가지 조건을 만족해야 한다.

• 탐욕스러운 선택 조건 (Greedy Choice Property)
  • 앞의 선택이 이후에 영향을 주지 않는다.
    
    
• 최적 부문 구조 조건 (Optimal Substructure)
  • 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

매트로이드 구조를 띄고 있으면 그리디가 성립하지만, 모든 그리디 문제가 매트로이드의 성질을 띄고 있지는 않는다.

탐욕적 알고리즘 구상

[BOJ-1931] 회의실 배정 문제를 기준으로 탐욕적 알고리즘을 구상하는 방법을 정리한다.

무식하게 풀기 (완전 탐색)

회의를 선택할 수 있는 모든 부분집합을 만들어가면서 그 중 회의들이 겹치지 않는 답들을 걸러내고 그 중 가장 큰 부분집합을 찾아낸다.

하지만 이 경우 집합의 크기가 $n$일 때, 부분집합의 수는 $2^n$이기 때문에 효율적이지 못하다.

탐욕법 (그리디 알고리즘)

가장 먼저 생각해 볼 수 있는 방법은 길이가 짧은회의부터 하나하나 순회하면서 앞의것들과 겹치지 않는 것들을 추가하는 방법이다. 이 방법은 회의실이 사용가능한 시간을 최대화 하려고 노력하기 때문에 그럴듯해보이나, 다음 그림과 같은 입력이 주어진다면 긴 회의 2개를 개최하는 대신 짧은 회의 하나만 개최하게 된다.

이 문제를 해결하는 그리디한 방법은 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하는 것이다.
가장 먼저 끝나는 회의를 선택한 뒤, 이 회의와 겹치는 모든 회의를 검사하지 않는다.
순서로 정리하면 다음과 같다.

1. 목록 $S$에 남은 회의 중 가장 일찍 끝나는 회의 $S_{min}$을 선택한다
2. $S_{min}$과 겹치는 회의를 $S$에서 모두 지운다
3. $S$가 모두 빌때까지 진행한다.
   
   

정당성 증명

앞서 그리디가 성립하는 두 가지 조건인 탐욕적 선택 속성의 정당성 부터 증명해본다.

• $S$의 최적해중 $S_{min}$을 포함하지 않는 답이 있다고 할 때, 이 답은 서로 겹치지 않는 회의의 목록인데, 이 목록에서 첫 번째로 개최되는 회의를 지우고 $S_{min}$을 대신 추가해서 새로운 목록을 만든다.

• $S_{min}$은 $S$에서 가장 일찍 끝나는 회의이기 때문에 지워진 회의는 이보다 일찍 끝날 수 없다.

• 따라서 두번쨰 회의와 $S_{min}$이 겹칠 일이 없으므로 항상 $S_{min}$을 포함하는 최적해는 존재한다.

다음으로는 최적부분구조의 성립을 확인해야 하는데 대부분의 경우 자명하기 때문에 이를 증명할 필요가 없다. 이 문제에서는 첫번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면 남은 회의 중 당연히 최대한 많은 회의를 선택해야 한다.

구현

직관적으로 구현하자면, 모든 회의의 목록을 저장해두고, 한 회의를 선택할 때마다 겹치는 회의들을 모두 제거한다. 이 설명은 쉽지만 구현에는 복잡하다. 따라서 다른 테크닉을 사용한다.

1. 모든 회의를 종료 시간의 오름차순으로 정렬한다.
2. 동적 계획법으로 바꿔 푼다.

사실 동적 계획법은 모든 경우의 수를 고려하기 때문에 대부분의 그리디 알고리즘 문제는 다이나믹으로도 풀이가 가능하다. 그러나 모든 경우를 고려하기 때문에 어떤 경우에서는 효율성으 극도로 낮아진다.

아래는 1번 방법으로 구현한 문제 풀이이다.

N = int(input())
time = []

for _ in range(N):
  start, end = map(int, input().split())
  time.append([start, end])

time = sorted(time, key=lambda a: a[0]) # 시작 시간을 기준으로 오름차순
time = sorted(time, key=lambda a: a[1]) # 끝나는 시간을 기준으로 다시 오름차순

last = 0 # 회의의 마지막 시간을 저장할 변수
conut = 0 # 회의 개수를 저장할 변수

for i, j in time:
  if i >= last: # 시작시간이 회의의 마지막 시간보다 크거나 같을경우
    conut += 1
    last = j

print(conut)

구현 과정

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 얼떤 우선순위로 선택을 내려야할지 결정한다. 이에 대한 직관을 얻기 위해서는 작은 입력을 손으로 풀어보는것이 효율적이다.
3. 어떤 방식이 동작할 것 같으면 앞선 두가지 속성을 증명해본다.