알고리즘 면접 심층 분석: 0/1 배낭 문제에서 동적 계획법과 분기 한계법의 실전 선택

기술 면접 준비 시 알고리즘 문제는 합불을 가르는 결정적 요소입니다. 그중 0/1 배낭 문제는 전형적인 조합 최적화 문제로, 지원자의 기본 알고리즘 이해도를 평가할 뿐만 아니라 다양한 제약 조건에서 최적해 전략을 선택하는 능력을 검증하는 시금석이 됩니다. 많은 지원자들이 동적 계획법의 점화식을 암기할 수 있지만, 면접관이 "만약 물품 수가 매우 많지만 배낭 용량은 상대적으로 작다면 어떤 알고리즘을 선택하겠습니까?"라고 질문할 때 종종 침묵에 빠지게 됩니다. 실제로 동적 계획법과 분기 한계법은 0/1 배낭 문제를 해결할 때 각자의 장점을 가지고 있으며, 그 본질적인 차이점과 적용 시나리오를 이해하는 것은 코드 템플릿을 외우는 것보다 훨씬 중요합니다.

이 글은 두 알고리즘의 핵심 메커니즘을 깊이 있게 탐구하며, 실제 코드 비교, 시간 복잡도 분석, 그리고 시나리오 기반 선택 전략을 통해 명확한 의사결정 프레임워크를 구축하도록 안내합니다. 우리는 표면적인 이론 소개에 머무르지 않고, 면접에서 가장 자주 묻는 실전 세부 사항에 초점을 맞출 것입니다: 두 방법의 메모리 사용 근본 차이는 무엇인가? 왜 어떤 경우에는 분기 한계법이 검색을 조기에 종료할 수 있는가? 문제 규모에 따라 어떤 방법을 사용할지 신속하게 판단하는 방법은? 이러한 질문에 대한 답이 바로 평범한 지원자와 우수 엔지니어를 구분하는 핵심입니다.

1. 문제 본질과 알고리즘 사상의 근본적 차이

0/1 배낭 문제의 형식적 설명은 매우 간단합니다: 용량이 C인 배낭과 n개의 물품이 주어졌을 때, 각 물품은 무게 w_i와 가치 v_i를 가지며, 배낭에 여러 물품을 선택하여 담되 총 무게가 C를 초과하지 않으면서 총 가치가 최대가 되도록 하는 문제입니다. 각 물품은 완전히 넣거나(1) 전혀 넣지 않거나(0)만 가능하며, 이것이 "0/1"의 의미입니다.

1.1 동적 계획법: 바닥부터 위로의 최적 부분 구조 구축

0/1 배낭 문제를 해결하는 동적 계획법의 핵심 사상은 문제의 최적해에는 그 부분 문제의 최적해가 포함된다는 중요한 관찰에 기반합니다. 이러한 "최적 부분 구조" 특성은 부분 문제의 해를 조합하여 원 문제의 해를 구성할 수 있게 해줍니다.

상태 dp[i][j]를 첫 i개의 물품을 고려하고 배낭 용량이 j일 때의 최대 가치라고 정의합니다. 상태 전이 방정식은 다음과 같습니다:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i)  if j >= w_i
dp[i][j] = dp[i-1][j]                             otherwise

이 방정식의 의미는 매우 직관적입니다: i번째 물품에 대해 두 가지 선택이 있습니다:

• 넣지 않음: 가치는 i-1개의 물품을 용량 j에서 고려했을 때의 최적해와 같습니다
• 넣음: 가치는 i-1개의 물품을 용량 j-w_i에서 고려했을 때의 최적해에 v_i를 더한 값과 같습니다

핵심 통찰: 동적 계획법은 표를 채우는 방식을 통해 시스템적으로 모든 부분 문제의 해를 계산하고 저장하여 중복 계산을 피합니다. 이 방법의 장점은 dp[n][C]를 계산하면 최대 가치뿐만 아니라 역추적을 통해 어떤 물품이 선택되었는지 쉽게 찾을 수 있다는 점입니다.

