알고리즘 - 탐욕(Greedy)

저번 글에서는 검색과 순열에 대해서 알아보았다.

이번 시간엔 'Greedy'라고 불리는 최적해를 구하는 방법을 알아보자.

 

탐욕

• 최적해를 구하는데 사용되는 근시안적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
• 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.

동작 과정

1. 해 선택 = 선택 절차(Selection Procedure) 
   • 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합(Solution Set)에 추가한다.
2. 실행 가능성 검사 = 적절성 검사(Feasibility Check)
   • 새로운 부분해 집합이 실행 가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다.
3. 해 검사 (Solutino Check)
   • 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1)의 해 선택부터 다시 시작한다.

필요한 2가지 조건

1. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족
2. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것
3. 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것
   • 즉, 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

조건을 만족하지 못하는 경우

• 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.
• 하지만, 이런 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능하며
• 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용 가능
• 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명 필요

근사 알고리즘(Approximation Algorithm)

• 근사 알고리즘은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미
• 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.

매트로이드

• 독립성이라는 성질을 만족하는 수학적 공간
• 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다.
• 이 구조가 '매트로이드'
• 단, 그리디 알고리즘이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다.
• 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

최적해 보장되지 않는 예

• 이진 트리의 최적합 경로 찾기
  • 모든 노드를 확인해보기 전에는 최적해를 보장할 수 없다.
• 동전 바꾸기
  • 액면이 바로 아래 액면의 배수가 되지 않으면 그리디 알고리즘으로 최적해가 보장되지 않는다.

최적해 보장 예

• 최소 신장 트리
  • 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장
• 회의실 배정 문제
  • 여러 부서에서 회의실 사용 요청, 회의 시작 시간과 종료 시간을 명시
  • 종료 시간이 가장 이른 회의순 배정(최적해 보장)

이전 글에서 봤던 Baby-gin을 탐욕 알고리즘을 이용해서 풀어보자.

• 6개의 숫자는 6자리의 정수 값으로 입력된다.
• counts 배열의 각 원소를 체크하여 run과 triplet 및 baby-gin 여부를 판단한다.

자주 실수하는 오답

• 입력받은 숫자를 정렬한 후, 앞뒤 3자리씩 끊어서 run 및 triplet을 확인하는 방법을 고려할 수도 있다.
• 위의 예처럼, 탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있으니 유의해야 한다.

 

 

이상으로 Greedy라고 하는 탐욕에 대해 배워보았다 !! 알고리즘 사이트에서 풀어보며 익숙해지자~~