[Algorithm] Greedy

탐욕 알고리즘

그리디 알고리즘은 최적 해를 구할 때 사용하는 근시안적인 방법입니다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적인 해를 선택해 나가면서 최종적인 해답에 도달합니다. 각 선택 시점에서 이루어지는 결정이 지역적으로는 최적일 때, 그 결정들이 모여서 만든 답이 최적 해라는 보장이 있어야 그리디 알고리즘으로 문제를 접근할 수 있습니다. 그리디 알고리즘은 한번 선택한 결정은 번복하지 않기 때문에 대부분의 단순하며 제한적인 문제들에 적용됩니다.

그리디 알고리즘의 동작 과정은 다음과 같습니다.

1. 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합에 추가한다.

2. 실행 가능성 검사: 새로운 부분 해 집합이 실행가능한지 확인한다. (문제의 제약 조건을 위반하지 않는 지 검사한다.)

3. 해 검사: 새로운 부분 해 집합이 문제의 해가 되는지 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1) 해 선택부터 다시 시작한다.

그리디 알고리즘은 두가지 필수 요소가 있습니다. 첫번째는 탐욕적 선택 속성(greedy choice property)입니다. 탐욕적 선택은 최적 해로 갈 수 있음을 보이는 것이고, 탐욕적 선택은 항상 안전하다는 것을 확인할 수 있어야합니다. 두번째는 최적 부분 구조(optimal substructure property)입니다. 최적화 문제를 정형화 해야한다는 의미이고, 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남아야 합니다. 정리하면 ‘원 문제의 최적 해 = 탐욕적 선택 + 하위 문제의 최적 해’임을 증명해야 합니다.

활용 예시

회의실 배정

하나의 회의실에 대한 사용 예약을 받을 때, 하루에 가장 많은 회의를 할 수 있는 방법을 찾는 경우! 회의가 끝나는 시간이 가장 빠른 것을 찾고 해당 회의와 겹치는 회의를 모두 삭제합니다. 다시 남은 회의 중 가장 먼저 끝나는 회의를 찾습니다!

Baby-Gin!

플레이어가 0~9로 이루어진 숫자 카드 6장을 받을 때 연속된 숫자 3장이거나 같은 숫자 3장으로 모두 처리가 가능할 경우 Baby-Gin! 받은 카드를 0~9 인덱스에 카드 수를 저장합니다. 이때 연속을 먼저 검증하면 333456 의 카드에서 345를 먼저 처리해버릴 가능성이 있습니다. 따라서 같은 숫자 3장을 먼저 검사하면 문제없이 Baby-Gin 을 검사할 수 있습니다.