기억하고싶은것들

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

integer 배열인 coins을 입력값으로 받고, 해당 배열에 들어있는 값들은 각각 다른 코인의 액수이다.

그리고 액수의 총합을 입력값으로 받는다.

총합의 금액을 만들 수 있는 최소한 작은 코인 개수를 반환하여라.

만약 총합의 값을 주어진 coins 배열로 만들 수 없다면 -1을 반환해라.

coins 배열에 들어있는 값의 코인의 갯수는 무한하다고 생각하면 된다.

이 문제는 주어진 문제를 sub 문제로 쪼개서 해결할 수 있다. 

예를 들어 입력 받은 총합이 n이고 [ 2 , 3, 5 ] coin 배열을 입력받았다고 하면 

f( n ) = Min( f(n-5), f(n-3), f(n-2) ) + 1 로 쪼개서 생각할 수 있다. 

    private int dp(int[] coins, int remains, int[] rst) {

        if (remains < 0)
            return -1;
        if (remains == 0)
            return 0;
        if (rst[remains - 1] != 0)
            return rst[remains - 1];

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int temp = dp(coins, remains - coin, rst); // make sub problem 
            if (temp >= 0 && temp < min) {
                min = temp + 1; // add 1 -> add self count
            }
        }
        rst[remains - 1] = min == Integer.MAX_VALUE ? -1 : min;
        return rst[remains - 1];
    }

그럼 다음으로 해당 코드를 호출하는 부분을 살펴 보자.

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }

        int[] rst = new int[coins.length];
        return dp(coins, amount, rst);
    }

출처 : https://leetcode.com/problems/coin-change/

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

int 배열을 입력값으로 받는다. cost[i]는 i번째 계단을 오르기 위한 금액이다.

해당 금액을 지불하면 해당 계단으로부터 1 또는 2개의 계단을 오를 수 있다. 

시작점은 0 또는 1번째 계단이 가능하다.

정상까지 도달하기 위한 최소한의 금액을 반환해라. 

해당 문제에서는 Top에 도달하기 위한 최소한의 금액이므로

반환되는 값은 Math.min( f(n-1), f(n-2)) 로 나타낼 수 있다. 

그리고, 방문한 계단에서의 최소로 지불해야 하는 값은 Math.min ( t[n-1], t[n-2] ) +cost [n]이다. 

해당 내역을 코드로 나타내면 아래와 같다.

    private int dp(int[] cost, int[] t, int len) {
        if (len == 0) {
            return t[0];
        }
        if (len == 1) {
            return t[1];
        }
        if (t[len] != 0) {
            return t[len];
        }

        int n1 = dp(cost, t, len - 1);
        int n2 = dp(cost, t, len - 2);
        t[len] = Math.min(n1, n2) + cost[len];

        return t[len];
    }

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] t = new int[len + 1];
        t[0] = cost[0];
        t[1] = cost[1];
        return Math.min(dp(cost, t, len - 1), dp(cost, t, len - 2));
    }

위의 방법은 DP문제를 Top-Down방식으로 해결하는 방법이고, 다음으로 Bottom-Up으로 해결하는 방법을 알아보자.

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] t = new int[len + 1];
        t[0] = cost[0];
        t[1] = cost[1];

        for (int i = 2; i < len; i++) {
        t[i] = Math.min(t[i - 1], t[i - 2]) + cost[i];
        }
        return Math.min(t[len-1], t[len-2]);
    }

문제 출처 :

leetcode.com/problems/min-cost-climbing-stairs/

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

계단을 올라보자. input으로 n을 받고 해당 값은 맨 위로 가기 위한 스텝의 개수이다.

각각 1 또는 2개의 계단만 오를 수 있다. 몇가지 방법으로 맨 위로 올라갈 수 있는지 구해라

해당 문제에서 n까지 도달하기 위한 방법은, 유저가 올라 갈 수 있는 계단의 개수는 1 또는 2 이므로,

f(n) = f(n-1) + fn-2) 로 표현될 수 있다.

이러한 형태의 문제는 dynamic programming을 통해서 해결될 수 있다.

추가적으로, 방문 했던 위치는 해당 위치로 올 수 있는 개수를 따로 저장해 두고 또 방문했을 때 재 계산을 하지 않고 저장된 값을 불러서 사용하면 된다. 

먼저, 위의 식 처럼 해결할 수 있는 Top-Down 방식을 보자. 

    private int df(int n, int[] t) {
        if (n == 1) {
            return 1;
        }
        if (n == 0) {
            return 1;
        }
        if (t[n] != 0) {
            return t[n];
        }
        int n1 = df(n - 1, t);
        int n2 = df(n - 2, t);
        t[n] = n2 + n1;
        return n1 + n2;
    }

