자료구조 공부를 시작할 때 큐(Queue)와 스택(Stack)이 제일 헷갈렸습니다. 이름은 아는데 막상 코드로 구현하려고 하면 손이 멈추는 그 느낌, 저도 똑같이 겪었습니다. 이번 글에서는 스택의 개념부터 실제 활용인 후위식 변환, 그리고 DFS 탐색까지 제가 직접 구현하면서 정리한 내용을 풀어보겠습니다.
스택 구현과 후위식 변환
스택은 LIFO(Last In First Out) 방식으로 동작하는 자료구조입니다. 여기서 LIFO란 가장 마지막에 들어온 데이터가 가장 먼저 나오는 구조를 말합니다. 접시를 쌓는 모습을 떠올리면 쉽습니다. 맨 위에 올려놓은 접시를 먼저 꺼내야 하는 것처럼, 스택도 마찬가지입니다.
저도 처음에 선입선출(FIFO)과 헷갈려서 꽤 고생했습니다. 둘의 차이를 명확히 잡고 나서야 코드가 눈에 들어오기 시작했습니다.
스택의 핵심 연산은 두 가지입니다.
- push: 스택의 가장 위(top)에 데이터를 삽입하는 연산. top 값을 1 증가시킨 뒤 해당 인덱스에 데이터를 저장합니다.
- pop: 스택의 가장 위(top)에서 데이터를 꺼내는 연산. 데이터를 null로 비운 뒤 top 값을 1 감소시킵니다.
직접 배열로 구현해보면서 느낀 점이 있습니다. top을 -1로 초기화하는 이유가 처음에는 어색했는데, 배열의 첫 인덱스가 0이기 때문에 데이터가 없는 초기 상태를 -1로 표현하는 것이 꽤 자연스럽다는 걸 나중에서야 이해했습니다. isEmpty() 메서드에서 top == -1이면 true를 반환하는 로직도 그래서 나온 것입니다.
이 스택을 실제로 활용하는 대표적인 예가 중위식(Infix)을 후위식(Postfix)으로 변환하는 문제입니다. 여기서 중위식이란 1 + 3 * 5처럼 연산자가 피연산자 사이에 오는 수식 표현 방식입니다. 반면 후위식은 1 3 5 * +처럼 연산자가 피연산자 뒤에 오는 방식으로, 컴퓨터가 연산 우선순위 없이 왼쪽에서 오른쪽으로 순서대로 계산할 수 있어 프로그램 내부에서 널리 활용됩니다.
변환 로직을 처음 봤을 때 솔직히 이건 예상 밖이었습니다. 연산자 우선순위(precedence)를 비교해서 스택에서 pop할 타이밍을 잡는 부분이 특히 까다로웠습니다. 규칙을 정리하면 다음과 같습니다.
- 숫자는 그대로 결과 문자열에 추가합니다.
- 연산자가 나오면 스택과 우선순위를 비교합니다. 현재 연산자의 우선순위가 스택 top보다 높으면 push, 낮거나 같으면 스택을 pop하여 출력한 뒤 push합니다.
- 여는 괄호 (는 그냥 스택에 넣고, 닫는 괄호 )가 나오면 여는 괄호가 나올 때까지 pop하여 출력합니다. 괄호는 결과에 포함하지 않습니다.
- 수식이 끝나면 스택이 빌 때까지 pop하여 출력합니다.
후위식으로 변환된 수식은 이후 다시 스택을 활용해서 계산할 수 있습니다. 숫자는 스택에 push하고, 연산자가 나오면 스택에서 숫자 두 개를 pop하여 계산한 뒤 결과를 다시 push하는 방식입니다. 48 / 2 * (9 + 3) 같은 수식도 이 방법으로 288이라는 결과를 정확하게 얻을 수 있습니다. 제가 직접 돌려봤을 때 연산자의 pop 순서, 즉 num1과 num2를 꺼내는 순서가 뒤바뀌면 나눗셈과 뺄셈에서 결과가 달라지기 때문에 이 부분을 특히 주의해야 합니다.
자바에서는 java.util.Stack 클래스가 이미 제공되지만(출처: Oracle Java Documentation), 직접 배열로 구현해보는 경험이 자료구조의 동작 원리를 이해하는 데 훨씬 도움이 됩니다. 라이브러리만 쓰다 보면 내부에서 어떤 일이 일어나는지 모른 채 넘어가게 되거든요.
DFS 탐색과 재귀함수 활용
스택을 가장 실감 나게 활용할 수 있는 알고리즘이 바로 DFS(Depth First Search)입니다. 여기서 DFS란 깊이 우선 탐색을 의미하며, 그래프에서 한 경로를 끝까지 탐색한 뒤 다시 돌아와 다른 경로를 탐색하는 방식입니다. 미로를 풀 때 한 방향으로 끝까지 가보고, 막히면 되돌아오는 것과 같은 원리입니다.
그래프(Graph)는 노드(정점)와 간선으로 이루어진 자료구조입니다. 여기서 간선이란 노드와 노드 사이의 연결 관계를 나타내는 선입니다. 간선에 방향이 있는 경우를 방향 그래프, 방향이 없어 양방향 이동이 가능한 경우를 무방향 그래프라고 합니다.
DFS는 스택으로도 구현할 수 있고, 재귀함수(recursive function)로도 구현할 수 있습니다. 여기서 재귀함수란 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 팩토리얼 계산을 예로 들면, 5!을 계산할 때 calcRecur(5)가 calcRecur(4)를 호출하고, calcRecur(4)가 calcRecur(3)을 호출하는 식으로 num == 1이 될 때까지 자기 자신을 반복 호출하다가 하나씩 값을 반환하며 풀립니다.
제가 직접 써봤는데, 재귀로 DFS를 구현하면 코드가 훨씬 간결해지지만 입력 크기가 커지면 스택 오버플로우(StackOverflow)가 발생할 수 있습니다. 스택 오버플로우란 함수 호출이 너무 깊어져서 콜 스택(call stack)이 할당된 메모리를 초과하는 오류를 말합니다. 반복문 기반 DFS가 안전한 경우가 있어서, 코딩테스트에서는 입력 크기를 보고 방식을 선택하는 것이 좋습니다.
코딩테스트에서 DFS를 적용한 대표 문제가 바로 여행 경로 문제입니다. ICN에서 출발해 모든 티켓을 한 번씩 사용하는 경로를 알파벳 순으로 구해야 합니다. 이 문제에서 핵심은 인접 리스트(adjacency list)를 알파벳 순으로 정렬해두고 DFS를 돌리는 것입니다. 인접 리스트란 각 노드에서 이동할 수 있는 노드들을 리스트 형태로 저장한 그래프 표현 방식입니다.
제 경험상 이 문제는 그래프 구성 단계에서 정렬을 미리 해두지 않으면 결과가 달라집니다. 구현 방법으로는 HashMap과 ArrayList를 조합하여 삽입 시 정렬을 유지하는 방법과, PriorityQueue를 사용하여 자동으로 정렬 상태를 유지하는 방법 두 가지가 있습니다. PriorityQueue를 쓰는 편이 코드가 훨씬 간결해지는데, computeIfAbsent 메서드를 활용하면 한 줄로 그래프 구성이 끝납니다. 처음 봤을 때는 낯설었지만 한 번 익혀두면 반복 사용하게 되는 패턴입니다.
자료구조와 알고리즘 학습에 대해 국내 주요 SW 교육 기관들도 스택, 큐, 그래프 탐색을 기초 필수 역량으로 분류하고 있습니다(출처: 정보통신산업진흥원(NIPA)). 그만큼 이 개념들을 확실히 잡고 넘어가는 것이 이후 복잡한 알고리즘을 이해하는 데 직접적인 영향을 줍니다.
스택 하나를 제대로 이해하고 나면 후위식 변환, DFS, 재귀함수까지 연결되는 흐름이 보이기 시작합니다. 처음에는 각각 따로따로 외우려고 했는데, 결국 스택이라는 하나의 구조 위에 올라가 있다는 걸 깨닫고 나서야 복잡하게 느껴지지 않았습니다. 지금 이 개념이 낯설게 느껴진다면, 직접 배열로 push와 pop을 구현해보는 것부터 시작해 보시길 권합니다. 손으로 써보는 것만큼 빠른 이해가 없더라고요.