기억하고싶은것들

Given an m x n grid of characters board and a string word, return true ifword exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

m x n의 알파벳이 들어 있는 바둑판과 문자열이 주어진다, 만약 주어진 문자가 해당 바둑판에서 조합이 가능하다면 true를 리턴하라

단어는 인접한 셀의 조합으로 만들어진다, 인접한 셀은 가로, 세로로 인접한 셀들을 말한다.

같은 문자의 셀은 한번밖에 사용되지 않는다. ( 셀의 중복 사용 불가 )

먼저 주어진 바둑판에서 부터 문자열의 첫 번째 단어와 맞는 위치를 찾아야 한다.

찾아진 위치에서 부터 위, 아래, 오른쪽, 왼쪽을 방문하며 주어진 문자열에 존재하는 단어인지 비교한다.

비교한 단어가 같은 경우에는 해당 단어가 위치한 좌표를 방문한 노드로 표기하고 다시 위의 행위(찾아진 위치에서 부터 위, 아래, 오른쪽, 왼쪽을 방문하며 주어진 문자열에 존재하는 단어인지 비교)를 반복하여 전체 문자열을 찾는지 확인하면 된다. 

각각의 단어를 방문하는 부분을 Backtracking을 통해서 이미 방문한 위치이거나, 비교하려는 단어가 타깃이 아닌 경우에는 다시 뒤의 노드로 돌아가면 된다. 

    private boolean bt(char[][] board, int y, int x, String word, int idx, boolean[][] visited1) {

        if (idx == word.length()) { //문자열의 모든 단어를 찾은 경우 
            return true;
        }

        int i = board.length;
        int j = board[0].length;
        if (x < 0 || x >= j) { // 조건이 맞지 않는 경우
            return false;
        }
        if (y < 0 || y >= i) { // 조건이 맞지 않는 경우
            return false;
        }
        if (visited1[y][x]) { // 조건이 맞지 않는 경우
            return false;
        }

        if (word.charAt(idx) == board[y][x]) {
            visited1[y][x] = true;
            // 다음 노드들이 조건 맞는지 확인
            boolean rst = bt(board, y - 1, x, word, idx + 1, visited1) || 
                    bt(board, y + 1, x, word, idx + 1, visited1)|| 
                    bt(board, y, x - 1, word, idx + 1, visited1) || 
                    bt(board, y, x + 1, word, idx + 1, visited1);

            if (!rst) { 
                visited1[y][x] = false;
            } else {
                return true;
            }
        }

        return false;
    }

    public boolean exist(char[][] board, String word) {

        char start = word.charAt(0);
        boolean[][] visited1 = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {

                if (board[i][j] == start) {
                    if (bt(board, i, j, word, 0, visited1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

출처 : https://leetcode.com/problems/word-search/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

각각 다른 숫자가 포함된 배열이 주어진다.

가능한 모든 순열을 반환하라.

어떠한 순서로든 가능하다.

가능한 모든 순열을 반환하는 문제이다.

Backtracking을 통해서 가능한 모든 조합을 탐색해 보도록 하자.

조건이 만족해서, 결과 list에 추가되는 부분

더 탐색할 하위 노드가 남아 하위 노드로 이동하는 부분으로 코드를 구분할 수 있다.

    public void backtracking(List<List<Integer>> rst, int[] nums, List<Integer> list) {
        if (list.size() == nums.length) { // 조건이 만족 하는지 확인
            rst.add(new ArrayList<>(list));
            return;
        }

        for (int i : nums) { // 더 탐색할 하위 노드 탐색
            if (!list.contains(i)) {
                list.add(i);
                backtracking(rst, nums, list);
                list.remove(list.size() - 1);
            }
        }
    }

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

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

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

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

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/