[초안] Java 라이브 코딩: 동적 계획법(Dynamic Programming) 기본기

왜 지금 이 주제인가

라이브 코딩 면접에서 동적 계획법(이하 DP)이 나왔을 때 떨어지는 사람과 통과하는 사람의 차이는 알고리즘 지식이 아니라 접근 방식의 명료함에 있다. DP는 BFS/DFS처럼 템플릿이 떨어지지 않고, 매 문제마다 “상태를 어떻게 정의할 것인가”를 새로 정해야 한다. 그래서 면접관 앞에서 가장 많이 무너지는 유형이기도 하다.

특히 HackerRank 스타일의 라이브 코딩에서는 다음과 같은 흐름이 거의 정형화되어 있다.

1. 문제를 본다.
2. 면접관에게 접근을 1~2분 안에 설명한다.
3. 점화식을 칠판/주석에 적는다.
4. 코드를 친다.
5. 작은 입력으로 손-trace 해 본다.
6. 시간 복잡도를 말한다.

이 흐름에서 “DP인 것 같다”까지는 누구나 가지만, 상태 정의를 말로 또렷하게 설명하지 못해서 거기서부터 발이 꼬이는 경우가 많다. 이 문서는 그 구간을 메우는 데 초점을 맞춘다.

DP란 무엇인가 — 한 문장 정의부터 다시

DP를 한 문장으로 정의하면 이렇다.

작은 부분 문제의 답을 한 번만 계산해서 저장해두고, 큰 문제의 답을 그 부분 문제들의 답으로 조합해서 만드는 기법.

이 정의에서 핵심 두 가지가 등장한다.

• Optimal substructure(최적 부분 구조): 큰 문제의 최적해가 작은 문제의 최적해로부터 만들어질 수 있어야 한다.
• Overlapping subproblems(중복 부분 문제): 같은 작은 문제가 여러 번 등장해야 한다. 한 번만 등장하면 그냥 분할 정복(divide and conquer)이지 DP가 아니다.

라이브 코딩에서 면접관에게 “이 문제가 DP라고 판단한 근거가 뭔가요?”라는 질문을 받으면, 위 두 조건을 자기 문제의 언어로 풀어 설명할 수 있어야 한다. 예를 들어 계단 오르기 문제라면 이렇게 말한다.

n번째 계단에 도달하는 경우의 수는 (n-1)번째에서 한 칸, (n-2)번째에서 두 칸 올라온 경우의 합으로 만들어집니다(최적 부분 구조). 그리고 재귀로 풀면 같은 f(k)가 여러 번 호출되니까 메모이제이션 이득이 있어서 DP로 풉니다(중복 부분 문제).

이 두 문장만 면접관 앞에서 또렷하게 말할 수 있어도 시작이 절반 이상 끝난다.

점화식을 세우는 순서 — 라이브 코딩에서의 5단계

점화식을 “감”으로 세우려고 하면 무너진다. 항상 다음 5단계로 진행한다.

1단계 — 무엇이 답인지부터 적는다

문제를 풀기 시작하기 전에 답이 무엇인지 한 줄로 적는다.

문제: 정수 배열 nums가 주어질 때, 인접하지 않은 원소만 골라 만들 수 있는 최대 합을 구하라.
답: 인접하지 않은 원소의 부분집합 중 합이 최대인 값

답을 적지 않은 채로 점화식을 만지면, 자기가 지금 무엇을 구하고 있는지 잊어버린다. 이건 5분만 헤매도 면접관이 인지한다.

2단계 — 상태(state)를 정의한다

상태는 “DP 테이블의 한 칸이 의미하는 것”이다. 보통 이렇게 적는다.

dp[i] = nums[0..i]까지만 봤을 때, 인접하지 않은 원소를 골라 만들 수 있는 최대 합

상태 정의는 반드시 다음 세 가지를 포함해야 한다.

• 인덱스(또는 매개변수)가 무엇을 의미하는지
• “지금까지의 무엇을 보았는지” 또는 “지금 어디에 있는지”
• 그 시점에서 우리가 저장하는 값이 무엇인지 (최댓값? 개수? 가능 여부?)

