DP 동적프로그래밍

zioo·2022년 4월 15일

algorithm python

DP란

큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.

방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 그러나 동적프로그래밍에서는 계산한부분을 남겨놓고 계속해서 필요할때 끌어다 쓴다.

부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

동작방식

구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.)
가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션
메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다.
가장 큰 문제를 풀이할때까지 반복한다.
☆무엇을 어떻게 저장할지 정하는게 중요하다.

동적 계획법 접근 방법

1. Botton-Up 방식 : 반복문을 이용

아래에서 위로 접근하는 방법이다.

부분 문제에서부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.

ex)
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

4를 1,2,3으로 나눈다고 가정해보자

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

로 실행할 수 있을것이다. 총 7가지의 경우

만약 1이라면 1가지의 경우
2라면 2가지의 경우
3이라면 4가지의 경우
4라면 7의 경우
5라면 13가지의 경우가 생길것이다.

여기서 d[n] = d[n-1]+d[n-2]+d[n-3] 이라는 점화식을 도출할 수 있다.

이처럼 직관적으로 구할 수 있는 작은 해를 구한 후 이를 이용하여 더 큰 문제를 풀 수 있다.

이 방법을 Bottom-up 방식이라고 부른다.

ex2)

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {

    for(int i = 3; i <=n; i++){
      memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
  }

2. Top-Down 방식 : 재귀함수 사용

위에서 아래로 접근하는 방법이다.
큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법이다.

ex) 위의 문제를 Top-Down으로 풀어보자

Bottom-up 방식을 사용할 때,
만약 d[7]을 구하려면 d[6] d[5] d[4]를 알아야 하고
d[6]을 구하려먼 d[5] d[4] d[3] 을 알아야 할 것이다.

일일히 다 구해주기에는 d[5] 와 d[4] 를 겹치는 일이 중복되어 시간복잡도의 낭비가 생길것이다.
이미 구한 값을 기록해두고 불필요한 재귀호출을 방지하는 메모이제이션 작업을 한다.

ex2)

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (memo[n] != 0) 
      return memo[n];

    memo[n] = fib(n-1) + fib(n-2);

    return memo[n];
  }