[JS] 동적 계획법 (Dynamic Programming, DP)

1. Dynamic Programming 이란?

주어진 문제를 여러 개의 작은 문제로 나누어 풀고, 작은 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 방법

하위 문제를 계산한 뒤 그 해결책을 저장
→ 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.
하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍!

2. 다이내믹 프로그래밍 조건

❗️다이내믹 프로그래밍은 다음 두 가지 가정이 만족할 때 사용한다.

Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
Optimal Substructure : 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

3. 예제

🧩 피보나치수열

1. Recursion + Memoization

메모이제이션(memoization)과 재귀로 피보나치수열 문제 풀기
⇒ Top-down 방식

function fibMemo(n, memo = []) {
    if(mamo[n] !== undefined) return memo[n];

    if(n <= 2) return 1;

    mamo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

2. Iteration + Tabulation

Tabulation
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 리스트(도표)에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법
⇒ Bottom-up 방식

function fibTab(n) {
    if(n <= 2) return 1;
    // n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    let fibNum = [0, 1, 1];

    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
    }

    return fibNum[n];
}

🧩 2 × 1 타일링

🌟 문제 개요

세로 길이 2, 가로 길이 n인 2 x n 보드가 있다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 한다.

입력값 : n ← number 타입은 1 이상의 정수
출력값 : number 타입

🔥 풀이

1. 먼저 입출력 예시를 살펴보자.

2. n = 4인 경우를 생각해보자.

a) 타일을 놓는 방법은 가장 왼쪽부터 세로로 놓거나, 가로로 놓는 것으로 시작한다. 이때 가로로 놓게 되면, 그 바로 아래는 가로로 놓을 수밖에 없다.

b) 위와 같이 시작을 하면 그다음에 채워야 될 나머지 칸의 수는 다음과 같다.

c) 그런데 우리는 이미 나머지 칸을 채우는 경우의 수를 구했다! 바로 각각 n = 3일 때의 경우의 수와, n = 2일 때의 경우의 수이다.

d) 즉, tiling(4) = tiling(3) + tiling(2)인 것이다!

3. 2번을 토대로 base case와 recursive case를 나눠보자. O(2^n)

function tiling(n) {
    //base case
    //-> n이 0, 1, 2 일때 출력값은 순서대로 0, 1, 2 이다.
    if(n <= 2) return n;

    //recursive case
    return tiling(n - 1) + tiling(n - 2);
}

4. 많이 본 코드이지 않은가? 맞다. 탈출 코드만 살짝 다를 뿐 피보나치와 코드와 같다!

5. 다만, 이 경우는 시간 복잡도가 O(2^n) 이기 때문에 1) 메모이제이션 이나, 2) bottom-up 방법 (1번부터 계산해 n에 도달하는 방법)을 써야 효율적이다. ⇒ O(n)

6. 메모이제이션을 활용한 방법 (dynamic with memoization) O(n)

function tiling(n) {
    const memo = [0, 1, 2];

    const aux = (n) => {
        if(memo[n] !== undefined) return memo[n];
        memo[n] = aux(n-1) + aux(n-2);
        return memo[n];
    }
    return aux();
}

7. bottom-up 방법 O(n) 추천

6번의 코드를 보면 이런 의문이 생긴다.
→ 결국 memo 배열에는 1부터 n까지의 경우에 수가 저장되는 것이 아닌가? 그렇다면 굳이 복잡하게 재귀 돌릴 필요 없이 1부터 n까지의 경우의 수를 차례대로 찾아 저장해주면 되겠네.
→ 맞다. 굳이 재귀 필요 없이 for문 돌려서 n이 될 때까지 하나씩 값을 찾아나가면 된다.

function tiling(n) {
    const memo = [0, 1, 2];

    for(let i = 3; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }
    //어짜피 n <= 2 라면 for 문을 거치지 않으니 
    //따로 if(n<=2) return memo[n]; 이렇게 조건 쓸 필요 없음
    return memo[n];
}

✨ 타일링 문제 연습하기

728x90