[코딩 테스트 합격자 되기 파이썬 - 3주차]백트래킹

개념

1. 백트래킹(Backtracking) 알고리즘의 작동 원리를 설명하고, 상태 공간 트리(State Space Tree) 개념과 연관 지어 설명해주세요. 주로 어떤 방식으로 구현되며 (예:재귀), 그 이유는 무엇인가요?

백트래킹 알고리즘은 어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것입니다. 책을 살펴보면, 시작점(루트)은 빈 리스트로 시작을 한다. 숫자가 4개가 포함되어 있으니, level 0 -> 1로 내려가면, 빈 리스트에 하나의 숫자씩 차지하게 된다. 
res = [[1], [2], [3], [4]]
숫자 2개의 조합을 완성해야 하므로, 이 아래로 선택한 숫자를 제외한 3개씩 노드를 가지게 되면 총 12개 조합이 완성되고, 이를 모두 통과하게 되면 O(12)이 될 것이다. ($O(N^{2} - N)$).
책에는 테스트로 보여주기 위해서 아주 적은 숫자로 지정하였지만, 실제 활용하기에는 어려울 가능성이 크다. 숫자가 조금만 증가해도 오래 걸릴 것이 예상된다.
여기서 우리는 2개의 조합의 합이 6을 초과하는 것을 알려면, 첫 번째로 들어오는 숫자가 최소 3이 넘어가야 하는 것을 알 수 있다. 그렇다면 여기서 우리는 1과 2 가 담긴 res 리스트에서 시작할 때, 3이 넘어가지 않기 때문에 가지 않겠다는 전략을 통하여 가지 않을 수 있다. 이렇게 되면, 우리는 
res = [[3], [4]] 
만을 이용하여 조합을 구하면 된다. 그렇게 되면 대략 절반이 감소하기 때문에 O(8) 이 될 것이다. (1, 2 는 방문 후 백트래킹, 3, 4 는 전부 방문) 
총 답은 res = [[3, 4], [4, 3]] 이 될 것이다. 
자세한 사항은 파이썬 책 p443 참고.

방금 위에 글로 설명하였지만 사실 트리로 그려보면 쉽게 이해할 수 있을 것이다. 상태 공간 트리는 각 선택에 대해서 선택을 했으면, 답에 담고, 선택하지 않으면 담지 않는 것을 상태로 나타내는 것을 보고 말하는 것 같다. 우리가 조합을 만들어 본다고 생각해보자. 로또 번호를 1부터 45번 까지 45개 중 6개의 조합을 만들려고 할 때, 1,2,3,4,5,6 부터 40,41,42,43,44,45개 까지 존재한다. 그럼 우리는 시작에는 빈 종이로 시작을 하니,
0. 루트에는 [] 빈 리스트,
1. 1부터 45까지 하나씩 담는다. [1], [2], ... ,[45]

2. 2개 째 담는다. 그러나 여기서 우리가 [1, 2] 와 [2, 1]은 같은 숫자 조합이기 때문에 위에서 얘기했던 굳이 안 가도 되는 곳이라면 백트래킹으로 돌아오자. [1, 2], [1, 3], ... [2, 3], [2, 4], ... [3, 4],... [44, 45], [45]
3. 계속 해서 담다 보면 탈락하는 노드가 여러 개 발생할 것이고, 총 길이가 6개인 조합들만 우리가 가져와서 사용하면 된다. 

백트래킹 알고리즘은 대체로 재귀를 통하여 많이 구현되곤 한다. 그 이유는,
1. 스택 자동 관리.
2. 코드 간결성
3. 직관적 구조 
를 이유를 들 수 있다. DFS와 구조상 매우 유사하기 때문에 그 이유도 유사한 것 같다. 

2. 백트래킹과 완전 탐색(Brute-force search)의 차이점은 무엇이며, 백트래킹이 완전 탐색에 비해 효율적인 이유는 무엇인가요? 백트래킹이 특히 유용한 문제 유형의 예시를 들어 설명해주세요.

