핵심 요약
- 백준 1915번(가장 큰 정사각형)은 단순 탐색 시 O(N3) 이상의 비용이 발생하는 고비용 문제입니다. 이를 O(NM)으로 최적화하는 과정은 알고리즘 최적화의 정수를 보여줍니다.
- DP의 본질: ‘현재의 해’를 구하기 위해 ‘과거의 해’를 재활용하는 메모이제이션 기법이 기하학적 도형 문제에서 어떻게 적용되는지 분석합니다.
- 점화식의 기하학적 증명:
min(왼쪽, 위, 대각선) + 1이라는 수식이 단순히 외워야 할 공식이 아니라, 정사각형 성립을 위한 ‘필요충분조건’임을 논리적으로 증명합니다. - 의존성(Dependency) 분석: 루프의 진행 방향(Top-Down vs Bottom-Up)이 DP 테이블 갱신에 미치는 치명적인 영향을 분석하며, 흔히 범하는 ‘미래 참조 오류’를 케이스 스터디로 다룹니다.
목차
- 1. 서론: 인간의 직관 vs 컴퓨터의 연산
- 2. [Deep Dive] 완전 탐색은 왜 실패하는가? (수학적 증명)
- 3. [Paradigm Shift] 관점의 이동: 시작점이 아닌 끝점
- 4. [Proof] 점화식의 기하학적/논리적 증명
- 5. [Case Study] 흔한 실수: 의존성 방향 오류
- 6. 최종 구현 및 코드 분석
- 7. [Advanced] 공간 복잡도 최적화
1. 서론: 인간의 직관 vs 컴퓨터의 연산
우리는 1,000 × 1,000 크기의 모니터 화면에서 ‘가장 큰 정사각형 창’을 찾으라고 하면 순식간에 찾아냅니다. 인간의 시각 정보 처리는 병렬적이고 패턴 인식에 특화되어 있기 때문입니다. 하지만 컴퓨터는 0과 1이라는 숫자의 나열만을 볼 뿐입니다. 컴퓨터에게 이 문제를 묻는다면, 컴퓨터는 무식하게 모든 가능성을 다 재봐야 합니다.
백준 1915번 문제는 이러한 ‘컴퓨터의 고충’을 이해하고, 어떻게 하면 컴퓨터가 효율적으로 패턴을 인식하게 할 수 있을지를 묻는 문제입니다. 특히 이 문제는 단순한 2차원 배열 탐색을 넘어, ‘자신을 포함한 부분 문제(Sub-problem)의 최적해’가 ‘전체 문제의 최적해’로 이어지는 최적 부분 구조(Optimal Substructure)를 명확히 보여주는 교과서적인 예제입니다.
2. [Deep Dive] 완전 탐색은 왜 실패하는가? (수학적 증명)
많은 입문자가 처음에는 완전 탐색(Brute Force)을 시도합니다. 이 접근법의 비용을 수학적으로 계산해 봅시다.
알고리즘 시나리오
- 격자의 모든 점
(i, j)를 순회합니다. (N × M) - 각 점을 ‘좌측 상단 꼭짓점’으로 가정합니다.
- 변의 길이
k를 1부터 점차 늘려가며, 해당 영역이 모두 ‘1’로 채워져 있는지 검사합니다.
시간 복잡도 분석
격자의 크기를 N × N이라고 가정합시다. (편의상 N=M)
- 시작점 선택: O(N2)
- 변의 길이
k확장: 최대 N까지 가능하므로 O(N) - 정사각형 내부 검사: 크기 k의 정사각형 내부가 모두 1인지 확인하려면 O(k2), 즉 최악의 경우 O(N2)
이를 모두 곱하면 총 시간 복잡도는 O(N5)에 달합니다. N=1,000이라면 1,000조 번의 연산이 필요하며, 이는 현대의 슈퍼컴퓨터로도 2초 안에 풀기 어려운 수치입니다. (내부 검사를 누적합으로 O(1)에 처리한다고 해도 O(N3)이며, 이 또한 10억 번의 연산으로 시간 제한을 초과합니다.)
결국 우리는 “검사했던 곳을 다시 검사하지 않는” 방법, 즉 DP가 필수적입니다.
3. [Paradigm Shift] 관점의 이동: 시작점이 아닌 끝점
완전 탐색의 패러다임은 “여기서 시작하면 얼마나 커질까?”입니다. 하지만 DP의 패러다임은 다릅니다. 우리는 질문을 뒤집어야 합니다.
“내가 정사각형의 우측 하단 끝점이라면, 나까지 오는 길에 얼마나 큰 정사각형이 연속되었는가?”
상태 dp[i][j]를 다음과 같이 정의합니다.
dp[i][j]: 좌표(i, j)를 우측 하단 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이.
이 정의가 강력한 이유는 ‘로컬리티(Locality)’ 때문입니다. (i, j)의 상태를 결정하기 위해 멀리 떨어진 좌표를 볼 필요 없이, 바로 인접한 이웃(왼쪽, 위, 대각선)들의 상태만 확인하면 된다는 점입니다.
4. [Proof] 점화식의 기하학적/논리적 증명
가장 중요한 점화식 dp[i][j] = min(왼쪽, 위, 대각선) + 1은 어떻게 유도되었을까요? 단순히 “셋 다 만족해야 하니까 min이다”라고 넘어가기엔 아쉽습니다. 이를 기하학적으로 증명해 봅니다.
귀류법을 통한 증명
가정: dp[i][j]가 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1보다 크다고 가정해 봅시다.
- 예를 들어, 위쪽(Up)=2, 왼쪽(Left)=2, 대각선(Diag)=2인데 내 결과가 4가 될 수 있을까요?
- 위쪽이 2라는 말은, 내 위쪽으로 2칸까지만 1이 연속되었다는 뜻입니다. 3칸 위는 0일 수도 있습니다.
- 그런데 내가 크기 4의 정사각형을 만들려면, 내 위쪽으로 최소 3칸은 1로 꽉 차 있어야 합니다.
- 이는 “위쪽이 2″라는 전제와 모순됩니다.
따라서 나의 크기는 가장 작은 이웃의 크기 + 1을 넘을 수 없습니다. (상한선 증명)
왜 하필 대각선까지 봐야 하는가?
왼쪽과 위쪽만 보면 안 될까요? 안 됩니다. 다음 케이스를 상상해 보세요.
1 1 1 1 <- 여기까지는 2x2 정사각형 0 1 <- 여기가 문제의 (i, j)
문제의 좌표 (i, j) 입장에서 봅시다.
- 위쪽
(i-1, j): 1들이 쌓여있으니 DP값 2 가능. - 왼쪽
(i, j-1): 0이라서 DP값 0.
하지만 대각선 (i-1, j-1)이 1이었다면? 위와 왼쪽 모두 2가 될 수도 있습니다.
1 1 0
1 1 1 (위쪽 DP=2)
0 1 1 (왼쪽 DP=2)
^ (나)
이 경우 위쪽도 2, 왼쪽도 2지만, 대각선 방향(왼쪽 위)에 구멍(0)이 있다면 나는 3x3은커녕 2x2도 될 수 없습니다. 정사각형은 빈틈이 없어야 하기 때문입니다. 즉, 대각선 성분은 정사각형의 '속'이 꽉 찼는지를 검증하는 역할을 합니다.
결국 세 방향 중 가장 열악한 환경(최솟값)이 나의 운명을 결정하며, 그 한계를 1칸 확장(나 자신)하는 것이 이 점화식의 진정한 의미입니다.
5. [Case Study] 흔한 실수: 의존성 방향 오류
독자님께서 처음에 범하셨던 실수는 '계산 순서(Dependency Order)'의 위반이었습니다. 이는 DP 구현 시 가장 빈번하게 발생하는 오류입니다.
미래를 참조하는 오류 (Future Reference)
독자님의 초기 코드는 (0,0)을 계산하기 위해 (0,1), (1,0), (1,1)을 참조했습니다. 하지만 이중 for문이 (0,0)에서 시작할 때, 참조 대상들은 아직 계산되지 않은 초기 상태(Raw Data)입니다.
- 현상: DP 테이블이 누적되어 커지지 않고, 1 또는 2에서 성장을 멈춤.
- 원인:
dp[i][j]를 구하는 시점에dp[i+1][j+1]은 미지의 값임.
해결책: 올바른 위상 정렬
DP는 본질적으로 DAG(Directed Acyclic Graph)의 최단/최장 경로 문제와 같습니다. 그래프의 간선 방향(의존성)에 따라 방문 순서를 정해야 합니다.
- 우측 하단 기준 점화식: 내 왼쪽, 위쪽을 참조하므로
0 -> N정방향 순회. - 좌측 상단 기준 점화식: 내 오른쪽, 아래를 참조하므로
N -> 0역방향 순회.
이처럼 점화식의 모양이 반복문의 방향을 결정한다는 사실을 명심해야 합니다.
6. 최종 구현 및 코드 분석
가장 직관적인 '우측 하단 기준 + 정방향 순회' 방식의 자바 코드입니다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
// dp[i][j]: (i, j)를 우측 하단으로 하는 최대 정사각형 한 변의 길이
// Padding: 인덱스 1부터 시작하여 i-1, j-1 참조 시 경계 검사를 제거함
long[][] dp = new long[n + 1][m + 1];
long maxSide = 0;
for (int i = 1; i <= n; i++) {
String line = br.readLine();
for (int j = 1; j <= m; j++) {
int val = line.charAt(j - 1) - '0';
// 현재 위치가 1일 경우에만 정사각형 확장을 시도
if (val == 1) {
// [핵심 로직]
// 내 주변 3곳 중 가장 작은 값 + 1
// 하나라도 0이면(빈 공간) min은 0이 되어, 나는 1(자기 자신)이 됨
dp[i][j] = Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
// val이 0이면 dp[i][j]는 0 (초기값 유지)
}
}
// 결과는 넓이이므로 변의 제곱 출력
System.out.println(maxSide * maxSide);
}
}
7. [Advanced] 공간 복잡도 최적화
위 풀이의 공간 복잡도는 O(NM)입니다. 하지만 N, M이 매우 크다면 메모리가 부족할 수 있습니다. 이를 O(M)으로 줄일 수 있을까요?
점화식을 다시 보면, dp[i][...]를 구할 때 필요한 것은 오직 바로 윗줄(i-1)의 정보뿐입니다. 그보다 더 위의 정보는 필요 없습니다.
- 따라서 N행 전체를 저장할 필요 없이, 두 개의 행(Prev, Curr)만 있으면 됩니다. (토글링 기법)
- 더 나아가, 변수 하나(temp)를 활용해
dp[i-1][j-1]값을 잠시 저장해둔다면 단 하나의 1차원 배열만으로도 구현이 가능합니다.
이러한 공간 최적화(Space Optimization) 테크닉은 현업에서 대용량 데이터를 처리하거나, 메모리 제한이 극도로 타이트한 임베디드 환경에서 매우 유용하게 사용됩니다.