09편에서 스택은 LIFO(후입선출), 큐는 FIFO(선입선출) 성질을 가진 자료구조라고 배웠다. 이 편은 그 성질이 실제로 어떤 문제를 푸는 데 쓰이는지, 독학사 시험에서 반복해서 나오는 네 가지 응용을 단계별로 완전히 추적한다.

괄호 검사 — 스택으로 짝을 맞추는 문제

수식이나 코드에서 괄호 (, ), [, ], {, }가 올바르게 짝지어졌는지 확인하는 문제는 스택의 가장 대표적인 응용이다.

쉽게 말하면: 여는 괄호를 만나면 스택에 쌓아 두고, 닫는 괄호를 만나면 스택 맨 위(top)의 여는 괄호와 짝이 맞는지 확인한 뒤 꺼낸다. 마지막에 스택이 완전히 비어 있어야 모든 괄호가 짝을 이룬 것이다.

알고리즘

1. 문자열을 앞에서부터 한 글자씩 읽는다.
2. 여는 괄호((, [, {)를 만나면 스택에 push한다.
3. 닫는 괄호(), ], })를 만나면 스택에서 pop한다. 이때 두 가지를 확인한다.
   • 스택이 이미 비어 있으면 짝이 없는 닫는 괄호이므로 즉시 “오류”로 판정한다.
   • pop한 여는 괄호의 종류가 지금 읽은 닫는 괄호와 짝이 맞는 종류인지 확인한다. 다르면 “오류”다(예: 여는 괄호는 (인데 닫는 괄호가 ]인 경우).
4. 문자열을 끝까지 읽었을 때 스택이 비어 있으면 “정상”, 무언가 남아 있으면 “오류”(짝 없는 여는 괄호가 있었다는 뜻)다.

단계별 추적 — 정상 사례

문자열 ( a [ b ] c )를 검사하는 과정이다(괄호가 아닌 문자는 건너뛴다).

단계별 추적 — 오류 사례

문자열 ( a [ b ) c ]를 검사하는 과정이다.

3번째 단계에서 이미 짝이 어긋났으므로 나머지 문자는 볼 필요도 없이 “오류”로 확정된다.

자주 틀리는 점: 괄호 개수만 세어서(여는 괄호 개수와 닫는 괄호 개수가 같은지만) 판정하면 안 된다. ( ] ) 같은 문자열은 여는 괄호와 닫는 괄호 개수가 같지만 순서와 종류가 어긋나 있다. 반드시 스택으로 순서와 종류를 함께 검사해야 한다.

중위식을 후위식으로 바꾸기

우리가 일상적으로 쓰는 2 + 3 * 4 같은 표기법을 중위 표기법(infix notation, 연산자가 피연산자 “사이”에 있다)이라고 부른다. 그런데 컴퓨터가 수식을 계산할 때는 괄호와 연산자 우선순위를 매번 따져야 하는 중위식보다, 연산자가 피연산자 뒤에 오는 후위 표기법(postfix notation, 또는 역폴란드 표기법(Reverse Polish Notation, RPN))이 계산하기 훨씬 단순하다. 그래서 컴파일러나 계산기 내부에서는 중위식을 후위식으로 바꾼 뒤 계산한다.

쉽게 말하면: 중위식은 사람이 읽기 편한 표기법이고, 후위식은 컴퓨터가 괄호와 우선순위 고민 없이 앞에서부터 순서대로 계산하기 편한 표기법이다. 스택은 이 변환 과정에서 “아직 출력할 자리가 안 된 연산자”를 잠시 보관하는 대기 장소 역할을 한다.

변환 알고리즘

