Dynamic Programming vs. Divide and Conquer

Divide and Conquer vs. Dynamic Programming

“Divide and Conquer"와 “Dynamic Programming"은 모두 복잡한 문제를 더 작은 부분으로 나누어 해결하는 전략이지만, 접근 방식과 적용 상황에서 중요한 차이가 있다.

분할 정복은 문제를 독립적인 하위 문제로 나누어 효율성을 높이는 반면, 동적 계획법은 중복되는 하위 문제의 결과를 저장하여 재계산을 방지한다.

알고리즘 선택은 문제의 성격에 따라 달라져야 한다.
하위 문제 간 중복이 있는지, 최적 부분 구조가 있는지를 파악하여 적절한 알고리즘을 선택하는 것이 중요하다.

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

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

Dynamic Programming(동적 계획법) 알고리즘

동적 계획법은 복잡한 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 결과를 저장(메모이제이션)하여 중복 계산을 피하는 방법이다.
이 알고리즘의 핵심 원리는 다음과 같다:

1. 최적 부분 구조(Optimal Substructure): 문제의 최적 해결책이 하위 문제의 최적 해결책으로 구성된다.
2. 중복되는 하위 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 발생하며, 그 결과를 저장해 재사용할 수 있다.

여행 계획을 세우는 과정과 유사하다.
서울에서 부산까지 가는 최적 경로를 찾을 때, 중간 도시들 간의 최적 경로를 먼저 계산하고 저장해 둡니다. 그리고 이 정보를 활용하여 전체 경로를 구성한다. 만약 대전에서 대구까지의 최적 경로를 이미 계산했다면, 이를 다시 계산하지 않고 저장된 결과를 재사용한다.

작동 원리 예시: 피보나치 수열

피보나치 수열은 동적 계획법의 기본적인 예:

 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

# 재귀적 방식 (비효율적)
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 동적 계획법 방식 (메모이제이션 사용)
def fibonacci_dp(n, memo={}):
    # 이미 계산된 값이 있으면 바로 반환
    if n in memo:
        return memo[n]
    
    # 기본 사례
    if n <= 1:
        return n
    
    # 결과 계산 및 저장
    memo[n] = fibonacci_dp(n-1, memo) + fibonacci_dp(n-2, memo)
    return memo[n]

# 동적 계획법 방식 (상향식 접근)
def fibonacci_bottom_up(n):
    # 결과를 저장할 배열
    dp = [0] * (n+1)
    
    # 기본 사례 설정
    dp[0] = 0
    dp[1] = 1
    
    # 하위 문제부터 차례로 해결
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

동적 계획법은 위 예시에서 볼 수 있듯이 두 가지 접근 방식이 있다:

• 하향식(Top-down): 메모이제이션을 활용한 재귀적 접근법
• 상향식(Bottom-up): 반복문을 사용하여 작은 문제부터 해결해 나가는 접근법

두 알고리즘의 핵심 차이점

1. 문제 해결 접근 방식

   • 분할 정복: 문제를 독립적인 하위 문제로 나누어 각각 해결한 후 결합한다. 하위 문제 간에는 중복이 없다.
   • 동적 계획법: 문제를 중복되는 하위 문제로 나누고, 각 하위 문제의 결과를 저장하여 재사용한다.

2. 하위 문제의 특성

   • 분할 정복: 하위 문제가 서로 독립적이다 (중복 없음).
   • 동적 계획법: 하위 문제가 서로 의존적이며 중복된다.

3. 예시로 보는 차이: 피보나치 수열
   피보나치 수열 F(n) = F(n-1) + F(n-2)를 계산할 때:

   • 분할 정복 접근: F(n)을 F(n-1)과 F(n-2)로 나누어 계산하면, 같은 하위 문제가 여러 번 계산된다.
     • 예: F(5)를 계산하려면 F(4)와 F(3)이 필요, F(4)를 계산하려면 F(3)과 F(2)가 필요 -> F(3)이 중복 계산됨
   • 동적 계획법 접근: F(n-1), F(n-2), … 등을 계산할 때 결과를 저장하고 재사용한다.
     • 예: F(3)의 값을 저장해두면 F(4)와 F(5)를 계산할 때 다시 계산하지 않고 저장된 값을 사용

