코딩 테스트 이론 - 그리디(greedy) 탐욕 알고리즘

탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘은 문제를 해결할 때 현재 단계에서 가장 최적의 선택을 반복적으로 수행하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 이 알고리즘은 항상 **국소적 최적해(Local Optimal Solution)**를 선택하며, 이를 통해 최종적으로 **전역적 최적해(Global Optimal Solution)**를 구하려고 시도합니다.

---

탐욕 알고리즘의 특징

1. 단계별 최적 선택:
   • 매 단계에서 그 순간 가장 최적인 선택을 합니다.
   • 이전 단계의 선택에 대해 다시 돌아가서 바꾸지 않습니다. (비가역적)
2. 문제의 구조적 특성 필요:
   • 탐욕 알고리즘이 최적해를 보장하려면 문제에 특정한 성질이 있어야 합니다:
     • Greedy Choice Property (탐욕 선택 속성):
       • 현재 단계에서의 최적 선택이 전체 문제의 최적해로 이어져야 함.
     • Optimal Substructure (최적 부분 구조):
       • 문제의 최적해가 그 부분 문제들의 최적해로 구성되어야 함.
3. 빠른 계산:
   • 일반적으로 O(n) 또는 O(nlog⁡n)과 같은 비교적 빠른 시간 복잡도로 동작합니다.
   • 재귀나 백트래킹처럼 모든 경우를 탐색하지 않기 때문에 효율적입니다.

---

탐욕 알고리즘의 적용 예시

1. 활동 선택 문제 (Activity Selection Problem):

• 문제: 여러 개의 활동이 시작 시간과 종료 시간으로 주어질 때, 겹치지 않는 최대한 많은 활동을 선택.
• 탐욕 선택:
  • 종료 시간이 가장 빠른 활동을 우선적으로 선택.

2. 거스름돈 문제 (Coin Change Problem):

• 문제: 최소한의 동전 개수로 거스름돈을 주는 방법을 구함.
• 탐욕 선택:
  • 가장 큰 단위의 동전을 먼저 선택.

3. 최소 신장 트리 (Minimum Spanning Tree):

• 문제: 그래프에서 모든 노드를 연결하는 간선의 가중치 합이 최소가 되도록 트리 구성.
• 탐욕 알고리즘:
  • Kruskal 또는 Prim 알고리즘이 사용됩니다.

4. 허프만 코딩 (Huffman Coding):

• 문제: 문자 빈도에 따라 최소 길이의 이진 코드를 생성.
• 탐욕 선택:
  • 가장 빈도가 낮은 두 문자를 병합.

탐욕 알고리즘 설계 단계

1. 문제를 나누기:
   • 문제를 여러 단계로 나눕니다.
2. 탐욕적 선택 기준 정의:
   • 각 단계에서 가장 최적인 선택 기준을 정의합니다.
3. 선택 반복:
   • 정의된 기준에 따라 각 단계에서 최적의 선택을 반복합니다.
4. 문제 종료 조건 확인:
   • 선택 과정이 종료되었는지 확인하고 결과를 반환합니다.

---

장점

1. 단순하고 빠름:
   • 계산이 단순하며, 보통 다른 알고리즘보다 효율적으로 동작.
2. 적용 가능성 높음:
   • 특정 문제에서 매우 효과적이며, 구현이 간단.

---

단점

1. 국소 최적해 ≠ 전역 최적해:
   • 모든 문제에서 최적해를 보장하지 않습니다.
   • 예를 들어, **배낭 문제(Knapsack Problem)**에서 탐욕 알고리즘은 최적해를 보장하지 못할 수 있음.
2. 문제 구조에 의존:
   • 탐욕 선택 속성과 최적 부분 구조가 없는 문제에는 사용할 수 없습니다.

---

탐욕 알고리즘과 DP의 차이

특성	탐욕 알고리즘	동적 계획법(DP)
선택 기준	현재 단계의 최적 선택	모든 경우를 탐색하며 최적해 계산
최적해 보장	문제 구조에 따라 최적해를 보장할 수도 있고 아닐 수도 있음	항상 최적해 보장
시간 복잡도	비교적 작음 O(n) 또는 O(nlog⁡n)	보통 높음 O(n^2) 또는 O(n⋅m)
적용 문제 유형	탐욕 선택 속성, 최적 부분 구조를 가진 문제	최적 부분 구조를 가진 모든 문제

---

예시 코드: 활동 선택 문제

def activity_selection(start, end):
    # 활동을 종료 시간 기준으로 정렬
    activities = sorted(zip(start, end), key=lambda x: x[1])
    selected = []
    prev_end = -1

    for s, e in activities:
        if s >= prev_end:  # 활동이 겹치지 않으면 선택
            selected.append((s, e))
            prev_end = e

    return selected

# 테스트
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, end))  # 출력: [(1, 2), (3, 4), (5, 7), (8, 9)]

 

이 알고리즘은 종료 시간이 가장 빠른 활동을 선택해 전체 최적해를 구합니다. 😊

 

https://youtu.be/_IZuE7NIeW4?si=-PXI9n2lSIhsD5xY

 

https://youtu.be/LD4AKF9tjro?si=24vlZX011sLyOrz9