핵심 요약
- 함정 분석 (Lucky Pass): 작성하신 코드는 최악의 경우 10억 번 이상의 연산을 수행하는 O(NM2) 로직입니다. 이는 테스트 케이스의 허점으로 인해 통과된 것일 뿐, 실제 인터뷰나 정교한 코딩 테스트에서는 100% ‘시간 초과’ 판정을 받게 됩니다.
- 문제의 본질 (Circular Dependency): 같은 행 내에서 좌측 이동과 우측 이동이 동시에 가능할 때, DP 테이블의 갱신 순서(Topological Order)가 꼬이는 현상을 그래프 이론 관점에서 분석합니다.
- 해결 솔루션 (Directional Split): 복잡한 양방향 의존성을 ‘왼쪽에서 오는 흐름(Left-to-Right DAG)’과 ‘오른쪽에서 오는 흐름(Right-to-Left DAG)’이라는 두 개의 단방향 비순환 그래프로 분리하여 해결하는 테크닉을 다룹니다.
- 성능 최적화: 매 좌표마다 반복문을 돌리는 중복을 제거하고, 3회의 선형 스캔(Linear Scan)만으로 O(NM) 복잡도를 달성하는 전체 과정을 코드로 증명합니다.
목차
- 1. 서론: 의외로 중첩 루프도 정답
- 2. 중첩 루프가 위험한 이유: O(NM²)
- 3. 순환 참조를 끊는 Directional Split
- 4. 점화식 유도: 3-Pass Scan 전략
- 5. 최종 구현 및 코드 분석
- 6. 결론: DP의 무방향성을 제어하는 법
1. 서론: 의외로 중첩 루프도 정답
백준 2169번 ‘로봇 조종하기’는 아주 교묘한 함정을 파놓은 문제입니다. 겉보기에는 전형적인 격자형 DP(Grid DP) 문제처럼 보입니다. 왼쪽 위 (0, 0)에서 출발하여 오른쪽 아래 (N-1, M-1)까지 가치의 합을 최대화하며 이동하는 것, 아주 익숙한 패턴입니다.
하지만 “왼쪽, 오른쪽, 아래쪽으로 이동 가능”하다는 조건 하나가 이 문제의 난이도를 급격히 올립니다. 일반적인 DP 문제는 이동 방향이 ‘우측’과 ‘하단’으로 고정되어 있어 계산의 순서가 명확합니다. 반면, 이 문제는 같은 행 안에서 좌우로 자유롭게 움직일 수 있다는 점이 문제입니다.
우선, 이 문제를 “특정 지점에 도착했을 때, 왼쪽이나 오른쪽으로 갈 수 있는 모든 경우의 수를 반복문으로 직접 더해보는 방식”으로 시도해보면 채점 결과는 ‘맞았습니다’가 나옵니다. 하지만 냉정하게 말씀드리자면, 그 풀이는 운이 좋아서 통과된 가짜 정답입니다. 만약 테스트 케이스가 조금만 더 악랄했거나 N, M이 조금만 더 컸다면 여지없이 ‘시간 초과(Time Limit Exceeded)’를 받았을 것입니다. 오늘은 왜 기존 풀이가 위험한지 수치적으로 증명하고, 이 유형의 ‘진짜 해법’인 Directional Split DP가 무엇인지 깊이 있게 파고들어 보겠습니다.
2. 중첩 루프가 위험한 이유: O(NM²)
먼저 독자님께서 작성하신 코드를 분석해 보겠습니다. 이 코드는 직관적이지만, 알고리즘 효율성 측면에서는 치명적인 결함을 안고 있습니다.
Code (Time Limit Exceeded Risk)
import java.util.*;
class Main {
static int MIN = -1_000_000_000;
public int solution(int n, int m, int[][] map) {
int[][] dp = new int[n][m];
for (int i=0; i<n; i++) Arrays.fill(dp[i], MIN);
// 1행 초기화
dp[0][0]=map[0][0];
for (int j=1; j<m; j++) dp[0][j]=dp[0][j-1]+map[0][j];
// DP 진행
for (int i=1; i<n; i++) {
for (int j=0; j<m; j++) {
int lt=j, rt=j;
int ltSum=0, rtSum=0;
// [Critical Section] 왼쪽 탐색: 최악의 경우 M회 반복
while (lt>=0) {
ltSum+=map[i][lt];
dp[i][j]=Math.max(dp[i][j],dp[i-1][lt]+ltSum);
lt--;
}
// [Critical Section] 오른쪽 탐색: 최악의 경우 M회 반복
while (rt<m) {
rtSum+=map[i][rt];
dp[i][j]=Math.max(dp[i][j],dp[i-1][rt]+rtSum);
rt++;
}
}
}
return dp[n-1][m-1];
}
}Big-O Analysis: 왜 10초가 걸리는가?
위 코드의 성능을 빅오(Big-O) 표기법으로 분석해보겠습니다. 코드의 핵심부는 3중 중첩 반복문으로 구성되어 있습니다.
- Outer Loop (i): 행의 개수
N만큼 반복합니다. - Middle Loop (j): 열의 개수
M만큼 반복합니다. - Inner Loop (while):
lt와rt변수를 통해 현재 행의 다른 열들을 탐색합니다. 특정 지점(i, j)에서 좌우로 끝까지 이동한다고 가정하면, 내부 연산 횟수는M에 비례합니다.
이를 수식으로 표현하면 총 연산 횟수 T(N, M)은 다음과 같습니다.
T(N, M) ≈ Σ (from i=1 to N) Σ (from j=1 to M) (M) = N × M × M = O(NM2)
문제의 제약 조건인 N, M ≤ 1,000을 대입해 봅시다.
1,000 × 1,000 × 1,000 = 1,000,000,000 (10억)
일반적인 Online Judge 시스템(Java 기준)은 1초당 약 1억 회(108)의 연산을 처리할 수 있습니다. 즉, 이 코드는 이론적으로 약 10초가 소요되며, 문제의 시간 제한인 1초를 10배나 초과하게 됩니다.
3. 순환 참조를 끊는 Directional Split
이 문제를 O(NM)으로 최적화하기 위해서는 DP의 기본 원리인 ‘부분 문제의 최적해를 이용한 전체 최적해 도출(Optimal Substructure)’을 만족시키면서, 중복 연산을 제거해야 합니다.
순환 참조(Circular Dependency)의 딜레마
일반적인 격자 DP(우측, 하단 이동만 허용)는 데이터의 흐름이 한 방향으로만 흐르기 때문에 (i-1, j)나 (i, j-1)의 계산이 끝났음이 보장됩니다. 하지만 이 문제는 같은 행 내에서 좌우 이동(Left ↔ Right)이 가능합니다.
dp[i][j]를 구하려면 왼쪽 값dp[i][j-1]이 필요할 수 있습니다.- 동시에 오른쪽 값
dp[i][j+1]이 필요할 수도 있습니다. - 하지만
dp[i][j+1]은 다시dp[i][j]를 필요로 합니다.
이러한 상호 의존성(Cycle) 때문에 단일 점화식으로는 값을 확정할 수 없습니다. 이를 해결하기 위해 우리는 문제를 분해(Decomposition)해야 합니다.
Directional Split (방향 분리) 전략
로봇은 한 번 방문한 곳을 다시 방문하지 않습니다. 따라서 한 행(Row) 내에서의 움직임은 연속된 ‘좌에서 우’ 흐름이거나, ‘우에서 좌’ 흐름 중 하나입니다. 이 두 가지 경우를 독립된 사건으로 분리하여 계산한 뒤 병합(Merge)하면 사이클을 제거할 수 있습니다.
4. 점화식 유도: 3-Pass Scan 전략
우리는 한 행(Row)을 처리할 때, 다음 3단계의 선형 스캔(Linear Scan)을 통해 값을 확정합니다.
Step 1: Left-to-Right Scan (L -> R)
왼쪽에서 오른쪽으로 이동하는 흐름만 고려하는 임시 배열 L[j]를 만듭니다.
L[j] = Max(위에서 내려옴, 왼쪽에서 옴) + 현재 값- 점화식:
L[j] = Max(dp[i-1][j], L[j-1]) + map[i][j]
Step 2: Right-to-Left Scan (R -> L)
오른쪽에서 왼쪽으로 이동하는 흐름만 고려하는 임시 배열 R[j]를 만듭니다.
R[j] = Max(위에서 내려옴, 오른쪽에서 옴) + 현재 값- 점화식:
R[j] = Max(dp[i-1][j], R[j+1]) + map[i][j]
Step 3: Merge
이제 (i, j)에 도달하는 최적의 값은, 왼쪽 흐름을 탔을 때의 최대값(L[j])과 오른쪽 흐름을 탔을 때의 최대값(R[j]) 중 더 큰 값입니다.
dp[i][j] = Max(L[j], R[j])
5. 최종 구현 및 코드 분석
위의 전략을 적용한 최종 코드입니다. 3중 반복문(While)을 제거하고, 행(Row)마다 3번의 선형 스캔만 수행하므로 시간 복잡도는 O(3NM), 즉 O(NM)으로 수렴합니다.
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
dp = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1. 첫 번째 줄 초기화 (왼쪽 -> 오른쪽 이동만 가능)
dp[0][0] = map[0][0];
for (int j = 1; j < M; j++) {
dp[0][j] = dp[0][j - 1] + map[0][j];
}
// 2. 두 번째 줄부터 N번째 줄까지 DP 수행
for (int i = 1; i < N; i++) {
int[] tempL = new int[M];
int[] tempR = new int[M];
// [Step 1] Left -> Right Scan
// 0번 열은 왼쪽에서 올 수 없으므로, 위(i-1)에서 내려오는 경우만 가능
tempL[0] = dp[i - 1][0] + map[i][0];
for (int j = 1; j < M; j++) {
// (위에서 내려옴) vs (왼쪽에서 옴) 중 큰 값 선택
tempL[j] = Math.max(dp[i - 1][j], tempL[j - 1]) + map[i][j];
}
// [Step 2] Right -> Left Scan
// M-1번 열은 오른쪽에서 올 수 없으므로, 위(i-1)에서 내려오는 경우만 가능
tempR[M - 1] = dp[i - 1][M - 1] + map[i][M - 1];
for (int j = M - 2; j >= 0; j--) {
// (위에서 내려옴) vs (오른쪽에서 옴) 중 큰 값 선택
tempR[j] = Math.max(dp[i - 1][j], tempR[j + 1]) + map[i][j];
}
// [Step 3] Merge
// 두 방향의 결과 중 최댓값을 dp[i][j]에 확정
for (int j = 0; j < M; j++) {
dp[i][j] = Math.max(tempL[j], tempR[j]);
}
}
System.out.println(dp[N - 1][M - 1]);
}
}이 최적화를 통해 연산 횟수는 10억 번에서 약 300만 번으로 줄어듭니다. 이는 약 333배 이상의 성능 향상이며, 어떠한 데이터가 들어와도 1초 내 수행을 보장합니다.
6. 결론: DP의 무방향성을 제어하는 법
백준 2169번은 단순한 구현력이 아니라 알고리즘의 시간 복잡도에 대한 감각을 묻는 문제입니다. “정답이 나왔다”는 사실에 안주하지 않고, “이게 왜 시간 내에 동작하는가?”를 끊임없이 의심해야 합니다.
오늘 배운 Directional Split DP 기법은 비단 이 문제뿐만 아니라, 특정 축을 기준으로 양방향 이동이 가능한 모든 격자형 문제(예: 빗물 받기, 특정 조건의 최단 경로 등)에 범용적으로 적용되는 강력한 패턴입니다. 복잡하게 얽힌 의존성(Dependency)을 만났을 때, 당황하지 말고 “방향별로 쪼개서 생각하자”는 원칙을 기억하시기 바랍니다.