JS, DP(Dynamic Programming)

[ 동적 계획법(Dynamic Programming) ]

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

즉 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 함

 

▶ DP를 사용하는 이유

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될수 있음

예를 들어 피보나치 수의 경우 1이상의 n의 경우 F(n) = F(n-2) + F(n-1)적용되는 수를 말함(F(0)=0, F(1)=1)

 

만약 n이 4라면 재귀호출 방식을 사용하게 되면

F(4) = F2 + F(3) = (F(0) + F(1) ) + ( F(1) + F(2) ) = (F(0) + F(1) ) + ( F(1) + (F(0) + F(1) ) )

중복된 값을 다시 구하게 되는 경우가 발생 따라서 n이 커짐에 따라  시간 초과나 런타임 에러가 남

 

따라서 단순히 재귀호출을 하는 대신 1, 2, 3, ..., n번째 피보나치 수를 순서대로 구하고 작은 문제의 답을 저장해서 사용

즉 DP의 핵심은 겹치는 부분 문제의 답을 저장해 재활용 한다는 것

 

▶ DP 구현방법

Top-Down 방식

큰 문제부터 문제를 쪼개가며 작은 문제로 만들고 다시 합쳐가며 원래 문제를 푸는 방식

주로 재귀함수를 사용함

let dp = [0, 1];
function solution(n) {
  if (!dp[n]) { dp[n] = solution(n - 1) + solution(n - 2);
  // 저장한 값이 없다면 재귀를 이용해 구하고 저장
  return solution[n];
}

 

Bottom-Up 방식

작은 문제들을 모아서 큰 문제를 만들어 쌓아 올려가는 방식

주로 for문을 사용함

function solution(n) {
    let dp = [0, 1]
    for(let i=3; i<=n; i++) dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

 

 

★Tip: 나머지 연산의 성질

코테를 풀다보면 언어가 표현할 수 있는 자료형의 범위를 넘어가 오버플로우가 남

문제를 잘 살펴보면 1234567으로 나눈 나머지를 리턴하는 함수등 나머지를 이용하게끔 문제가 나옴

나머지 연산의 성질을 이용하여 모든 단계에서 %연산을 사용해 오버플로우가 일어나지 않게 만들 수 있음

(a + b) % m = ((a % m) + (b % m)) % m

 

F(n) % m 
= (F(n-1) + F(n-2)) % m
= (F(n-1) % m + F(n-2) % m) % m

 

- 나머지 연산의 성질을 이용한 피보나치수 문제

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

function solution(n) {
    let arr = [0, 1]
    for(let i=2; i<=n; i++) arr[i] = (arr[i - 2] + arr[i - 1]) % 1234567
    return arr[n]
}