[Coding Test][Python] Exhaustive Search(완전 탐색)(Backtracking)개념 및 예제(순열, 조합, 부분집합)

※ Exhaustive Search(완전 탐색) 란?

Exhaustive Search(완전 탐색)는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 알고리즘 기법이다.

특징

• 완전성(Completeness) : 가능한 모든 경우를 확인하므로, 반드시 정답을 찾을 수 있다.
• 비효율성(Inefficiency) : 최악의 경우 계산량이 급격히 증가하여 실행시간이 길어질 수 있다.
• 단순성(Simplicity) : 구현이 쉽고 직관적이다.

적용방법

• Iterative Approach : 단순 반복문을 통해 확인한다.
• Recursive Approach : Backtracking 기법과 함께 사용되어 불필요한 탐색을 줄일 수 있다.
• Bitmasking : 이진수 표현을 이용해 모든 경우의 수를 탐색할 수 있다.

1. Backtracking 개념

모든 가능한 경우를 탐색하는 과정에서 불필요한 경로를 초기에 가지치기(Pruning)하여 탐색 속도를 높이는 기법이다. 완전 탐색의 일종이지만, 불가능한 경우의 탐색을 중단하여 불필요한 계산을 줄이는 것이 핵심이다.

특징

• 완전 탐색 기반
• Pruning(가지치기) : 특정 조건을 만족하지 않는 경우, 해당 탐색을 중단
• 재귀 사용
• DFS와 유사 : 탐색을 진행하다가 조건에 맞지 않으면 이전 상태로 돌아간다.

동작방식

1. 현재 상태에서 가능한 모든 후보(Candidate)를 탐색
2. 유효하지 않은 경우 Pruning
3. 유효한 경우에만 다음 단계로 진행
4. 답을 찾거나 끝까지 탐색하면 이전 단로 되돌아감(Backtrack)
5. 모든 경우를 확인하면 종료

Backtracking은 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 통해 유효하지 않는 경우를 정의하고(Pruning), 유효하지 않다면 탐색을 멈춘 뒤 이전 단계로 돌아가 다시 다른 경우를 탐색하는 기법이라 정리할 수 있습니다.

여기서, 답이 될 가능성이 있다면 "유망하다(Promising)"라고 합니다.

2. Backtracking 예제 - 순열(Permutation), 조합(Combination), 부분집합(Subset)

2-1) 순열 Permutation

def permutation(nums):
    def backtrack(path, used):
        if len(path) == len(nums):
            print(path)
            return
        
        for i in range(len(nums)):
            if not used[i]:  
                used[i] = True
                backtrack(path + [nums[i]], used)  
                # 백트래킹
                used[i] = False

    backtrack([], [False] * len(nums))

permutation([1, 2, 3, 4])

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

2-2) 조합 Combination

def combination(nums, k):
    def backtrack(start, path):
        if len(path) == k:
            print(path)
            return
        
        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])  

    backtrack(0, [])

combination([1, 2, 3, 4], 2)

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

 

2-3) 부분집합 Subset

def subset(nums):
    def backtrack(start, path, k):
        if len(path) == k:
            print(path)
            return

        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]], k)  

    for k in range(len(nums) + 1):  
        backtrack(0, [], k)

subset([1, 2, 3, 4])

[]
[1]
[2]
[3]
[4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

 

Backtracking을 통해 순열, 조합, 부분집합을 구하는 코드에 대해서 확인해보았습니다.

python의 itertools를 이용하면 간편하게 사용할 수 있지만 대부분 코테에서는 itertools 같은 외부 라이브러리는 사용하지 못하니 구현 연습해보시는 것이 좋다고 생각됩니다.