---
title: "분기 한정법: 최적해가 될 수 없는 탐색 가지를 버리기"
author: "Lee"
published_at: "2026-10-25T10:32:01.259Z"
updated_at: "2026-09-30T09:47:53.647Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%B6%84%EA%B8%B0-%ED%95%9C%EC%A0%95%EB%B2%95-%EC%B5%9C%EC%A0%81%ED%95%B4%EA%B0%80-%EB%90%A0-%EC%88%98-%EC%97%86%EB%8A%94-%ED%83%90%EC%83%89-%EA%B0%80%EC%A7%80%EB%A5%BC-%EB%B2%84%EB%A6%AC%EA%B8%B0"
ai_assisted: false
---

# 분기 한정법: 최적해가 될 수 없는 탐색 가지를 버리기

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%B6%84%EA%B8%B0-%ED%95%9C%EC%A0%95%EB%B2%95-%EC%B5%9C%EC%A0%81%ED%95%B4%EA%B0%80-%EB%90%A0-%EC%88%98-%EC%97%86%EB%8A%94-%ED%83%90%EC%83%89-%EA%B0%80%EC%A7%80%EB%A5%BC-%EB%B2%84%EB%A6%AC%EA%B8%B0)

분기 한정법은 최적화 문제의 탐색 공간을 여러 선택으로 나누고, 각 부분 공간에서 얻을 수 있는 최선의 한계를 계산해 탐색량을 줄인다. 현재 확보한 완성 해와 비교하여 더 좋은 답이 나올 수 없는 가지를 제거한다.

![최대화 문제에서 현재 해 80과 가지의 상한 70·95를 비교하는 분기 한정](/api/v1/media/11fb3715-d817-4712-8373-c4954080b70e)

*낙관적 상한조차 현재 최선보다 좋지 않은 가지는 탐색하지 않는다.*

### 가능한 해와 낙관적 한계를 구분하기

최대 가치 문제에서는 현재 최선의 실현 가능한 해가 하한이고, 어떤 분기에서 얻을 수 있는 최대 가능 가치의 낙관적 추정이 상한이다. 상한이 현재 해보다 크지 않다면 그 분기를 더 볼 필요가 없다. 최소 비용 문제에서는 방향이 반대다.

0/1 배낭에서 남은 물건을 분수로 쪼개도 된다고 완화하면 원래 문제보다 선택 자유가 커진다. 가치/무게 비율순으로 채운 분수 배낭 값은 원래 분기에서 얻을 수 있는 가치의 상한이다. 실제 0/1 해가 아니어도 상한으로는 쓸 수 있다.

```text
search(partial_choice, current_value, remaining_capacity):
    optimistic_bound = current_value + fractional_upper_bound(
        unprocessed_items, remaining_capacity
    )
    if optimistic_bound <= best_feasible_value:
        return
    if all items have been decided:
        best_feasible_value = max(best_feasible_value, current_value)
        return
    explore the branch that takes the next item, if it fits
    explore the branch that skips the next item
```

전역 최선 값은 실현 가능한 완성 해에서만 갱신해야 한다. 상한 계산 결과를 그대로 정답으로 저장하면 분수 물건을 선택한 불가능한 값을 반환할 수 있다. 상한 함수도 현재 분기에서 아직 사용할 수 있는 물건만 고려해야 한다.

### 작은 숫자로 가지 제거하기

현재 최선이 20이고 어떤 부분 선택의 현재 가치가 8, 남은 물건을 느슨하게 허용해도 더할 수 있는 가치가 10이면 상한은 18이다. 이 가지는 최선 20을 이길 수 없으므로 중단한다. 다른 가지의 상한이 27이라면 실제로 27을 얻는다는 보장은 없지만 더 탐색할 이유는 있다.

한계를 너무 낙관적으로 잡으면 정확성은 유지되지만 가지가 거의 제거되지 않는다. 반대로 안전한 상한보다 낮게 잡으면 진짜 최적해를 버릴 수 있다. 부동소수점 반올림도 잘못된 가지 제거를 만들 수 있어 보수적인 계산이 필요하다.

깊이 우선은 메모리를 적게 쓰고 완성 해를 빨리 얻을 수 있다. 가장 유망한 한계부터 보는 우선순위 탐색은 많은 대기 상태를 저장할 수 있다. 좋은 초기 해와 타이트한 한계가 실제 성능에 큰 영향을 준다.

최악에는 많은 조합을 방문하여 지수 시간이 걸릴 수 있다. 백트래킹이 제약 위반으로 불가능한 해를 버린다면 분기 한정은 가능한 해 중에서도 현재 최선보다 좋아질 수 없는 영역을 버린다. 탐색 순서와 최적성 증명을 분리해 이해해야 한다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)