5. Brute Force(완전 탐색), Back tracking

지난시간에는 재귀와 분할정복에 대해서 알아보았습니다. 이번에는 Brute-force algorithm과 Backtracking 알고리즘에 대해서 살펴보도록 하겠습니다.

 

1. Brute-force algorithm(완전 탐색 알고리즘)

백트래킹을 알기 위해선 먼저 브루트포스 또는 완전 탐색에 대해 알아야 합니다. 

브루트포스나 완전 탐색은 solution에 대해 가능성 있는 모든 후보들을 시스템적으로 나열하고 각 후보들이 problem의 상태를 만족하는지 판별하는 알고리즘입니다. 

말그대로 주먹구구식의, 무식하게 푸는 방식이지만 때로는 무식한 방법이 더 쉽게 문제를 해결할 수 있는 경우도 있습니다. 또한 광범위하게 사용이 가능합니다.

brute-force 방식으로 문제를 풀면 O(9**n)의 시간복잡도를 가지게 된다!

 

스도쿠를 예로 들자면, 아래와 같은 스도쿠를 brute-force 기법으로 풀게 된다면 9x9 size의 스도쿠 판의 각 판마다 1~9까지의 수들을 전부 넣어보면서 조건을 만족하는지 하나하나 확인을 해야하는데, 이 경우에 시간복잡도가 O(9**n)이 나오게 됩니다. 그래서 이런 상황에서는 brute-force 방식이 매우 비효율적이게 됩니다.

이런 상황에서의 문제를 해결하기 위해 첫번째 칸에 1을 넣고 바로 다음칸에 1을 넣는 경우는 규칙에 어긋납니다. 따라서 이와 같은 행동이 나올 시에 거기서 다른 칸에 다른 숫자를 넣지 않고 바로 뒤로 가는 방법을 찾아야하는데, 이런 이유로 백트래킹(Backtracking)이라는 이름이 붙게 된 것입니다.

 

 

 

2. Brute-force로 순열 문제구현

def bit_str(ans):
    if len(ans) == n: #만약 만들어진 문자열이 원하는 길이가 됐을 때,
        print(*ans)
    else:
        for s in data:
            ans.append(s)
            bit_str(ans) #recursion을 이용하여 반복
            ans.pop() #len(ans)==3 일때 맨 오른쪽 요소를 pop(제거)해준다


n, data = 3, 'abc'
bit_str([])

 

이 코드로 이어지는 결과를 그림으로 나타내면,

다음과 같이 aaa, aab, aac, aba, abb, abc, ... 으로 aaa부터 ccc까지 모두 나열되게 된다.

 

+) 프로그래밍을 하다보면 for loop보다 recursion이 오히려 더 좋다고 한다.

코드를 겉으로 보기에는 이중 for loop이 더 간결해 보일 수는 있지만, n의 size가 매우 커질 경우 코드가 시간 안에 돌아가지 않을 것이기 때문!

 

 

 

 

3. Backtracking(백트래킹) 알고리즘

오늘 알아볼 2가지 내용 중 하나인 Brute-force에 대해 알아보았으니 마지막 내용인 Backtracking에 대해 알아보겠습니다.

Backtracking은 traversing tree(트리 순회) 구조와 같은 문제의 유형에 특히 유용한 recursion의 한 형태인데, 각 노드에 대한 수 많은 옵션들이 제시된 곳에서 유용한 것입니다. 

• 굳이 모든 노드를 순회하지 않아도되므로 효율적!

또한, Backtracking은 exhaustive searching(완전 탐색)을 위한 divide-and-conquer 방식입니다. 여기서 중요한 점은 백트래킹은 결과를 낼 수 없는 가지들은 쳐낸다는 점입니다. 정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 것만 살펴보는 것입니다.

• 완전탐색을 위한 분할정복? -> 완전 탐색은 오래 걸리니 분할 정복이라는 툴로 시간을 줄임

 

Backtracking의 과정을 도식화

즉, 위의 그림처럼 가지를 모두 탐색하면서 조건을 일일히 따져보는 것이 아니라, 중간에 failed candidates(가망이 없는 후보)가 발견되면 다음 가지로 넘어가지 않고 다시 되돌아가(back) 현재 노드부터 다시 tracking을 시작하여 결과를 찾아내는 알고리즘인 것입니다.

즉 Failed Candidates 이후의 노드들은 어차피 볼 필요도 없다는 아이디어가 중요합니다.

• 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.
• 코딩에서 반복문 횟수를 줄일 수 있기 때문에 효율적이다.

 

아래는 3*3 스도쿠를 백트래킹 방식으로 구현한 것을 도식화 한 것입니다.

조건에 맞는 방식에서만 탐색을 이어나간다.

 

 

 

 

 

 

4. 문제를 통해 보는 Backtracking Algorithm

 

1. 15649번 : N과 M(1)

https://www.acmicpc.net/problem/15649

def bit_str(ans):
    if len(ans) == m:
        print(*ans)
    else:
        for i in range(1,n+1):
            if i not in ans:   #백트래킹에서의 가지치기, 근데 이건 옳은 가지 찾기인듯
                ans.append(i)
                bit_str(ans)
                ans.pop()


n,m = map(int,input().split())
bit_str([])

 

재귀를 사용할 때 가장 중요한 base case를 출력 요구 조건으로 해주었습니다. (리스트 요소의 개수가 m가 같을 때 출력해라)

그 이후 2번에서 진행하였던 brute-force로 순열 구하기에서 if i not in ans: 로 조건에 대해서 가지치기를 해주었습니다.

 

 

 

2. 15650번 : N과 M(2)

https://www.acmicpc.net/problem/15650

def bit_str(ans):
    if len(ans) == m:
        n_ans = sorted(ans)
        if ans == n_ans:
            print(*ans)
    else:
        for i in range(1,n+1):
            if i not in ans: 
                ans.append(i)
                bit_str(ans) 
                ans.pop() 


n, m = map(int, input().split())
bit_str([])

위의 문제와 유사하지만 bit_str이 오름차순으로 정렬되어 있을때만 print하도록 코드를 짜주었습니다.

 

+) 다른 사람 풀이

def combine(ans):
    if len(ans) == m:
        print(*ans)
    else:
        for i in range(1, n + 1):
            if (len(ans) >= 1) and (i <= ans[-1]):
                continue

            else:
                ans.append(i)
                combine(ans)
                ans.pop()


n, m = map(int, input().split())
combine([])

 

 

 

 

 

 

 

Reference

https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Recursion-and-Backtracking%EC%9E%AC%EA%B7%80-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9?category=1070664

[자료구조와 알고리즘 | 파이썬] Recursion and Backtracking(재귀 & 백트래킹) + Divide and Conquer(분할정복)

 

https://velog.io/@yusuk6185/%EB%B0%B1%EC%A4%80-15649-N%EA%B3%BC-M-1-%ED%8C%8C%EC%9D%B4%EC%8D%AC-with-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

[백준 15649] N과 M (1) - 파이썬 with 백트래킹

 

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제