기억하고싶은것들

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

중복되는 값이 없는 integer 배열이 주어진다.

가능한 모든 하위 집합을 반환하라.

해답에는 중복된 하위 집합을 포함하면 안 된다.

해답은 어떠한 순서도 상관없다.

가능한 모든 하위 집합을 반환하는 문제이다. 

Backtracking을 통해서 가능한 모든 조합을 탐색하고 조건이 만족하지 않는 경우는 패스해 보도록 하자.

여기서 조건이 만족하지 않는 경우는 이미 그전에 탐색에서 하위 집합에 포함된 원소이다.

    public void backtracking(List<List<Integer>> rst, ArrayList<Integer> list, int[] nums, int idx) {

        rst.add(new ArrayList<>(list));

        for (int i = idx; i < nums.length; i++) { // startIndex를 통해 이미 추가한 원소 필터링 
            list.add(nums[i]);
            backtracking(rst, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }

그럼 다음으로 해당 메서드를 호출해주는 코드를 살펴보도록 하자.

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        backtracking(rst, new ArrayList<Integer>(), nums, 0);
        return rst;
    }

출처 : https://leetcode.com/problems/subsets/

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/