Divide and Conquer vs. Branch and Bound

“Divide and Conquer(분할 정복)“과 “Branch and Bound(분기 한정)“은 복잡한 문제를 해결하는 다른 접근법을 제공하며, 각각의 장단점과 적합한 활용 사례가 있다.

“Divide and Conquer"와 “Branch and Bound"는 복잡한 문제를 해결하기 위한 두 가지 중요한 알고리즘 패러다임이다.
분할 정복은 문제를 작은 하위 문제로 나누어 해결하는 일반적인 방법인 반면, 분기 한정은 최적화 문제에서 효율적으로 최적해를 찾기 위한 전문화된 방법이다.

분할 정복은 정렬, 검색 등의 기본 알고리즘에 널리 사용되며, 분기 한정은 TSP, 배낭 문제 등의 복잡한 최적화 문제에 효과적이다.
두 알고리즘 모두 컴퓨터 과학에서 중요한 도구이므로, 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요하다.

Divide and Conquer(분할 정복) 알고리즘

분할 정복은 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 방법이다.
이 알고리즘은 다음과 같은 세 단계로 구성된다:

분할(Divide): 원래 문제를 더 작은 하위 문제들로 나눈다.
정복(Conquer): 각 하위 문제를 재귀적으로 해결한다.
결합(Combine): 하위 문제들의 해결책을 합쳐 원래 문제의 해결책을 만든다.

대규모 건설 프로젝트와 유사하다. 전체 건물(문제)을 여러 층이나 구역(하위 문제)으로 나누어 각각 건설(정복)한 다음, 모든 부분을 연결(결합)하여 전체 건물을 완성한다.

작동 원리 예시: 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복의 대표적인 예:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 피벗 선택 (여기서는 첫 번째 요소를 피벗으로 선택)
    pivot = arr[0]
    
    # 분할: 피벗보다 작은 요소와 큰 요소를 분리
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    
    # 정복: 재귀적으로 하위 배열 정렬
    less = quick_sort(less)
    greater = quick_sort(greater)
    
    # 결합: 정렬된 하위 배열과 피벗을 결합
    return less + [pivot] + greater

이 알고리즘은 배열을 피벗을 기준으로 두 부분(분할)으로 나누고, 각 부분을 재귀적으로 정렬(정복)한 다음, 정렬된 두 부분을 피벗과 함께 결합하여 최종 정렬된 배열을 만든다.

특징 및 장단점

장점:

큰 문제를 작은 문제로 나누어 해결함으로써 복잡성을 줄일 수 있다.
많은 경우 효율적인 시간 복잡도(일반적으로 O(n log n))를 가진다.
일부 문제에서 병렬 처리에 적합하다.

단점:

재귀 호출로 인한 스택 오버플로우가 발생할 수 있다.
모든 하위 문제를 해결해야 하므로 가지치기(pruning)가 어렵다.
일부 경우에 비효율적일 수 있다(예: 피벗 선택이 잘못된 경우의 퀵 정렬).

Branch and Bound(분기 한정) 알고리즘

분기 한정은 최적화 문제(주로 조합 최적화 문제)를 해결하기 위한, 특히 NP-hard 문제에 효과적인 알고리즘이다.
이 알고리즘은 다음과 같은 두 가지 주요 요소로 구성된다:

분기(Branching): 문제의 해공간을 여러 하위 공간으로 분할한다.
한정(Bounding): 각 하위 공간에 대한 한계(상한 또는 하한)를 계산하여 유망하지 않은 해공간을 가지치기한다.

분기 한정 알고리즘은 일반적으로 탐색 트리를 사용하여 문제의 해공간을 탐색하며, 유망하지 않은 가지(subspace)를 제거하여 탐색 공간을 줄인다.

미로에서 보물 찾기와 유사하다.미로의 여러 경로(분기)를 탐색하되, 각 경로마다 보물과의 최소 거리(한계)를 계산한다. 이미 찾은 보물까지의 거리보다 현재 경로의 최소 거리 추정치가 더 크면, 그 경로는 더 이상 탐색하지 않는다(가지치기).

작동 원리 예시: 배낭 문제(Knapsack Problem)

