핵심 요약
- 백준 7579번(앱)은 0/1 Knapsack 문제의 변형으로, 일반적인 메모리 기준 DP 접근 시 시간 복잡도 O(NM)의 벽에 부딪히는 난이도 있는 문제입니다.
- Constraint Analysis: 문제 해결의 열쇠는 최대 1,000만에 달하는 ‘메모리’가 아니라, 합계가 10,000에 불과한 ‘비용’에 주목하여 DP 테이블의 Key-Value를 역전(Inversion)시키는 데 있습니다.
- 1D Array Optimization: 2차원 DP를 1차원으로 압축할 때 발생하는 ‘데이터 오염(Data Corruption)’ 문제를 방지하기 위해 역순 순회(Backward Iteration)가 수학적으로 필연적임을 증명합니다.
목차
- 1. 서론: 개발자를 유혹하는 ‘가성비’의 함정
- 2. 왜 메모리 기준은 실패하는가?
- 3. 관점의 대전환: 종속 변수의 역전
- 4. 0/1 Knapsack과 1차원 배열의 수학적 증명
- 5. 정답 코드 해부
- 6. 결론: 알고리즘은 제약 조건 위에서 춤춘다
1. 서론: 개발자를 유혹하는 ‘가성비’의 함정
많은 입문자가 이 문제를 처음 접했을 때 직관적으로 ‘그리디(Greedy) 알고리즘’을 떠올립니다. “비용 대비 메모리 효율(Memory per Cost)이 높은 순서대로 앱을 끄면 되지 않을까?”라는 생각입니다. 예를 들어, 비용 1로 메모리 10을 얻는 앱 A(효율 10)와 비용 10으로 메모리 100을 얻는 앱 B(효율 10)가 있다면 효율이 높은 순서대로 정렬하여 선택하는 방식입니다.
하지만 이 접근은 ‘배낭 문제(Knapsack Problem)’의 특성상 반드시 실패합니다. 그리디 알고리즘은 물건을 쪼갤 수 있는(Fractional) 상황에서는 유효하지만, 앱을 끄거나 끄지 않거나(0/1)의 선택지만 존재하는 상황에서는 최적해를 보장하지 못합니다. 효율은 좋지만 목표 메모리를 채우기 위해 불필요하게 큰 앱을 꺼야 하거나, 효율은 낮지만 딱 맞는 크기의 앱을 끄는 것이 전체 비용을 낮추는 경우가 존재하기 때문입니다. 결국, 우리는 모든 조합을 탐색하되 중복 연산을 제거하는 다이나믹 프로그래밍(DP)의 세계로 들어가야 합니다.
2. 왜 메모리 기준은 실패하는가?
DP를 적용하기로 마음먹었다면, 가장 먼저 해야 할 일은 ‘상태(State)의 정의’입니다. 보통의 배낭 문제는 “배낭의 용량(무게)만큼 채울 때의 최대 가치”를 구합니다. 이를 그대로 적용하면 다음과 같은 점화식이 나옵니다.
dp[m]=m만큼의 메모리를 확보하기 위해 필요한 최소 비용
이 정의는 논리적으로는 완벽하지만, ‘공학적 제약 조건’ 앞에서 무너집니다. 문제의 입력 조건을 정밀하게 분석해 봅시다.
- 확보해야 할 메모리 M: 최대 10,000,000 (1,000만)
- 앱의 개수 N: 최대 100
시간 복잡도와 공간 복잡도의 붕괴
만약 dp[10000000] 배열을 선언한다고 가정해 봅시다.
- 공간 복잡도 (Space Complexity): Java에서
int형은 4바이트입니다. 1,000만 개의 정수 배열은 약 40MB(10^7 * 4 bytes)를 차지합니다. 문제의 메모리 제한은 보통 128MB~256MB이므로, 40MB는 겉보기엔 허용 가능한 수치처럼 보입니다. 이것이 첫 번째 함정입니다. - 시간 복잡도 (Time Complexity): DP는 기본적으로
앱의 개수(N)×배열의 크기(M)만큼 반복합니다. 즉,100 * 10,000,000 = 1,000,000,000(10억) 번의 연산이 필요합니다. 현대의 CPU는 보통 1초에 약 1억 번의 연산을 처리합니다. 따라서 이 접근 방식은 답을 구하는 데 약 10초가 소요되며, 이는 시간 제한(통상 1초)을 10배 이상 초과하는 Time Limit Exceeded(시간 초과)로 직결됩니다.
결론적으로, ‘메모리’를 인덱스로 삼는 방식은 이 문제에서 구조적으로 불가능합니다.
3. 관점의 대전환: 종속 변수의 역전
우리는 막다른 길에 다다랐습니다. 이때 필요한 것이 바로 ‘독립 변수와 종속 변수의 역전(Inversion)’입니다. 문제의 제약 조건을 다시 살펴봅시다. 우리가 간과한 작은 숫자가 있습니다.
- 앱의 최대 비용: 100
- 앱의 개수: 100
- 가능한 최대 총비용: 100 × 100 = 10,000
1,000만이라는 거대한 숫자에 비해, 1만이라는 숫자는 너무나 작고 다루기 쉽습니다. 여기서 알고리즘의 패러다임이 바뀝니다.
기존 (불가능): 메모리m을 만들 때 → 최소 비용은? (f: Memory → Cost)
변경 (가능): 비용c를 썼을 때 → 확보 가능한 최대 메모리는? (f: Cost → Memory)
이 새로운 정의에 따르면 배열의 크기는 dp[10001]이 되며, 시간 복잡도는 100(N) * 10,000(Cost Sum) = 1,000,000 (100만) 번의 연산으로 줄어듭니다. 이는 0.01초 내에 수행 가능한 수치로, 시간 제한을 아주 여유롭게 통과할 수 있는 최적의 알고리즘이 됩니다.
4. [Deep Dive] 0/1 Knapsack과 1차원 배열의 수학적 증명
이제 점화식을 세울 차례입니다. 비용을 인덱스로 삼았으므로, 우리는 다음과 같은 로직을 전개합니다. “현재 앱을 끄지 않았을 때의 메모리”와 “현재 앱을 끄고(비용 지불), 남은 비용으로 얻었던 최대 메모리 + 현재 앱의 메모리” 중 더 큰 값을 선택합니다.
왜 반드시 ‘뒤에서부터(Backward)’ 반복해야 하는가?
독자님의 코드를 보면 for (int k=10000; k>=cost; k--)와 같이 역순으로 순회하고 있습니다. 이것은 단순한 스타일의 차이가 아니라, 1차원 배열을 사용할 때 데이터의 무결성을 보장하기 위한 수학적 필연성입니다. 이를 증명해 보겠습니다.
우리가 i번째 앱(비용 3, 메모리 10)을 처리한다고 가정해 봅시다. 그리고 DP 배열은 i-1번째 앱까지 처리된 상태입니다.
Case 1: 정방향 순회 (0 → 10,000) – 오답
k=3시점:dp[3]을 갱신합니다.dp[3] = max(dp[3], dp[0] + 10) = 10.k=6시점:dp[6]을 갱신합니다.dp[6] = max(dp[6], dp[3] + 10).
여기서 치명적인 문제가 발생합니다. dp[6]이 참조하는 dp[3]은 ‘i-1번째 단계의 값’이어야 하는데, 방금 위에서 ‘i번째 단계의 값(10)’으로 덮어쓰여졌습니다. 결과적으로 dp[6]은 20이 되며, 이는 비용 3짜리 앱을 두 번 중복 사용한 결과가 됩니다. 이는 앱을 한 번만 끌 수 있다는 0/1 배낭 문제의 대전제(Constraint)를 위반합니다.
Case 2: 역방향 순회 (10,000 → 0) – 정답
k=6시점:dp[6] = max(dp[6], dp[3] + 10). 이때dp[3]은 아직 갱신되지 않은, 즉 ‘i-1번째 단계의 순수한 값’입니다.k=3시점: 이제서야dp[3]이 갱신됩니다.
역순으로 순회하면, dp[k]를 계산할 때 참조하는 dp[k-cost]는 항상 현재 단계의 간섭을 받지 않은 과거의 데이터임이 보장됩니다. 이것이 2차원 DP(dp[i][k])를 공간 복잡도 O(C)인 1차원 DP(dp[k])로 압축할 수 있는 핵심 원리입니다.
5. 정답 코드 해부
위 설명을 토대로 정답 코드를 작성하면 아래와 같습니다.
import java.util.*;
class Main {
static int n, m;
static int[][] apps;
static int[] dp;
public static void solution() {
// ans를 최댓값으로 초기화하여 min 비교 준비
int ans = Integer.MAX_VALUE;
for (int i=0; i<n; i++) {
int cost = apps[i][0];
int mem = apps[i][1];
// [핵심 포인트 1] 역순 순회
// 최대 비용(10000)부터 현재 비용(cost)까지 내려가며 탐색
// 인덱스 k가 cost보다 작으면 dp[k-cost]가 음수 인덱스가 되므로
// 조건식 k >= cost는 유효성 검사 역할도 겸함
for (int k=10000; k>=cost; k--) {
// [핵심 포인트 2] 점화식 적용
// dp[k]: 기존에 비용 k로 얻은 메모리
// dp[k-cost] + mem: 현재 앱을 추가하여 비용 k를 만들었을 때의 메모리
dp[k] = Math.max(dp[k], dp[k-cost]+mem);
// [핵심 포인트 3] 실시간 정답 도출 (Pruning 효과)
// DP 테이블을 다 채우고 나서 다시 루프를 돌며 M 이상을 찾는 것이 아니라,
// 값을 갱신하는 즉시 목표 메모리(m) 달성 여부를 확인합니다.
// 이는 불필요한 2차 탐색을 줄이는 훌륭한 최적화입니다.
if (dp[k] >= m) ans = Math.min(ans, k);
}
}
System.out.println(ans);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
apps=new int[n][2];
// 입력 데이터 파싱 순서 준수 (문제 조건에 맞게 메모리 -> 비용 순)
for (int i=0; i<n; i++) apps[i][1]=sc.nextInt();
for (int i=0; i<n; i++) apps[i][0]=sc.nextInt();
// [핵심 포인트 4] 배열 크기 설정
// 100 * 100 = 10000 이므로 0번 인덱스 포함 10001 크기 할당
// 인덱스 초과(OutOfBounds)를 방지하는 정확한 크기 계산입니다.
dp=new int[10001];
solution();
}
}
코드 총평
이 코드는 O(N * CostSum)의 시간 복잡도와 O(CostSum)의 공간 복잡도를 가지는 가장 효율적인 해답입니다. 특히 ans 변수를 루프 내부에서 갱신하는 방식은 전체 DP 테이블을 순회하는 비용을 절감해줍니다.
6. 결론: 알고리즘은 제약 조건 위에서 춤춘다
백준 7579번 문제 풀이의 여정은 “알고리즘은 문제의 제약 조건(Constraints)에 종속된다”는 대원칙을 다시금 확인시켜 줍니다. 1,000만이라는 메모리 요구량은 우리에게 정공법을 포기하고 우회로를 찾으라는 신호였습니다. 그 신호를 읽고 ‘비용’을 기준으로 삼는 발상의 전환, 그리고 1차원 배열에서의 데이터 오염을 막기 위한 역순 순회 테크닉은 비단 이 문제뿐만 아니라 모든 최적화 문제에서 통용되는 강력한 무기입니다.
앞으로 어떤 복잡한 제약 조건이 주어지더라도, 당황하지 않고 숫자의 크기를 비교하며 “무엇을 인덱스로 삼을 것인가?”부터 고민하는 엔지니어의 시각을 가지시길 바랍니다. 이 리포트가 그 여정에 단단한 초석이 되기를 바랍니다.