1.2 분기 한계법: 지능형 검색과 가지치기의 예술

동적 계획법의 바닥부터 위로 구축하는 방식과 달리, 분기 한계법은 지능형 검색 전략을 사용합니다. 이 방법은 해 공간을 트리로 구성하고, 각 노드가 부분 해(일부 물품의 선택 여부가 결정됨)를 나타내도록 하며, "한계" 함수를 사용하여 최적해를 얻을 수 없는 가지를 잘라냅니다.

분기 한계법의 핵심 구성 요소:

1. 해 공간 트리: 각 노드는 결정 지점(현재 물품을 선택할지 여부)에 해당하며, 왼쪽 분기는 선택, 오른쪽 분기는 미선택을 의미합니다
2. 우선순위 큐: 어떤 휴리스틱 전략(보통 가치 상한 기준)에 따라 다음 확장할 노드를 선택합니다
3. 한계 함수: 현재 노드에서 계속 검색할 때 달성할 수 있는 최대 가능 가치를 추정합니다
4. 가지치기 전략: 어떤 분기가 현재까지 알려진 최적해보다 더 나은 해를 생성할 수 없음을 발견하면 해당 분기 탐색을 즉시 중단합니다

# 분기 한계법 노드 클래스의 단순화된 예시
class 해_노드:
    def __init__(self, 단계, 이익, 무게, 상한):
        self.단계 = 단계      # 현재 결정된 물품 인덱스
        self.이익 = 이익      # 현재 획득한 가치
        self.무게 = 무게      # 현재 사용된 용량
        self.상한 = 상한      # 가치 상한 추정치

1.3 사상 비교: 두 가지 완전히 다른 문제 해결 철학

두 방법의 본질적 차이를 더 명확하게 보여주기 위해 다음 비교 표를 통해 정리합니다:

철학적 관점에서 동적 계획법은 구성적입니다 - 알려진 최적 부분을 조합하여 전체 최적을 구축합니다. 반면 분기 한계법은 탐색적입니다 - 거대한 해 공간에서 최적해를 찾으면서 동시에 희망이 없는 영역을 현명하게 피합니다. 이러한 근본적 차이는 다양한 시나리오에서의 성능을 결정합니다.

2. 시간 복잡도와 공간 복잡도 심층 분석

면접에서 자주 묻는 질문은 "이 두 방법의 시간 복잡도는 각각 얼마입니까?"입니다. "모두 지수 시간 복잡도입니다"라고 간단히 답하는 것은 충분하지 않습니다. 우리는 복잡도 뒤에 숨은 실제 의미를 이해하고, 실제 문제에서 이것이 무엇을 의미하는지 알아야 합니다.

2.1 동적 계획법의 복잡도 특징

0/1 배낭 문제를 해결하는 동적 계획법의 시간 복잡도는 O(nC)이며, 여기서 n은 물품 수이고 C는 배낭 용량입니다. 여기서 주의해야 할 점은 C가 입력 길이가 아니라 입력 값이라는 사실입니다. 이론 컴퓨터 과학에서 이를 "의사 다항 시간" 알고리즘이라고 합니다.

# 동적 계획법 구현의 핵심 부분
def 배낭_동적계획법(무게들, 가치들, 용량):
    n = len(무게들)
    dp = [[0] * (용량 + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, 용량 + 1):
            if 무게들[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w-무게들[i-1]] + 가치들[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][용량]

공간 최적화 기법: dp[i][w]는 dp[i-1][...]에만 의존하므로, 2차원 배열을 1차원으로 압축할 수 있습니다:

def 배낭_동적계획법_최적화(무게들, 가치들, 용량):
    n = len(무게들)
    dp = [0] * (용량 + 1)
    
    for i in range(n):
        # 뒤에서 앞으로 순회해야 이전 라운드 결과를 덮어쓰지 않음
        for w in range(용량, 무게들[i]-1, -1):
            dp[w] = max(dp[w], dp[w-무게들[i]] + 가치들[i])
    
    return dp[용량]