배낭 문제는 분기 한정의 대표적인 예:

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
def knapsack_branch_and_bound(weights, values, capacity):
    n = len(weights)
    
    # 항목을 가치/무게 비율에 따라 내림차순 정렬
    items = sorted([(values[i]/weights[i], weights[i], values[i], i) 
                   for i in range(n)], reverse=True)
    
    # 최적해와 최대 가치를 저장할 변수
    best_value = 0
    best_solution = [0] * n
    
    # 현재 상태를 나타내는 클래스
    class Node:
        def __init__(self, level, weight, value, includes):
            self.level = level      # 현재 결정 레벨
            self.weight = weight    # 현재까지의 무게
            self.value = value      # 현재까지의 가치
            self.includes = includes.copy()  # 포함된 항목 목록
            
            # 상한 계산 (남은 공간에 분할 가능한 물건을 넣을 경우의 가치)
            self.bound = self.calculate_bound(weights, values, capacity, items)
        
        def calculate_bound(self, weights, values, capacity, items):
            if self.weight > capacity:
                return 0
            
            bound_value = self.value
            j = self.level
            total_weight = self.weight
            
            # 남은 항목들을 가치/무게 비율이 높은 순으로 최대한 추가
            while j < n and total_weight + items[j][1] <= capacity:
                total_weight += items[j][1]
                bound_value += items[j][2]
                j += 1
            
            # 마지막 항목은 분수로 추가
            if j < n:
                bound_value += (capacity - total_weight) * items[j][0]
            
            return bound_value
    
    # 탐색 큐
    queue = [Node(0, 0, 0, [0] * n)]
    
    while queue:
        node = queue.pop(0)
        
        # 마지막 레벨에 도달한 경우
        if node.level == n:
            if node.value > best_value and node.weight <= capacity:
                best_value = node.value
                best_solution = node.includes
            continue
        
        # 현재 항목의 인덱스
        i = items[node.level][3]
        
        # 현재 항목을 포함하지 않는 경우
        new_includes = node.includes.copy()
        child = Node(node.level + 1, node.weight, node.value, new_includes)
        
        # 한계값이 현재 최대 가치보다 크면 유망하다고 판단
        if child.bound > best_value:
            queue.append(child)
        
        # 현재 항목을 포함하는 경우
        if node.weight + items[node.level][1] <= capacity:
            new_includes = node.includes.copy()
            new_includes[i] = 1
            child = Node(node.level + 1, 
                         node.weight + items[node.level][1], 
                         node.value + items[node.level][2], 
                         new_includes)
            
            if child.bound > best_value:
                queue.append(child)
    
    return best_value, best_solution

이 알고리즘은 가치/무게 비율이 높은 항목부터 고려하며, 각 항목을 포함하거나 포함하지 않는 두 가지 선택지(분기)를 탐색한다. 각 노드에서 상한(bound)을 계산하여 유망하지 않은 가지는 더 이상 탐색하지 않는다(한정).

특징 및 장단점

장점:

최적화 문제에서 효율적으로 최적해를 찾을 수 있다.
가지치기를 통해 불필요한 탐색을 줄일 수 있다.
복잡한 조합 최적화 문제에 적합하다.

단점:

구현이 상대적으로 복잡하다.
효율적인 한계 함수(bounding function)를 설계하는 것이 중요하며 어려울 수 있다.
최악의 경우 여전히 지수 시간이 소요될 수 있다.

두 알고리즘의 핵심 차이점

문제 해결 접근 방식
- 분할 정복: 문제를 독립적인 하위 문제로 나누어 각각 해결한 후 결합한다.
- 분기 한정: 해공간을 체계적으로 탐색하며, 유망하지 않은 부분을 제거한다.
탐색 공간
- 분할 정복: 모든 하위 문제를 해결한다.
- 분기 한정: 유망한 하위 문제만 탐색하고, 나머지는 가지치기한다.
적용 문제 유형
- 분할 정복: 정렬, 검색, 행렬 곱셈 등 다양한 문제에 적용할 수 있다.
- 분기 한정: 주로 조합 최적화 문제(TSP, 배낭 문제 등)에 적용된다.
예시로 보는 차이: 외판원 문제(TSP)
외판원 문제(Traveling Salesman Problem)는 모든 도시를 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 문제다.
- 분할 정복 접근: 모든 가능한 경로를 나열하고 비교한다. 이는 도시 수가 많아지면 비효율적입니다(시간 복잡도: O(n!)).
- 분기 한정 접근: 부분 경로의 하한(lower bound)을 계산하여 유망하지 않은 경로는 탐색하지 않는다. 이를 통해 탐색 공간을 크게 줄일 수 있다.

