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

DP란?

큰 문제를 여러개의 작은 문제로 나누고 계산했던 정보를 바탕으로 문제를 해결해 나가는 하나의 방식.

DP의 조건

DP를 사용하기 전 2가지의 조건이 맞는지 확인 해봐야 한다.

1. 최적 부분 구조 (Optimal Substructure)
   큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미

2. 중복되는 부분 문제 (Overlapping Subproblem)
   동일한 작은 문제를 반복적으로 해결해야 하는 경우

1번을 실생활 예로 들자면,
부산 - 대전 - 서울 순서로 부산에서 서울로 가는 최소의 거리를 찾으려 한다.

부산 - 대전으로 갈때에 최소의 경로를 선택 후 대전 - 서울의 최소 경로를 선택한다.

추가로 부산 - 대전 - 서울 - 강원도 순서로 부산에서 강원도로 가는 최소의 거리를 찾으려 할 때 부산 - 대전 - 서울의 거리를 다시 알아보지 않아도, 이미 최소의 거리를 알고 있기 때문에 서울-강원도의 최소 거리를 알게되면 부산에서 강원도의 최소경로를 알게된다.

2번은 피보나치 수열에서 발생하는 문제라고 생각하면된다.

DP를 사용하는 이유

큰 문제를 여러개의 작은문제로 나누는 방식에는 재귀함수가 있다.
재귀함수를 통해 문제를 해결했을 때 DP를 사용하는 이유을 알 수 있다.

대표적인 예로 피보나치 수열로 알아보자

재귀함수를 코드로 나타내면 다음과 같다.

	function fibonacci(num){
      if(num <= 1){
       	return 1; 
      }else{
       	return fibonacci(num-1) + fibonacci(num-2);
      }
    }
	
	console.log(fibonacci(4)) // 5

재귀함수의 과정은 다음과 같다.

	num = 4 의 경우 fibonacci(3) + fibonacci(2) 호출
    num = 3 의 경우 fibonacci(2) + fibonacci(1) 호출
    num = 2 의 경우 fibonacci(1) + fibonacci(0) 호출
    num = 1 || 0 의 경우 조건 탈출
    

그런데 여기서 num=4의 경우와 num=3의 경우에서 똑같은 fibonacci(2)를 호출하고 있다.
즉 f(n-1)에서 한 번 구한값을 f(n-2)에서 또 다시 같은 과정을 반복하는 셈이다.

구하는 과정의 숫자가 커지게 되면 어떻게 될까?!
연산의 복잡도는 굉장히 커지게 된다. (피보나치의 시간복잡도 : O(N^2))

그래서 우리는 여기에 DP라는 개념을 도입할것이다.
어떻게? 나누고, 계산했던 정보를 바탕으로!!

DP사용하기

다음과 같은 과정으로 DP를 적용할 수 있는지 먼저 파악하자.

1. DP로 풀 수 있는 문제인지 확인(2가지 조건)
2. 문제의 변수 파악
3. 변수 간 관계식 만들기(점화식)
4. 변수 저장하기 및 구현

DP로 피보나치 해결하기

1. DP로 풀 수 있는 문제인지 확인

f(4)를 통해서 f(3)과f(2)를 구할 수 있고(1번 조건), 중복되는 함수 호출이 존재함. => 통과

2. 문제의 변수 파악

피보나치 수열에는 n만 들어가기 때문에 변수는 n

3. 변수 간 관계식 만들기(점화식)

피보나치의 점화식 : f(n) = f(n-1) + f(n-2);

4. 변수 저장하기 및 구현

const dp = new Array(10).fill(0); // 10의 길이를 가지는 배열 안에 각 요소를 0으로 초기화

function fibonacci(num) {
  if (num === 1 || num ===2) {
    return 1;
  }

  if (dp[num] !== 0) {
    // 0이 아니라 이미 계산한 적이 있다면 저장된 값을 반환
    return dp[num];
  }

  dp[num] = fibonacci(num - 1) + fibonacci(num - 2);
  return dp[num]
}

fibonacci(5)를 호출할 경우 순서는 다음과 같다.

fibonacci(5) > fibonacci(4) > fibonacci(3) > fibonacci(2) > fibonacci(1) > fibonacci(2)//dp[2]저장된 값이 있어 탈출 > fibonacci(3)//dp[3]저장된 값이 있어 탈출 > fibonacci(4)//dp[4]저장된 값이 있어 탈출

풀어 볼 문제

• 피보나치 문제
  https://www.acmicpc.net/problem/1003

• DP개념 확인 문제
  https://www.acmicpc.net/problem/2579