동적 계획법(Dynamic Programming)과 분할 정복(Divide and Conquer)

Posted on | In

정의 및 특징

동적 계획법(Dynamic Programming)

동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘이다.

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이다. 여기서 그리디 알고리즘(탐욕 알고리즘) 과 대비된다.

그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식입니다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없겠죠. 하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택합니다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있습니다.

정리하면

  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 큰 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 기법입니다.
  • 상향식 접근법으로 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결괏값을 이용해 상위 문제를 풀어가는 방식을 활용합니다.
  • Memoization 기법을 활용합니다. Memoization (메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하며, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술입니다. 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됩니다.


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

  • 문제를 나눌 수 없을 때까지 나누어서 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘입니다.
  • 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식입니다.
  • 일반적으로 재귀 함수로 구현됩니다.
  • 문제를 잘게 쪼갤 때, 부분 문제는 동적 계획법과 달리 중복되지 않습니다.
  • 즉 Memoization 기법을 사용하지 않습니다.
  • 분할 정복의 대표적인 예시 : Quick Sort, Merge Sort



공통점 및 차이점

공통점

  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할

차이점

동적 계획법

  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

분할 정복

  • 부분 문제는 서로 중복되지 않음
  • Memoization 기법 사용 안함



동적 계획 알고리즘 예시

동적계획 알고리즘의 예시를 알아보고 문제를 통해 이해하자.

피보나치 수열

동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있다. 피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략하기도 한다. 수열은 아래와 같다.

1
(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현한다. 아래는 피보나치 수열의 n번째 수를 구하는 함수다.

Memoization을 활용하지 않은 코드

1
2
3
4
5
6
7
int fibo(int n)
  {
    if (n<=2)
      return 1;
    else
      return fibo(n-1) + fibo(n-2);
   }

시간 복잡도는 O(n^2)

Memoization을 활용한 코드

image

1
2
3
4
5
6
7
8
def fibo_dp(num): 
  cache = [0 for index in range(num+1)] #메모이제이션을 위한 list 
  comprehension cache[0] = 0 #f(0)의 값을 저장 
  cache[1] = 1 #f(1)의 값을 저장 
  
  for index in range(2,num+1): #0과 1은 저장되어 있으니 2부터 시작 
    cache[index] = cache[index-1] + cache[index-2] #메모이제이션 기법 사용 
  return cache[num]

시간 복잡도는 O(n)

Memoization은 중복되는 계산을 다시 계산하지 않기 때문에 기존의 알고리즘보다 속도가 매우 빠를 수밖에 없습니다.

0%