실제 적용 사례

Divide and Conquer 적용 사례
1. 병합 정렬(Merge Sort): 배열을 절반으로 나누어 정렬한 후 병합
2. 이진 검색(Binary Search): 정렬된 배열에서 중간점을 기준으로 검색 범위를 반으로 줄임
3. 카라츠바 알고리즘(Karatsuba Algorithm): 큰 수의 곱셈을 효율적으로 수행
4. 최근접 점쌍 찾기(Closest Pair of Points): 2D 평면에서 가장 가까운 두 점을 찾음
Branch and Bound 적용 사례
1. 외판원 문제(Traveling Salesman Problem): 모든 도시를 방문하는 최단 경로 찾기
2. 배낭 문제(Knapsack Problem): 제한된 무게 내에서 최대 가치의 물건 선택
3. 작업 할당 문제(Job Assignment Problem): n개의 작업을 n명의 작업자에게 최적으로 할당
4. 정수 계획법(Integer Programming): 정수 제약 조건이 있는 최적화 문제 해결

코드 비교: 최적 해 찾기 문제

두 알고리즘의 차이를 보여주기 위해 간단한 최적화 문제.

분할 정복 접근법: 모든 부분집합 생성

 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
def find_optimal_subset_dc(weights, values, capacity):
    n = len(weights)
    
    # 모든 가능한 부분집합을 생성하여 최적해 찾기
    def generate_subsets(index, current_weight, current_value, selected):
        if index == n:
            return current_value if current_weight <= capacity else 0, selected.copy()
        
        # 현재 항목을 포함하지 않는 경우
        val1, sel1 = generate_subsets(index + 1, current_weight, current_value, selected)
        
        # 현재 항목을 포함하는 경우
        selected.append(index)
        val2, sel2 = generate_subsets(index + 1, 
                                     current_weight + weights[index], 
                                     current_value + values[index], 
                                     selected)
        selected.pop()
        
        # 더 나은 결과 반환
        if val1 >= val2:
            return val1, sel1
        else:
            return val2, sel2
    
    return generate_subsets(0, 0, 0, [])

분기 한정 접근법: 유망한 부분집합만 생성

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def find_optimal_subset_bnb(weights, values, capacity):
    n = len(weights)
    
    # 항목을 가치/무게 비율에 따라 내림차순 정렬
    items = [(values[i]/weights[i], weights[i], values[i], i) 
            for i in range(n)]
    items.sort(reverse=True)
    
    best_value = 0
    best_selection = []
    
    def bound(index, current_weight, current_value):
        if current_weight > capacity:
            return 0
        
        bound_value = current_value
        j = index
        total_weight = current_weight
        
        # 남은 항목들을 가치/무게 비율이 높은 순으로 최대한 추가
        while j < n and total_weight + items[j][1] <= capacity:
            total_weight += items[j][1]
            bound_value += items[j][2]
            j += 1
        
        # 마지막 항목은 분수로 추가
        if j < n:
            bound_value += (capacity - total_weight) * items[j][0]
        
        return bound_value
    
    def branch_and_bound(index, current_weight, current_value, selected):
        nonlocal best_value, best_selection
        
        # 종료 조건
        if index == n:
            if current_value > best_value and current_weight <= capacity:
                best_value = current_value
                best_selection = selected.copy()
            return
        
        # 현재 상태의 상한 계산
        upper_bound = bound(index, current_weight, current_value)
        
        # 가지치기: 상한이 현재 최적값보다 작으면 탐색 중단
        if upper_bound <= best_value:
            return
        
        # 현재 항목을 포함하지 않는 경우
        branch_and_bound(index + 1, current_weight, current_value, selected)
        
        # 현재 항목을 포함하는 경우
        if current_weight + items[index][1] <= capacity:
            selected.append(items[index][3])
            branch_and_bound(index + 1, 
                           current_weight + items[index][1], 
                           current_value + items[index][2], 
                           selected)
            selected.pop()
    
    branch_and_bound(0, 0, 0, [])
    return best_value, best_selection

