Backtracking 문제

숲사람·2022년 10월 3일

Backtracking DP recursion

멘타트 컬렉션

목록 보기

6/13

207. Course Schedule

문제

[강의, 사전수강필요 강의] 의 강좌 정보가 배열로 주어질때, 주어진 강좌를 모두 수강할 수 있는지 없는지 판단하라.

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Input: numCourses = 4, prerequisites = [[1,0],[2,1],[2,0],[3,2]]
Output: true
Input: numCourses = 2, prerequisites = [[0,2],[2,1],[1,0],[3,2]]
Output: false

아이디어

adjacent[사전수강강의] 에 해당하는 강의 리스트를 자료구조를 생성하면 , 방향성 그래프 자료구조가 된다.
만약 그래프에 사이클이 존재한다면, 모든 강좌를 수강할 수 가 없다는 뜻이다.
따라서 해당 그래프의 사이클의 존재유무를 찾는게 이 문제가 요구하는것이다(해설참고함)

해결

is_cycle() 함수의 visited[] 값을 3가지로 정한게 참고한 답안. (이해하기가 쉽지 않았음.) 단순히 visited 체크된 값을 방문했을때 false를 해버리면 True도 false가 되어버린다(예시: TBD). 따라서 백트래킹으로 탐색할때, 이미 방문을 마친(이미 is_cycle() false 라서 사이클이 아님을 검증한) 노드는 2로 체크하여 굳이 다시 방문하지 않는다.

class Solution {
    vector<vector<int>> adj;
    bool is_cycle(vector<int> &vis, int cur) {
        /*
        vis 0: not visited
        vis 1: visited
        vis 2: no need to visit
        */
        if (vis[cur] == 1)
            return true;
        if (vis[cur] == 0) {
            vis[cur] = 1;
            for (int i = 0; i < adj[cur].size(); i++) {
                if (is_cycle(vis, adj[cur][i]))
                    return true;
            }
        }
        vis[cur] = 2;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        adj = vector<vector<int>>(numCourses);
        vector<int> visites(numCourses, 0);
        
        for (auto it: prerequisites) {
            adj[it[1]].push_back(it[0]);
        }
        // 각 강좌들이 모두 연결되어있지 않을수도있기에, 모든 값을 순회한다.
        for (int i = 0; i < numCourses; i++) {
            if (is_cycle(visites, i))
                return false;
        }
        return true;
    }
};

279. Perfect Squares

문제

어떤 수를 1, 4, 9, 16과 같은 완전제곱수(Perfect Square)의 합으로 나타낼수 있을때, 해당 수를 표현할 수 있는 최소한의 완전제곱수의 갯수는 몇개 인가?

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

해결 아이디어

f(n) = min(f(n - 1^2), ~ , f(n - i^2)) + 1 이라는 점화식 관계를 구할 수 있음. 단 i 는 i*i <= n 까지

해결

backtracking + memoization으로 해결

class Solution {
    int mem[10001];
public:
    int numSquares(int n) {
        int ret = INT_MAX;
        if (mem[n])
            return mem[n];
        if (n == 0)
            return 0;
        
        for (int i = 1; i*i <= n; i++) {
            if (n - (i*i) < 0)
                continue;
            ret = min(ret, numSquares(n - (i*i)) + 1);
        }
        mem[n] = ret;
        return ret;
    }
};

131. Palindrome Partitioning

문제

주어진 문자열을 파티셔닝 한다고 할때, 나눈 sub문자열이 모두 palindrome인 경우를 모두 출력하라.

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

해결

백트래킹, for문을 돌며 cur 부터 i길이만큼 문자를 확인하고 그 뒤 문자열은 재귀적으로 체크. 추가로 s.substr(시작 인덱스, 길이) 두번재 인자가 길이임 주의.

class Solution {
    vector<vector<string>> ret;
    vector<string> tmp;
    