위의 예시도 들었지만, 로또 번호의 조합의 경우의 수를 구할 때를 생각해보자.
완전 탐색의 경우, 1부터 45까지 모든 수를 거쳐가며, 6개씩 번호를 뽑을 것이다. 그 중에서는 중복되는 숫자 조합이 포함되어 있을 것이기 때문에 어찌 보면 낭비가 발생하고 있다. 
백트래킹의 경우, 가능성이 없다 싶으면 바로 백트래킹을 하여 더 이상의 진행을 하지 않게 된다. 위의 예시에서, 2단계를 보면, [45] 에서 더 많은 조합이 이루어지고 있지 않는다. 이는 방문을 하였지만, 앞서 동일한 숫자의 조합이 구성되어 있기 때문에 백트래킹을 통하여 더 이상 진행하지 않았다. 
완전 탐색과 비교하면, 유망성에 대해 검사를 하게 되고, 답이 될 가능성이 없다고 판단되면 가지치기를 통하여 더 이상 그 방향으로는 진행을 하지 않고 백트래킹으로 돌아오는 과정을 통하여 완전 탐색보다는 더 효율적이게 동작할 것이다.

3. 백트래킹 알고리즘의 시간 복잡도는 일반적으로 어떻게 표현되며, 실제 수행 시간에 가장 큰 영향을 미치는 요소는 무엇인가요? '가지치기(Pruning)' 기법이 백트래킹의 효율성을 어떻게 개선하는지 실제 문제 예시를 들어 설명해주세요.

백트래킹 알고리즘은 일반적으로 완전 탐색과 동일하게 표현한다. 그러나 위에서 설명한 것 처럼, 답이 될 가능성에 대해서 판단하고, 답이 될 가능성이 없다고 판단되는 노드로는 더 이상 탐색이 이루어 지지 않는 것을 보고, 나무에서 이쪽으로는 더 이상 자라지 마라고 가지를 치는 것 처럼, 이를 보고 가지치기 기법이라고 하는 것이다. 

N-Queens 의 문제에서, 모든 경우의 수를 판단하는 완전 탐색의 경우, 모든 경우의 수를 판단하기 때문에 시간 복잡도 측면에서는 $N^{N}$ 이 될 것이다. 그러나 가지치기를 할 경우, 첫 번째 퀸을 놓을 때는 자유롭게 놓을 수 있다. 그러나 두 번째 퀸을 놓을 때는 안 되는 경우의 수가 생기게 된다. 이때 가지치기를 통해, 이 이상의 가지가 생기지 않도록 방문처리를 한 후 더 이상의 진행을 하지 않는다. 이렇게 할 경우에 시간 복잡도를 상당부분 줄일 수 있을 것이다. 
자세한 설명은 책을 참고하고 아래에 있는 실전문제에서 확인하길 바란다.

실전

1. 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

백트래킹을 활용하는 데 있어서 주로 활용되는 조합을 구하는 문제이다. 

def solution(N) :
    res = []
    def backtrack(sm, nums, start) :
        if sm == 10 :
            res.append(nums)
            return

        for i in range(start, N + 1) :
            if sm + i <= 10 :
                backtrack(sm + i, nums + [i], i + 1)

    backtrack(0, [], 1)
    return res

조합의 합이 10이 되면 res 리스트에 추가 하고 백트래킹 한다. start 가 1부터 돌면서 해당하는 조합을 발견하면 res에 추가, return 하는 방식으로 이루어지며, 총 합이 10을 초과하게 되면 i + 1 처리와 함께 다음으로 넘어가게 된다. 

가장 기본적인 1, 2, 3, 4, 5 중에서 10을 완성시킬 수 있는 숫자 조합은 [1, 2, 3, 4], [1, 4, 5], [2, 3, 5] 가 있다. 여기서 1, 2, 3, 4 를 res에 추가 후 1, 2, 3, 5 를 시도하였더니 11로 10을 초과하게 된다. 그 다음에는 1, 2, 4 를 시도할 것이고 1, 2, 4, 5 를 하였더니 역시 10을 초과하여 1, 2, 5 => 1, 3 까지 백트래킹 할 것이다. 1, 3, 4, 5 => 1, 3, 5 => 1, 4 => 1, 4, 5 => res에 추가 => 1, 5 => 2... 이런 방식으로 진행 될 것 같다. 

2. 피로도

프로그래머스

def solution(k, dungeons):
    answer = -1
    visited = [0] * len(dungeons)

    def dfs(k, cnt):
        nonlocal answer
        for i in range(len(dungeons)):
            if not visited[i] and k >= dungeons[i][0]:
                visited[i] = 1
                dfs(k - dungeons[i][1], cnt + 1)
                visited[i] = 0

        answer = max(answer, cnt)

    dfs(k, 0)
    return answer