분할 정복 방식은 모든 가능한 부분집합을 생성하여 비교하는 반면, 분기 한정 방식은 상한(bound)을 계산하여 유망하지 않은 가지는 탐색하지 않는다.
이를 통해 분기 한정 방식이 더 효율적으로 최적해를 찾을 수 있다.

선택 가이드

Divide and Conquer를 선택해야 할 때
- 문제가 자연스럽게 독립적인 하위 문제로 나뉠 때
- 하위 문제의 해결책을 쉽게 결합할 수 있을 때
- 재귀적 구조가 명확할 때
- 정렬, 검색과 같은 기본적인 알고리즘 문제를 해결할 때
- 병렬 처리가 필요할 때
Branch and Bound를 선택해야 할 때
- 최적화 문제를 해결해야 할 때
- 문제의 해공간이 너무 크지만, 효과적인 가지치기가 가능할 때
- 완전 탐색이 비효율적일 때
- 조합 최적화 문제(TSP, 배낭 문제 등)를 해결할 때
- 효율적인 한계 함수를 설계할 수 있을 때
문제 접근 방법
1. 문제 분석: 문제의 구조와 특성을 파악한다.
  - 문제가 독립적인 하위 문제로 나눌 수 있는지
  - 최적화 문제인지, 효과적인 가지치기가 가능한지
2. 알고리즘 선택:
  - 문제가 명확하게 분할 가능하고 하위 문제를 결합할 수 있으면 → 분할 정복
  - 최적화 문제이고 효과적인 한계 함수를 설계할 수 있으면 → 분기 한정
3. 구현 방법:
  - 분할 정복: 재귀 함수를 사용하여 하위 문제를 해결하고 결과를 결합
  - 분기 한정: 상태 공간 트리를 탐색하며 한계 함수를 사용하여 가지치기

두 알고리즘 비교

특성	Divide and Conquer	Branch and Bound
기본 원리	문제를 작은 하위 문제로 분할하여 해결	해공간을 분기하고 유망하지 않은 부분을 가지치기
목적	효율적인 문제 해결	최적화 문제의 최적해 찾기
접근 방식	재귀적, 하향식(top-down)	체계적인 열거, 상태 공간 트리 탐색
문제 해결 전략	분할 → 정복 → 결합	분기 → 한계 계산 → 가지치기
탐색 범위	모든 하위 문제 탐색	유망한 하위 문제만 탐색
가지치기(pruning)	일반적으로 사용하지 않음	필수적으로 사용(핵심 요소)
적용 문제 유형	정렬, 검색, 행렬 연산 등	조합 최적화 문제(TSP, 배낭 문제 등)
시간 복잡도	일반적으로 O(n log n) (예: 병합 정렬)	최악의 경우 지수 시간이지만 가지치기로 개선
공간 복잡도	재귀 호출 스택으로 인해 높을 수 있음	탐색 트리 저장으로 인해 높을 수 있음
최적해 보장	일반적으로 보장	완전한 탐색 시 보장
중간 결과 활용	하위 문제 해결 후 결합	현재까지의 최적값을 가지치기에 활용
구현 복잡성	중간	높음 (한계 함수 설계가 어려움)
대표 알고리즘	병합 정렬, 퀵 정렬, 이진 검색	분기한정법 기반 TSP, 배낭 문제 해결
상태 관리	하위 문제별 독립적 상태	탐색 경로의 전체 상태 유지
적합한 문제 크기	중간~큰 크기	중간 크기 (너무 크면 여전히 비효율적)
병렬화 가능성	높음 (독립적 하위 문제)	제한적 (탐색 상태 의존성)
메모리 사용 패턴	분할-결합 단계에서 메모리 사용	가지치기 결정을 위한 상태 정보 저장
탐색 순서	문제 구조에 따라 결정	BFS, DFS, 최선 우선 등 다양한 전략 사용 가능
휴리스틱 활용	일반적으로 사용하지 않음	한계 함수, 탐색 순서 등에 활용