기억하고싶은것들

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/

Let's play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. 'M' represents an unrevealedmine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:

1. If a mine ('M') is revealed, then the game is over - change it to 'X'.
2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

지뢰 찾기 게임을 플레이하자!

2차원의 char 배열이 주어진다.

• 'M'은 플레이어가 지뢰라고 표시해 놓은 칸
• 'E'는 눌러지지 않는 칸
• 'B'는 아무것도 없는 칸
• '숫자'는 주변에 인접한 지뢰의 개수
• 'X'는 지뢰 

다음으로, 누를 지점의 값을 input으로 입력을 받는다

그 후에 2차원 char 배열의 결과를 반환하라.

1. 만약, 'M'이 눌리면 'X'로 변환하고 게임 끝
2. 만약, 주변에 지뢰가 하나도 없는 'E'가 눌리면, 'B'로 바뀌고 해당 인접한 칸의 값을 변환
3. 만약, 주변에 지뢰가 하나 이상 있는 'E'가 눌리면, 숫자로 바꾼다.
4. 더 이상 표현할 수 있는 칸이 없을 때 2차원 배열을 반환하라

지뢰 찾기는 주변에 인접한 칸들을 방문하며 문제를 풀어가는 특징이 있다.

이러한 문제는 기존에 Graph의 Level (인접한 레벨) 별로  방문하는 BFS로 해결할 수 있다.

graph에서는 자신의 child를 방문했다면, 2차원의 배열에서는 자신에 인접한 칸들을 방문하면 된다. 

int [] dx = new int[] { 0, -1, 0, 1, 1, -1, 1, -1 };
int[] dy = new int[] { 1, 0, -1, 0, 1, -1, -1, 1 };

주변에 인접한 칸들이 방문 가능한 칸인지 판별하고, 방문이 가능하다면 queue에 담아서 순차적으로 방문을 하면 된다. 

또한, 중복적으로 방문한 칸을 들리지 않기 위해서 방문한 칸들을 기록하는 2차원의 배열을 두면 무한 반복을 막을 수 있다.

    public char[][] updateBoard(char[][] board, int[] click) {

        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        queue.offer(click);
        visited[click[0]][click[1]] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int mines = getNumberOfMines(board, x, y);

            if (mines == 0) {
                board[x][y] = 'B';

                for (int i = 0; i < 8; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    // Check adjacent cell visitable or not 
                    if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length && !visited[nx][ny]) {
                        queue.offer(new int[] { nx, ny });
                        visited[nx][ny] = true; // Check this cell visited 
                    }
                }
            } else {
                board[x][y] = (char) (mines + '0');
            }
        }

        return board;
    }

추가적으로, 해당 셀 주변에 지뢰가 몇 개 있는지 판별하는 메서드를 따로 두었다.

    private int getNumberOfMines(char[][] board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
                cnt += board[nx][ny] == 'M' ? 1 : 0;
            }
        }
        return cnt;
    }

문제 출처 :

leetcode.com/problems/minesweeper/

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

이진트리의 루트가 주어지고, 트리의 각 레벨의 가장 큰 값들을 담은 배열을 반환해라. ( 0부터 시작 )

해당 문제에서는 트리의 레벨 별로 특정한 값을 찾는 문제 이므로, 트리의 레벨별로 그래프를 순환하는 bfs를 사용하여 문제를 해결해 보자.

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> rst = new ArrayList<>();
        if (root == null) { // Check Input is Null
            return rst;
        }
        
        queue.add(root); 
        while (!queue.isEmpty()) { // Check by Tree Level
            int size = queue.size();
            int max = Integer.MIN_VALUE;

            for (int i = 0; i < size; i++) { // Only Rotate Level Node 
                TreeNode temp = queue.poll();
                if (temp.val > max) {
                    max = temp.val;
                }

                if (temp.right != null) {
                    queue.add(temp.right);
                }
                if (temp.left != null) {
                    queue.add(temp.left);
                }
            }
            rst.add(max);
        }
        return rst;
    }