[알고리즘] DP 동적계획법

✅ 동적계획법(DP)

 

1. 동적계획법이란?

- 하나의 큰 문제를 여러 개의 작은 문제로 분할하여 푸는 방법

- 이미 계산된 작은 문제의 결과 값을 별도의 메모리 영역에 저장해두고 활용함.

- 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킬 수 있음.

답을 재활용하는 것!
"어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고,
과거에 구한 해를 활용하는" 방식의 알고리즘

 

2. 동적계획법 사용 조건

1) 큰 문제를 작은 문제로 나눌 수 있음.

2) 작은 문제에서 구한 값이 그것을 포함하는 큰 문제에서도 동일한 값으로 사용됨 (피보나치 수열)

---

✅ 분할정복법 VS 동적계획법

 

공통점

큰 문제를 쪼개서 가장 작은 단위로 분할한다.

 

차이점

- 분할정복법 : 부분 문제는 서로 중복되지 않음 (메모이제이션 기법 사용 X)

- 동적계획법 : 부분 문제는 중복되어 상위 문제 해결시 재활용됨 (메모이제이션 기법 사용 O)

💡 용어정리 💡 
메모이제이션(memoization)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때,
이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여
프로그램 실행 속도를 빠르게 하는 기술이다. 

---

✅ 동적계획법 사용 방법

 

1. 완전탐색법으로 접근한다.

2. 반복되는 부분 문제를 찾는다.

3. 기저단계를 설정한다.

4. 점화식을 설정한다.

5. 중복된 문제를 한번만 계산하기 위해 메모이제이션을 이용한다.

💡 용어정리 💡 
기저단계 : 점화식으로 더 이상 계산하지 못하는 부분

---

✅ 동적계획법 사용 예시 (피보나치 수열)

 

1. 재귀로 해결한 피보나치 수열

int fibonacci(unsigned int n)
{
    if(n <= 1)
        return 1;
    else
        return fibonacci(n-1)+f(n-2);
}

💥 반복되는 계산이 많음

2. 동적계획법 (Top-down 방식) 사용

int memo[100]{}; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
  if (n<=1) //0번째, 1번째 피보나치 수
    return n;
  if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]; //메모 리턴
  memo[n] = fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
  return memo[n];
}

 

3. 동적계획법 (Bottom-up 방식) 사용

int dp[50] = { 1,1 };

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

 

💥 시간 복잡도 차이

(왼) 일반 피보나치 수열 / (오) DP 피보나치 수열

1) 일반 피보나치 수열

- 재귀를 사용하기 때문에 높이가 n인 트리가 2개 존재함

- 시간 복잡도 : O(2^n)

 

2) DP 피보나치 수열

- 두번씩 반복할 필요가 없음

- 시간 복잡도 : O(n)