그리디 알고리즘: 개념, 종류 및 성능 비교

1. 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 현재 시점에서 가장 최적이라고 판단되는 선택을 반복하여 최종 해답에 도달하는 알고리즘이다. 각 단계에서의 최적 선택이 전체 문제의 최적 해를 보장하는 문제에 적합하다.

이 알고리즘은 복잡한 문제를 단순한 단계의 조합으로 해결하며, 계산 과정에서 미래의 상황을 고려하지 않고 지금 당장 가장 좋은 선택을 한다.

1.1 그리디 알고리즘의 특징

• 지역적 최적해(Local Optimal Solution): 매 단계에서 최적의 선택 수행
• 전역적 최적해(Global Optimal Solution): 일부 문제에서 전체 최적 해를 보장
• 빠른 계산: 단순한 선택 기준으로 문제 해결
• 탐욕적 선택 속성(Greedy Choice Property): 각 단계의 최적 선택이 전체 최적 해로 이어짐
• 최적 부분 구조(Optimal Substructure): 문제의 부분 문제를 독립적으로 최적화할 수 있음

2. 그리디 알고리즘의 동작 원리

그리디 알고리즘은 다음과 같은 과정으로 수행된다:

1. 해 선택: 현재 상황에서 가장 최적의 선택 수행
2. 타당성 검사: 해당 선택이 문제의 제약 조건을 위반하지 않는지 확인
3. 해 결정: 선택한 해를 최종 해답에 포함
4. 종료: 모든 선택이 완료되면 알고리즘 종료

3. 주요 그리디 알고리즘

3.1 거스름돈 문제 (Coin Change)

• 개념: 최소한의 동전 개수로 특정 금액을 만드는 문제
• 시간 복잡도: O(n) (n: 동전 종류 수)
• 특징:
  • 동전이 특정 조건(단조 감소)일 때 최적해 보장
  • 실제 화폐 단위에서는 그리디 접근이 유효

3.2 활동 선택 문제 (Activity Selection Problem)

• 개념: 가장 많은 활동을 수행하도록 활동을 선택하는 문제
• 시간 복잡도: O(n log n) (활동 정렬 시)
• 특징:
  • 종료 시간이 빠른 활동부터 선택
  • 일정이 겹치지 않도록 선택

3.3 허프만 코딩 (Huffman Coding)

• 개념: 문자 데이터를 효율적으로 압축하기 위한 알고리즘
• 시간 복잡도: O(n log n)
• 특징:
  • 빈도수가 낮은 문자는 더 긴 코드로 변환
  • 최소 비용으로 이진 트리 생성

4. 그리디 알고리즘의 성능 분석

4.1 시간 복잡도

• 일반적인 경우: 문제에 따라 다양 (대부분 O(n log n) 또는 O(n))
• 활동 선택 문제: O(n log n) (정렬 후 선택)
• 허프만 코딩: O(n log n) (우선순위 큐 사용)

4.2 공간 복잡도

• 입력 데이터와 선택한 해를 저장하는 데 필요
• 주로 O(n) 또는 O(1)

5. 그리디 알고리즘의 장점과 단점

5.1 장점

• 단순성과 효율성: 구현이 간단하고 수행 속도가 빠름
• 최적해 보장: 특정 문제에서는 항상 최적해 제공
• 실시간 문제 해결: 빠른 계산이 필요한 환경에서 유용

5.2 단점

• 최적해 보장 불가: 일부 문제에서는 최적해를 찾지 못함
• 복잡한 문제 해결 어려움: 전역 최적해를 보장하는 문제에는 부적합
• 탐욕적 특성 필요: 탐욕적 선택 속성이 없으면 적용 불가

6. 그리디 알고리즘의 활용 사례

• 최소 신장 트리(MST): 크루스칼, 프림 알고리즘
• 최단 경로: 다익스트라 알고리즘
• 리소스 할당: 스케줄링, 배낭 문제(근사 해)
• 압축 알고리즘: 허프만 코딩

7. 결론

그리디 알고리즘은 각 단계에서의 최적 선택을 통해 빠르게 문제를 해결하는 효율적인 접근 방식이다. 특정 문제에서는 최적해를 보장하지만, 탐욕적 선택 속성과 최적 부분 구조를 만족하지 않는 경우 정확한 해를 구하지 못할 수 있다. 문제의 특성과 요구 사항에 따라 적절한 알고리즘을 선택하는 것이 중요하다.