[TIL] 2026-06-17 — 알고리즘 시험: 그리디·DP·백트래킹 3문제

게시 2026/06/17

By GoldBoll

15 분읽는 시간

오늘은 알고리즘 시험으로 세 문제를 풀었다. 패러다임이 각각 다르다 — 그리디(회의실 배정), DP(계단 오르기), 백트래킹+가지치기(MT 장보기). 세 문제 모두 “정답 코드를 짜는 법”보다 틀리기 쉬운 한 끗이 핵심이었다. 그리디는 정렬 기준, DP는 초기값과 점화식, 백트래킹은 분기 검사 순서. 각 문제에서 “왜 그렇게 해야 통하는지”를 정리한다.

오늘 한 일 요약

회의실 배정(그리디 / 활동 선택)을 종료 시간 오름차순 정렬로 풀어 정렬 기준의 중요성을 확인
계단 오르기(DP)를 1·2칸(피보나치)·1·2·3칸(트리보나치)으로 나눠 풀고 DP 4단계 프레임을 적용
MT 장보기(백트래킹+가지치기)에서 분기 검사 순서를 잡고, 가지치기가 정답이 아니라 탐색량만 줄인다는 걸 노드 수로 직접 측정
세 문제 모두 채점 테스트 전부 통과

1. 회의실 배정 — 그리디는 “기준”이 전부

회의실이 하나뿐이고, 각 회의는 [시작, 종료) 반열린 구간이다. 한 회의가 끝나는 시각에 다음 회의를 바로 시작할 수 있다. 겹치지 않게 배정할 수 있는 최대 회의 수를 구하는 문제 — 전형적인 활동 선택(Activity Selection) 그리디다.

틀리기 쉬운 포인트: 정렬 기준

그리디 문제는 “어떤 기준으로 정렬/선택하느냐”가 정답과 오답을 가른다. 이 문제의 올바른 기준은 종료 시간 오름차순이다.

  
// 종료 시간 오름차순 — 일찍 끝나는 회의 우선
bool compareMeeting(const Meeting& a, const Meeting& b) {
    return a.end < b.end;
}

시작 시간순으로 정렬하면 틀린다. 시작이 가장 이른 긴 회의 하나(예: (1,10))를 먼저 골라버리면 그 회의가 방을 10까지 독점해, 그 안에 안 겹치게 들어갈 수 있던 짧은 회의 여러 개를 모두 놓친다. 결과적으로 1개만 고르고 끝나는데, 최적은 3개일 수 있다.

종료 시간순이 옳은 이유는 직관적이다 — 회의를 일찍 끝낼수록 뒤에 남는 시간이 최대가 되어 더 많은 회의를 담을 여지가 생긴다. 이게 활동 선택 그리디의 정당성(greedy choice property)이다.

선택 조건: 반열린 구간이라 `>=`

  
int lastEnd = 0;   // 마지막으로 선택한 회의의 종료 시각
for (const Meeting& m : meetings) {
    if (m.start >= lastEnd) {   // 직전 회의가 끝난 뒤(또는 끝나자마자) 시작
        count++;
        lastEnd = m.end;
    }
}

조건이 > 가 아니라 >= 인 이유는 구간이 [start, end) 반열린 구간이기 때문이다. 직전 회의가 end에 끝나고 다음 회의가 같은 start == end 시각에 시작하는 건 겹치지 않으므로 허용해야 한다. 여기서 >로 잘못 쓰면 “끝나자마자 시작하는 회의”를 놓쳐 답이 작아진다.

검증

{(0,5),(5,6),(2,7),(6,8),(1,9),(8,9)}를 종료 시간순으로 정렬한 뒤 그리디로 고르면 (0,5)→(5,6)→(6,8)→(8,9) 4개가 선택된다. 시간복잡도는 정렬이 지배해 O(N log N).

2. 계단 오르기 — 점화식을 직접 세운다 (DP)

n개의 계단을 한 번에 1칸 또는 2칸(Part B는 1·2·3칸)씩 오를 때, n번째 계단에 도달하는 서로 다른 방법의 수를 구한다. DP를 4단계 프레임으로 푸는 연습이었다.

DP 4단계 프레임

상태 정의: dp[i] = i번째 계단에 도달하는 방법의 수
점화식: i번째 직전에 있던 위치(1·2·(3)칸 전)의 방법 수를 모두 더한다
초기값: 바닥 포함해서 기저를 정한다
복잡도: O(n)

Part A — 1·2칸 (피보나치)

  
dp[0] = 1;               // 바닥에 그대로 있는 것도 1가지
if (n >= 1) dp[1] = 1;   // 1번 계단: (1) 한 가지
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];   // 직전엔 i-1(1칸 전) 또는 i-2(2칸 전)
}

i번째 계단에 오는 마지막 걸음은 “1칸 전에서 1칸” 또는 “2칸 전에서 2칸” 둘뿐이다. 그래서 dp[i] = dp[i-1] + dp[i-2] — 피보나치 수열이 된다.

틀리기 쉬운 포인트: 초기값 `dp[0] = 1`

dp[0]을 0이 아니라 1로 둬야 점화식이 맞는다. “바닥(0번 계단)에 그냥 서 있는 것”도 하나의 방법으로 세야, dp[2] = dp[1] + dp[0] = 1 + 1 = 2처럼 작은 값들이 올바르게 맞춰진다. dp[0]=0으로 두면 전체가 어긋난다. 기저값이 점화식의 토대라서, 여기서 한 칸만 틀려도 전부 틀린다.

Part B — 1·2·3칸 (트리보나치)

  
dp[0] = 1;
if (n >= 1) dp[1] = 1;
if (n >= 2) dp[2] = 2;   // (1+1), (2) → 2가지
for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];   // 세 경우 합
}

