[Algorithm] 동적 계획법(DP, Dynamic Programming)

💟 정의

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킨다.
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다.
• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다.

 

💟 조건

1. 최적 부분 구조(Optimal Substructure)
   - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem)
   - 동일한 작은 문제를 반복적으로 해결해야 한다.

 

💟 피보나치 수열

제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략하기도 한다. 단순 재귀 함수로 피보나치 수열을 구현하면 지수 시간 복잡도를 가진다. 같은 메서드가 여러 번 호출된다는 문제가 있다.

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

 

💟 메모이제이션(Memorization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나이지만, DP에 국한된 개념은 아니다.
• 한 번 계산한 결과를 메모리 공간에 메모해 놓고, 같은 문제를 다시 호출하면 메모한 결과를 가져온다. = 캐싱(Caching)

1. TOP-DOWN

• 하향식(재귀 함수를 이용)

d = [0] * 100

def fibo(x):

  # 종료 조건
  if x == 1 or x == 2:
    return 1
    
  # 이미 계산한 적 있는 문제일 경우
  if d[x] != 0:
    return d[x]
    
  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

print(fibo(99))

2. BOTTOM-UP

• 상향식(반복문 이용)
• 다이나이믹 프로그래밍의 전형적인 형태이다. 결과 저장용 리스트는 DP 테이블이라고 한다.

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
  d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

💟 동적 계획법의 등장

이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다. 처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져온다.

int fiboData[100] = {0,};

int fibo(int n)
{
  if (n <= 2) 
    return 1;
  if (fiboData[n] == 0)
    fiboData[n] = fibo(n - 1) + fibo(n - 2);
  return fiboData[n];
}

1. fiboData라는 배열을 생성 - 연산한 값들이 저장될 예정
2. n이 2 이하일 경우 1을 반환, 그 이상일 경우 fiboData[n]에 연산 값이 없는지 검사
3. 없을 경우, 새로 연산해서 fiboData[n]에 값을 저장하고, 반환
4. 만약 연산 값이 존재한다면 바로 fiboData[n]을 반환

재귀와는 다르게 중복되는 연산이 사라진다. 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘이다.

 

💟 장점과 단점

  동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이다.

모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식인 그리디 알고리즘(탐욕 알고리즘)과 대비된다. 이는 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없다.

동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택한다. 이런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가진다.