상태 정의가 모호하면 점화식도 모호해진다. 거꾸로 말하면, 점화식이 잘 안 떠오를 때는 상태 정의가 잘못된 경우가 90%다.

3단계 — 점화식(transition)을 만든다

상태 i를 작은 상태들로부터 만드는 식을 적는다.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

이 식의 의미를 면접관에게 말로 풀 수 있어야 한다.

인덱스 i를 안 쓰면 답은 dp[i-1] 그대로고, 인덱스 i를 쓰면 i-1은 못 쓰니까 dp[i-2] + nums[i]가 됩니다. 둘 중 큰 쪽이 dp[i]가 됩니다.

4단계 — 초기값(base case)을 정한다

가장 자주 실수하는 구간이다. 보통 0번째, 1번째 인덱스를 직접 손으로 계산해 적어둔다.

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

초기값을 0으로 그냥 두는 실수가 많다. 점화식이 max를 쓰는 경우 0이 정답이 되어버려 모든 답이 0으로 망가질 수 있다.

5단계 — 답이 어디에 있는지 적는다

정답: dp[n-1]

이 단계를 빠뜨리면 “계산은 다 했는데 답을 어디서 꺼내지?” 하면서 마지막 줄에서 멈춘다.

Top-down vs Bottom-up — 어느 쪽을 쓸 것인가

라이브 코딩에서의 권장은 Bottom-up 우선이다. 이유는 세 가지다.

1. 면접관이 dp 배열을 직접 출력해서 같이 봐줄 수 있어 디버깅이 빠르다.
2. 시간/공간 복잡도를 설명하기 직관적이다.
3. 입력 사이즈가 클 때 스택 깊이 사고가 안 난다.

다만 트리/그래프 위 DP, 또는 “모든 부분 문제가 다 필요한 게 아닐 때”는 Top-down이 더 자연스럽다. 면접관에게는 이렇게 말하면 좋다.

기본은 bottom-up으로 가겠습니다. 다만 상태 공간이 큰데 실제 방문하는 상태가 적다면 top-down + 메모이제이션이 더 효율적이라 그 경우엔 바꾸겠습니다.

상태 정의에서 자주 빠지는 함정

함정 1 — “포함했는가/안 했는가”를 상태에 안 넣음

배낭(knapsack)류 문제에서 “지금 원소를 골랐는지 여부”가 다음 결정에 영향을 주는데, 상태에 그게 없으면 점화식이 깨진다. House Robber 같은 문제를 처음 풀 때 흔히 겪는다. 해결책은 보통 두 가지다.

• 상태를 dp[i][0](안 고름), dp[i][1](고름)으로 분리
• 또는 “인접 제약을 점화식에 직접 반영” (dp[i-2] + nums[i])

함정 2 — 상태가 너무 많아서 시간/공간이 터짐

상태에 차원을 자꾸 늘리다 보면 O(n^3)이 쉽게 나오고, 그러다 메모리 한계도 넘는다. 라이브 코딩에서 “상태가 4차원이 되었어요”라고 말하는 순간 면접관은 다른 정의를 시도해 보라는 신호로 받아들인다. 줄이는 방법은:

• 상태 압축(롤링 배열): dp[i]가 dp[i-1], dp[i-2]만 본다면 변수 두 개로 충분
• 상태 차원 합치기: 두 정수 상태를 (a*MAX + b)로 묶기
• 정렬/그룹화로 한 차원 제거

함정 3 — 초기값을 0이 아닌 값으로 둬야 하는데 잊음

“최솟값 DP”에서 가장 흔하다. 초기값을 0으로 두면 점화식의 min이 항상 0이 되어 답이 무너진다. 이 경우엔 Integer.MAX_VALUE로 초기화하고, 더하기 연산에서 오버플로 안 나도록 조건 분기를 둬야 한다.

if (dp[i - coin] != Integer.MAX_VALUE) {
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}

