DynamicProgramming, DP

[dlehdanakf]

개요

• 재귀호출 알고리즘을 작성할 때 이전에 호출하여 연산했던 결과값을 저장하여 연산량을 획기적으로 줄어들게 만드는 프로그래밍 방법
• 주로 HashMap 을 사용하여 구현하는듯 하다. 어차피 JS 에선 Object를 사용하면 끝이다.

예제

피보나치 수열 구하기

• 피보나치 수열에서 i 번째 수열이란, N_i = N_(i-1) + N_(i-2) 이다.
• N₀ = 0, N₁ = 1, N₂ = 1, N₃ = 2, N₄ = 3
• 해결하는 방법은 N 번째를 구하기 위해 앞서 계속해서 이전 값들을 구해줘야하는데 이 때 이전에 연산한 값들을 캐싱하며 나아가면 되는 것 이다.

const fibonacci = i => {
    if(i === 0) return 0;
    if(i === 1) return 1;
    return fibonacci(i - 1) + fibonacci(i - 2);
};

• 위 방법은 DP를 사용하지 않은 상태로 재귀호출을 할 때마다 같은 값을 반복해서 연산해야한다.
• 캐싱하는 코드를 넣으면 아래와 같아진다.

const DP = { };
const fibonacciDP = i => {
    if(i === 0) return 0;
    if(i === 1) return 1;
    if(DP[i] !== undefined) return DP[i];
    return DP[i] = fibonacciDP(i - 1) + fibonacciDP(i - 2);
};

n개의 계단을 오를 때 한 계단 씩, 또는 두 계단 씩, 최대 세 계단 씩 오를 수 있다.
계단을 오르는데 총 몇 가지 방법이 있는가?

• 피보나치와는 다르게 뒤에서 부터 생각을 해보자.
• n 번째 계단을 오른다는건 n - 1 계단에서 한 칸 올라왔거나, n - 2 계단에서 두 칸 올라왔거나, 마찬가지로 n - 3 에서 세 칸 올라왔을 것이다.
• 따라서 n 번째 계단에 오르는 경우의 수는 위 세 가지 경우의 수를 모두 합한 수가 된다.
• N_i = N_(i-1) + N_(i-2) + N_(i-3)
• 피보나치와 마찬가지로 재귀적으로 구하면 된다.

const calcCount = n => {
    if(n < 0) {
        return 0;
    } else if(n === 0) {
        return 1;
    } else {
        return calcCount(n - 1) + calcCount(n - 2) + calcCount(n - 3);
    }
};

• DP를 사용한다면 아래와 같아진다. 무진장 빨라진다.

const DP = { 0: 1 };
const calcCountDP = n => {
    if(DP[n] !== undefined) {
        return DP[n];
    }

    if(n < 0) {
        return 0;
    } else {
        return DP[n] = calcCountDP(n - 1) + calcCountDP(n - 2) + calcCountDP(n - 3);
    }
};

[dlehdanakf]

프로그래머스 문제풀이

거스름돈

문제

• 문제 바로가기
• 5원을 거슬러줘야 하는데 잔고에는 1, 2, 5원짜리 동전만 존재한다. 총 몇 가지의 잔돈 조합으로 5원을 거슬러 줄 수 있겠는가?
• 예를 들어, 5원을 거슬러주기 위해서는 1원을 다섯 개 주던가, 1원 한 개, 2원 두 개를 거슬러줄 수 있다. 총 경우의 수는?

푸는 방법

• 주어진 동전을 무제한으로 활용할 수 있으므로 1원 부터 2원, 5원까지 차근차근 활용할 수 있는 경우의 수를 따져 나아가보자. 긴장할 필요 없다 ㅋ
• DP 배열을 선언하여 n 개의 원소를 만들고 0으로 초기화한다. const DP = new Array(n + 1).fill(0); 1 부터 편하게 가기 위해 n+1개 선언한다.
• 1원, 2원, 5원짜리 동전을 각각 한 개씩 써서 만들 수 있는 액수는 어떻게 되는가? 당연하게도 1원, 2원, 5원이다. 그러면 DP 배열에 각각 1 씩 넣어주자.

1	2	3	4	5
1	1	0	0	1

• 한 개 씩 사용했을 때 액수이므로 3원, 4원은 만들 수 없으니까 경우의 수는 0인 상태다.
• 이제 동적프로그래밍 방법론 측면으로 접근해보자. 1원짜리 동전에 대해 경우의 수를 1 ~ 5 까지 모두 계산을 해보는거다.
• 액수 2원을 만드는 방법 중에는 1원에서 1원짜리 동전 한 개를 추가 사용하여 만드는 방법이 있다.
• 액수 3월을 만드는 방법 중에는 2원에서 1원짜리 동잔 한 개를 추가 사용하여 만드는 방법이 있다...
• 그렇다면 식은 이렇게 된다. DP[2] += DP[1], DP[3] += DP[2], DP[4] += DP[3], DP[5] += DP[4]

1	2	3	4	5
1	2	1	1	2

• 1원짜리 동전을 사용하여 경우의 수를 모두 더하니 3원, 4원을 만드는 방법이 생긴다. 1원짜리 3개로 3원 만들기!
• 2원짜리 동전에 대해서도 경우의 수를 따져보자. 액수 3원을 만드는 방법 중에는 1원에서 2원짜리 동전 한 개를 추가 사용하여 만드는 방법이 있다. DP[3] += DP[1]

