프롤로그: 사건의 시작
코딩 테스트의 세계는 때로는 순수한 논리만으로 설명하기 어려운 미스터리로 가득하다. 모든 조건이 동일해 보이는데도, 사소한 차이 하나가 성공과 실패라는 극명한 결과를 낳기도 한다.
여기, 바로 그런 미스터리한 사건 파일이 하나 있다. 사건 현장은 백준 온라인 저지의 21736번 문제, "헌내기는 친구가 필요해"이다.
문제
2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.
도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. // ... 생략
불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.
이 문제를 해결하기 위해 용의선상에 오른 두 알고리즘이 있다. 완전 탐색 알고리즘인 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이다. 놀랍게도, 캠퍼스의 모든 칸을 방문해야 하는 이 문제에서 두 알고리즘의 이론적 시간 복잡도는 동일하다.
하지만 결과는 완전히 달랐다. BFS는 여유롭게 '통과'라는 판결을 받았지만, 유독 DFS에게는 '시간 초과'라는 냉혹한 판결이 내려졌다.
이론이라는 완벽한 알리바이를 가진 DFS는 정말 유죄인가? 대체 무엇이 이들의 운명을 가른 것인가?
지금부터 이 미스터리한 사건의 진실을 함께 파헤쳐 보자.
1장: 용의선상에 오른 두 알고리즘
사건을 해결하기 위해, 먼저 용의선상에 오른 두 주역을 자세히 살펴볼 필요가 있다. 이들은 그래프 탐색의 가장 대표적인 방법으로, 오랜 시간 수많은 문제 해결에 기여해 온 베테랑이다.
용의자 #1: 너비 우선 탐색 (BFS) - 신중한 지도 제작자
BFS는 시작점에서 가장 가까운 곳부터 마치 물결이 퍼져나가듯, 층(Layer)을 이루며 주변을 탐색하는 신중한 전략가다.
이 전략가는 큐(Queue) 라는 작업 목록을 사용하여, 현재 위치에서 갈 수 있는 모든 곳을 목록에 추가한 뒤, 들어온 순서대로 차근차근 방문한다.
// BFS 슈도 코드
void bfs(좌표 start) {
Queue<좌표> queue = new ArrayDeque<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
좌표 current = queue.poll(); // 목록의 가장 앞에서부터 처리
// 작업 수행...
for (좌표 next : current.getAdjacent()) {
if (!visited[next]) {
visited[next] = true;
queue.add(next); // 갈 수 있는 곳들을 목록 맨 뒤에 추가
}
}
}
}
용의자 #2: 깊이 우선 탐색 (DFS) - 열정적인 외길 탐험가
DFS는 한 방향이 막힐 때까지 무조건 직진하는 저돌적인 탐험가다.
더 이상 갈 곳이 없으면 바로 이전 갈림길로 돌아와 다른 길로 다시 깊게 파고든다. 이 탐험가는 주로 재귀(Recursion) 라는 기술을 사용하여 자신의 경로를 기억하며, 이 방식은 코드가 간결하고 직관적이라는 장점이 있다.
// DFS 슈도 코드
void dfs(좌표 current) {
visited[current] = true;
// 작업 수행...
for (좌표 next : current.getAdjacent()) {
if (!visited[next]) {
dfs(next); // 다음 경로로 즉시 깊게 파고든다
}
}
}
완벽한 알리바이: $O(N \times M)$
이 두 용의자가 가진 결정적인 알리바이는 바로 시간 복잡도다.
캠퍼스 지도의 크기가 $N \times M$일 때, 두 알고리즘 모두 모든 칸을 정확히 한 번씩만 방문하고, 각 칸의 상하좌우를 확인한다. 따라서 두 방법 모두 전체 작업을 수행하는 데 걸리는 시간은 $O(N \times M)$으로 완벽하게 동일하다.
왜 그럴까?
일반적으로 그래프 탐색의 시간 복잡도는 정점(Vertex)의 수를 V, 간선(Edge)의 수를 E라고 할 때 $O(V+E)$로 표현된다. 이는 '모든 정점을 한 번씩 방문하고($O(V)$), 모든 간선을 한 번씩 확인한다($O(E)$)'는 의미다.
이 이론을 우리 사건의 현장인 $N \times M$ 캠퍼스 지도에 적용해 보면,
- 정점(V)은 무엇인가? 🗺️
지도상의 'X'(벽)가 아닌 모든 칸('O', 'I', 'P')이 바로 정점이다. 따라서 정점의 최대 개수는 $N \times M$개가 된다. 즉, $|V| \approx N \times M$ 이다. - 간선(E)은 무엇인가? ↔️
한 칸에서 상하좌우로 이동할 수 있는 '길'이 바로 간선이다. 각 칸(정점)은 최대 4개의 이웃(간선)을 가질 수 있다. 모든 칸에 대해 간선을 고려하면, 간선의 총개수 역시 $N \times M$에 비례하게 된다. 즉, $|E| \approx 4 \times (N \times M)$ 이다.
따라서 시간 복잡도 $O(V+E)$는 $O((N \times M) + 4 \times (N \times M))$이 되고, 빅오(Big-O) 표기법에 따라 최종적으로 $O(N \times M)$ 이라는 결론이 도출된다.
결국, 두 알고리즘 모두 visited 배열을 통해 방문 여부를 철저히 검사하며 모든 칸을 딱 한 번씩만 들여다보기에, 이론상으로는 실행 시간에 차이가 있을 수 없다.
이론적으로는 그렇다. 그렇기에 이들의 운명이 달라진 것은 더욱 풀기 어려운 수수께끼가 된다. 알리바이가 확실한데, 어째서 한 명만 범인으로 지목된 것일까?
2장: 결정적 증거들 - 탐정의 수사 노트
겉으로 완벽해 보였던 DFS의 알리바이는, 그 내부를 깊숙이 들여다본 순간 균열이 드러나기 시작했다.
범행의 단서는 알고리즘의 '논리'가 아닌, '구현 방식'과 '실행 환경'이라는 예상치 못한 곳에 숨어있었다. 탐정의 수사 노트에 기록된 결정적 증거들은 다음과 같다.
증거 #1: 너무 비싼 '보고 전화' (함수 호출 오버헤드) 📞
재귀 DFS는 노드 하나를 방문할 때마다 자기 자신을 다시 호출한다. 이 '함수 호출' 이라는 행위는 생각보다 비싼 작업이다.
이는 마치 탐험가가 갈림길을 만날 때마다 본부에 전화를 걸어 현재 상태, 위치, 다음 행선지를 상세히 보고하는 것과 같다.
반면 BFS의 while 반복문은 마치 가벼운 '문자 메시지'와 같다. 다음 할 일을 목록(Queue)에 적어두고, 순서가 되면 하나씩 처리할 뿐, 거창한 '보고 전화'는 필요 없다.
<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg">
<!-- Background -->
<rect width="800" height="600" fill="#1a1a2e"/>
<!-- Title divider -->
<line x1="0" y1="300" x2="800" y2="300" stroke="#444" stroke-width="2"/>
<!-- DFS Recursive (Top half) -->
<!-- Heavy phone calls -->
<g transform="translate(50, 50)">
<!-- Explorer figure -->
<circle cx="50" cy="100" r="20" fill="#ff6b6b"/>
<rect x="45" y="120" width="10" height="30" fill="#ff6b6b"/>
<line x1="35" y1="130" x2="55" y2="140" stroke="#ff6b6b" stroke-width="3"/>
<line x1="65" y1="130" x2="45" y2="140" stroke="#ff6b6b" stroke-width="3"/>
<line x1="45" y1="150" x2="35" y2="180" stroke="#ff6b6b" stroke-width="3"/>
<line x1="55" y1="150" x2="65" y2="180" stroke="#ff6b6b" stroke-width="3"/>
<!-- Heavy phone -->
<rect x="70" y="105" width="25" height="40" fill="#2c2c54" stroke="#fff" stroke-width="2"/>
<rect x="75" y="110" width="15" height="8" fill="#4ade80"/>
<circle cx="82" cy="125" r="3" fill="#ef4444"/>
<circle cx="82" cy="135" r="3" fill="#ef4444"/>
<!-- Phone waves (heavy/expensive) -->
<g stroke="#ff4444" stroke-width="3" fill="none">
<path d="M 100 115 Q 120 105 140 115"/>
<path d="M 100 125 Q 125 110 150 125"/>
<path d="M 100 135 Q 130 115 160 135"/>
</g>
<!-- Stack operations (expensive) -->
<g transform="translate(200, 50)">
<!-- Stack tower getting taller -->
<rect x="0" y="100" width="40" height="20" fill="#ff6b6b" stroke="#fff"/>
<rect x="0" y="80" width="40" height="20" fill="#ff8787" stroke="#fff"/>
<rect x="0" y="60" width="40" height="20" fill="#ffa8a8" stroke="#fff"/>
<rect x="0" y="40" width="40" height="20" fill="#ffc9c9" stroke="#fff"/>
<rect x="0" y="20" width="40" height="20" fill="#ffe0e0" stroke="#fff"/>
<!-- Heavy arrows showing push/pop operations -->
<path d="M 50 90 L 70 90 L 65 85 M 70 90 L 65 95" stroke="#ff4444" stroke-width="3" fill="none"/>
<path d="M 70 70 L 50 70 L 55 65 M 50 70 L 55 75" stroke="#ff4444" stroke-width="3" fill="none"/>
<path d="M 50 50 L 70 50 L 65 45 M 70 50 L 65 55" stroke="#ff4444" stroke-width="3" fill="none"/>
</g>
<!-- Multiple recursive calls -->
<g transform="translate(300, 80)">
<circle cx="0" cy="0" r="15" fill="#ff6b6b"/>
<line x1="15" y1="0" x2="40" y2="-20" stroke="#ff4444" stroke-width="2"/>
<line x1="15" y1="0" x2="40" y2="0" stroke="#ff4444" stroke-width="2"/>
<line x1="15" y1="0" x2="40" y2="20" stroke="#ff4444" stroke-width="2"/>
<circle cx="55" cy="-20" r="12" fill="#ff8787"/>
<circle cx="55" cy="0" r="12" fill="#ff8787"/>
<circle cx="55" cy="20" r="12" fill="#ff8787"/>
<!-- More recursive calls -->
<line x1="67" y1="-20" x2="85" y2="-30" stroke="#ff4444" stroke-width="1"/>
<line x1="67" y1="-20" x2="85" y2="-10" stroke="#ff4444" stroke-width="1"/>
<line x1="67" y1="0" x2="85" y2="-5" stroke="#ff4444" stroke-width="1"/>
<line x1="67" y1="0" x2="85" y2="5" stroke="#ff4444" stroke-width="1"/>
<line x1="67" y1="20" x2="85" y2="10" stroke="#ff4444" stroke-width="1"/>
<line x1="67" y1="20" x2="85" y2="30" stroke="#ff4444" stroke-width="1"/>
<circle cx="95" cy="-30" r="8" fill="#ffa8a8"/>
<circle cx="95" cy="-10" r="8" fill="#ffa8a8"/>
<circle cx="95" cy="-5" r="8" fill="#ffa8a8"/>
<circle cx="95" cy="5" r="8" fill="#ffa8a8"/>
<circle cx="95" cy="10" r="8" fill="#ffa8a8"/>
<circle cx="95" cy="30" r="8" fill="#ffa8a8"/>
</g>
<!-- Performance indicator (slow) -->
<g transform="translate(550, 100)">
<rect x="0" y="0" width="100" height="20" fill="none" stroke="#ff4444" stroke-width="2"/>
<rect x="0" y="0" width="25" height="20" fill="#ff4444"/>
<text x="110" y="15" fill="#ff4444" font-family="Arial" font-size="14">2x slower</text>
</g>
</g>
<!-- BFS Iterative (Bottom half) -->
<g transform="translate(50, 350)">
<!-- Explorer figure -->
<circle cx="50" cy="100" r="20" fill="#4ade80"/>
<rect x="45" y="120" width="10" height="30" fill="#4ade80"/>
<line x1="35" y1="130" x2="55" y2="140" stroke="#4ade80" stroke-width="3"/>
<line x1="65" y1="130" x2="45" y2="140" stroke="#4ade80" stroke-width="3"/>
<line x1="45" y1="150" x2="35" y2="180" stroke="#4ade80" stroke-width="3"/>
<line x1="55" y1="150" x2="65" y2="180" stroke="#4ade80" stroke-width="3"/>
<!-- Light phone/message -->
<rect x="70" y="110" width="20" height="30" fill="#2c2c54" stroke="#4ade80" stroke-width="1"/>
<rect x="72" y="113" width="16" height="6" fill="#4ade80"/>
<circle cx="80" cy="125" r="2" fill="#4ade80"/>
<circle cx="80" cy="132" r="2" fill="#4ade80"/>
<!-- Light message waves -->
<g stroke="#4ade80" stroke-width="1" fill="none">
<path d="M 95 120 Q 110 115 125 120"/>
<path d="M 95 125 Q 110 120 125 125"/>
</g>
<!-- Queue (simple list) -->
<g transform="translate(200, 80)">
<rect x="0" y="0" width="30" height="15" fill="#4ade80" stroke="#fff"/>
<rect x="35" y="0" width="30" height="15" fill="#4ade80" stroke="#fff"/>
<rect x="70" y="0" width="30" height="15" fill="#4ade80" stroke="#fff"/>
<rect x="105" y="0" width="30" height="15" fill="#4ade80" stroke="#fff"/>
<!-- Simple arrow showing queue processing -->
<path d="M 140 7 L 160 7 L 155 3 M 160 7 L 155 11" stroke="#4ade80" stroke-width="2" fill="none"/>
</g>
<!-- Simple while loop -->
<g transform="translate(300, 80)">
<circle cx="0" cy="0" r="15" fill="#4ade80"/>
<!-- Simple loop arrow -->
<path d="M 15 0 Q 35 -20 35 0 Q 35 20 15 0" stroke="#4ade80" stroke-width="2" fill="none"/>
<path d="M 15 0 L 20 -3 M 15 0 L 20 3" stroke="#4ade80" stroke-width="2" fill="none"/>
</g>
<!-- Performance indicator (fast) -->
<g transform="translate(550, 100)">
<rect x="0" y="0" width="100" height="20" fill="none" stroke="#4ade80" stroke-width="2"/>
<rect x="0" y="0" width="90" height="20" fill="#4ade80"/>
<text x="110" y="15" fill="#4ade80" font-family="Arial" font-size="14">Fast</text>
</g>
</g>
<!-- Cost comparison visualization -->
<g transform="translate(600, 150)">
<!-- DFS cost bars -->
<rect x="0" y="0" width="30" height="80" fill="#ff6b6b"/>
<rect x="35" y="20" width="30" height="60" fill="#ff8787"/>
<rect x="70" y="40" width="30" height="40" fill="#ffa8a8"/>
<!-- BFS cost bars -->
<rect x="0" y="120" width="30" height="20" fill="#4ade80"/>
<rect x="35" y="130" width="30" height="10" fill="#6ee7b7"/>
<rect x="70" y="135" width="30" height="5" fill="#a7f3d0"/>
</g>
</svg>
예를 들어, sparcie.wordpress.com의 한 실험 보고서는, 이 '보고 전화'의 비용이 기계 코드 수준에서 얼마나 비싼지를 보여준다.
A function call and return involves a number of relatively expensive operations. Firstly information from the calling code needs to be pushed onto the stack (usually important register information), then the processor can “call” the function code which basically pushes a return address onto the stack and jumps to the function code. The first thing the newly called function must do is allocate space on the stack for its local variables... Once finished the function will... remove local variables from the stack and then return control to the code that called it.
함수 호출과 복귀는 상대적으로 비싼 여러 연산을 포함합니다. 먼저 호출하는 코드의 정보(주요 레지스터 정보 등)를 스택에 넣어야 하고, 그 다음 프로세서는 함수 코드를 "호출"할 수 있는데, 이는 기본적으로 반환 주소를 스택에 넣고 함수 코드로 점프하는 것입니다. 새로 호출된 함수가 가장 먼저 해야 할 일은 자신의 지역 변수를 위한 공간을 스택에 할당하는 것입니다... 작업이 끝나면 함수는... 지역 변수를 스택에서 제거한 다음, 자신을 호출했던 코드로 제어권을 돌려줍니다.
즉,
- 호출 전 (상태 저장): 호출하는 쪽의 현재 상태(중요 레지스터 값 등)와 돌아올 주소를 스택에 차곡차곡 저장.
- 호출 시 (공간 할당): 새로운 함수의 작업 공간(지역 변수)을 스택에 추가로 할당.
- 종료 및 복귀 (상태 복원): 작업이 끝나면 할당했던 작업 공간을 정리하고, 저장해뒀던 주소로 돌아가, 이전에 저장했던 상태를 복원.
반면 BFS의 while 반복문은 마치 가벼운 '문자 메시지'와 같다. 다음 할 일을 목록(Queue)에 적어두고, 순서가 되면 하나씩 처리할 뿐, 거창한 '보고 전화'는 필요 없다.
실제로 해당 실험에서는 재귀 DFS가 반복문 DFS에 비해 노드당 처리 오버헤드가 2배 이상이었고, 이는 전체 실행 시간에서 4배 이상의 성능 저하로 이어졌다고 보고한다.
노드가 수십만 개인 이 사건 현장에서, 비싼 전화 통화가 수십만 번 반복되니 그 누적된 비용은 무시할 수 없는 수준에 이르게 된다.
증거 #2: 무너져 내린 '조사 기록탑' (스택 오버플로우) 📚
더욱 치명적인 증거는 재귀 호출의 동작 방식 자체에 있었다. 재귀 호출은 '콜 스택(Call Stack)'이라는 공간에 '조사 기록(함수 정보)'을 책처럼 차곡차곡 쌓아 올리는 방식으로 동작한다. 길이 끝나고 되돌아올 때 비로소 책을 하나씩 치운다.
만약 캠퍼스에 600x600 크기의 길고 구불구불한 길이 있다면 어떻게 될까? DFS는 그 길을 따라 수십만 번의 재귀 호출을 하게 되고, 이는 수십만 권의 책으로 이루어진 아찔한 높이의 '조사 기록탑'을 쌓는 것과 같다.
결국 이 탑은 자체 무게를 이기지 못하고 무너져 내린다. 이것이 바로 StackOverflowError 다.
프로그램이 비정상적으로 종료되는 이 치명적인 오류는, 코딩 테스트 환경에서 종종 '시간 초과' 또는 '런타임 에러'로 보고된다. 즉, DFS는 성능이 느려서 시간 초과를 받은 것이 아니라, 애초에 완주조차 하지 못하고 중간에 쓰러져 버린 것이다. 이것이 사건의 가장 강력한 증거이다.
<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg">
<rect width="800" height="300" fill="#f8f9fa"/>
<rect x="50" y="20" width="700" height="60" fill="#dc3545" rx="10"/>
<text x="400" y="45" text-anchor="middle" fill="white" font-size="18" font-weight="bold">증거 #2: 무너져 내린 '조사 기록탑' (스택 오버플로우)</text>
<text x="470" y="65" text-anchor="middle" fill="white" font-size="24">📚</text>
<g transform="translate(50, 100)">
<rect x="0" y="0" width="150" height="150" fill="#e8f5e9" stroke="#4caf50" stroke-width="2"/>
<text x="75" y="20" text-anchor="middle" fill="#2e7d32" font-size="12" font-weight="bold">캠퍼스 미로</text>
<text x="75" y="35" text-anchor="middle" fill="#2e7d32" font-size="10">600 × 600</text>
<path d="M10 50 Q30 40, 50 50 T90 50 Q110 40, 130 50 T140 70 Q130 90, 110 100 T70 100 Q50 110, 30 100 T10 120 Q20 140, 40 130"
fill="none" stroke="#ff9800" stroke-width="3"/>
<circle cx="10" cy="50" r="4" fill="#f44336"/>
<circle cx="40" cy="130" r="4" fill="#4caf50"/>
<path d="M15 52 L25 48" stroke="#ff5722" stroke-width="2" marker-end="url(#arrowhead)"/>
<path d="M45 52 L55 48" stroke="#ff5722" stroke-width="2" marker-end="url(#arrowhead)"/>
<path d="M85 52 L95 48" stroke="#ff5722" stroke-width="2" marker-end="url(#arrowhead)"/>
</g>
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
<polygon points="0 0, 10 3.5, 0 7" fill="#ff5722"/>
</marker>
</defs>
<g transform="translate(250, 100)">
<text x="75" y="20" text-anchor="middle" fill="#1976d2" font-size="12" font-weight="bold">콜 스택 (Call Stack)</text>
<rect x="50" y="130" width="50" height="8" fill="#2196f3" stroke="#1976d2"/>
<rect x="50" y="122" width="50" height="8" fill="#42a5f5" stroke="#1976d2"/>
<rect x="50" y="114" width="50" height="8" fill="#64b5f6" stroke="#1976d2"/>
<rect x="50" y="106" width="50" height="8" fill="#90caf9" stroke="#1976d2"/>
<rect x="50" y="98" width="50" height="8" fill="#bbdefb" stroke="#1976d2"/>
<text x="75" y="150" text-anchor="middle" fill="#1976d2" font-size="8">조사 기록</text>
<text x="75" y="160" text-anchor="middle" fill="#1976d2" font-size="8">(함수 정보)</text>
</g>
<path d="M220 175 L280 175" stroke="#ff9800" stroke-width="4" marker-end="url(#bigarrow)"/>
<defs>
<marker id="bigarrow" markerWidth="15" markerHeight="10" refX="14" refY="5" orient="auto">
<polygon points="0 0, 15 5, 0 10" fill="#ff9800"/>
</marker>
</defs>
<g transform="translate(350, 100)">
<text x="100" y="20" text-anchor="middle" fill="#d32f2f" font-size="12" font-weight="bold">수십만 번의 재귀 호출</text>
<g id="high-stack">
<rect x="75" y="30" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="34" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="38" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="42" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="46" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="50" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="54" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="58" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="62" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="66" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="70" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="74" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="78" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="82" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="86" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="90" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="94" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="98" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="102" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="106" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="110" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="114" width="50" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="75" y="118" width="50" height="4" fill="#f44336" stroke="#d32f2f"/>
</g>
<text x="100" y="140" text-anchor="middle" fill="#d32f2f" font-size="10">수십만 권의 책</text>
<text x="100" y="152" text-anchor="middle" fill="#d32f2f" font-size="10">아찔한 높이!</text>
</g>
<path d="M480 175 L540 175" stroke="#ff5722" stroke-width="4" marker-end="url(#bigarrow2)"/>
<defs>
<marker id="bigarrow2" markerWidth="15" markerHeight="10" refX="14" refY="5" orient="auto">
<polygon points="0 0, 15 5, 0 10" fill="#ff5722"/>
</marker>
</defs>
<!-- 무너진 스택 -->
<g transform="translate(560, 100)">
<text x="80" y="20" text-anchor="middle" fill="#d32f2f" font-size="12" font-weight="bold">💥 스택 붕괴!</text>
<!-- 무너진 책들 -->
<g transform="rotate(-15 100 100)">
<rect x="70" y="80" width="30" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="75" y="85" width="30" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="80" y="90" width="30" height="4" fill="#f44336" stroke="#d32f2f"/>
</g>
<g transform="rotate(25 100 120)">
<rect x="85" y="100" width="30" height="4" fill="#e57373" stroke="#d32f2f"/>
<rect x="90" y="105" width="30" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="95" y="110" width="30" height="4" fill="#e57373" stroke="#d32f2f"/>
</g>
<g transform="rotate(-30 100 140)">
<rect x="60" y="120" width="30" height="4" fill="#f44336" stroke="#d32f2f"/>
<rect x="65" y="125" width="30" height="4" fill="#e57373" stroke="#d32f2f"/>
</g>
<!-- 먼지 구름 효과 -->
<circle cx="80" cy="130" r="12" fill="#ffeb3b" opacity="0.5"/>
<circle cx="100" cy="125" r="8" fill="#ffeb3b" opacity="0.3"/>
<circle cx="120" cy="135" r="10" fill="#ffeb3b" opacity="0.4"/>
<text x="80" y="160" text-anchor="middle" fill="#d32f2f" font-size="10" font-weight="bold">StackOverflowError</text>
</g>
</svg>증거 #3: 융통성 없는 '원칙주의자 조수' (JVM의 꼬리 재귀 최적화 미지원) 🤖
몇몇 언어에는 '꼬리 재귀 최적화(Tail Call Optimization, TCO)'라는 기술을 지원하는 똑똑한 조수(컴파일러)가 있다. 이 조수는 보고의 마지막 절차가 또 다른 보고일 경우, 굳이 새 기록을 쌓지 않고 기존 기록을 재활용하는 식으로 일을 최적화해준다.
예를 들어, TCO를 지원하는 똑똑한 조수는 마치 계주(Relay Race) 경기와 같이 일한다. 1번 주자는 2번 주자에게 바통을 넘겨주는 순간 자신의 임무가 완전히 끝난다. 2번 주자가 결승선에 들어올 때까지 1번 주자가 트랙에 남아 기다릴 필요가 없다. 즉, 마지막 동작(tail call)이 다음 주자를 부르는 것이라면, 현재 주자의 정보(스택 프레임)는 더 이상 필요 없으므로 그 공간을 다음 주자가 재사용한다.
하지만 자바(JVM)라는 조수는 이러한 융통성을 발휘하지 않는 원칙주의자다. 마치 군대의 지휘 보고 체계처럼, 사령관이 대대장에게, 대대장이 중대장에게, 중대장이 소대장에게 임무를 전달한다. 소대장은 임무를 완수한 뒤 반드시 중대장에게 보고해야 하고, 중대장은 그 보고를 취합해 대대장에게, 대대장은 최종적으로 사령관에게 보고를 올려야 임무가 끝난다.
이 방식은 누가 누구에게 지시했는지 그 경로(Stack Trace)가 명확하게 남는다는 엄청난 장점이 있지만, 중간 보고 절차 때문에 과정이 길어지고 각 지휘관(함수)들은 보고가 끝날 때까지 자리를 떠날 수 없다.
이 차이가 왜 발생하는지, 그리고 왜 이것이 우리 사건의 결정적 증거가 되는지 더 깊이 파헤쳐 보자.
JVM은 왜 TCO를 포기했는가?
자바에 능숙한 개발자라면 한 번쯤 의문을 가졌을 것이다. "왜 똑똑한 JVM은 이 명백한 최적화를 수행하지 않는 걸까?" 이는 실수가 아닌, 플랫폼의 핵심 철학이 담긴 의도적인 설계 결정이다.
실제로 Oracle의 Java 언어 아키텍트인 브라이언 게츠(Brian Goetz)는 TCO 미지원이 자바의 계산 모델(computation model)과 깊이 연관되어 있음을 여러 차례 설명한 바 있다.
"A tail-call 'optimization' is not really an optimization in the usual sense, like loop unrolling or inlining. It is a modification of the computation model. ... So, the 'feature' of a preserved stack is not a bug, it is a feature. We could change the model, but it's a big and risky job, and it's not at all clear that this is a net win for the platform."
"꼬리 호출 '최적화'는 루프 언롤링이나 인라이닝 같은 일반적인 의미의 최적화가 아닙니다. 그것은 계산 모델 자체의 변경입니다. ... 따라서 '보존된 스택'은 버그가 아니라 하나의 기능(feature)입니다. 우리는 이 모델을 바꿀 수도 있겠지만, 그것은 매우 크고 위험한 작업이며, 이것이 플랫폼 전체에 이득이 될지는 전혀 명확하지 않습니다."
이 말은 TCO 미지원이 기술적 한계나 실수가 아니라, 자바의 정체성과 직결된 깊은 고민의 결과임을 시사한다.
그렇다면, 최적화를 포기하면서까지 지키고 싶었던 자바의 핵심 가치가 무엇일까.
1. '꼬리 호출'의 정확한 의미
먼저, 모든 재귀 호출이 꼬리 호출인 것은 아니다. 꼬리 호출은 함수가 반환되기 직전의 마지막 연산이 오직 '다른 함수를 호출하는 것'이어야 한다.
// 이것은 꼬리 호출이 아님!
// factorial(n-1) 호출 후, 그 반환값에 n을 곱하는 연산이 남아있다.
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // 곱셈 연산이 마지막!
}
// 이것이 진정한 꼬리 호출
// helper() 호출이 아무 추가 연산 없이 마지막 동작이다.
int tailRecFactorial(int n) {
return helper(n, 1);
}
int helper(int n, int acc) {
if (n <= 1) return acc;
return helper(n - 1, n * acc); // 오직 helper() 호출만 남음!
}
TCO는 위 코드의 helper()와 같은 진정한 꼬리 호출만 최적화하여, helper()를 위한 새 스택 프레임을 쌓는 대신 기존 프레임을 재사용하고 인자 값만 바꿔치기한다. 사실상 내부적으로는 while 루프처럼 동작하게 만든다.
꼬리 재귀의 개념과 자바에서의 대안에 대한 Baeldung의 아티클에서는 이 개념을 명확한 코드 예시와 함께 설명하며, 자바에서는 TCO가 지원되지 않으므로 개발자가 직접 재귀 로직을 반복문(iteration)으로 전환하는 것이 StackOverflowError를 피하는 가장 효과적인 해결책임을 강조한다.
2. 최적화를 포기한 이유: 스택 무결성과 보안
JVM이 TCO를 지원하지 않는 가장 큰 이유는 스택의 무결성(Integrity)을 지키기 위함이다. 자바 플랫폼의 핵심 기능 중 상당수가 현재 실행 중인 콜 스택을 정확하게 들여다보는 능력에 의존한다.
- 보안(Security): 자바의
SecurityManager는 특정 코드가 위험한 작업을 수행할 권한이 있는지 검사할 때, 그 코드를 누가 호출했는지 콜 스택을 역추적한다. 만약 TCO가 적용되어A -> B -> C의 호출에서B의 스택 프레임이 사라진다면(A -> C),B가 가진 보안 문맥이 소실되어 보안 정책을 우회할 가능성이 생긴다. - 디버깅(Debugging): 개발자에게 정확하고 완전한 스택 트레이스(Stack Trace) 는 신성불가침의 영역이다. 예외가 발생했을 때, 어떤 경로를 통해 그 지점에 도달했는지 명확히 보여주는 것은 디버깅의 핵심이다. 앞서 언급한 브라이언 게츠는 스택 오버플로우 답변 자바의 '보존된 스택'은 버그가 아니라 디버깅과 보안을 위한 핵심 '기능(a feature, not a bug)'이라고 못 박았다. TCO는 이 경로를 의도적으로 단축시켜 버리므로, 오류의 원인을 추적하는 것을 훨씬 더 어렵게 만든다.
- 리플렉션 및 기타 기능: 스택 정보를 활용하는 리플렉션, 로깅, 프로파일링 등 다양한 기능들이 TCO로 인해 오작동할 수 있다.
결론적으로, JVM 설계자들은 TCO가 주는 약간의 성능적 이점보다 플랫폼의 안정성, 보안, 디버깅 용이성이라는 핵심 가치가 더 중요하다고 판단했다.
이러한 설계 철학의 결과, 다른 언어였다면 최적화될 수 있었을 재귀 호출마저 자바에서는 모든 비용을 정직하게 지불해야 했고, 우리 사건 속 '조사 기록탑'은 다른 어떤 환경에서보다 더 빠르고 확실하게 무너지게 된 것이다.
이는 DFS의 실패를 설명하는 매우 중요한 법의학적 증거다.
3장: 전문가의 증언 (심층 분석)
이미 결정적 증거들은 확보되었다. 하지만 이 사건을 완벽하게 이해하고 싶은 탐정들을 위해, 컴퓨터 하드웨어 전문가들을 증인으로 소환했다. 이들의 증언은 DFS의 유죄를 더욱 확실하게 만들어 줄 것이다.
증언 #1: "CPU는 연속된 작업을 선호한다" (캐시 친화성) 🧠
CPU는 일을 처리할 때, 거대한 창고(RAM)에서 모든 데이터를 가져오는 것이 아니라, 바로 옆 작은 작업대(캐시 메모리)에 자주 쓸 재료들을 가져다 놓고 쓴다. 작업대에서 재료를 바로 꺼내 쓰는 것이 창고까지 다녀오는 것보다 수십, 수백 배 빠르기 때문이다. 이 현상을 이해하기 위해, 우리는 컴퓨터 아키텍처의 근본 원리 하나를 짚고 넘어가야 한다.
바로 '공간적 지역성(Spatial Locality)'의 원리와, 이를 활용하는 CPU의 기본 동작 단위인 '캐시 라인(Cache Line)'이다.
프로그램의 공간적 지역성 원리는 어떤 의미가 있을까요? 프로그램이 어떤 데이터에 접근하면 다음에는 인접한 데이터에 접근할 가능성이 높으므로 접근해야 할 데이터만 캐시에 접근하는 것은 현명하지 않습니다. 따라서 더 나은 방법은 해당 데이터가 있는 곳의 '묶음' 데이터를 캐시에 저장하는 것입니다. (컴퓨터 밑바닥의 비밀, p.388)
이 '데이터 묶음'이 바로 캐시 라인이다. 즉, CPU가 창고(RAM)에 갈 때는, 필요한 나사 하나만 집어 오는 것이 아니라 나사가 담긴 '부품 상자' 전체를 들고 작업대(캐시)에 가져다 놓는다.
BFS와 DFS 메커니즘을 이 기본 원리를 기반으로 해석해본다면 어떨까?
BFS의 작업 방식 (캐시를 효율적으로 사용하는 장인):
BFS는 현재 노드의 '모든 이웃'을 차례대로 방문한다. 2차원 배열에서 이웃 노드들은 메모리 주소상으로도 인접해 있을 확률이 매우 높다. BFS가 (r, c) 칸에 접근할 때, CPU는 해당 칸이 포함된 캐시 라인, 즉 '부품 상자' 전체를 캐시로 가져온다.
이 상자 안에는 이웃인 (r, c+1), (r, c+2) 등의 데이터가 함께 담겨 있을 가능성이 크다. 따라서 BFS가 다음 이웃을 방문하려 할 때는, 이미 그 데이터가 작업대 위에 놓여 있는 상태가 된다. 이것이 바로 캐시 히트(Cache Hit)이며, 압도적인 성능 향상으로 이어진다.
DFS의 작업 방식 (창고를 계속 왕복하는 신입):
재귀 DFS는 현재 노드의 한 이웃을 따라 메모리의 아주 먼 곳까지 한 번에 점프한다.
예를 들어 (r, c)를 방문한 직후, 수십 번의 재귀 호출 끝에 전혀 다른 메모리 영역의 (r+100, c+50)에 접근할 수 있다. 이 과정에서 CPU는 완전히 새로운 '부품 상자'를 창고에서 가져와야만 한다. 더 큰 문제는, DFS가 다시 (r, c)로 돌아와 그 옆의 다른 이웃 (r, c+1)을 처리하려 할 때 발생한다. 그사이 작업대(캐시)는 다른 온갖 잡동사니(새로운 캐시 라인)들로 채워져, 처음에 가져다 놓았던 '부품 상자'는 이미 창고로 돌려보내졌을 확률이 높다. 결국 또다시 느린 창고까지 데이터를 가지러 가야 하는 비효율, 즉 캐시 미스(Cache Miss)가 빈번하게 발생한다.
이처럼 CPU의 작업 효율성, 즉 캐시 친화성 측면에서 BFS는 공간적 지역성을 적극적으로 활용하여 캐시 히트율을 높이는 반면, DFS는 메모리 곳곳을 불규칙하게 뛰어다니며 캐시 미스를 유발하는 구조적 한계를 가진다. 이 차이가 두 용의자의 실질적인 성능 차이를 만든 또 하나의 숨겨진 증거이다.
여기에 더해, CPU 전문가의 증언에는 한 가지 흥미로운 내용이 더 있다. 바로 '분기 예측(Branch Prediction)' 이다. 분기 예측은 굉장히 흥미로운 포인트이다.
분기 점프 명령어는 자신의 실행 결과에 따라 점프 여부를 결정해야 하는데, 이 명령어 실행이 완료되지 않은 시점에 CPU는 어떤 분기의 명령어를 파이프라인에 넣어야 할지 어떻게 알 수 있을까요?
사실 CPU 역시 이를 알지 못한다면 어떻게 해야 할까요? 답은 매우 간단합니다. 미리 예측을 하는 것이죠.
CPU는 뒤이어 어디로 분기할 가능성이 있는지 추측합니다. 추측이 맞았다면 파이프라인은 계속 앞으로 흘러갈 것입니다. 추측이 틀렸다면 안타깝게도 파이프라인에서 이미 실행 중이던 잘못된 분기 명령어 전부를 무효화합니다. 여기에서 알 수 있듯이, CPU 추측이 틀리면 바로 성능 손실이 발생합니다.
최신 CPU의 이런 '추측' 과정을 분기 예측이라고 합니다. 물론 이 예측은 동전 던지기처럼 간단하지 않으며, 프로그램 실행 이력을 기반으로 예측을 실행하는 등 여러 가지 데이터를 기반으로 합니다.
(컴퓨터 밑바닥의 비밀, p.314 ~ 315)
즉, 현대 CPU는 다음 실행될 코드를 미리 '예측'하고 준비하여 파이프라인의 효율을 극대화하는 기술을 사용한다. 이때 BFS의 while문이나 for문처럼 규칙적인 반복문은 CPU가 다음 행동을 예측하기 매우 쉽다. 하지만 재귀 DFS에서 빈번하게 발생하는 함수 호출과 복귀(call/ret)는 다음에 어디로 뛸지 예측하기 훨씬 까다로운 '간접 분기(indirect branch)'에 해당한다.
CPU의 예측이 빗나갈 때마다 파이프라인을 비우고 다시 시작하는 페널티가 발생하는데, 이러한 예측 실패가 수십만 번 누적되면 캐시 미스와 마찬가지로 무시할 수 없는 성능 차이를 유발하는 또 다른 '공범'이 될 수 있다.
하지만 여기서 한 가지 의문이 생긴다.
캐시 미스로 인한 지연은 분명 존재하지만,
이는 나노초($10^{-9}$초) 단위의 미세한 시간이다.
이런 작은 차이들이 모여 1초, 2초의 실행 시간 제한을 넘길 만큼
거대한 차이를 만들 수 있을까?
수십만 번의 연산에서 이 정도 차이가 과연 결정적 증거가 될 수 있는가?
만약 두 알고리즘이 끝까지 완주한다는 전제하에 순수하게 실행 시간만 비교한다면, 캐시 효율성은 '상수 시간(constant factor)'의 차이를 만들어내는 중요한 요인이다. 수십만, 수백만 번의 연산이 반복되면 이 나노초 단위의 차이는 분명 눈에 띄는 시간 차이로 이어진다.
하지만 이 사건의 '시간 초과'는 단순히 '조금 느려서' 발생한 문제가 아닐 것이다. 따라서, 캐시 미스는 성능을 저하시키는 '공범'에 가깝지만, 사건을 파국으로 이끈 '주범'은 따로 있다. 우리는 지금까지 CPU의 '작업 효율성'에 집중했지만, 이보다 더 근본적인 문제, 즉 애초에 알고리즘이 사용하는 '작업 공간' 자체의 특성을 들여다봐야 한다.
두 용의자는 작업 효율성도 달랐지만, 그들이 의존하는 메모리 공간의 종류와 한계 또한 근본적으로 달랐다. 이제 두 번째 전문가인 메모리 아키텍트의 증언을 들어보자.
증언 #2: "메모리 사용 방식이 근본적으로 다르다" (힙 vs 스택) 💾
두 알고리즘은 단순히 작업 방식뿐만 아니라, 사용하는 메모리의 종류와 그 동작 원리부터 근본적으로 다르다. 모든 프로그램이 실행될 때 운영체제가 할당해주는 메모리 공간은 크게 스택(Stack)과 힙(Heap)으로 나뉜다.
컴퓨터 과학의 바이블로 불리는 일명 공룔책 "Operating System Concepts" (Silberschatz, Galvin, Gagne 저)에서는 프로세스의 메모리 구조를 설명하며 두 공간의 역할을 다음과 같이 정의한다.
"The stack is used for static memory allocation... and contains temporary data such as function parameters, return addresses, and local variables. ... The heap is used for dynamic memory allocation and is managed by calls such as new, malloc... "
"스택은 정적 메모리 할당에 사용되며... 함수 파라미터, 반환 주소, 지역 변수와 같은 임시 데이터를 포함한다. ... 힙은 동적 메모리 할당에 사용되며,
new,malloc과 같은 호출에 의해 관리된다..." (10th ed.)
이 정의를 바탕으로 두 용의자의 메모리 전략을 해부해 보자.
BFS와 힙(Heap): 유연하고 광활한 동적 작업 공간
BFS 코드에서 new ArrayDeque<>()를 통해 Queue를 생성하는 순간, 이 Queue 객체는 힙(Heap) 메모리 영역에 자리를 잡는다. 힙은 프로그램이 실행되는 동안 개발자가 원할 때 new 키워드 등을 통해 자유롭게 메모리를 할당하고 해제(물론 자바에서는 가비지 컬렉터가 담당한다)할 수 있는 '동적 할당' 공간이다.
힙의 가장 큰 특징은 광대하고 유연하다는 점이다. JVM이 시작될 때 설정된 최대 크기(-Xmx) 내에서, 큐에 수십만 개의 좌표 데이터가 들어와도 메모리가 허용하는 한 계속해서 공간을 확장해 나갈 수 있다. BFS가 미로의 넓은 광장을 만나 큐의 크기가 폭발적으로 늘어나더라도, 힙은 묵묵히 그 데이터를 모두 받아준다. 이는 예측 불가능한 크기의 작업 목록을 다뤄야 하는 BFS에게는 더할 나위 없이 안정적인 전략이다.
DFS와 스택(Stack): 빠르지만 엄격하고 치명적인 정적 작업 공간
반면 재귀 DFS는 new를 통해 명시적으로 작업 목록을 만들지 않는다. 대신 dfs() 함수가 자기 자신을 호출할 때마다, 자바는 이 함수의 정보(파라미터, 지역 변수, 돌아갈 위치 등)를 스택(Stack) 메모리 영역에 '스택 프레임(Stack Frame)'이라는 단위로 쌓는다. 이것이 바로 우리가 '조사 기록탑'에 비유했던 것의 실체다.
스택은 CPU가 직접 관리하기에 접근 속도가 매우 빠르다는 장점이 있지만, 치명적인 한계를 가진다. 바로 스레드마다 크기가 고정되어 있다는 점이다. 일반적인 JVM 환경에서 스택 하나의 크기는 보통 1MB 정도로 제한된다. 이는 컴파일 시점에 크기를 예측하기 어려운 거대한 데이터를 저장하기 위한 공간이 아니라, 함수 호출처럼 깊이가 제한적이고 예측 가능한 작업을 위한 임시 공간이기 때문이다.
결국 재귀 DFS는 600x600 크기의 맵에서 깊은 경로를 만나자마자, 이 제한된 1MB의 공간을 순식간에 소진해 버렸고, 더 이상 스택 프레임을 쌓을 곳이 없어지자 StackOverflowError 를 내뿜으며 처참하게 무너져 내린 것이다.
결론적으로, 두 용의자의 운명을 가른 것은 단순히 캐시 효율성의 차이를 넘어선 메모리 운용 전략의 근본적인 차이였다. BFS는 크고 유연한 '힙'을 활용하는 안정적인 전략을 택해 살아남았고, 재귀 DFS는 빠르지만 한계가 명확한 '스택'에 모든 것을 거는 위험한 도박을 하다가 자멸했다. 이 선택이 바로 사건 현장에서 둘의 생존을 가른 가장 직접적인 원인이다.
그런데 이런 의문이 들 수 있다.
질문: 증언 #1에서는 BFS가 메모리의 '인접한' 데이터를 잘 활용해서 캐시 효율적이라고 했습니다. 하지만 증언 #2에서는 BFS가 사용하는 Queue 객체가 '광활한' 힙 메모리에 동적으로 할당된다고 했습니다. 동적으로 할당된 객체들이 어떻게 메모리상에서 인접하다고 보장할 수 있으며, 어떻게 캐시 효율성을 논할 수 있나요?
답변: 이 질문의 답은 BFS가 접근하는 데이터를 두 종류로 나누어 생각하면 명확해진다.
1. BFS의 '핵심 작업 데이터': map[][] 과 visited[][] 배열
- 이 데이터의 특징: 이들은 거대하고, 메모리상에서 물리적으로 연속된(Contiguous) 공간을 차지하는 배열이다. new 좌표[N][M]으로 생성되는 순간, 힙 메모리에 N * M 크기의 연속된 덩어리로 자리를 잡는다.
- 이 데이터와 관련된 증언: 바로 증언 #1 (캐시 친화성) 이다. BFS가 map[r][c]에 접근한 뒤, 바로 옆 map[r][c+1]에 접근할 때, 이 두 데이터는 물리적으로 인접해 있다. CPU가 map[r][c]를 읽으면서 캐시 라인에 '주변 데이터'를 통째로 가져왔기 때문에, map[r][c+1]은 이미 캐시에 존재할 확률이 매우 높다. 즉, 캐시 효율성은 주로 이 거대한 핵심 데이터 배열에 순차적으로 접근하기 때문에 발생하는 이점이다.
2. BFS의 '보조 관리 데이터': Queue와 그 안의 좌표 객체들
- 이 데이터의 특징: 이들은 new ArrayDeque<>(), new 좌표()를 통해 힙 메모리 곳곳에 동적으로, 그리고 흩어져서(Non-contiguous) 생성될 수 있다. Queue 객체 자체의 주소와, 그 큐가 참조하는 각각의 좌표 객체들의 주소는 서로 멀리 떨어져 있을 수 있다.
- 이 데이터와 관련된 증언: 바로 증언 #2 (힙 vs 스택) 이다. 재귀 DFS가 고정된 크기의 '스택'에 모든 것을 걸다가 StackOverflowError로 자멸한 반면, BFS는 이 '보조 데이터'를 광활하고 유연한 '힙'에 저장하는 전략을 택했다. 덕분에 탐색할 노드가 수십만 개가 되어도 메모리 부족 없이 안정적으로 관리할 수 있었던 것이다. 즉, 힙의 광활함은 BFS가 실패하지 않고 완주할 수 있었던 생존의 비결이다.
즉, 두 증언의 관계를 표로 정리하면 다음과 같다.
| 메모리 | 종류데이터의 역할 | 관련된 증언 (이점) |
| 힙 (Heap) | 핵심 데이터 저장소 (map, visited 배열) | 증언 #1 (캐시 친화성): 연속된 공간에 순차 접근 |
| 힙 (Heap) | 보조 데이터 관리 (Queue 및 좌표 객체) | 증언 #2 (스택 vs 힙): 유연한 공간으로 오버플로우 방지 |
| 스택 (Stack) | 재귀 DFS의 작업 공간 (함수 호출 프레임) | 증언 #2 (스택 vs 힙): 고정된 크기로 인해 오버플로우 발생 |
따라서 두 증언은 상반되는 것이 아니라, BFS의 성공 비결을 서로 다른 각도에서 설명한다.
- 증언 #1은 BFS가 '어떻게 빠르게' 동작하는지(핵심 데이터 접근 방식)를 설명하고,
- 증언 #2는 BFS가 '왜 실패하지 않는지'(보조 데이터 관리 방식)를 설명한다.
이 두 가지 장점이 합쳐져 BFS가 이 사건의 최종 승자가 될 수 있었던 것이다.
하지만 여기서 두 번째 질문이 떠오른다.
두 번째 질문: 애초에 왜 스택은 1MB 정도로 작게 제한되고, 힙은 그렇지 않은 것인가?
답변: 이 질문에 답하기 위해서는 컴퓨터 시스템의 근본적인 동작 원리를 상기해볼 필요가 있다.
스택이 작고 빠른 이유는 예측, 속도, 그리고 효율성에 있다.
1. 설계 목적: 예측 가능성과 속도
스택의 주된 임무는 함수의 호출 순서를 질서정연하게 관리하는 것이다. 함수 A가 B를 부르고, B가 C를 부르는 과정은 매우 구조적이고 '일시적'이다. C가 끝나면 B로, B가 끝나면 A로 반드시 돌아온다. 이렇게 수명이 짧고 예측 가능한 데이터를 다루기 때문에, 거대한 공간을 미리 할당해 둘 필요가 없다.
무엇보다 중요한 것은 속도다. 스택에 메모리를 할당하고 해제하는 작업은 단순히 스택 포인터(Stack Pointer)라는 표시기(레지스터)의 주소 값을 옮기는 것만으로 끝난다. 이는 CPU가 수행할 수 있는 가장 빠른 메모리 조작 방식 중 하나로, 빈번한 함수 호출 성능에 최적화되어 있다.
2. 가장 결정적인 이유: 멀티스레딩 환경의 효율성
현대의 프로그램은 수많은 스레드(일을 처리하는 일꾼)를 동시에 실행한다. 모든 스레드는 자신만의 독립적인 스택 공간을 필요로 한다. 이것이 스택 크기가 작아야만 하는 결정적인 이유다.
만약 스택의 기본 크기가 1MB가 아니라 1GB처럼 거대하다고 상상해 보자. 스레드를 단 1,000개만 만들어도 무려 1TB의 메모리가 필요하게 된다. 이는 엄청난 자원 낭비이며, 수많은 스레드를 가볍게 생성하고 사용하는 현대적 프로그래밍 패러다임과 정면으로 배치된다.
따라서 스택 크기를 작게 유지하는 것은, 각 스레드를 가볍고 효율적으로 만들어 전체 시스템의 확장성을 높이는 핵심적인 설계 결정이다.
반면 힙이 크고 유연한 이유는 예측 불가능성에 대한 대비하기 위함이다.
1. 설계 목적: 예측 불가능성 대응
힙은 프로그램이 실행되는 동안, 언제, 얼마나, 오랫동안 필요할지 모르는 데이터들을 위한 공간이다. 우리 문제의 Queue처럼 얼마나 많은 데이터가 들어올지, 사용자가 업로드하는 파일의 크기가 얼마일지, 게임 속에서 몬스터 객체가 몇 마리나 생성될지 등, 컴파일 시점에는 전혀 예측할 수 없는 데이터들을 담아야 한다.
이러한 예측 불가능성과 동적인 생명주기를 감당하기 위해, 힙은 거대하고 유연하게 설계되었다. 필요할 때 필요한 만큼 '빌려 쓰고', 필요 없어지면 '반납'(GC)하는 모델이다.
2. 속도와의 트레이드오프
이 유연성은 대가를 치른다. 힙에 메모리를 할당(new)하려면, JVM은 비어있는 적절한 공간을 찾아내야 한다. 또한, 더 이상 사용되지 않는 객체(쓰레기)를 찾아내 처리하는 가비지 컬렉션(Garbage Collection) 과정도 주기적으로 필요하다. 이 모든 과정은 단순히 포인터 하나를 움직이는 스택에 비해 훨씬 복잡하고 비용이 많이 든다. 즉, 힙은 속도를 일부 희생하여 유연성과 크기를 얻은 것이다.
따라서, 재귀 DFS가 실패한 이유는, 단기 기억을 위해 설계된 좁은 '책상(스택)' 위에 수십만 권의 '책(함수 호출 정보)'을 쌓으려고 하는, 공간의 목적에 맞지 않는 위험한 행동을 했기 때문이다. 반면 BFS는 '도서관(힙)'의 넓은 공간을 활용하여 작업 목록을 안전하게 관리했기에 완주할 수 있었다.
<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg">
<!-- Background -->
<rect width="800" height="600" fill="#f8f9fa"/>
<!-- Title Section -->
<rect x="50" y="20" width="700" height="60" fill="#2c3e50" rx="10"/>
<text x="400" y="45" text-anchor="middle" fill="white" font-size="18" font-weight="bold">메모리 사용 방식의 근본적 차이</text>
<text x="400" y="65" text-anchor="middle" fill="white" font-size="14">힙(Heap) vs 스택(Stack)</text>
<!-- BFS Section (Left) -->
<rect x="50" y="100" width="330" height="480" fill="#e8f5e8" stroke="#27ae60" stroke-width="2" rx="10"/>
<!-- BFS Title -->
<rect x="70" y="120" width="290" height="40" fill="#27ae60" rx="5"/>
<text x="215" y="135" text-anchor="middle" fill="white" font-size="14" font-weight="bold">BFS</text>
<text x="215" y="150" text-anchor="middle" fill="white" font-size="12">힙(Heap) 메모리 사용</text>
<!-- Heap Memory Representation -->
<rect x="90" y="180" width="250" height="200" fill="#52c41a" opacity="0.3" stroke="#27ae60" stroke-width="2" rx="5"/>
<text x="215" y="200" text-anchor="middle" fill="#27ae60" font-size="12" font-weight="bold">동적 메모리 할당</text>
<!-- Queue visualization in heap -->
<g transform="translate(110, 220)">
<!-- Queue blocks growing dynamically -->
<rect x="0" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="35" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="70" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="105" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="140" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="175" y="0" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="0" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="35" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="70" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="105" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="140" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="175" y="25" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="0" y="50" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="35" y="50" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="70" y="50" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<rect x="105" y="50" width="30" height="20" fill="#52c41a" stroke="#27ae60"/>
<!-- Arrow showing expansion -->
<path d="M 210 35 L 225 35" stroke="#27ae60" stroke-width="2" marker-end="url(#arrowgreen)"/>
<text x="235" y="40" fill="#27ae60" font-size="10">확장 가능</text>
</g>
<!-- Heap characteristics -->
<g transform="translate(70, 400)">
<circle cx="10" cy="10" r="5" fill="#27ae60"/>
<text x="25" y="15" fill="#2c3e50" font-size="11">광대하고 유연</text>
<circle cx="10" cy="30" r="5" fill="#27ae60"/>
<text x="25" y="35" fill="#2c3e50" font-size="11">new ArrayDeque()</text>
<circle cx="10" cy="50" r="5" fill="#27ae60"/>
<text x="25" y="55" fill="#2c3e50" font-size="11">JVM 최대 크기까지</text>
<circle cx="10" cy="70" r="5" fill="#27ae60"/>
<text x="25" y="75" fill="#2c3e50" font-size="11">예측 불가능한 크기 OK</text>
</g>
<!-- Success indicator -->
<circle cx="215" cy="540" r="20" fill="#27ae60"/>
<text x="215" y="547" text-anchor="middle" fill="white" font-size="16" font-weight="bold">✓</text>
<!-- DFS Section (Right) -->
<rect x="420" y="100" width="330" height="480" fill="#ffeaea" stroke="#e74c3c" stroke-width="2" rx="10"/>
<!-- DFS Title -->
<rect x="440" y="120" width="290" height="40" fill="#e74c3c" rx="5"/>
<text x="585" y="135" text-anchor="middle" fill="white" font-size="14" font-weight="bold">DFS (재귀)</text>
<text x="585" y="150" text-anchor="middle" fill="white" font-size="12">스택(Stack) 메모리 사용</text>
<!-- Stack Memory Representation -->
<rect x="460" y="180" width="250" height="200" fill="#ff7875" opacity="0.3" stroke="#e74c3c" stroke-width="2" rx="5"/>
<text x="585" y="200" text-anchor="middle" fill="#e74c3c" font-size="12" font-weight="bold">정적 메모리 할당 (1MB 제한)</text>
<!-- Stack frames visualization -->
<g transform="translate(480, 220)">
<!-- Stack frames stacking up -->
<rect x="50" y="120" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="132" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="100" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="112" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="80" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="92" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="60" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="72" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="40" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="52" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="20" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="32" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<rect x="50" y="0" width="120" height="15" fill="#ff4d4f" stroke="#e74c3c"/>
<text x="110" y="12" text-anchor="middle" fill="white" font-size="9">dfs() frame</text>
<!-- Overflow indication -->
<path d="M 110 -10 L 110 -25" stroke="#e74c3c" stroke-width="3"/>
<text x="110" y="-30" text-anchor="middle" fill="#e74c3c" font-size="10" font-weight="bold">OVERFLOW!</text>
<!-- Limit line -->
<line x1="30" y1="140" x2="190" y2="140" stroke="#e74c3c" stroke-width="2" stroke-dasharray="5,5"/>
<text x="210" y="145" fill="#e74c3c" font-size="9">1MB 한계</text>
</g>
<!-- Stack characteristics -->
<g transform="translate(440, 400)">
<circle cx="10" cy="10" r="5" fill="#e74c3c"/>
<text x="25" y="15" fill="#2c3e50" font-size="11">빠르지만 한계 명확</text>
<circle cx="10" cy="30" r="5" fill="#e74c3c"/>
<text x="25" y="35" fill="#2c3e50" font-size="11">재귀 호출마다 프레임</text>
<circle cx="10" cy="50" r="5" fill="#e74c3c"/>
<text x="25" y="55" fill="#2c3e50" font-size="11">크기 고정 (1MB)</text>
<circle cx="10" cy="70" r="5" fill="#e74c3c"/>
<text x="25" y="75" fill="#2c3e50" font-size="11">깊은 경로 = 위험</text>
</g>
<!-- Failure indicator -->
<circle cx="585" cy="540" r="20" fill="#e74c3c"/>
<text x="585" y="547" text-anchor="middle" fill="white" font-size="16" font-weight="bold">✗</text>
<!-- Arrow markers -->
<defs>
<marker id="arrowgreen" markerWidth="10" markerHeight="10" refX="9" refY="3" orient="auto" markerUnits="strokeWidth">
<path d="M0,0 L0,6 L9,3 z" fill="#27ae60"/>
</marker>
</defs>
<!-- Comparison arrows -->
<path d="M 380 300 L 420 300" stroke="#34495e" stroke-width="3" marker-end="url(#arrowgray)"/>
<defs>
<marker id="arrowgray" markerWidth="10" markerHeight="10" refX="9" refY="3" orient="auto" markerUnits="strokeWidth">
<path d="M0,0 L0,6 L9,3 z" fill="#34495e"/>
</marker>
</defs>
<text x="400" y="290" text-anchor="middle" fill="#34495e" font-size="12" font-weight="bold">VS</text>
</svg>
4장: 반전, 그리고 진범의 등장
모든 증거가 DFS를 가리키고 있다. 그렇다면 DFS가 그 자체로 유죄일까?
재귀 호출의 오버헤드, 스택 오버플로우의 치명타, JVM의 비협조적인 태도까지, 이들은 모두 공범일 수 있다. 그렇다면 진범은 누구인가? DFS 그 자체인가? 여기서, 오해하면 안 된다. 엄밀한 의미에서, 진범은 '깊이 우선 탐색(DFS)'이라는 알고리즘 그 자체는 아니다.
DFS의 핵심은 '가능한 한 깊게 탐색한 후, 막히면 돌아와 다른 길을 찾는다'는 아이디어다. 이 아이디어 자체에는 죄가 없다. 문제는 그 아이디어를 구현하기 위해 선택한 '재귀(Recursion)'라는 도구이다. 비효율적인 보고 체계와 기억력의 한계를 가진 낡고 위험한 도구 말이다.
그렇다, 진범은 바로 '재귀'라는 구현 방식이다.
그렇다면 재귀를 사용하지 않으면 DFS도 통과할까?
정답은 YES.
누명을 벗기 위한 새로운 선택: 반복문과 스택
누명을 벗기 위해, DFS는 자신의 가장 큰 단점이었던 '재귀'를 버리고, BFS가 사용하던 '작업 목록' 전략을 자신만의 스타일로 채택해보자.
즉, 스택(Stack) 을 사용해보자.
스택은 큐와 반대로 '가장 나중에 들어온 것(Last-In)'이 '가장 먼저 나가는(First-Out)' 구조를 가진다.
이 특징을 이용하면, 재귀 없이도 DFS의 '깊이 우선' 탐색 방식을 완벽하게 구현할 수 있다.
- 다음에 갈 곳을 스택에
push하여 쌓아둔다. - 스택의 가장 위에서(
pop) 다음 탐색 대상을 꺼낸다.
가장 최근에 발견한 경로를 먼저 탐색하게 되므로, 자연스럽게 깊이 우선 탐색이 이루어진다.
// 누명을 벗은 DFS의 새로운 행동 방식
void iterativeDfs(좌표 start) {
Stack<좌표> stack = new Stack<>();
stack.push(start); // 큐 대신 스택을 사용
while (!stack.isEmpty()) {
좌표 current = stack.pop(); // 가장 최근에 넣은 것을 먼저 꺼낸다
if (visited[current]) continue; // 방문했다면 건너뛰기
visited[current] = true;
// 작업 수행...
for (좌표 next : current.getAdjacent()) {
if (!visited[next]) {
stack.push(next); // 다음 경로를 스택에 추가
}
}
}
}
이 새로운 방식(반복형 DFS)은 스택 오버플로우의 위험에서 완전히 자유로우며, 불필요한 함수 호출 오버헤드도 없다. 그 결과, BFS와 대등한, 때로는 더 효율적인 성능을 보여준다.
이로써 DFS는 자신의 누명을 벗었다. 범인은 알고리즘이 아닌, '재귀'라는 낡은 도구였음이 마침내 밝혀졌다.
에필로그: 사건 종결 보고서
사건 번호: BOJ-21736
사건명: "헌내기는 친구가 필요해" DFS 시간 초과 미스터리
수사 결과: 해결 (Case Closed)
이것으로 한 편의 미스터리했던 사건이 막을 내렸다.
이제 최종 보고서를 통해 사건의 전말을 정리해보자.
최종 보고서
본 사건은 동일한 시간 복잡도($O(N \times M)$)라는 알리바이를 가졌음에도, 유독 '재귀 기반 DFS'만이 시간 초과 판결을 받은 기이한 현상이었다.
수사 초기, 모든 증거는 DFS를 범인으로 지목하는 듯했다. 하지만 심층 수사 결과, 진범은 DFS라는 알고리즘 자체가 아닌, 그것을 구현한 '재귀'라는 비효율적이고 위험한 방식이었음이 밝혀졌다. 특히 자바(JVM) 환경의 특성(꼬리 재귀 최적화 미지원)과 맞물려, 재귀는 '함수 호출 오버헤드'와 치명적인 '스택 오버플로우'를 유발하며 스스로 무너져 내렸다.
결정적으로, '스택(Stack)을 이용한 반복문'이라는 새로운 방식으로 무장한 DFS는 누명을 벗고 BFS와 대등한 성능을 입증해 보였다. 이로써 우리는 진범이 '알고리즘'이 아닌 '구현'에 있었음을 명백히 확인하며 본 사건을 종결한다.
탐정의 수사 원칙 (실전 코딩 테스트 전략)
이 사건 파일을 덮기 전, 모든 탐정들이 기억해야 할 세 가지 핵심 수사 원칙이 있다.
- 최단 경로를 찾거나 거대한 맵을 안전하게 탐색할 때는, BFS를 첫 번째 용의선상에 올려라.
BFS는 스택 오버플로우의 위험이 없으며, 구조적으로 안정적이고 신뢰도 높은 최선의 선택지 중 하나다. - DFS를 사용해야 한다면, '재귀'의 함정을 경계하라.
백트래킹 등 특정 상황에서는 재귀가 직관적일 수 있다. 하지만 입력 데이터가 크다면, 스택 오버플로우를 피할 수 있는 '반복문과 스택을 이용한 DFS'를 우선적으로 고려해야 한다. - 이론이 전부가 아님을 명심하라.
시간 복잡도는 위대한 지표지만, 절대적인 왕은 아니다. 실제 성능은 우리가 사용하는 언어의 특징, 자료구조의 선택, 그리고 하드웨어의 동작 방식까지 모든 것이 얽혀 만들어 내는 복잡한 결과물이다.
이제 이 미스터리를 해결했고, 한 단계 더 성장한 탐정이 되었다. 앞으로 마주할 수많은 코딩 테스트 현장에서, 이 경험이 여러분의 추리를 더욱 날카롭게 만들어 줄 것이라 믿는다.
🚀 전체 코드
import java.util.Stack;
import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n;
static int m;
static 좌표[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
n = Integer.parseInt(stringTokenizer.nextToken());
m = Integer.parseInt(stringTokenizer.nextToken());
map = new 좌표[n][m];
좌표 start = null;
for (int i = 0; i < n; i++) {
stringTokenizer = new StringTokenizer(br.readLine());
String trim = stringTokenizer.nextToken().trim();
for (int j = 0; j < m; j++) {
String type = String.valueOf(trim.charAt(j));
map[i][j] = new 좌표(i, j, type);
if (type.equals("I")) {
start = map[i][j];
}
}
}
int result = dfsByStack(start);
if (result == 0) {
System.out.println("TT");
} else {
System.out.println(result);
}
}
public static int bfs(좌표 start){
Queue <좌표> queue = new ArrayDeque<>();
queue.offer(start);
int count = 0;
while (!queue.isEmpty()) {
좌표 cur = queue.poll();
if (cur.visited || cur.is벽()) {
continue;
}
cur.markVisited();
if (cur.is사람()) {
count++;
}
for (좌표 nxt : cur.getAdjacent()) {
if (!nxt.visited && !nxt.is벽()) {
queue.offer(nxt);
}
}
}
return count;
}
/**
* 시간 초과
*/
public static int dfs(좌표 cur) {
if (cur.visited || cur.is벽()) {
return 0;
}
cur.markVisited();
int count = 0;
if (cur.is사람()) {
count++;
}
for (좌표 nxt : cur.getAdjacent()) {
if (!nxt.visited && !nxt.is벽()) {
count += dfs(nxt);
}
}
return count;
}
public static int dfsByStack(좌표 start) {
Stack<좌표> stack = new Stack<>();
stack.push(start);
int count = 0;
while (!stack.isEmpty()) {
좌표 cur = stack.pop();
if (cur.visited || cur.is벽()) {
continue;
}
cur.markVisited();
if (cur.is사람()) {
count++;
}
for (좌표 nxt : cur.getAdjacent()) {
if (!nxt.visited && !nxt.is벽()) {
stack.push(nxt);
}
}
}
return count;
}
public static class 좌표 {
int x;
int y;
String type;
boolean visited;
public 좌표(int x, int y, String type) {
this.x = x;
this.y = y;
this.type = type;
this.visited = false;
}
private boolean is도연() {
return type.equals("I");
}
private boolean is벽() {
return type.equals("X");
}
private boolean is길() {
return type.equals("O");
}
private boolean is사람() {
return type.equals("P");
}
public List<좌표> getAdjacent() {
List<좌표> neighbors = new ArrayList<>(4);
int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
for (int[] d : dirs) {
int nx = this.x + d[0];
int ny = this.y + d[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
neighbors.add(map[nx][ny]);
}
}
return neighbors;
}
public void markVisited() {
this.visited = true;
}
}
}
'알고리즘' 카테고리의 다른 글
| "느린 정렬"은 정말 항상 느릴까? (feat. 버블, 삽입 정렬의 재발견) (0) | 2025.06.28 |
|---|---|
| 백트래킹 개념, 유망 함수와 가지치기, 예시 문제로 이해하기 (0) | 2025.05.25 |
| 집합, 유니온 파인드 알고리즘, 개념과 구현 + 최적화 + 활용 예시까지 (시간 복잡도와 재귀 호출 스택 디테일 포함) (0) | 2025.05.04 |
| 이진 탐색 트리로 왜 충분하지 않을까? M원 트리 그리고 B-트리의 등장 이유 (B트리, B+트리, B* 트리 연산까지) (0) | 2025.04.27 |
| 다익스트라 알고리즘 완벽 가이드: 2차원 행렬부터 우선순위 큐까지, 자바 구현으로 배우는 최단 경로 찾기 (0) | 2025.04.26 |
