Greedy Algorithm vs. Divide and Conquer

Divide and Conquer vs. Greedy Algorithm

“Divide and Conquer"와 “Greedy Algorithm"은 문제 해결을 위한 두 가지 중요한 알고리즘 패러다임이다.
분할 정복은 문제를 더 작은 하위 문제로 나누어 해결하는 체계적인 접근 방식인 반면, 탐욕 알고리즘은 각 단계에서 지역적 최적 선택을 통해 문제를 해결하는 직관적인 접근 방식이다.

분할 정복은 정확한 최적해를 보장하지만 구현이 복잡할 수 있고, 탐욕 알고리즘은 구현이 간단하고 효율적이지만 항상 최적해를 보장하지는 않는다. 문제의 특성을 잘 이해하고 적절한 알고리즘을 선택하는 것이 중요하다.

Divide and Conquer(분할 정복) 알고리즘

분할 정복은 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 방법이다.
이 알고리즘은 다음과 같은 세 단계로 구성된다:

1. 분할(Divide): 원래 문제를 더 작은 하위 문제들로 나눈다.
2. 정복(Conquer): 각 하위 문제를 재귀적으로 해결한다.
3. 결합(Combine): 하위 문제들의 해결책을 합쳐 원래 문제의 해결책을 만든다.

대규모 프로젝트 관리와 유사하다. 큰 프로젝트(문제)를 여러 팀에 나누어 할당(분할)하고, 각 팀이 자신의 과제를 해결(정복)한 다음, 모든 결과를 통합(결합)하여 전체 프로젝트를 완성한다.

작동 원리 예시: 병합 정렬(Merge Sort)

병합 정렬은 분할 정복의 대표적인 예:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def merge_sort(arr):
    # 기본 사례: 배열의 길이가 1 이하면 이미 정렬된 것으로 간주
    if len(arr) <= 1:
        return arr
    
    # 분할 단계: 배열을 두 부분으로 나눔
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 정복 단계: 재귀적으로 각 부분을 정렬
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 결합 단계: 정렬된 두 부분을 병합
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 두 리스트의 요소를 비교하여 작은 것부터 결과에 추가
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 남은 요소들을 결과에 추가
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

이 알고리즘은 배열을 절반씩 나누어(분할) 각 부분을 재귀적으로 정렬(정복)한 다음, 정렬된 두 부분을 하나로 병합(결합)한다.

Greedy Algorithm(탐욕 알고리즘)

탐욕 알고리즘은 각 단계에서 현재 상황에서 가장 최적인 선택(지역적 최적해)을 선택하여 최종적으로 전체 문제의 최적해를 찾는 방법이다.
이 알고리즘은 다음과 같은 특징을 가진다:

1. 지역적 최적 선택(Local Optimal Choice): 각 단계에서 현재 상황에서 최선의 선택을 한다.
2. 탐욕적 선택 속성(Greedy Choice Property): 지역적 최적 선택이 전체 문제의 최적해로 이어진다.
3. 최적 부분 구조(Optimal Substructure): 문제의 최적해가 하위 문제의 최적해를 포함한다.

등산을 할 때 매 순간 가장 가파른 경로를 선택하는 것과 유사하다(이를 ‘언덕 오르기’라고도 합니다). 각 지점에서 가장 높이 올라갈 수 있는 방향(지역적 최적)을 선택하여 산 정상(전체 최적)에 도달하려고 한다.
하지만 이 방법이 항상 정상에 도달하는 것을 보장하지는 않으며, 지역적 정상에 갇힐 수 있다.

작동 원리 예시: 거스름돈 문제

거스름돈 문제는 탐욕 알고리즘의 대표적인 예:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def coin_change_greedy(amount, coins):
    # 동전을 내림차순으로 정렬
    coins.sort(reverse=True)
    
    result = []  # 사용할 동전 목록
    
    for coin in coins:
        # 현재 동전을 최대한 많이 사용
        while amount >= coin:
            amount -= coin
            result.append(coin)
    
    return result

# 예시: 한국 화폐 단위로 거스름돈 계산
amount = 1260
coins = [500, 100, 50, 10]
print(coin_change_greedy(amount, coins))  # [500, 500, 100, 100, 50, 10]