1	2	3	4	5
1	2	2	3	4

• 5원을 만드는게 목표니까 5원짜리 동전을 두 개 이상 사용할 일은 없다.
• 최종적으로 5원을 만드는 방법의 가짓수는 4 가 된다.
• DP[a] += DP[b] 형태의 식을 사용하여 문제를 해결해 나아가는데 a 와 b의 관계는 b - a = n원짜리 동전 으로 볼 수 있다.
• 따라서 최종적으로 코드를 작성해보면 아래와 같이 나타나게된다. 대박 심플하다.

function solution(n, money) {
    const DP = new Array(n + 1).fill(0);
    money.forEach(i => {
        DP[i] += 1;
        for(let j = i + 1; j <= n; j++) {
            DP[j] += DP[j - i];
        }
    });

    return DP[n];
}

[dlehdanakf]

프로그래머스 문제풀이

멀리뛰기

문제

• 문제 바로가기
• 등장인물은 계단을 한번에 한 칸, 또는 두 칸씩 올라갈 수 있다.
• 3번째 계단을 오르는 방법은 1 칸씩 세 번 오르는 방법과, 2 칸 + 1 칸, 1 칸 + 2 칸으로 오르는 방법 총 세 가지이고,
• 4번째 계단을 오르는 방법은 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2 으로 총 다섯 가지이다.
• 이와 같이 n 개의 계단을 오를 때 총 몇 가지의 방법으로 오를 수 있는가?

푸는 방법

• n 번째 계단을 오르는 방법은 n - 1 번째 계단에서 한 칸 올라왔거나, n - 2 번째 계단에서 두 칸 올라오는 방법이 있다.
• N_i = N_{(i - 1)} + N_{(i - 2)}
• 위와 같이 점화식을 만들고 재귀적으로 호출해 나아가면 된다.
• 하지만 무작정 재귀호출을 사용하면 스택오버플로우가 발생할 것이다. 따라서 적절히 DP 소스를 뿌려주어야한다.
• 푸는 방법은 위 이슈 본문과 동일하다.

function solution(n) {
    const DP = new Array(n + 1).fill(0);
    const up = n => {
        if(n === 1 || n === 0) return 1;
        if(n < 0) return 0;

        if(DP[n]) return DP[n];
        return DP[n] = (up(n - 1) + up(n - 2)) % 1234567;
    };

    return up(n);
}

거스름돈 문제와 무엇이 다른가?

• 똑같이 DP를 사용하는 문제지만, 거스름돈 코드에서 money 변수를 그대로 [1.2]로 만들어 멀리뛰기 문제로 대입시켜도 문제를 해결할 수 없다.
• 그 이유는 문제에서 제시하는 조건이 다르기 때문인데, 거스름돈은 순서를 고려하지 않은 경우의 수 지만, 멀리뛰기는 순서까지 고려하여 제한조건을 제시했기 때문이다.
• 예를 들어, 거스름돈에서 5원을 거슬러줄 때 1 + 2 + 2 원을 하던, 2 + 1 + 2 원을 하던 똑같이 1개의 1원과 2개의 2원을 사용하는 같은 경우의 수로 보지만, 멀리뛰기는 다른 경우의 수로 본다.
• 따라서 똑같이 1차원 DP 배열을 사용하더라도 다른 값이 담기는 것 이다.
• 이런 문제를 구분하는 방법은 표면적으로는 순서를 중시하는 문장이 있는가 이고, 제시되는 가짓수가 유동적인가 고정적인가로 구분할 수 있을 것 같다.
• 거스름돈은 동전이 구체적으로 제시되지 않고 배열에 담겨 넘어왔지만 멀리뛰기는 1칸, 2칸으로 고정되어 제시되었다.
• 어려운 문제면 아마 멀리뛰기 문제에서 1칸, 2칸도 배열로 넘어왔을 것 같기도 하다. 다음에 배열로 담아서도 풀어보자
• 아무튼, 지나온 DP 배열 속 원소들이 순서를 따져 본 경우의 수인지, 아닌지도 판단해야한다.

function solution(n) {
    const jump = [1,2];
    const DP = new Array(n + 1).fill(0);
    const up = n => {
        if(n === 1 || n === 0) return 1;
        if(n < 0) return 0;

        if(DP[n]) return DP[n];
        return DP[n] = jump.reduce((acc, cur) => acc + up(n - cur), 0) % 1234567;
    };

    return up(n);
}

• 한번에 오를 수 있는 계단이 만약에 jump 배열로 넘어온다고 가정한다면 위와 같은 코드로 문제를 해결할 수 있다.

[dlehdanakf]

피보나치 수열

• 프로그래머스 문제 바로가기
• 희한하게 재귀함수로 풀었을 때 런타임 에러가 발생하며 통과되지 않는 문제가 있었다.
• 아마 메소드 스택이 지나치게 많이 쌓이면서 스택오버플로우 문제가 있는듯 하다.
• 기존 재귀함수로 풀던 문제를 루프문으로 바꿔 풀었더니 무난하게 패쓰!
• 모든 재귀함수는 루프문으로 표현할 수 있다.

function solution(n) {
    if(n === 1) return 1;

    const DP = new Array(n + 1).fill(0);
    DP[0] = 0, DP[1] = 1;
    for(let i = 2; i <= n; i++) {
        DP[i] = (DP[i - 1] + DP[i - 2]) % 1234567;
    }

    return DP[n];
}