가지치기(Pruning)

가지치기는 백트래킹 과정에서 더 이상 유망하지 않은(promising하지 않은) 경로를 조기에 차단하는 기법이다.
즉, 특정 경로가 해결책으로 이어질 가능성이 없다고 판단되면, 그 경로를 더 이상 탐색하지 않고 바로 다른 경로를 탐색합니다.

가지치기의 중요성

효율성 향상: 불필요한 탐색을 줄여 알고리즘의 실행 시간을 크게 단축한다.
자원 절약: 메모리 사용량을 줄이고 CPU 자원을 효율적으로 사용한다.
실용성 증대: 가지치기 없이는 현실적으로 해결하기 어려운 복잡한 문제도 해결 가능하게 만든다.

가지치기 적용 방법

가지치기를 적용하는 핵심은 ‘유망성 테스트(promising test)‘이다.
각 단계에서 현재 상태가 최종 해결책으로 이어질 가능성이 있는지를 판단하는 함수를 만들어 사용한다.

상태 탐색: 현재 상태에서 가능한 다음 단계들을 확인한다.
유망성 테스트: 각 다음 단계가 유망한지(promising) 테스트한다. 유망하지 않다면 그 경로는 더 이상 탐색하지 않는다.
재귀적 탐색: 유망한 다음 단계들에 대해서만 재귀적으로 탐색을 계속한다.

유망성 테스트(promising test)

유망성 테스트는 백트래킹 알고리즘에서 가지치기를 효과적으로 구현하기 위한 핵심 요소이다.

유망성 테스트(Promising Test)는 현재의 부분 해결책이 최종 해결책으로 발전할 가능성이 있는지를 판단하는 함수이다. 다시 말해, 지금까지 선택한 경로가 목표에 도달할 희망이 있는지 평가하는 과정이다.

이 테스트를 통해 ‘유망하지 않은(non-promising)’ 상태라고 판단되면, 해당 경로의 탐색을 즉시 중단하고 다른 경로를 탐색한다. 이것이 바로 ‘가지치기(Pruning)‘의 핵심 메커니즘이다.

유망성 테스트의 기본 구조

유망성 테스트는 일반적으로 다음과 같은 형태를 가집니다:

현재 상태가 문제의 제약 조건을 만족하는지 확인
현재 상태에서 목표 상태에 도달할 가능성이 있는지 확인
위의 모든 조건을 통과했다면 유망함

유망성 테스트의 중요성

유망성 테스트는 백트래킹 알고리즘의 효율성을 크게 향상시키는 핵심 요소이다.
문제의 특성에 맞는 적절한 유망성 테스트를 설계하고 구현함으로써 탐색 공간을 효과적으로 줄이고, 해결책을 더 빠르게 찾을 수 있다.

유망성 테스트의 종류

유망성 테스트는 문제의 특성에 따라 다양한 형태로 구현될 수 있다.
크게 세 가지 유형으로 나눌 수 있다:

제약 조건 기반 유망성 테스트
문제의 제약 조건을 만족하는지 확인한다.
예를 들어, N-Queens 문제에서는 퀸들이 서로 공격하지 않는 위치에 있는지 확인한다.

1
2
3
4
5
6
7
def is_promising(board, row):
    for i in range(row):
        # 같은 열에 있거나 대각선 상에 있는지 확인
        if board[i] == board[row] or \
           abs(board[i] - board[row]) == row - i:
            return False
    return True

경계 조건 기반 유망성 테스트
현재 상태가 경계 조건을 초과하는지 확인한다.
예를 들어, 배낭 문제(Knapsack Problem)에서는 현재까지 선택한 물건들의 무게가 배낭의 용량을 초과하는지 확인한다.
1 2
def is_promising(current_weight, max_weight): return current_weight <= max_weight
목표 도달 가능성 기반 유망성 테스트
현재 상태에서 목표 상태에 도달할 가능성이 있는지 평가한다.
예를 들어, 부분합 문제에서 현재까지의 합과 남은 원소들의 합을 고려하여 목표값에 도달할 가능성이 있는지 확인한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def is_promising(current_sum, target, remaining_elements):
    # 현재 합이 이미 목표를 초과한 경우
    if current_sum > target:
        return False
    
    # 현재 합에 모든 남은 원소를 더해도 목표에 도달할 수 없는 경우
    if current_sum + sum(remaining_elements) < target:
        return False
    
    return True

유망성 테스트 설계 원칙

효과적인 유망성 테스트를 설계하기 위한 몇 가지 중요한 원칙이 있다:

정확성(Correctness)
유망성 테스트는 반드시 정확해야 한다.
즉, 실제로 해결책으로 이어질 수 있는 경로를 ‘유망하지 않다’고 잘못 판단해서는 안 된다.
이는 알고리즘의 완전성(completeness)을 보장하기 위해 필수적이다.
효율성(Efficiency)
유망성 테스트는 가능한 한 빠르게 실행되어야 한다. 테스트 자체가 복잡하고 시간이 많이 소요된다면, 가지치기의 이점이 줄어들 수 있다.
조기 감지(Early Detection)
유망하지 않은 경로는 가능한 한 일찍 감지하는 것이 중요하다. 탐색 깊이가 깊어질수록 가지치기의 효과는 기하급수적으로 증가한다.
문제 특성 활용(Problem-Specific)
문제의 특성과 도메인 지식을 활용하여 더 효과적인 유망성 테스트를 설계할 수 있다. 일반적인 접근법보다 문제에 특화된 테스트가 더 효율적일 수 있다.

유망성 테스트 최적화 기법