이 알고리즘은 매 단계에서 가장 큰 단위의 동전부터 사용하여(탐욕적 선택) 최소한의 동전으로 거스름돈을 만든다.

두 알고리즘의 핵심 차이점

1. 문제 해결 접근 방식

   • 분할 정복: 문제를 더 작은 하위 문제로 나누어 각각 해결한 후 결합한다.
   • 탐욕 알고리즘: 각 단계에서 현재 상황에서 최선의 선택을 하여 문제를 해결한다.

2. 결정 방식

   • 분할 정복: 전체 문제를 고려하여 하위 문제로 분할하고, 모든 하위 문제의 해결책을 종합적으로 고려한다.
   • 탐욕 알고리즘: 매 단계에서 지역적 최적 선택만을 고려하며, 이전 결정을 수정하지 않는다.

3. 최적해 보장

   • 분할 정복: 모든 경우를 고려하므로 일반적으로 최적해를 보장한다.
   • 탐욕 알고리즘: 모든 문제에서 최적해를 보장하지는 않으며, 특정 조건(탐욕적 선택 속성, 최적 부분 구조)을 만족해야 한다.

4. 예시로 보는 차이: 배낭 문제(Knapsack Problem)
   배낭 문제는 두 알고리즘의 차이를 잘 보여주는 예이다:

   • 일반적인 배낭 문제: 여러 물건의 가치와 무게가 있을 때, 제한된 무게 내에서 최대 가치를 선택하는 문제
   • 분할 가능한 배낭 문제: 물건을 부분적으로 선택할 수 있는 경우
     분할 정복 접근: 모든 가능한 물건의 조합을 고려하여 최적해를 찾습니다. 이는 물건의 수가 많을 때 비효율적이다.
     탐욕 알고리즘 접근: 단위 무게당 가치가 높은 물건부터 선택한다. 이 방법은 분할 가능한 배낭 문제에서는 최적해를 보장하지만, 일반 배낭 문제에서는 최적해를 보장하지 않는다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   # 분할 가능한 배낭 문제의 탐욕 알고리즘 해결법 def fractional_knapsack(capacity, weights, values): # 각 물건의 단위 무게당 가치 계산 items = [(values[i] / weights[i], weights[i], values[i]) for i in range(len(weights))] # 단위 무게당 가치를 기준으로 내림차순 정렬 items.sort(reverse=True) total_value = 0 for unit_value, weight, value in items: if capacity >= weight: # 물건 전체를 선택 total_value += value capacity -= weight else: # 물건의 일부만 선택 total_value += unit_value * capacity break return total_value

실제 적용 사례

• Divide and Conquer 적용 사례
  1. 퀵 정렬(Quick Sort): 배열을 피벗을 기준으로 분할하여 정렬
  2. 이진 검색(Binary Search): 정렬된 배열에서 중간점을 기준으로 검색 범위를 반으로 줄임
  3. 최대 부분 배열 문제(Maximum Subarray Problem): 배열을 분할하여 최대 합을 가진 부분 배열을 찾음
  4. 스트라센 알고리즘(Strassen’s Algorithm): 행렬 곱셈을 효율적으로 수행
• Greedy Algorithm 적용 사례
  1. 최소 신장 트리(Minimum Spanning Tree): 크루스칼(Kruskal), 프림(Prim) 알고리즘
  2. 다익스트라 알고리즘(Dijkstra’s Algorithm): 최단 경로 찾기
  3. 허프만 코딩(Huffman Coding): 데이터 압축
  4. 작업 스케줄링(Job Scheduling): 가장 짧은 작업부터 처리하는 방식

코드 비교: 동전 개수 최소화 문제

가능한 동전 종류가 주어졌을 때, 특정 금액을 만들기 위한 최소 동전 개수를 구하는 문제.

• 분할 정복 접근법 (실제로는 동적 계획법이 더 적합)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  def min_coins_dc(coins, amount): # 모든 가능한 경우를 고려 if amount == 0: return 0 result = float('inf') for coin in coins: if coin <= amount: sub_result = min_coins_dc(coins, amount - coin) if sub_result != float('inf'): result = min(result, sub_result + 1) return result