1. 입력을 왼쪽부터 한 토큰(피연산자 또는 연산자 또는 괄호)씩 읽는다.
2. 피연산자(숫자, 변수)를 만나면 바로 출력 리스트에 추가한다.
3. 여는 괄호 (를 만나면 스택에 push한다.
4. 닫는 괄호 )를 만나면, 스택에서 (가 나올 때까지 계속 pop하며 출력에 추가한다. ( 자체는 출력하지 않고 버린다.
5. 연산자를 만나면, 스택 top에 있는 연산자의 우선순위가 지금 만난 연산자의 우선순위보다 높거나 같은 동안 계속 pop하여 출력에 추가한 뒤, 지금 만난 연산자를 push한다.
6. 입력을 다 읽으면, 스택에 남아 있는 연산자를 모두 pop하여 출력에 추가한다.

연산자 우선순위는 *, /가 +, -보다 높다고 본다(수학에서 곱셈·나눗셈을 덧셈·뺄셈보다 먼저 계산하는 것과 같다).

단계별 추적 — A + B * C

최종 후위식은 A B C * +다. 이 결과는 “먼저 B와 C를 곱하고, 그 결과를 A와 더한다”는 뜻으로, 원래 중위식이 곱셈을 덧셈보다 먼저 계산해야 한다는 우선순위 규칙을 정확히 반영한다.

단계별 추적 — 괄호가 있는 경우 (A + B) * C

괄호 안의 A + B가 먼저 A B +로 묶여 출력되고, 그다음에 C, *가 이어져 “괄호 안을 먼저 계산하고 그 결과를 C와 곱한다”는 뜻이 정확히 유지된다.

후위식 계산하기

후위식을 얻었으면, 이번에는 스택을 이용해 피연산자만 쌓았다가 연산자를 만나면 꺼내서 계산하는 방식으로 값을 구한다.

알고리즘

1. 토큰을 왼쪽부터 읽는다.
2. 피연산자를 만나면 스택에 push한다.
3. 연산자를 만나면, 스택에서 값을 두 번 pop한다. 먼저 pop한 값이 오른쪽 피연산자, 나중에 pop한 값이 왼쪽 피연산자다(순서에 주의해야 한다 — 뺄셈·나눗셈처럼 순서가 결과에 영향을 주는 연산에서 특히 중요하다). 계산 결과를 다시 push한다.
4. 입력을 다 읽으면 스택에 남은 값 하나가 최종 결과다.

단계별 추적 — A B C * +에 A=2, B=3, C=4 대입

중위식으로 계산해도 곱셈을 먼저 하므로 3 * 4 = 12, 2 + 12 = 14로 같은 결과가 나온다. 후위식 계산은 우선순위나 괄호를 전혀 신경 쓰지 않고 왼쪽부터 순서대로 스택만 조작해서 같은 답에 도달한다는 점이 핵심이다.

자주 틀리는 점: 뺄셈이나 나눗셈처럼 순서가 중요한 연산에서 두 번 pop한 값의 순서를 거꾸로 쓰는 실수가 흔하다. 후위식 A B -를 계산할 때 먼저 pop되는 값은 B이고 나중에 pop되는 값은 A이므로, 계산식은 (나중에 pop한 값) - (먼저 pop한 값), 즉 A - B가 되어야 한다. B - A로 뒤집으면 오답이다.

함수 호출과 스택 — 재귀가 스택을 쓰는 이유

프로그램이 함수를 호출하면, 컴퓨터는 “이 함수가 끝나면 어디로 돌아가야 하는지”(복귀 주소)와 “그 함수 안에서 쓰는 지역 변수들”을 호출 스택(call stack)이라는 자료구조에 쌓아 둔다. 함수 A가 함수 B를 호출하면 B에 대한 정보가 A의 정보 위에 push되고, B가 끝나면 그 정보가 pop되면서 정확히 A가 호출했던 지점으로 되돌아간다. 함수 호출도 결국 “가장 최근에 호출된 함수가 가장 먼저 끝나고 돌아간다”는 LIFO 성질을 그대로 따르기 때문에 스택으로 관리하는 것이다.

이 성질이 가장 뚜렷하게 드러나는 예가 재귀(recursion, 함수가 자기 자신을 다시 호출하는 것)다. factorial(3)을 계산하는 재귀 함수를 호출했을 때 호출 스택이 어떻게 쌓이고 풀리는지 추적해 보자(factorial(n)은 n이 0이면 1을 반환하고, 그렇지 않으면 n * factorial(n - 1)을 반환한다고 하자).

호출은 3, 2, 1, 0 순서로 쌓였다가(push), 반환은 0, 1, 2, 3 순서로 풀린다(pop). 가장 나중에 호출된 factorial(0)이 가장 먼저 끝나고 반환하는 이 모습이 정확히 LIFO다.

자주 틀리는 점: 재귀 호출이 너무 깊어지면(예: 종료 조건이 없는 무한 재귀) 호출 스택에 정보가 계속 push되기만 하고 pop되지 않아, 결국 09편에서 본 스택 오버플로가 실제로 발생한다. “재귀의 무한 반복은 왜 위험한가”라는 질문의 정답이 바로 이것이다.

BFS와 큐 — 왜 너비 우선 탐색은 큐를 쓰는가

15편에서 그래프 탐색을 본격적으로 다루지만, 큐의 응용을 이해하려면 너비 우선 탐색(Breadth-First Search, BFS)의 감각을 먼저 잡아 두는 것이 좋다. BFS는 시작 지점에서 가까운 노드부터, 즉 “한 단계씩 넓게” 방문하는 탐색 방법이다. 이 “가까운 것부터 순서대로”라는 성질이 정확히 큐의 FIFO와 맞아떨어진다.

간단한 그래프(A가 B, C와 연결되고, B가 D와 연결된 경우)에서 A부터 BFS를 수행하는 과정을 큐로 추적해 보자.

최종 방문 순서는 A, B, C, D다. A와 직접 연결된 B, C를 먼저 다 방문한 뒤에야 B의 다음 단계인 D로 넘어가는 것을 볼 수 있다. 만약 큐 대신 스택을 썼다면(이 경우는 깊이 우선 탐색, Depth-First Search, DFS가 된다) A, B, D, C처럼 한 방향으로 최대한 깊이 들어갔다가 돌아오는 순서가 되어 전혀 다른 방문 순서가 만들어진다. 이 차이는 15편에서 인접행렬·인접리스트 표현과 함께 완전한 그래프 예제로 다시 다룬다.

쉽게 말하면: 스택으로 탐색하면 “한 방향으로 끝까지 파고들었다가 되돌아오는” 성향(DFS)이 되고, 큐로 탐색하면 “가까운 곳부터 사방으로 넓게 퍼지는” 성향(BFS)이 된다. 어떤 자료구조를 쓰느냐가 탐색의 모양 자체를 결정한다.

자주 틀리는 점

• 괄호 검사에서 개수만 세는 실수: 여는 괄호와 닫는 괄호의 개수가 같다고 해서 올바른 짝짓기라고 단정하면 안 된다. 순서와 종류까지 스택으로 확인해야 한다.
• 중위-후위 변환에서 우선순위 비교 방향을 반대로 적용하는 실수: 새 연산자를 push하기 전에는 “스택 top의 우선순위가 새 연산자보다 높거나 같은 동안” 계속 pop해야 한다. 이 조건을 반대로 적용하면 엉뚱한 순서로 출력된다.
• 후위식 계산에서 pop 순서를 뒤집는 실수: 뺄셈·나눗셈처럼 순서가 중요한 연산은 “나중에 pop한 값 연산 먼저 pop한 값” 순서를 지켜야 한다.
• 재귀와 반복문을 성능 차이 없이 항상 바꿔 쓸 수 있다고 착각하는 실수: 재귀는 호출 스택에 정보를 계속 쌓으므로, 매우 깊은 재귀는 반복문보다 메모리를 더 많이 쓰고 스택 오버플로 위험이 있다.
• DFS와 BFS를 사용하는 자료구조로 헷갈리는 실수: 스택(또는 재귀 호출 스택)을 쓰면 DFS, 큐를 쓰면 BFS라는 대응 관계를 정확히 기억해야 한다.

핵심 정리

• 괄호 검사는 여는 괄호를 push하고 닫는 괄호에서 pop하여 종류와 순서를 확인하며, 끝에 스택이 비어 있어야 정상이다.
• 중위식을 후위식으로 바꿀 때는 연산자를 스택에 임시로 쌓았다가 우선순위 비교 결과에 따라 출력하고, 후위식을 계산할 때는 피연산자를 push했다가 연산자를 만나면 두 번 pop해 계산한다.
• 함수 호출은 호출 스택에 의해 관리되며, 재귀 호출이 LIFO로 쌓였다가 풀리는 과정이 이를 잘 보여준다.
• BFS는 큐(FIFO)를 이용해 가까운 노드부터 순서대로 방문하고, DFS는 스택(또는 재귀)을 이용해 한 방향으로 깊이 들어갔다가 되돌아온다.

마무리 복습

참고 자료

• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 평가영역과 출제 범위를 확인할 수 있는 공식 자료.
• 국가평생교육진흥원 독학학위제  — 독학학위제 시험 체계 전반을 확인할 수 있는 공식 사이트.