3칸 점프가 추가되면 마지막 걸음의 경우가 세 가지(1·2·3칸 전)로 늘어, dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 트리보나치가 된다. dp[2]=2라는 초기값을 하나 더 잡아줘야 i=3부터 점화식이 세 항을 모두 참조할 수 있다. 검증: climbStairs3(12) = 927 (트리보나치 1,1,2,4,7,13,24,44,81,149,274,504,927).

왜 DP인가 — 순수 재귀의 함정

이 점화식을 그냥 재귀로 짜면 f(i) = f(i-1) + f(i-2)가 같은 부분문제를 중복 계산한다. 호출 트리가 지수적으로 불어나 O(2^n)이 되고, n이 조금만 커져도 매우 느려진다. DP 테이블(또는 메모이제이션)로 각 dp[i]를 한 번만 계산해 저장하면 O(n)으로 떨어진다. “중복 부분문제 + 최적 부분구조”가 보이면 DP를 쓰라는 신호다.

3. MT 장보기 — 백트래킹과 가지치기

양수 가격 목록에서 몇 개를 골라 합이 예산(target)과 정확히 같아지는 조합이 몇 가지인지 센다. 각 상품은 “담는다 / 안 담는다” 두 갈래라, 부분집합 합(subset sum)을 백트래킹으로 모두 탐색하는 문제다. (prices는 오름차순 정렬되어 들어온다.)

틀리기 쉬운 포인트: 분기 검사 순서

재귀 함수 맨 위의 세 종료 조건은 성공 → 가지치기 → 실패 순서로 둬야 한다.

  
long long countWays(const vector<int>& prices, int idx, int sum, int target) {
    explored++;
    if (sum == target) return 1;                  // 성공: 정확히 맞음
    if (sum > target)  return 0;                  // 가지치기: 이미 초과
    if (idx == (int)prices.size()) return 0;      // 실패: 다 봤는데 못 맞춤

    long long withItem    = countWays(prices, idx + 1, sum + prices[idx], target);
    long long withoutItem = countWays(prices, idx + 1, sum, target);
    return withItem + withoutItem;
}

성공 검사(sum == target)를 실패 검사(idx == size)보다 먼저 둬야 한다. 만약 실패 검사를 먼저 두면, 마지막 상품을 담아 정확히 예산을 맞춘 조합(예: 마지막 원소 {10} 단독으로 딱 10을 만든 경우)이 “인덱스를 끝까지 다 봤다”는 이유로 실패 처리되어 누락된다. 실제로 순서를 바꾸면 테스트4(상품 10개, 예산 10)의 답이 10이 아니라 9로 줄어든다.

성공을 먼저 검사하는 게 정당한 이유는 가격이 모두 양수라서다. sum == target이 된 순간, 더 담으면 반드시 초과하므로 그 자리에서 1로 확정하고 멈춰도 된다.

가지치기는 정답을 바꾸지 않는다 — 탐색량만 줄인다

sum > target이면 0을 반환하고 더 내려가지 않는 게 가지치기다. 양수만 있으니 이미 초과한 합은 더 담아도 절대 target으로 돌아올 수 없어서, 그 아래 가지를 통째로 잘라낸다.

핵심은 가지치기가 결과값(정답)을 바꾸지 않고 탐색량(노드 수·속도)만 줄인다는 점이다. 테스트4(상품 1~10, 예산 10)에서 직접 측정한 결과:

가지치기	탐색 노드 수	정답
적용	349	10
제거	1701	10

가지치기를 빼면 노드 수가 349에서 1701로 약 5배 늘지만, 답은 10으로 똑같다. 가지치기는 “맞는 답을 더 빨리 찾는” 최적화이지, 답 자체를 만드는 로직이 아니라는 걸 숫자로 확인했다.

검증

{5,12,8,3,7}, 예산 15 → 3 (탐색 49 / 최대 63)
{2,4,6,8}, 예산 10 → 2 (탐색 27 / 최대 31)
{3,3,3}, 예산 6 → 3 (탐색 13 / 최대 15)
{1..10}, 예산 10 → 10 (탐색 349 / 최대 2047)

정렬은 백트래킹의 동반자다 — 오름차순으로 들어오기에 가지치기(sum > target)가 더 일찍, 더 자주 발동해 탐색량을 줄인다.

오늘 배운 것 정리

그리디는 정렬 기준이 전부다. 회의실 배정에서 시작 시간순은 긴 회의가 방을 독점해 오답을 낸다. “일찍 끝낼수록 뒤에 남는 시간 최대화” — 종료 시간 오름차순이라야 활동 선택이 성립한다. 그리고 반열린 구간이라 선택 조건은 >=.
DP는 초기값과 점화식의 한 칸이 전체를 좌우한다. dp[0]=1(바닥에 그냥 있는 1가지)로 둬야 피보나치/트리보나치 점화식이 작은 값부터 맞아 떨어진다. 같은 점화식을 순수 재귀로 짜면 중복 계산으로 O(2^n), DP로 저장하면 O(n).
백트래킹은 분기 검사 순서가 정답을 가른다. 성공(sum==target)을 실패(idx==size)보다 먼저 검사해야 마지막 원소로 딱 맞춘 조합을 놓치지 않는다. 양수 전제라서 성공 즉시 확정이 정당하다.
가지치기는 답이 아니라 속도다. 349 vs 1701 노드 — 가지치기를 빼도 정답 10은 불변. 가지치기는 탐색 공간을 줄이는 최적화이지 정답을 만드는 로직이 아니라는 걸 노드 수로 직접 측정해 확인했다.

TIL, 알고리즘