그럼 해당 코드를 호출하는 부분을 보자

    public int climbStairs(int n) {
        int[] t = new int[n + 1];
        t[0] = 1;
        t[1] = 1;
        int rst = df(n, t);
        return rst;
    }

그럼, 다음으로 Bottom-Up 방식을 보자

    public int climbStairs(int n) {
        int[] t = new int[n];
        t[0] = 1;
        t[1] = 1;
        for (int i=2; i<n; i++) {
        t[i] = t[i-1] + t[i-2];
        }
        return t[n-1];
    }

문제 출처 :

leetcode.com/problems/climbing-stairs/

• dynamic programming에 대한 개념 설명
• dynamic programming을 적용하기 위한 조건 
• dynamic programming의 특징
• dynamic programming의 접근법

Dynamic Programming은 보통 DP라고 줄여 쓰는것을 볼 수 있다.

이름만 봤을때는 뭔가 엄청나게 대단하고 복잡한 알고리즘일것 같은데, 실제 해당 내역을 공부하면 이름이랑 뭔가 맞지 않는다는게 느껴진다.

보통 인터넷을 찾아봤을때, Dynamic Programming의 정의는 아래와 같다.

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 

개념은 그렇게 어렵지 않고, 받아들일수 있다.

그러면, 이러한 DP를 어떠한 상황에 적용할 수 있는지 알아보자.

가장 대표적인 예시로는 피보나치 수열이 있다. 

간단하게 피보나치 수열에 대한 정의를 보면 아래와 같다.

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이다.
처음 여섯 항은 각각 (0), 1, 1, 2, 3, 5, 8이다.
편의상 0번째 항을 0으로 두기도 한다.

DP라는 개념이 등장하기 전에는 대부분 해당 문제를 재귀적으로 해결하였다. 

아래는 예시 코드이다.

int fibonacci(int n) {
    if (n<=2)
      return 1;
    else
      return fibonacci(n-1) + fibonacci(n-2);
}

하지만 해당 방법으로 문제를 풀게 된다면, 반복되는 값들을 반복적으로 구한다는 문제가 있다. 

아래의 그림에서 트리에서 반복적으로 fib(5) 이하의 노드들을 계산하게 된다. 

한번만 계산해 놓고 해당 값을 다시 만나면 이전에 계산해 놓은 값을 가져다가 쓰기만 하면 계산 시간을 효율적으로 줄일 수 있게된다.

이러한 점을 반영하여서 DP의 적용 조건과 특징을 살펴보자.

DP의 적용 조건

• 부분문제 반복 ( Overlapping Subproblem )
  • 피보나치 수열과 같이  f(n) = f(n-1) + f(n-2) 와 같이 
    어떠한 문제가 여러개의 부분 문제로 쪼개 질 수 있고, 해당 부분 문제가 또 다시  재귀적으로 부분 문제로 쪼개질 수 있는 것
• 최적 부분구조 ( Optimal Substructure )
  • 피보나치 수열과 같이 f(n) = f(n-1) + f(n-2)와 같이
    작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있는 것

( 해당 조건은 뭔가 전문적인 단어들이 들어가서 어렵게 표현된 것처럼 보이는데, DP의 핵심은 "복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 것" 이다. 이 핵심을 풀어서 전문적으로 설명해 놓은게 조건이라고 생각하자.)

DP의 특징으로는 Memorization이다.

반복적으로 등장하는 계산을 기억해 두었다가, 해당 계산이 다시 등장할때, 재계산을 하지 않고 기억해 두었던 값을 가져다 사용하는 것이다. 

위의 피보나치 수열 그래프에서 반복적으로 등장하는 fibo(5), fibo(4) ... 값들을 기억하고 사용하면 된다. 

접근법

이제 개념적인 부분과 특징을 알아 보았으니 실제로 문제를 만났을때 어떻게 접근해야하는지에 대해서 알아보도록 하자.

크게 2가지 방법이 있다. 

• Top-Down
  • 재귀로 해결 하는 대부분의 방식
  • 큰 문제를 해결 하기 위해 작은 문제로 나누고, 해당 값이 아직 계산되지 않은 경우 더 작은 값으로 나누며 값을 찾아가는 방식
  • ( 예시는 위의 fibonacci 코드 )
• Botton-up
  • 작은 문제에서 부터 하나씩, 하나씩 값을 찾아가는 방식
  • ( 예시는 아리의 코드 )

int fibonacci (int n) {
  fibodata[0] = 0;
  fiboData[1] = 1;
  for (int i=2; i<=n; i++) {
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  }
  return fiboData[n];
}