DP·탐색 문제를 푸는 사고 과정

DP 문제에서 점수가 갈리는 지점

동적 계획법 문제에서 떨어지는 사람 대부분은 점화식을 몰라서 떨어지지 않습니다. 점화식은 알거나 검색해서 찾을 수 있습니다. 갈리는 지점은 그 앞입니다. 이 문제에 왜 DP가 맞는지, 상태가 왜 그 모양이어야 하는지, 그 상태로 정말 충분한지를 말로 설명할 수 있느냐입니다. 상태 정의 없이 점화식만 튀어나오면 면접관은 그 문제를 전에 본 적이 있구나로 이해하고, 조건을 살짝 바꿔서 다시 묻습니다. 그때 무너집니다.

그래서 이 페이지는 점화식 모음이 아니라 상태를 세우는 절차를 다룹니다. 문제 하나를 잡고 상태를 정의하고, 그 정의가 맞는지 반례로 두들겨 보고, 복잡도를 계산하고, 조건이 바뀌었을 때 어디가 무너지는지까지 갑니다.

DP인지 아닌지 먼저 판단하기

모든 최적화 문제가 DP는 아닙니다. DP가 성립하려면 두 가지가 필요합니다. 하나는 최적 부분 구조, 즉 전체의 최적해가 부분 문제의 최적해로 조립된다는 성질입니다. 다른 하나는 부분 문제가 겹친다는 성질입니다. 겹치지 않으면 그냥 분할 정복이고, 메모이제이션을 붙여 봐야 메모리만 씁니다.

실전에서는 이렇게 확인합니다. 작은 입력 몇 개의 답을 손으로 적습니다. 그 답들 사이에 “n의 답은 n보다 작은 것들의 답으로 만들어진다”는 관계가 보이면 DP 후보입니다. 관계가 안 보이면 아직 상태를 잘못 잡은 것이거나 DP가 아닌 것입니다. 이 손계산 단계를 건너뛰고 바로 배열부터 잡는 습관이 실패의 대부분을 만듭니다.

연습 문제: 동전으로 금액 만들기

액면가가 여러 개인 동전이 무제한으로 있습니다. 목표 금액 target을 만드는 데 필요한 최소 동전 개수를 구하고, 만들 수 없으면 −1을 반환하십시오. 동전 종류 수는 수십 개, 목표 금액은 수만 정도라고 가정합니다.

이 문제를 고른 이유는 그리디 유혹이 있기 때문입니다. 큰 동전부터 쓰면 될 것 같지만 그렇지 않고, 왜 안 되는지 반례로 설명할 수 있느냐가 첫 관문입니다.

약한 답

“동전을 큰 것부터 정렬해서 최대한 많이 쓰고 남은 금액을 다음 동전으로 채우면 됩니다. 안 되면 DP로 dp 배열을 만들어서 dp[i] = min(dp[i-coin] + 1)로 풀면 됩니다. 복잡도는 O(n)입니다.”

강한 답

“먼저 그리디가 되는지 확인하겠습니다. 액면가가 1, 3, 4이고 목표가 6이면 그리디는 4+1+1로 3개를 쓰지만 3+3으로 2개가 최적입니다. 그래서 일반적인 액면가에서는 그리디가 깨지고, 큰 선택이 나중 선택을 제약하면서 부분 문제가 겹치므로 DP로 가겠습니다.

상태를 문장으로 정의하겠습니다. dp[a]는 금액 a를 만드는 최소 동전 개수이고, 만들 수 없으면 무한대로 둡니다. 이 정의로 충분한 이유는, 어떤 동전을 마지막에 썼든 그 이전 금액을 만드는 최적해는 그 동전이 무엇이었는지와 무관하기 때문입니다. 동전이 무제한이라 사용 이력을 기억할 필요가 없다는 점이 상태를 1차원으로 유지해 줍니다.

전이는 각 금액 a에 대해 모든 동전 c를 시도해 dp[a] = min(dp[a], dp[a-c] + 1)입니다. 초기값은 dp[0] = 0이고, 이는 아무것도 안 쓰는 것이 금액 0의 유일한 방법이라는 뜻입니다. 복잡도는 상태 수 × 전이 비용이므로 목표 금액 T와 동전 종류 수 C에 대해 O(T·C)이고, 공간은 O(T)입니다. 그리디 대비 비용을 지불하는 대신 액면가 구성에 상관없이 정답을 보장한다는 점을 얻습니다.”

무엇이 달랐는가

강한 답은 세 가지를 더 했습니다. 첫째, 그리디를 반례로 명시적으로 죽였습니다. 그냥 “그리디는 안 됩니다”가 아니라 1, 3, 4와 목표 6이라는 구체적인 숫자를 냈습니다. 반례를 만들 줄 안다는 것은 알고리즘의 성립 조건을 이해했다는 신호입니다. 둘째, 상태를 정의하면서 “왜 이 정보만으로 충분한가”를 함께 말했습니다. 이것이 DP 답변의 핵심이고, 대부분이 빠뜨리는 부분입니다. 셋째, 복잡도를 상태 수와 전이 비용의 곱으로 분해해서 말했습니다. 약한 답의 O(n)은 n이 무엇인지도 불분명하고 전이 비용을 아예 세지 않았습니다.

INF = float('inf')