메모이제이션(Memoization)
동일한 상태에 대한 유망성 테스트 결과를 캐싱하여 중복 계산을 피한다.
특히 동적 계획법(Dynamic Programming)과 결합할 때 유용하다.
휴리스틱(Heuristic) 활용
문제의 도메인 지식을 활용한 휴리스틱을 사용하여 더 효과적인 가지치기를 수행한다.
예를 들어, 미로 탈출 문제에서 목표 지점까지의 맨해튼 거리(Manhattan distance)를 고려하는 휴리스틱을 사용할 수 있다.
비트 연산(Bit Operations) 활용
상태를 비트 마스크로 표현하여 유망성 테스트의 효율성을 높일 수 있다.
특히 집합 연산이 많은 문제에서 유용하다.
병렬 처리(Parallel Processing) 활용:
독립적인 유망성 테스트를 병렬로 처리하여 성능을 향상시킬 수 있다.
다중 코어 환경에서 특히 유용하다.

예제

N-Queens 문제

8x8 체스판에 8개의 퀸을 서로 공격할 수 없도록 배치하는 문제를 생각해보면:

가치치기 없는 백트래킹에서는 모든 가능한 퀸 배치를 시도한다.
8x8 체스판에 8개의 퀸을 배치하는 방법은 64C8 = 4,426,165,368가지이다.

가지치기 적용 백트래킹에서는

한 행에 하나의 퀸만 배치할 수 있음을 이용합니다.
이미 배치된 퀸들과 공격 관계에 있는 위치는 시도하지 않습니다.

다음은 Python으로 구현한 N-Queens 문제의 가지치기 백트래킹 예제입니다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def solve_n_queens(n):
    board = [-1] * n  # board[i]는 i번째 행에서 퀸의 열 위치
    solutions = []
    
    def is_promising(row):
        # 현재까지 배치된 퀸들이 서로 공격할 수 없는지 확인
        for i in range(row):
            # 같은 열에 있거나 대각선 상에 있는지 확인
            if board[i] == board[row] or abs(board[i] - board[row]) == row - i:
                return False
        return True
    
    def place_queen(row):
        if row == n:  # 모든 퀸을 성공적으로 배치했을 때
            solutions.append(board[:])
            return
        
        for col in range(n):
            board[row] = col  # row번째 행의 col번째 열에 퀸 배치
            
            # 가지치기: 현재 배치가 유망한 경우에만 다음 행으로 진행
            if is_promising(row):
                place_queen(row + 1)
            # 유망하지 않으면 다음 열 위치로 이동 (암묵적 가지치기)
    
    place_queen(0)
    return solutions

# 8-Queens 문제 해결
solutions = solve_n_queens(8)
print(f"총 해결책 수: {len(solutions)}")

위 코드에서 is_promising 함수가 가지치기를 담당한다.
이 함수는 현재 퀸 배치가 유망한지 검사하고, 유망하지 않으면 해당 경로의 탐색을 중단한다.

부분합 문제

주어진 집합에서 원소들의 부분집합 중 합이 특정 값 T가 되는 부분집합을 찾는 문제를 생각해보면.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def subset_sum(numbers, target):
    n = len(numbers)
    solution = [0] * n  # 0 또는 1 (선택 여부)
    found = [False]  # 해결책을 찾았는지 여부 (리스트로 만들어 참조 전달)
    
    def backtrack(index, current_sum):
        if found[0]:  # 이미 해결책을 찾았으면 중단
            return
        
        if current_sum == target:  # 목표 합을 달성했을 때
            found[0] = True
            print("해결책:", [numbers[i] for i in range(n) if solution[i] == 1])
            return
        
        if index == n or current_sum > target:  # 가지치기: 목표 합을 초과하면 중단
            return
        
        # 현재 원소를 선택하는 경우
        solution[index] = 1
        backtrack(index + 1, current_sum + numbers[index])
        
        # 가지치기가 적용되지 않았다면, 현재 원소를 선택하지 않는 경우도 탐색
        if not found[0]:
            solution[index] = 0
            backtrack(index + 1, current_sum)
    
    backtrack(0, 0)
    return found[0]

# 예제
numbers = [3, 34, 4, 12, 5, 2]
target = 9
result = subset_sum(numbers, target)
print("해결책 존재 여부:", result)

이 코드에서 가지치기는 두 가지 상황에서 발생한다:

current_sum > target: 현재 합이 이미 목표값을 초과하면 더 이상 탐색하지 않는다.
found[0]: 이미 해결책을 찾았으면 더 이상 탐색하지 않는다.

가지치기 적용 시 고려사항

유망성 테스트의 효율성: 유망성 테스트 자체가 너무 복잡하면 가지치기의 이점이 줄어들 수 있다.
적절한 가지치기 시점: 너무 이른 가지치기는 실제 해결책을 놓칠 수 있고, 너무 늦은 가지치기는 효율성이 떨어진다.
문제 특성 이해: 문제의 특성을 잘 이해하면 더 효과적인 가지치기 조건을 설계할 수 있다.

핵심 요약

백트래킹은 모든 가능한 해결책을 탐색하는 완전 탐색 기법이다.
가지치기는 유망하지 않은 경로를 조기에 차단하여 효율성을 크게 향상시키는 기법이다.
가지치기의 핵심은 유망성 테스트로, 현재 상태가 해결책으로 이어질 가능성이 있는지 판단한다.
가지치기는 백트래킹 알고리즘의 시간 복잡도와 공간 복잡도를 크게 개선한다.
실전에서는 문제의 특성에 맞는 적절한 가지치기 조건을 설계하는 것이 중요하다.