메모이제이션 누락 실수 — 라이브에서 가장 흔한 죽음

Top-down으로 풀 때 다음과 같은 코드를 쓰는 사람이 매우 많다.

int solve(int i) {
    if (i == 0) return nums[0];
    if (i == 1) return Math.max(nums[0], nums[1]);
    return Math.max(solve(i - 1), solve(i - 2) + nums[i]);
}

이 코드는 DP가 아니다. 단순한 재귀이고, 시간 복잡도는 O(2^n)이다. 메모이제이션을 빼먹은 순간 “저는 DP를 풀었습니다”라고 말할 수 없다. 올바른 형태는 다음과 같다.

Integer[] memo;
 
int solve(int i) {
    if (i == 0) return nums[0];
    if (i == 1) return Math.max(nums[0], nums[1]);
    if (memo[i] != null) return memo[i];
    return memo[i] = Math.max(solve(i - 1), solve(i - 2) + nums[i]);
}

라이브에서는 메모를 적는 줄을 의도적으로 강조해서 말한다.

여기서 memo에 저장하지 않으면 같은 i가 지수적으로 호출되니, 반드시 저장 먼저 합니다.

구현 시 흔한 버그 모음

라이브 코딩 도중 자주 터지는 버그를 미리 알면 손이 멈추지 않는다.

• off-by-one: dp 배열 길이를 n으로 잡았는데 dp[n]을 참조 → ArrayIndexOutOfBoundsException. 보통 길이를 n+1로 잡고 1-indexed로 푸는 게 안전하다.
• base case 누락: n == 0, n == 1을 처리 안 해 NPE 또는 음수 인덱스 접근.
• 상태 갱신 순서 꼬임: 1차원 코인 변경(coin change unbounded)에서 dp[i] = dp[i] + dp[i - coin] 순서가 잘못되면 같은 동전을 한 번만 쓰는 0/1 배낭이 되어 버린다. 1차원으로 0/1 배낭을 풀 때는 거꾸로 순회해야 한다는 것도 같은 맥락이다.
• 초기값 누락으로 max/min이 망가짐: 위에서 다룸.
• 자료형 오버플로: 합/곱 DP는 long이 필요할 때가 많다. int로 받았다가 음수로 뒤집힘.
• 결과 인덱스 오해: dp[n-1]이 정답인데 dp[n]을 반환하거나 그 반대.
• Math.max / Math.min 인자 순서 의식 부족: 한 변수에 자기 자신을 비교 안 하고 덮어써 이전 후보가 사라짐.

이 목록을 머리 속에 두고 코드를 짜면, 화면 위에서 면접관이 “여기 인덱스 한번 보세요”라고 했을 때 즉답이 가능하다.

라이브 면접에서 접근 방식을 설명하는 정해진 흐름

말하는 순서를 외워두면, 머리가 하얘져도 입이 먼저 움직인다.

1. 문제 재진술: “문제는 ~를 구하는 것이고, 입력은 ~, 출력은 ~입니다.”
2. brute force 먼저: “가장 단순한 방법은 ~인데 시간복잡도가 ~라 입력 크기 N=10^5에서 안 됩니다.”
3. 관찰: “여기서 같은 부분 문제가 반복됩니다. 따라서 DP가 후보입니다.”
4. 상태 정의: “dp[i]를 ~로 정의합니다.”
5. 점화식: “dp[i] = ... 입니다. 이유는 ~입니다.”
6. 초기값: “dp[0]=, dp[1]= 입니다.”
7. 정답 위치: “정답은 dp[n-1] 입니다.”
8. 복잡도: “시간 O(N), 공간 O(N), 롤링 배열로 O(1)까지 줄일 수 있습니다.”
9. 코드 작성.
10. dry run: 작은 예제 1개 손으로 돌림.
11. 엣지 케이스: 빈 배열, 길이 1, 모두 음수 등.

이 흐름은 “문제 → 코드”로 점프하지 않게 막아주는 안전망이다. 면접관도 이 순서를 들으면 채점 항목을 하나씩 체크해 나가게 된다.

