BOJ 풀이 노트: 배낭 DP와 절댓값 힙 구현 점검

2026. 2. 26. · tech

BOJ 12865와 11286을 1차원 배낭 DP와 사용자 정의 비교자 우선순위 큐 관점에서 실전적으로 정리한 풀이 노트.

오늘은 DP 1문제 + 자료구조 1문제로 루틴을 구성했다.

• BOJ 12865 - 평범한 배낭
• BOJ 11286 - 절댓값 힙

두 문제 모두 정석 패턴을 정확히 구현하면 안정적으로 통과된다. 핵심은 12865에서의 역순 순회 이유, 11286에서의 우선순위 정의를 코드로 명확히 고정하는 것이다.

1) BOJ 12865 - 평범한 배낭

문제 핵심 요약

물건마다 무게와 가치가 주어질 때, 최대 허용 무게 K를 넘지 않으면서 얻을 수 있는 가치 합의 최댓값을 구하는 0/1 배낭 문제다. 각 물건은 최대 1번만 선택 가능하다.

접근 아이디어(왜 이 방법인지)

완전탐색은 경우의 수가 커서 비효율적이다. 이 문제는 전형적인 0/1 Knapsack이라 DP가 정석이다.

dp[cap] = cap 무게 한도에서 가능한 최대 가치로 두고, 각 물건 (w, v)를 보며 다음처럼 갱신한다.

• dp[cap] = max(dp[cap], dp[cap - w] + v)

여기서 핵심은 cap을 큰 값에서 작은 값으로 역순 순회하는 점이다. 그래야 같은 물건이 한 라운드에서 중복 사용되지 않는다(0/1 조건 유지).

시간/공간 복잡도

• 시간: O(N*K)
• 공간: O(K)

실수하기 쉬운 포인트

• cap을 오름차순으로 돌리면 같은 물건을 여러 번 쓰는 효과가 나서(완전 배낭처럼) 오답이 된다.
• 2차원 DP로도 풀 수 있지만, 1차원으로 줄일 때 순회 방향을 바꾸지 않으면 쉽게 틀린다.
• 입력 크기 대비 int 범위를 점검해야 한다(이 문제는 int로 충분).

C++ 코드 설명(핵심 라인)

for (int cap = K; cap >= w; --cap) {
    dp[cap] = max(dp[cap], dp[cap - w] + v);
}

한 물건을 처리할 때 역순으로 갱신해 0/1 조건을 보장하는 핵심 루프다.

vector<int> dp(K + 1, 0);

기본값 0은 “아무 물건도 선택하지 않은 상태”를 의미해 초기화가 자연스럽다.

다른 풀이 가능성

• 2차원 DP(dp[i][cap])로 상태를 더 직관적으로 표현할 수 있다.
• 분기 한정(Branch and Bound) 같은 방식도 가능하지만, BOJ 12865 범위에서는 DP가 가장 안정적이다.

2) BOJ 11286 - 절댓값 힙

문제 핵심 요약

정수 x가 주어질 때,

• x != 0이면 힙에 삽입
• x == 0이면 절댓값이 가장 작은 값을 출력/제거

절댓값이 같다면 **더 작은 실제 값(음수 우선)**을 먼저 꺼내야 한다.

접근 아이디어(왜 이 방법인지)

삽입/삭제가 반복되고, 매번 “우선순위가 가장 높은 원소”가 필요하므로 우선순위 큐가 적합하다.

다만 기본 priority_queue 정렬 기준으로는 문제 조건(절댓값 우선, 동률 시 실제값 작은 쪽 우선)을 표현할 수 없어서, 사용자 정의 비교자를 사용한다.

비교 규칙:

1. abs(a) < abs(b)이면 a가 우선
2. abs(a) == abs(b)이면 a < b가 우선

시간/공간 복잡도

• 시간: 연산당 O(log N), 전체 O(N log N)
• 공간: O(N)

실수하기 쉬운 포인트

• 절댓값 동률일 때 음수를 먼저 꺼내야 하는 조건을 빼먹기 쉽다.
• C++ priority_queue 비교자 의미(“우선순위가 낮은지”를 반환) 때문에 부등호 방향을 반대로 써서 틀리기 쉽다.
• x==0인데 힙이 비었을 때 0을 출력해야 한다.

C++ 코드 설명(핵심 라인)

if (aa == bb) return a > b;
return aa > bb;

절댓값 기준 최소 힙 + 동률 시 실제값 최소 힙 동작을 만들기 위한 비교자 핵심이다.

if (x == 0) {
    if (pq.empty()) cout << 0 << '\n';
    else { cout << pq.top() << '\n'; pq.pop(); }
}

문제의 질의 규칙을 그대로 반영한 처리 분기다.

다른 풀이 가능성

• multiset<pair<int,int>>로 (abs(x), x)를 저장해도 동일하게 구현 가능하다.
• 다만 이 문제는 priority_queue + comparator가 코드 길이와 성능 면에서 가장 간결하다.

오늘 정리 포인트:

• 12865는 역순 순회가 0/1 배낭의 핵심 안전장치다.
• 11286은 문제의 우선순위 규칙을 비교 함수로 정확히 번역하는 게 전부다.

정석 패턴 2개를 확실히 손에 익혀두면, 이후 변형 문제에서도 구현 속도와 정확도를 동시에 챙길 수 있다.