def min_coins(coins, target):
    # dp[a] = 금액 a를 만드는 최소 동전 개수
    dp = [INF] * (target + 1)
    pick = [-1] * (target + 1)   # 경로 복원용: a에서 마지막에 쓴 동전
    dp[0] = 0

    for a in range(1, target + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c

    if dp[target] == INF:
        return -1, []

    # 실제로 어떤 동전을 썼는지 되짚기
    used, a = [], target
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[target], used

# 그리디가 깨지는 반례
print(min_coins([1, 3, 4], 6))   # (2, [3, 3]) — 그리디는 4+1+1로 3개

바깥 루프가 금액, 안쪽 루프가 동전인 순서에 주의하십시오. 이 순서는 “각 금액을 완성할 때 쓸 수 있는 모든 마지막 동전을 본다”는 뜻이고, 동전 무제한 사용이 자연스럽게 허용됩니다. 만약 각 동전을 한 번씩만 쓸 수 있는 문제로 바뀌면 이 루프 순서로는 답이 틀리고, 동전을 바깥 루프로 빼고 금액을 역순으로 돌아야 합니다. 루프 순서가 문제의 제약을 표현한다는 점을 설명할 수 있으면 이 영역에서 상당히 앞서 있는 것입니다.

탐색 쪽으로 넘어가면

같은 면접에서 DP와 탐색은 자주 붙어서 나옵니다. 판단 기준은 단순합니다. 답이 “최적값 하나”이고 상태가 유한하게 셀 수 있으면 DP 쪽이고, 답이 “조합 자체”이거나 상태 공간이 커서 전부 채울 수 없으면 백트래킹 쪽입니다. 백트래킹에서는 가지치기가 성능의 전부인데, 여기서 가장 흔한 사고가 정답을 잘라 버리는 가지치기입니다.

가지치기 조건을 넣을 때는 “이 조건으로 잘린 가지 안에 정답이 있을 수 있는가”를 반드시 스스로 물어야 합니다. 예를 들어 “현재까지 비용이 지금까지 찾은 최선보다 크면 중단”은 비용이 단조 증가할 때만 안전합니다. 음수 비용이 섞이면 그 가지 안에서 총합이 다시 내려갈 수 있으므로 정답을 잃습니다. 면접에서 가지치기를 제안했다면 이 단조성 전제를 같이 말해야 합니다.

후속 질문과 대응

이 영역에서 자주 나오는 실수

가장 흔한 것은 상태에 정보를 덜 넣는 것입니다. 남은 횟수나 직전 선택 같은 정보가 결정에 영향을 주는데 상태에 없으면, 같은 인덱스에서 서로 다른 답이 나와야 하는 상황이 생기고 메모이제이션이 틀린 값을 재사용합니다. 반대로 필요 없는 정보까지 상태에 넣어 차원을 늘리면 시간과 메모리가 함께 터집니다. 상태를 한 문장으로 말해 보는 습관이 양쪽을 다 막아 줍니다.

두 번째는 초기값을 대충 두는 것입니다. 0으로 채우면 “만들 수 없음”과 “0개로 만들 수 있음”이 구분되지 않아 최솟값 문제에서 조용히 틀립니다. 무한대와 0의 의미를 각각 말로 설명할 수 있어야 합니다.

세 번째는 복잡도를 배열 크기만으로 세는 것입니다. 전이마다 안쪽 루프가 도는데 그것을 빼먹으면 실제보다 훨씬 낙관적인 숫자가 나옵니다. 복잡도는 항상 상태 수 곱하기 전이 하나의 비용입니다.

네 번째는 재귀 깊이입니다. 목표 금액이 수만이면 메모이제이션 재귀는 언어 기본 설정에서 스택이 넘칩니다. 제출 후에야 발견하기 쉬운 문제라 미리 인지하고 있어야 합니다. 언어별 성능 특성은 파이썬 성능 가이드와 C++ 성능 가이드에서 확인할 수 있습니다.

답하기 전 자가 점검

• 작은 입력 두세 개의 답을 손으로 적어 보았는가
• 그리디가 안 되는 이유를 구체적인 반례로 댈 수 있는가
• 상태를 완결된 한 문장으로 말했는가
• 그 상태만으로 미래 결정이 가능한 이유를 설명했는가
• 초기값과 도달 불가 값의 의미를 구분했는가
• 복잡도를 상태 수 × 전이 비용으로 계산했는가
• 루프 순서가 문제의 제약과 일치하는지 확인했는가
• 가지치기를 넣었다면 정답을 자르지 않는 근거가 있는가

연습 방식

문제를 새로 푸는 것보다 푼 문제의 조건을 바꿔 보는 편이 효과가 큽니다. 동전을 한 번씩만 쓸 수 있게 바꾸면 루프 순서와 상태가 어떻게 변하는지, 최소 개수 대신 만드는 방법의 가짓수를 물으면 min이 sum으로 바뀌면서 초기값 의미가 어떻게 달라지는지, 동전 개수 상한이 종류별로 주어지면 상태에 무엇이 추가되어야 하는지 직접 답해 보십시오. 세 변형을 막힘없이 설명할 수 있으면 이 문제 유형은 끝난 것입니다.

기초 문법이 발목을 잡는다면 C++ 학습 라이브러리나 심층 가이드로 돌아가 손을 먼저 풀고, 문제 접근 순서 전반은 문제 해결 과정 설명에서 이어 보시기 바랍니다.

관련 언어 학습으로 복습하기