    bool is_palindrome(string s) {
        int ssize = s.length();
        for (int i = 0; i < ssize / 2; i++) {
            if (s[i] != s[ssize - i - 1])
                return false;
        }
        return true;
    }
    void recur(string s, int cur) {
        if (cur >= s.length()) {
            ret.push_back(tmp);
            return;
        }
        
        for (int i = cur; i < s.length(); i++) {
            string tgt = s.substr(cur, i-cur+1);
            if (!is_palindrome(tgt))
                continue;
            tmp.push_back(tgt);
            recur(s, i+1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        recur(s, 0);
        return ret;
    }
};

1155. Number of Dice Rolls With Target Sum

문제

k개의 면을 가진 주사위 n개가 존재한다. 이 주사위 n개를 던졌을때, 그 합이 target값이 나오는 경우의 수를 구하라. 결과 값은 % 1000000007 으로 모듈러 연산해서 리턴하라(오버플로우 발생예방)

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

각각의 주사위 값은 유니크하다. (1,6) (6,1)은 독립적인 경우의 수다.

Back Tracking (Brute-force 방법)

먼저 생각해 볼 수 있는 방법은, Back Tracking으로 완전탐색 하는것이다. n을 하나씩 줄이면서 다음 재귀함수를 호추하고 인자로 현재 sum을 넘긴다. 그리고 sum==target일때, 1을 리턴한다. 결과는 TLE가 발생한다.

// n: number of k-faces dice
class Solution {
    vector<vector<int>> memo;
    int total;
    int bt(int n, int face, int sum, int tgt) { 
        /* base case */
        if (n == 0) {
            if (sum == tgt) //found
                return 1;
            return 0;
        }

        int way = 0;
        for (int i = 1; i <= face; i++) {
            way = (way + bt(n - 1, face, sum + i, tgt)) % 1000000007;
        }
        return way;
    }
public:
    int numRollsToTarget(int n, int k, int target) {
        memo = vector<vector<int>>(n + 1, vector<int>(target + 1, -1));
        return bt(n, k, 0, target);
    }
};

해결 DP (top-down with memoization)

[주사위 번호] 현재까지 합 이라고 해보자. 예시로 n:3 k:3 target:7이 주어진다. 이를 그림으로 풀어가보면 아래와 같이 (주사위번호, 현재까지 합) 에 따른 중복된 재귀호출을 발견할 수 있다. 따라서 이부분은 memoization을 한다.

                       [0]1   ...
             +1          +2         +3
        [1]2           [1]3          [1]4
   +1   +2  +3
[2]3 [2]4 [2]5    [2]4 [2]5 [2]6     ...

위의 Back Tracking 구조에서 memo[] 처리 부분만 추가한다.

// n: number of k-faces dice
class Solution {
    vector<vector<int>> memo;
    int total;
    int bt(int n, int face, int sum, int tgt) {
        /* base case */
        if (sum > tgt) // sum이 memo[]배열을 초과할경우 에러 예방
            return 0;
        if (n == 0) {
            if (sum == tgt) //found
                return 1;
            return 0;
        }
        if (memo[n][sum] != -1)
            return memo[n][sum];
            
        int way = 0;
        for (int i = 1; i <= face; i++) {
            // bt() with unique (n, sum) is calculated repeatedly. and it return the same result, so memoize it.
            way = (way + bt(n - 1, face, sum + i, tgt)) % 1000000007;
        }
        memo[n][sum] = way;
        return memo[n][sum];
    }
public:
    int numRollsToTarget(int n, int k, int target) {
        memo = vector<vector<int>>(n + 1, vector<int>(target + 1, -1));
        return bt(n, k, 0, target);
    }
};

78. Subsets

문제

배열에 주어진 숫자로 만들 수 있는 모든 조합을 리턴하라.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

해결

0 개부터 n(배열갯수)개 까지 각각의 수를 선택할수 있는 조합(Combination)을 백트래킹을 통해 구한다.

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
    int nsize;
    
    void back_tracking(vector<int> nums, int cur, int tgt) {
        if (tgt < 0)
            return;
        if (tgt == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = cur; i < nsize; i++) {
            tmp.push_back(nums[i]);
            back_tracking(nums, i + 1, tgt - 1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        nsize = nums.size();
        for (int i = 0; i <= nsize; i++) {
            back_tracking(nums, 0, i);
        }
        return ret;
    }
};

39. Combination Sum

문제

주어진 값들을 더해서(중복선택 가능) target이 되는 조합을 구하라. 결과 조합이 중복될 수 없다. ([2,2,3]과 [3,2,2]는 동일)

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

해결

백트래킹 문제. 잘 몰랐던것.

tmp임시 벡터를 어떻게 선언해야하는지
재귀 호출 직전에 현재값을 push_back()하고, 호출이 끝나면 pop_back()을 해야함.
결과 조합이 중복되지 않기 위해서는 i를 curr부터 시작하야함.
아래와같이 하면 위 예제의 결과는[[2,2,3],[2,3,2],[3,2,2],[7]]이 나오게된다.
```
for (int i = 0; i < candidates.size(); i++)
```

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
    void back_tracking(vector<int> &candidates, int target, int curr)
    {
        if (target < 0) return;
        if (target == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = curr; i < candidates.size(); i++) {
            tmp.push_back(candidates[i]);
            back_tracking(candidates, target - candidates[i], i);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        back_tracking(candidates, target, 0);
        return ret;
    }
};

46. Permutations

문제

주어진 배열 요소의 모든 순열(순서대로 나열하는 경우의수)을 출력. (모든 값은 unique함이 보장)

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

풀이 - backtracking

nsize만큼의 배열을 모두 backtracking하는데, 만약 tmp배열에 이미 존재하면 skip. (이를 위해 tmp배열을 O(n)만큼 탐색해야함)

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
public:
    void back_tracking(vector<int> nums, int size) {
        if (size < 0)
            return;
        if (size == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // if nums[i] is already exist in nums[i]; then continue
            bool cont = false;
            for (int j = 0; j < tmp.size(); j++) { // O(n)
                if (tmp[j] == nums[i]) {
                    cont = true;
                    break;
                }
            }
            if (cont == true)
                continue;
            tmp.push_back(nums[i]);
            back_tracking(nums, size - 1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int nsize = nums.size();
        back_tracking(nums, nsize);
        return ret;
    }
};

풀이 - backtracking 개선

해시테이블을 사용하여 O(n)동안 tmp를 탐색했던 시간복잡도를 O(1)로 줄임. 대박적!!
주어진 문제의 입력의 배열크기가 최대 6이라서 실제 실행시간의 큰 이득은 없는데 만약 입력이 엄청 커지면 드라마틱하게 성능 향상이 있을것임.

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
    unordered_map<int, bool> tmp_map;
public:
    void back_tracking(vector<int> nums, int size) {
        if (size < 0)
            return;
        if (size == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // if nums[i] is already exist in nums[i]; then continue
            if (tmp_map[nums[i]] == true) // O(1) Wow!
                continue;
            
            tmp.push_back(nums[i]);
            tmp_map[nums[i]] = true;
            back_tracking(nums, size - 1);
            tmp_map[nums[i]] = false;
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int nsize = nums.size();
        back_tracking(nums, nsize);
        return ret;
    }
};

풀이

정확히 std::next_permutation 사용. (근데 이걸로 풀고 끝내면 공부 하나도 안된다. )

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;   
        std::sort(nums.begin(), nums.end());
        do {
            ret.push_back(nums);   
        } while(std::next_permutation(nums.begin(), nums.end()));
        return ret;
    }
};

22. Generate Parentheses

문제

n이 주어지면 n쌍의 올바른 괄호형태의 모든 경우의수를 리턴하라.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

해결 O(N!)

괄호가 나열되는 모든 경우의 수 중에서 정상적인 괄호만 추출하기. parans 문자열로 next_permutation을 사용하려면 parans가 초기에 정렬된 상태여야 하기 때문에 "((()))" 가 되어야한다.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        std::string parans;
        
        parans.append(n, '(');
        parans.append(n, ')');
        
        do {
            if (is_well_formed(parans)) {
                //cout << parans << " ";
                ret.push_back(parans);
            }
        } while (std::next_permutation(parans.begin(), parans.end()));
        
        return ret;
    }
    
