Learn Valid Parentheses, Reverse Linked List, and Tree Max Depth with Step-by-Step Visualization in DSA View View 👀👀
Hoi hoi! I’m @nyaomaru, a frontend engineer who struggles to make game sounds. 😿 Have you used DSA...
개요 #
알고리즘 문제를 풀다 보면 이런 순간이 온다. 코드 한 줄 한 줄은 다 이해가 되는데, 전체가 어떻게 돌아가는지는 여전히 흐릿하다. 프론트엔드 엔지니어 nyaomaru가 만든 DSA View View는 바로 그 간극을 겨냥한 도구다. TypeScript로 구현한 알고리즘을 직접 실행시키고, 런타임 상태를 한 스텝씩 앞뒤로 넘겨가며 볼 수 있다.
이번 글에서 다룬 문제는 세 개다. Valid Parentheses, Reverse Linked List, Maximum Depth of Binary Tree. 겉보기엔 공통점이 없어 보이지만, 각각 스택 · 포인터 조작 · 재귀라는 완전히 다른 사고 방식을 하나씩 담고 있다. 그리고 셋 다 최종 코드만 들여다봐서는 머릿속에 잘 안 그려지는 부류다.
앞선 글에서는 Two Sum, Binary Search, Bubble Sort를 같은 방식으로 다뤘다.
이전 글: Two Sum, Binary Search, Bubble Sort 편 보기 →
🥞 Valid Parentheses — 스택 #
문자열 ()[]{}은 유효하다. 여는 괄호마다 짝이 되는 닫는 괄호가 있다. 반면 ([)]는 유효하지 않다. 괄호는 다 짝이 맞는데, 닫히는 순서가 틀렸다.
(
[
)
][가 (보다 먼저 닫혀야 한다. 그럼 이 "순서"를 어떻게 추적할까?
스택이 자연스러운 이유 #
스택의 규칙은 단순하다. 마지막에 넣은 것을 가장 먼저 꺼낸다. LIFO(Last In / First Out)다. 접시를 쌓는 장면을 떠올리면 된다.
🍽️ ← 먼저 꺼내는 것
🍽️
🍽️맨 위에 마지막으로 올린 접시가 제일 먼저 손에 잡힌다. 괄호도 똑같다. (, [, { 순서로 열렸다면 닫히는 순서는 반드시 }, ], )가 된다. 역순이다. 스택이 딱 맞아떨어지는 구조다.
구현은 이렇다.
function isValid(s: string): boolean {
const stack: string[] = [];
const pairs: Record<string, string> = {
")": "(",
"]": "[",
"}": "{",
};
for (const char of s) {
if (char === "(" || char === "[" || char === "{") {
stack.push(char);
continue;
}
if (stack.length === 0) return false;
const target = stack.pop();
if (target !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}핵심은 stack이 어떻게 변하느냐다. ([])를 넣어보자.
빈 스택에서 시작해 (를 만나면 push한다. stack = ["("]. [도 여는 괄호니까 push. stack = ["(", "["]. 다음은 ]. 닫는 괄호다. 이건 [를 닫아야 하는데, 스택 맨 위에 있는 것도 [다. 일치하니 pop. stack = ["("]. 마지막 )도 마찬가지로 스택 top의 (와 맞아떨어져 pop. stack = [].
문자열 끝에 도달했고 스택이 비어 있다. 유효하다. 🎉
실패하는 경우 #
([)]는 어디서 걸릴까?
(
↓
stack = ["("]
[
↓
stack = ["(", "["]여기서 )를 만난다. )는 (를 필요로 하는데 스택 top은 [다.
expected: (
actual: [일치하지 않는 순간 바로 false를 반환한다. 나머지를 볼 필요도 없다.
복잡도 #
문자열을 한 번만 순회한다.
Time: O(n)
Space: O(n)최악의 경우 스택에 여는 괄호가 전부 쌓인다.
👀 눈으로 확인하기 #
stack.push(char)와 stack.pop()만 읽으면, 지금 스택 안에 뭐가 들어 있는지 놓치기 쉽다. ({[]}) 같은 입력이라면 더 그렇다. 지금 top이 뭐지? 어떤 여는 괄호를 닫으려는 중이지?
머릿속에 다 담아두는 대신, 스택이 변하는 과정을 한 스텝씩 따라가면 된다.
DSA View View에서 Valid Parentheses 실행해보기 →
개념적으로는 이런 흐름이다.
(
↓
[(]
{
↓
[(, {]
[
↓
[(, {, []
]
↓
[(, {]
}
↓
[(]
)
↓
[]열린 괄호를 기억해두고, 항상 가장 최근 것부터 맞춰라.
이게 전부다. 스택이 갑자기 훨씬 덜 신비해진다.
🔗 Reverse Linked List — 포인터 #
다음은 연결 리스트 뒤집기다. 1 → 2 → 3 → 4 → 5를 5 → 4 → 3 → 2 → 1로 만든다.
말로 하면 간단한데, 연결 리스트는 배열과 사정이 다르다. 배열은 값이 인덱스 위치에 그냥 놓여 있다.
0 1 2 3 4
↓ ↓ ↓ ↓ ↓
1 2 3 4 5연결 리스트는 각 노드가 다음 노드를 가리키는 구조다.
1 → 2 → 3 → 4 → 5 → null화살표 하나하나가 의미를 갖는다. 리스트를 뒤집는다는 건 이 화살표들의 방향을 바꾸는 일이다.
1 ← 2 ← 3 ← 4 ← 5여기서 함정이 있다. 화살표를 너무 일찍 바꿔버리면, 리스트의 나머지 부분으로 갈 길이 사라진다. 😿
변수 세 개 #
반복문 해법은 prev, current, next 세 변수를 쓴다.
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let current = head;
while (current !== null) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}짧다. 그런데 이 몇 줄 안에서 벌어지는 일은 꽤 많다. 1 → 2 → 3 → null로 천천히 따라가보자. 시작 상태는 prev = null, current = 1이다.
1단계 — 다음 노드 저장. const next = current.next;로 next = 2를 확보한다. 왜 필요할까? 곧 1 → 2 화살표를 바꿀 참인데, 2를 기억해두지 않고 바꾸면 나머지 리스트에 접근할 방법이 없어진다. 먼저 갈 곳을 저장한다.
2단계 — 화살표 뒤집기. current.next = prev;. 원래 1 → 2였지만 prev가 null이니 이제 1 → null이 된다. 첫 화살표가 뒤집혔다.
3단계 — prev 이동. prev = current; 로 prev = 1.
4단계 — current 이동. current = next; 아까 저장해둔 2로 옮겨간다.
상태는 이렇게 된다.
null ← 1 2 → 3 → null
↑ ↑
prev current그리고 정확히 같은 일을 반복한다. next = 3 저장, 2 → 1로 뒤집기, prev = 2 / current = 3으로 이동.
null ← 1 ← 2 3 → null
↑ ↑
prev current한 번 더. next = null, 3 → 2 뒤집기, prev = 3 / current = null.
null ← 1 ← 2 ← 3
↑
prevcurrent === null이므로 반복문이 멈추고, prev가 새로운 head가 된다. return prev; 🎉
복잡도 #
각 노드를 한 번씩만 방문한다.
Time: O(n)
Space: O(1)새 리스트를 만들지 않는다. 포인터 몇 개만 옮길 뿐이다.
👀 눈으로 확인하기 #
원문 저자가 "읽기만 해서는 이해하기 어려운 코드"의 대표 사례로 꼽은 게 바로 이 네 줄이다.
const next = current.next;
current.next = prev;
prev = current;
current = next;단순해 보이지만, 처음 보면 머릿속에서 질문이 쏟아진다.
잠깐.
- current는 지금 어디 있지?
- next를 잃어버린 건가?
- 어떤 화살표가 바뀐 거지?
- prev는 정확히 뭘 가리키고 있지?
DSA View View에서 Reverse Linked List 실행해보기 →
단계별로 시각화하면 포인터가 움직이는 모습을 그대로 쫓아갈 수 있다.
prev current
↓ ↓
null 1 → 2 → 3
↓↓↓
null ← 1 2 → 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 ← 3
↑
prev정체불명의 대입문 네 개로 보지 않게 되는 순간, 알고리즘은 훨씬 간단해진다. 실제로는 이런 리듬일 뿐이다.
next 저장
↓
화살표 뒤집기
↓
prev 이동
↓
current 이동
↓
반복🌳 Maximum Depth of Binary Tree — 재귀 #
마지막은 트리다.
3
/ \
9 20
/ \
15 7이 트리의 최대 깊이는? 루트에서 리프까지 가장 긴 경로는 3 → 20 → 15, 노드 세 개다. 답은 3.
작은 트리로 생각하기 #
어느 한 노드에 서 있다고 하자. 트리 전체를 한꺼번에 이해할 필요는 없다. 딱 두 가지만 물으면 된다. 왼쪽 서브트리의 깊이는? 오른쪽 서브트리의 깊이는? 둘 중 큰 값을 고르고, 현재 노드 몫으로 1을 더한다.
function maxDepth(root: TreeNode | null): number {
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}핵심은 Math.max(leftDepth, rightDepth) + 1 한 줄이다. 그런데 재귀는 낯설게 느껴진다. maxDepth(root.left)를 호출하는 순간 현재 함수는 어디로 가는가? 그 많은 호출들이 어떻게 결국 숫자 하나가 되는가?
작은 예제로 따라가보자.
1
/ \
2 3
/
41에서 시작한다. 하지만 1은 자기 깊이를 알기 전에 왼쪽 자식에게 maxDepth(2)를 묻는다. 2는 다시 maxDepth(4)를 묻는다. 4는 자식이 없으니 양쪽 모두 null에 도달하고, maxDepth(null)은 0을 반환한다.
그래서 4는 max(0, 0) + 1 = 1을 계산할 수 있게 된다. 이 값이 2로 돌아간다. 2의 왼쪽 깊이는 1, 오른쪽은 null이라 0. max(1, 0) + 1 = 2가 된다.
다시 1로 돌아온다. 오른쪽 서브트리도 1을 반환하므로 leftDepth = 2, rightDepth = 1. 최종적으로 max(2, 1) + 1 = 3. 🎉
내려갔다가 다시 올라온다 #
재귀가 재미있어지는 지점이 여기다. 함수 호출은 트리를 따라 아래로 내려간다.
1
↓
2
↓
4
↓
null하지만 답은 위로 되돌아오면서 만들어진다.
null → 0
4 → 1
2 → 2
1 → 3재귀는 그저 "같은 함수를 계속 부르는 것"이 아니다. 방향이 둘이다.
내려간다
↓
base case에 도달한다
↓
값을 위로 되돌린다여기서 base case는 if (root === null) return 0;이다. 이게 없으면 재귀는 멈출 자리를 잃는다.
복잡도 #
모든 노드를 한 번씩 방문한다.
Time: O(n)재귀 호출 스택은 트리 높이에 비례한다.
Space: O(h)균형 잡힌 트리라면 대략 O(log n)이다. 반대로 트리가 연결 리스트처럼 한쪽으로만 뻗은 최악의 경우라면
1
\
2
\
3
\
4깊이는 O(n)까지 늘어난다.
👀 눈으로 확인하기 #
원문 저자는 재귀를 시각화 사례로 가장 좋아한다고 했다. 최종 구현은 이렇게 작은데,
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;그 함수 호출 안쪽에 숨어 있는 게 너무 많다. 코드만 읽으면 이런 느낌이 든다.
maxDepth()
inside maxDepth()
inside maxDepth()
inside maxDepth()
...지금 우리는 어디에 있는 거지? 😿
DSA View View에서 Maximum Depth of Binary Tree 실행해보기 →
실행을 한 스텝씩 밟아보면 두 방향을 모두 따라갈 수 있다. 내려가는 길과
1
↓
2
↓
4
↓
null돌아오는 길.
null → 0
↓
4 → 1
↓
2 → 2
↓
1 → 3더 작은 하위 문제들에게 답을 물어보고, 그 답으로 현재 답을 만든다.
🧠 세 문제가 남긴 것 #
문제 셋은 완전히 달라 보이지만, 각각 쓸모 있는 사고 틀을 하나씩 준다.
Valid Parentheses — 가장 최근 항목을 먼저 처리해야 할 때는 스택을 쓴다.
내가 마지막으로 연 게 뭐였지?Reverse Linked List — 참조를 바꿀 때는, 기존 연결을 끊기 전에 아직 필요한 것을 저장해둔다.
이 포인터를 바꾸기 전에, 다음에 가야 할 곳은 어디지?Maximum Depth of Binary Tree — 문제를 같은 문제의 더 작은 버전으로 쪼갠다.
자식들에게 답을 받아서 내 답을 만들 수 있나?세 문제를 묶어서 배우는 이유가 여기 있다. 구현 자체는 크지 않다. 그런데 각각이 스택, 포인터, 재귀라는 서로 다른 멘탈 모델을 하나씩 끌고 온다. 그리고 이 멘탈 모델은 문법보다 익히기 훨씬 어렵다.
코드는 무슨 일이 일어나는지를 알려준다. 하지만 어떻게 일어나는지도 보고 싶다는 게 저자의 문제의식이다.
Photo by 🎯 마무리 #
정리하면 이렇다. 스택으로 푸는 Valid Parentheses, 포인터 조작으로 푸는 Reverse Linked List, 재귀로 푸는 Maximum Depth of Binary Tree. 더 중요한 건 각 알고리즘이 실행되는 동안의 상태 변화를 따라갔다는 점이다.
스택이 쌓이고 비워지는 과정(stack.push() / stack.pop()), 연결 리스트를 훑고 지나가는 prev · current · next, 그리고 트리를 타고 내려갔다가 답을 안고 올라오는 재귀 호출까지.
DSA View View는 이걸 보려고 만든 도구다. TypeScript 구현을 직접 쓰거나 불러와서, 원하는 입력으로 실행하고, 런타임을 앞뒤로 이동할 수 있다.
혹시 알고리즘을 공부하다가 "줄 단위로는 다 알겠는데 전체가 뭔지 모르겠다" 싶은 순간이 있었다면, 실행 과정을 보는 쪽이 그 조각들을 이어줄지도 모른다.
저자는 다음에 다뤘으면 하는 문제를 댓글로 알려달라고 했다. 마음에 들었다면 저장소에 스타도 환영이라고.
이 글은 위 출처를 바탕으로 한국 독자를 위해 재작성한 기사입니다. 원문의 사실과 수치에 근거하며, 별도의 견해를 포함하지 않습니다.