로컬 연습 환경

라이브 코딩에 대비하려면 IDE의 자동완성에 의존하지 않는 환경에서 한 번씩 풀어보는 게 좋다. HackerRank 면접은 보통 웹 기반 단일 파일 환경이다.

준비물:

• JDK 17 이상
• 단일 Main.java 파일에 푸는 습관
• Scanner로 입력 받는 패턴 1개 머리에 저장
• System.out.println 출력만으로 디버깅하는 습관

기본 골격:

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
 
        System.out.println(solve(nums));
    }
 
    static int solve(int[] nums) {
        // 여기에 DP
        return 0;
    }
}

연습할 때는 다음 규칙을 지킨다.

• 시간을 재고 푼다 (한 문제 25분 컷).
• 처음에는 “말로 접근부터 5분간 설명”을 음성으로 녹음하거나 글로 적는다.
• 다 풀면 dp 배열을 출력해서 직접 눈으로 trace 한다.
• 한 문제를 푼 직후 같은 문제를 bottom-up 또는 top-down 다른 방식으로 한 번 더 푼다.

연습 문제

다음 두 문제를 풀이는 가린 채 직접 풀어본 뒤 details 블록을 펼친다. 펼치기 전에 반드시 점화식부터 종이/주석에 적어 두는 것이 학습 효과가 크다.

문제 1 (쉬움) — 계단 오르기

한 번에 1칸 또는 2칸 오를 수 있을 때, n칸짜리 계단의 꼭대기까지 올라가는 서로 다른 방법의 수를 구하라.

• 입력: 정수 n (1 ≤ n ≤ 45)
• 출력: 가능한 방법의 수

먼저 직접 점화식을 적어볼 것.

dp[i] = dp[i-1] + dp[i-2]

dp[1] = 1
dp[2] = 2

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(climb(n));
    }
 
    static int climb(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
 
        int prev2 = 1; // dp[1]
        int prev1 = 2; // dp[2]
        int curr = 0;
        for (int i = 3; i <= n; i++) {
            curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

문제 2 (중간) — 코인 체인지(최소 동전 개수)

서로 다른 액면가의 동전 배열 coins와 정수 amount가 주어질 때, amount를 만들기 위한 동전 최소 개수를 구하라. 만들 수 없으면 -1을 반환한다. 같은 동전을 여러 번 사용할 수 있다.

• 입력: coins[] (1 ≤ 길이 ≤ 12, 1 ≤ 액면 ≤ 2^31-1), amount (0 ≤ amount ≤ 10^4)
• 출력: 최소 동전 개수, 또는 -1

먼저 직접 풀어볼 것. 그리디로 풀면 안 된다는 것을 먼저 반례로 보여주는 것이 중요하다. (예: coins = [1, 3, 4], amount = 6 → 그리디는 4+1+1=3개, 최적은 3+3=2개)

dp[v] = min over all c in coins where v - c >= 0 of (dp[v - c] + 1)

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) coins[i] = sc.nextInt();
        int amount = sc.nextInt();
 
        System.out.println(coinChange(coins, amount));
    }
 
    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
 
        for (int v = 1; v <= amount; v++) {
            for (int c : coins) {
                if (c <= v && dp[v - c] != Integer.MAX_VALUE) {
                    dp[v] = Math.min(dp[v], dp[v - c] + 1);
                }
            }
        }
 
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

면접 답변 프레이밍 — 시니어 백엔드 관점

DP 자체는 알고리즘 영역이지만, 시니어 백엔드 후보로서 답변할 때는 다음 관점을 한 줄씩 곁들이면 단순 코딩 테스트 통과자가 아니라 “설계 감각이 있는 사람”으로 보인다.

