[CS기초] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복하여 최종 해를 구하는 알고리즘입니다.

 

 

그리디 알고리즘의 특징

그리디 알고리즘이 정확한 최적해를 보장하기 위해서는 다음 두 조건을 만족해야 합니다.

1. Greedy Choice Property (탐욕 선택 속성)
   • 전체 문제의 최적해는 부분 문제의 최적해로 구성되어야 한다.
   • 즉, 지금 당장의 최선의 선택이 결국 전체에서도 최선의 선택이어야 한다.
   • 예) 활동 선택 문제 (Activity Selection)
2. Optimal Substructure (최적 부분 구조)
   • 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.
   • 즉, 문제를 작은 부분으로 나누었을 때, 이들 각각의 최적해를 합치면 전체 문제의 최적해가 되어야 한다.
   • 예) 다익스트라 알고리즘(Dijkstra Algorithm)

위 두 조건을 모두 만족하지 못한다면, 보통 DP(동적 계획법) 또는 백트래킹 같은 다른 해결방법을 찾아야 합니다.

 

 

일반적인 풀이 과정

1. 정렬
   • 기준(비용, 이익, 종료 시간 등)에 따라 정렬
2. 반복문으로 선택
   • 조건 검사를 통해 가능한 경우만 선택
3. 선택한 결과를 저장 및 누적 처리

 

대표적인 예시 문제

문제	설명
동전 문제	가장 큰 금액의 동전을 우선 사용해서 거슬러줌
활동 선택 문제	가장 빨리 끝나는 활동을 먼저 선택
회의실 배정	종료 시간이 빠른 회의부터 배정
프림 / 크루스칼 알고리즘	최소 신장 트리 (MST) 구성
허프만 코딩	가중치 기반의 최적 압축 트리

 

 

주의사항

• 그리디가 항상 정답을 보장하지는 않는다.
  • 예시) 일반적인 동전 문제에서, 동전 단위가 각 동전의 배수가 아니라면 DP로 해결해야 한다.
• 정당성 분석 필수
  • 정렬 기준이 적절한지, 그 선택이 전체 최적해에 영향을 주는지 증명 또는 반례에 대한 검토가 필요하다.