    bool is_well_formed(string s) {
        std::stack<char> stk;
        for (char c: s) {
            if (c == '(')
                stk.push('(');
            else if (c == ')')
                if (!stk.empty())
                    stk.pop();
        }
        if (stk.empty())
            return true;    
        else
            return false;
    }
};

해결 O(2^N)

backtracking 으로 더 효율적으로 해결. 좌우 괄호갯수가 각각 n이 될때까지 str 뒤에 괄호를 합쳐서 모든 경우의 수 탐색.

괄호를 오른쪽에 덧 붙이는 것만으로도 모든 경우의 수를 탐색 할 수 있다. (처음에 문자열 왼쪽 오른쪽 모두 덧붙이는 완전탐색을 해야하나? 고민했었음. 한쪽만 해도 됨)

(이부분이 이 코드의 핵심일듯!)

        if (nr_right < nr_left) 
            recur(ret, nr_left, nr_right + 1, str + ")", n);

오른쪽에 )를 덧붙일수 있는 조건은, 덧 붙이기 전 항상 왼쪽의 (갯수가 더 많아야한다. 반면 (를 를 덧붙이기 위한 조건은 n개 이하 이기만 하면된다.

시간복잡도는 한 함수에서 재귀함수가 두번호출되었으니 O(2^N)이다.

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<string> generateParenthesis(int n) {
        std::vector<string> ret;
        std::string str;
        recur(ret, 0, 0, "", n);
        return ret;
    }
    
    void recur(std::vector<string> &ret, int nr_left, int nr_right, std::string str, int n) {
        /* base case */
        if (nr_left == n && nr_right == n) {
            ret.push_back(str);
            return;
        }
        
        /* recursion */
        if (nr_left < n)
            recur(ret, nr_left + 1, nr_right, str + "(", n);
        if (nr_right < nr_left) 
            /* if you want to append ")" on right side, it is required that number of "(" is less than ")" */
            recur(ret, nr_left, nr_right + 1, str + ")", n);
    }
};

str.append() 를 쓰면 안되는 이유 -> str 변수값이 바뀜.
처음에 str.append("(") 를 통해 합쳐서 인자로 전달했는데, 자꾸 오답이 나와서 디버깅을 한참했다. 그 이유는 해당 함수 내에서 str이 두번쓰이기 때문이다. 첫번째 recur()함수에서 str 에 (를 append해서 전달하면 그 다음 recur()함수에서 이미 append되어버린 문자열을 가지고 전달을 한다. str 변수가 바뀌지 않도록 str + "(" 로 전달해야한다. 어이없는 실수!

        if (nr_left < n)
            recur(ret, nr_left + 1, nr_right, str.append("("), n);
        if (nr_right < nr_left) 
            recur(ret, nr_left, nr_right + 1, str.append(")"), n);

17. Letter Combinations of a Phone Number

문제

주어진 숫자가 아래 휴대폰 키패드에서 어떤 문자의 조합이 될 수 있는지 출력하기. (주어진 숫자 자릿수는 0이상 4이하)

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

해결

Backtracking 문제. 우선 각 키패드 숫자를 key로 하고 사용가능한 문자열을 value로 하는 해시 table생성 하고. 백트래킹 방식으로 모든 가능성의 조합문자를 만들어냄. 아래 tmp 배열을 미리 생성하고 재귀적으로 호출할때 현재 idx에 현재 테이블 문자를 저장하고 다음 재귀함수에 보냄.
char **result 를 동적 할당하고, 마지막 base case에서 tmp를 strcpy함. 더블포인터만 할당했기 때문에 그 안의 char * 타입 값도 미리 동적할당 해야함.

Backtracking 참고할만한 영상 : https://www.youtube.com/watch?v=Ar40zcPoKEI

char table[8][5] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int reslen;

int hash(char c)
{
    return c - '2';
}

void back_tracking(char *d, int idx, int dsize, char **res, char *tmp)
{
    /* Base Case */
    if (idx >= dsize) {
        if (!dsize) return;
        //printf("%s ", tmp);
        res[reslen] = (char *)malloc(strlen(tmp) + 1);
        strcpy(res[reslen++], tmp);
        return;
    }
    /* Recursion */
    char *c = table[hash(d[idx])]; 
    for (int i = 0; i < strlen(c); i ++) {
        tmp[idx] = c[i];
        back_tracking(d, idx + 1, dsize, res, tmp);
    }
}

char ** letterCombinations(char * digits, int* returnSize){
    char **result = (char **)malloc(sizeof(char *) * 4000);
    char tmp[6] = {0,};
    reslen = 0;
    back_tracking(digits, 0, strlen(digits), result, tmp);
    *returnSize = reslen;
    return result;
}

221021 다시 풀어봄

class Solution {
    string map[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    
    void backtracking(string s, string combi, int pos) {
        if (pos > s.length())
            return;
        if (pos == s.length()) {
            if (pos != 0)
                ret.push_back(combi);
            return;
        }
            
        string btn = map[s[pos] - '0'];
        for (int i = 0; i < btn.length(); i++) {
            backtracking(s, combi + btn[i], pos + 1);
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        string combi = "";
        backtracking(digits, combi, 0);
        return ret;
    }
};

숲사람

기록 & 정리 아카이브용

이전 포스트

Monotonic Stack 문제

다음 포스트