• 메모이제이션 = 캐시: “이 패턴은 백엔드에서 자주 쓰는 결과 캐싱과 동일한 사고입니다. 동일 입력 → 동일 출력 → 한 번만 계산.” 이 말로 DP와 일상 캐시를 묶는다.
• 상태 공간 = 데이터 모델링: 상태 정의의 명확함은 곧 데이터 모델 설계 감각이다. 모호한 상태 정의는 모호한 테이블 스키마와 같다고 비유 가능.
• 시간/공간 trade-off: 롤링 배열로 메모리를 줄이는 결정은, 운영 시스템에서 메모리/CPU 자원을 다루는 결정과 같은 결의 사고임을 짚는다.
• 불가능 케이스를 명시적으로 다룬다: -1 반환, NPE 가드, 오버플로 가드는 백엔드에서 invalid 응답/에러 응답을 명시적으로 분리하는 습관과 일치한다.

면접관이 “DP는 실무에서 자주 쓰나요?”라고 물으면 이렇게 답하면 자연스럽다.

매일 짠다기보다는, 결과 재사용 + 부분 문제 분해라는 사고 자체가 캐시 설계, 배치 집계, 비용 산정 같은 데서 거의 같은 모양으로 등장합니다. 그래서 DP를 익혀두는 것은 알고리즘 자체보다도 “재사용 가능한 부분 답을 어떻게 설계할 것인가”라는 백엔드 감각을 다지는 것에 가깝다고 생각합니다.

자주 묻는 꼬리 질문에 대한 짧은 답안

라이브가 끝난 뒤 받기 쉬운 후속 질문들을 미리 준비해 둔다.

• “공간을 더 줄일 수 있나요?” → “현재 점화식이 dp[i-1], dp[i-2]만 보니까 변수 두 개로 충분합니다. O(N)을 O(1)로 줄일 수 있습니다.”
• “재귀로 풀면 어떻게 달라지나요?” → “호출 그래프상 같은 i가 반복되니 메모이제이션이 필수고, 깊이가 N까지 갈 수 있어 입력이 크면 stack 위험이 있습니다. 그래서 bottom-up 선호입니다.”
• “입력이 10^7 정도로 커지면?” → “현재 O(N) 시간/메모리이니, 메모리는 문제될 수 있고 그때는 롤링 배열로 줄입니다. 시간은 보통 1초 안 들어옵니다.”
• “음수 동전이 들어오면?” → “문제 정의상 보통 양수만 가정하지만, 음수가 허용되면 동일 액수를 만드는 무한 루프가 가능해 DP 정의 자체가 깨집니다. 이 경우 다른 모델이 필요합니다.”
• “0/1 배낭처럼 같은 동전을 한 번만 쓸 수 있다면?” → “그땐 1차원 dp를 거꾸로 순회해야 합니다. 정방향이면 같은 동전을 두 번 쓰는 unbounded가 되어버립니다.”

직전 1주일 라이브 코딩 체크리스트

면접 직전 1주일 동안 매일 30분만 다음 항목을 점검하면, DP 라이브에서 무너지지 않는다.

• 점화식 5단계(답 정의 → 상태 → 점화식 → 초기값 → 정답 위치)를 빈 종이에 외워서 적을 수 있다.
• 상태 정의를 한 문장으로 또렷하게 말할 수 있다.
• base case 누락이 없는지 dp[0], dp[1]을 항상 손으로 적는다.
• top-down으로 풀 때 메모이제이션 한 줄을 빼먹지 않는다.
• 1차원 배낭에서 정방향/역방향 순회 차이를 설명할 수 있다.
• 롤링 배열로 공간을 O(1)까지 줄이는 변형을 1분 안에 보일 수 있다.
• 오버플로 가드(Integer.MAX_VALUE 체크, long 사용)를 자동으로 떠올린다.
• dry run을 위해 작은 입력 1개를 표로 그린다.
• brute force → 관찰 → DP 변환 흐름을 입으로 1분 안에 설명할 수 있다.
• 시간/공간 복잡도를 양쪽 다 말하고 끝낸다.

이 체크리스트를 완성한 상태에서 라이브에 들어가면, 알고리즘 실력이 아니라 사고의 명료함으로 통과하는 사람이 된다. DP 라이브 코딩의 합격 기준은 거의 항상 거기에 있다.