이 문제는 사실 백트래킹 보다는 DFS 인거 같은데 잘 모르겠다. 

하나씩 살펴보자. answer 가 내가 던전을 돌 수 있는 최대 던전 수가 될 것이다. 방문 배열을 하나 만들어 놓고, dfs 함수를 호출하여 나의 현재 피로도와 진행했던 던전 횟수를 입력한다.
초기 상태인 (k, 0) 에서 dfs를 수행하면서 피로도는 감소할 것이고, 요구되는 피로도와 소모되는 피로도는 다를 수 있기 때문에 모든 경우의 수 끝에 최대로 돌 수 있는 던전 수가 구해질 것이다. 

잘 이해가 안 되어서 주어진 예시에서 던전 순서를 바꾼 후 디버깅을 하였더니, 바뀌어도 0, 1, 2 던전을 모두 돌 수 있다면, 모두 방문하는 코드이다. for 문이 모든 던전을 일단 방문을 하기 때문에 (만약 방문 했다면, 백트래킹 되겠지만) 순서는 크게 상관 없다. 주어지는 던전의 갯수도 최대 8이기 때문에 별 다른 제한사항이 없다 하더라도, 무리없이 진행될 것이라 예상된다. 

3. N-퀸

프로그래머스

이 문제는 아까 위에서 말했던 N-Queens 문제이다. 퀸은 상 하 좌 우 대각으로 움직이기 때문에 범위 제한이 중요한 문제이다. 대각 역시 퀸이 움직일 수 있는 대각의 특성을 한 번 생각해보자. (y, x) 좌표가 있다고 가정하고, (0, 0), (1, 1), ... 이렇게 y = x + c 인 대각으로 움직이는 것과, (0, n - 1), (1, n - 2), ... 이렇게 y = -x + n 인 대각으로도 움직일 수 있다. 그렇기 때문에 우리는 방문 처리를 위해 대각선의 배열의 길이를 n * 2 로 만들어야 한다. 

def dfs(n, y, v1, v2, v3) :
    ans = 0
    if y == n :
        ans += 1

    for j in range(n) :
        if v1[j] == v2[y + j] == v3[y - j] == 0 :
            v1[j] = v2[y + j] = v3[y - j] = 1
            ans += dfs(n, y + 1, v1, v2, v3)
            v1[j] = v2[y + j] = v3[y - j] = 0
            
    return ans

def solution(n):
    v1 = [0] * n
    v2 = [0] * (2 * n)
    v3 = [0] * (2 * n)
    answer = dfs(n, 0, v1, v2, v3)
    return answer

여기서 배열은 행을 나타내고, 열은 y변수로 지정하였다. (배열은 행, 열 둘 중 하나만 나타내면, 나머지는 dfs를 재귀 수행하면서 처리할 수 있다. 왜냐하면 체스판은 N*N 이기 때문이다.) 

v1은 행,
v2는 양의 상관관계 (x가 증가하면, y도 증가),
v3는 음의 상관관계 (x가 증가하면, y는 감소)

y가 무사히 끝까지 도달하면, 모든 퀸이 놓여졌다는 말이므로, ans += 1 을 수행하고 이를 재귀적으로 수행하면서 ans에 가능한 경우의 수를 계속해서 쌓아 나간다고 생각하면 된다. 

어느 부분에서 가지치기가 이루어 지는지 알아보도록 하자. 자세한 건 책에 설명이 나와있다. 첫 번째 퀸은 모든 곳에 놓을 수 있다. 두 번째 퀸 부터 놓을 수 없는 곳이 정해지게 되는데, 이를 방문표시를 통하여 가지치기를 시작한다. 이렇게 되면, 놓을 수 있는(방문할 수 있는) 퀸의 자리가 제한이 되게 되고, 완전탐색을 굳이 하지 않아도 2번째, 3번째에서 가지치기가 가능해진다. 글로만 잘 이해가 가지 않는다면, 책에 저자와 편집자 두 분의 그림 설명이 기가 막히니 참고 바란다. 

코드는 비교적 간단하게 여겨질 수 있으나, 이를 생각해내기 까지가 참 어려운 문제인 것 같다.