탐욕 알고리즘 Greedy Algorithm

탐욕 알고리즘 Greedy Algorithm

---

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

탐욕 알고리즘의 동작 과정

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

탐욕 알고리즘 예

**거스름돈 줄이기**

→ “어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”

1. 해 선택
2. 여기에서는 멀리 내다볼 것 없이 가장 좋은 해를 선택한다
   단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어들므로 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다
3. 실행 가능성 검사
4. 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인한다
   초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1. 로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다
5. 해 검사
6. 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 셈이다. 더 드려도, 덜 드려도 안 되기 때문에 거스름돈을 확인해서 액수에 모자라면 다시 1. 로 돌아가서 거스름도에 추가할 동전을 고른다.

Baby-gin을 완전검색

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

풀이

자주 하는 실수

• 입력받은 숫자를 정렬한 후, 앞뒤 3자리씩 끊어서 run 및 triplet을 확인하는 방법을 고려할 수도 있다
  • 정렬하여 [4, 4, 4, 4, 5, 6]을 얻어내면 쉽게 baby-gin을 확인할 수 있다
  • ex) [1, 2, 3, 1, 2, 3]
  • 정렬하면 [1, 1, 2, 2, 3, 3]로서, 오히려 baby-gin 확인을 실패할 수 있다
• ex) [6, 4, 4, 5, 4, 4]
• 위의 예처럼, 탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있으니 유의해야 한다