[자료구조/알고리즘] 동적계획법(DP)

프로그래머스에서 피보나치 수열 코딩테스트 문제를 풀다가...

신나게 재귀함수로 풀어야지~~ 하고 풀었지만 시간초과, 런타임 에러...

프로그래머스에서 제공하는 코딩테스트 연습 힌트 모음집을 보니까 딱 나의 케이스에 대한 내용이 있었다🤣

---

 

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 되어 시간초과가 난 것이었다,,

return f(n) = f(n-1) + f(n-2)

 

이렇게 하게 되면 f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 같은 값을 구하는 과정을 반복하게 되기 때문에 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가하는 것이다.

 

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용하게 되면 앞에서 계산된 값을 다시 반복할 필요가 없이 적은 수의 반복만으로도 계산이 가능해진다.

 

이 참에 DP에 대해 학습해야겠다..!

---

1. 동적계획법(DP)이란?

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

2. DP의 사용 조건

1) Overlapping Subproblems (겹치는 부분 문제)

• 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능

2) Optimal Substructure (최적 부분 구조)

• 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 사용가능

3. DP 사용하기

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

2) 문제의 변수 파악

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

4) 메모하기 (memoization or tabulation)

5) 기저 상태 파악하기

6) 구현하기

4. 구현방법

1) Bottom-Up 방식 (Tabulation)

• 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결

function solution(n) {
  if (n === 1 || n === 2) return n;
  const dp = Array(n).fill(0);
  const mod = 1000000007;
  dp[0] = 1;
  dp[1] = 2;
  for (let i = 2; i < n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
  return dp[n - 1];
}

• 연산 결과를 저장할 1차원 배열 dp의 길이 n으로 설정, 0으로 초기화
• n = 1일 때 경우의 수인 1과 n = 2일 때 경우의 수인 2를 배열의 가장 처음에 설정

2) Top-Down 방식

• 위에서부터 바로 호출을 시작하여 제일 밑 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

function solution(n) {
  if (n === 1 || n === 2) return n;
  const memo = Array(n + 1).fill(0);
  const mod = 1000000007;

  const dp = (n) => {
    if (n <= 2) return n;
    if (memo[n] > 0) return memo[n];
    memo[n] = (dp(n - 1) + dp(n - 2)) % mod;
    return memo[n];
  };
  return dp(n);
}

• 재귀함수를 사용해서 구현 --> 효율성 테스트 실패