그리디 알고리즘 — 활동선택, 허프만, 교환 논법

여러분, 오늘 배울 그리디 알고리즘은 정말 매력적인 전략이에요.

DP가 모든 가능성을 다 따져보는 거라면, 그리디는 지금 가장 좋은 것만 선택해요.

마치 뷔페에서 가장 맛있어 보이는 것부터 접시에 담는 거죠.

다이어그램을 보시면 DP와 그리디의 탐색 범위 차이가 확 보여요.

이게 얼마나 대단하냐면, O(n log n)만에 최적해를 구할 수 있어요.

DP의 O(n 제곱)이나 O(n W)에 비하면 엄청 빠르죠.

하지만 아무 때나 쓸 수 있는 건 아니에요.

그리디가 최적해를 보장하려면 두 가지 조건이 필요해요.

그림 가운데를 보세요. 두 조건이 박스로 나와 있어요.

첫째, 그리디 선택 속성이에요. 지금 최선이 전체 최선의 일부가 되어야 해요.

쉽게 말하면, 지금 고른 것을 나중에 후회하지 않아야 한다는 뜻이에요.

둘째, 최적 부분 구조예요. 부분 문제의 최적이 전체 최적으로 이어져야 해요.

이 두 조건을 어떻게 확인하느냐가 이번 레슨의 핵심이에요.

반례가 하나라도 있으면 그리디는 쓸 수 없어요.

도표 하단을 보면 반례 확인 방법이 정리되어 있어요.

그래서 증명이 중요한 거예요. 교환 논법이라는 도구를 배울 거예요.

교환 논법은 다른 선택으로 바꿔도 손해가 없음을 보이는 기법이에요.

활동 선택, 허프만 코딩, 동전 교환까지 실전 예시로 파고들어 볼게요.

DP로 풀면 느린 문제를 그리디로 한 방에 푸는 쾌감을 느껴봅시다.

자, 가장 유명한 예시인 활동 선택부터 시작할게요.