실제 적용 사례

• Divide and Conquer 적용 사례
  1. 퀵 정렬(Quick Sort): 배열을 피벗을 기준으로 분할하여 정렬
  2. 이진 검색(Binary Search): 정렬된 배열에서 중간점을 기준으로 검색 범위를 반으로 줄임
  3. 행렬 곱셈(Strassen’s Algorithm): 행렬을 분할하여 곱셈을 효율적으로 수행
  4. 최근접 점쌍 찾기(Closest Pair of Points): 평면 상의 점들을 분할하여 최근접 점쌍을 찾음
• Dynamic Programming 적용 사례
  1. 최장 공통 부분 수열(Longest Common Subsequence): 두 문자열 간의 공통 부분 수열 찾기
  2. 배낭 문제(Knapsack Problem): 제한된 무게 내에서 최대 가치의 물건을 선택
  3. 최단 경로 문제(Shortest Path Algorithms): 다익스트라, 플로이드-워셜 등의 알고리즘
  4. 행렬 연쇄 곱셈(Matrix Chain Multiplication): 여러 행렬의 곱셈 순서 최적화

코드 비교: 이항 계수 계산

이항 계수(Binomial Coefficient) C(n,k)를 계산하는 두 가지 방법을 비교:

• 분할 정복 접근법

  1 2 3 4 5 6 7

  def binomial_coefficient_dc(n, k): # 기본 사례 if k == 0 or k == n: return 1 # 분할 정복 방식: C(n,k) = C(n-1,k-1) + C(n-1,k) return binomial_coefficient_dc(n-1, k-1) + binomial_coefficient_dc(n-1, k)

• 동적 계획법 접근법

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

  def binomial_coefficient_dp(n, k): # DP 테이블 초기화 dp = [[0 for _ in range(k+1)] for _ in range(n+1)] # 기본 사례 채우기 for i in range(n+1): dp[i][0] = 1 # C(i) = 1 for i in range(k+1): if i <= n: dp[i][i] = 1 # C(i,i) = 1 # 나머지 값 계산 for i in range(1, n+1): for j in range(1, min(i, k)+1): dp[i][j] = dp[i-1][j-1] + dp[i-1][j] return dp[n][k]

분할 정복 방식은 중복 계산으로 인해 시간 복잡도가 O(2^n)이 되지만, 동적 계획법 방식은 결과를 저장하고 재사용하여 시간 복잡도가 O(n*k)로 개선된다.

선택 가이드

• Divide and Conquer를 선택해야 할 때
  • 문제가 자연스럽게 독립적인 하위 문제로 나뉠 때
  • 하위 문제 간에 중복이 없을 때
  • 병렬 처리가 필요할 때(독립적인 하위 문제는 병렬로 처리 가능)
  • 정렬, 검색과 같은 기본적인 알고리즘 문제를 해결할 때
• Dynamic Programming을 선택해야 할 때
  • 동일한 하위 문제가 반복해서 계산될 때
  • 최적화 문제(최대/최소값 찾기)를 해결할 때
  • 문제에 최적 부분 구조가 있을 때(전체 문제의 최적해가 하위 문제의 최적해로 구성)
  • 그리디 알고리즘으로는 대개 해결할 수 없는 복잡한 최적화 문제를 해결할 때
• 문제 접근 방법
  1. 문제 분석: 문제의 구조를 먼저 이해한다.
     • 하위 문제가 중복되는지 확인한다.
     • 최적 부분 구조가 있는지 확인한다.
  2. 알고리즘 선택:
     • 중복 하위 문제와 최적 부분 구조가 있으면 → 동적 계획법
     • 문제가 독립적인 하위 문제로 나뉘면 → 분할 정복
  3. 접근 방식 선택 (동적 계획법의 경우):
     • 하향식(메모이제이션): 재귀적 구조가 자연스러울 때
     • 상향식(테이블링): 메모리 효율성이 중요하거나 반복 구조가 자연스러울 때

두 알고리즘 비교

참고 및 출처