• 탐욕 알고리즘 접근법

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  def min_coins_greedy(coins, amount): # 동전을 내림차순으로 정렬 coins.sort(reverse=True) count = 0 for coin in coins: # 현재 동전을 최대한 많이 사용 while amount >= coin: amount -= coin count += 1 # 모든 동전을 사용해도 금액을 만들 수 없는 경우 if amount > 0: return -1 return count

  여기서 주목할 점은 탐욕 알고리즘이 항상 최적해를 보장하지 않는다는 것.
  예를 들어, 동전 종류가 [1, 3, 4]이고 금액이 6인 경우:

  • 탐욕 알고리즘: 4 + 1 + 1 = 3개의 동전 사용
  • 최적해: 3 + 3 = 2개의 동전 사용

선택 가이드

• Divide and Conquer를 선택해야 할 때
  • 문제가 동일한 구조의 더 작은 하위 문제로 자연스럽게 나눠질 때
  • 문제의 크기가 크고 분할하여 해결할 수 있을 때
  • 정확한 최적해가 필요할 때
  • 병렬 처리가 가능하거나 필요할 때
  • 전체 탐색 공간을 효율적으로 줄일 수 있을 때
• Greedy Algorithm을 선택해야 할 때
  • 각 단계에서의 최선의 선택이 전체 문제의 최적해로 이어질 때
  • 빠른 실행 시간이 중요할 때
  • 문제의 크기가 크고 모든 경우를 고려하기 어려울 때
  • 근사 해답이 허용될 때(최적이 아니더라도 충분히 좋은 해답)
  • 문제가 최적 부분 구조와 탐욕적 선택 속성을 가질 때
• 문제 접근 방법
  1. 문제 분석: 문제의 구조와 특성을 파악합니다.
     • 문제가 더 작은 하위 문제로 나눠질 수 있는지
     • 지역적 최적 선택이 전체 최적해로 이어지는지
  2. 알고리즘 선택:
     • 문제가 분할 정복의 구조를 가지고 있으면 → 분할 정복
     • 문제가 탐욕적 선택 속성과 최적 부분 구조를 가지고 있으면 → 탐욕 알고리즘
  3. 검증:
     • 분할 정복: 하위 문제들이 올바르게 정의되었는지, 결합 방법이 적절한지 확인
     • 탐욕 알고리즘: 선택한 탐욕적 전략이 항상 최적해를 보장하는지 증명하거나 검증

응용 예제: 최소 신장 트리(MST) 구현

최소 신장 트리 문제는 주어진 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소인 트리를 찾는 문제.
이 문제는 탐욕 알고리즘인 크루스칼 알고리즘으로 효율적으로 해결할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 크루스칼 알고리즘을 이용한 최소 신장 트리 구현
def kruskal_mst(graph, vertices):
    # 결과를 저장할 리스트
    result = []
    
    # 간선을 가중치 기준으로 오름차순 정렬
    edges = sorted(graph, key=lambda x: x[2])
    
    # 각 정점의 부모를 자기 자신으로 초기화
    parent = [i for i in range(vertices)]
    
    # 두 정점이 속한 집합 찾기 (Find 연산)
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    # 두 집합 합치기 (Union 연산)
    def union(x, y):
        parent[find(x)] = find(y)
    
    i, e = 0, 0
    
    # MST는 (정점 수 - 1)개의 간선을 가짐
    while e < vertices - 1:
        u, v, w = edges[i]
        i += 1
        
        # 사이클을 형성하는지 확인
        x = find(u)
        y = find(v)
        
        if x != y:  # 사이클이 형성되지 않으면 간선 추가
            e += 1
            result.append([u, v, w])
            union(x, y)
    
    return result

# 예시
graph = [
    [0, 1, 10],  # [시작 정점, 도착 정점, 가중치]
    [0, 2, 6],
    [0, 3, 5],
    [1, 3, 15],
    [2, 3, 4]
]
vertices = 4

mst = kruskal_mst(graph, vertices)
print("최소 신장 트리의 간선:", mst)

이 크루스칼 알고리즘은 탐욕적 접근을 사용한다:

1. 모든 간선을 가중치 순으로 정렬합니다.
2. 가중치가 가장 작은 간선부터 선택합니다(탐욕적 선택).
3. 사이클을 형성하지 않는 간선만 추가합니다.

두 알고리즘 비교

참고 및 출처