스택, 큐, 덱으로 흐름 제어하기

순서가 문제의 절반을 결정한다

코딩 테스트 문제를 풀다 보면 값 자체보다 "어떤 순서로 들어오고, 어떤 순서로 나가야 하는가"가 더 중요한 순간이 자주 등장합니다. 괄호가 올바르게 닫히는지 확인해야 할 때, 프린터 대기열에서 어떤 문서가 먼저 출력되는지 계산해야 할 때, 일정 구간 안에서 최댓값을 빠르게 갱신해야 할 때가 그렇습니다.

이런 문제를 무작정 배열 하나로 처리하려고 하면 코드가 쉽게 복잡해집니다. 앞에서 빼고, 뒤에서 넣고, 중간을 지우고, 다시 검사하는 식의 구현이 반복되면 실수할 지점도 늘어납니다. 반대로 자료구조를 잘 고르면 문제의 규칙이 아주 짧은 코드로 정리됩니다.

이번 장에서 다룰 스택, 큐, 덱은 모두 "흐름"을 다루는 자료구조입니다. 세 자료구조의 차이는 어디에서 넣고 어디에서 빼느냐에 있습니다.

• 스택은 마지막에 들어온 것이 먼저 나갑니다.

• 큐는 먼저 들어온 것이 먼저 나갑니다.

• 덱은 양쪽 끝에서 넣고 뺄 수 있습니다.

이 단순한 차이가 문제 풀이에서는 매우 큰 차이를 만듭니다. 코딩 테스트에서는 자료구조를 외우는 것보다, 문제의 흐름을 보고 "이 흐름은 스택인가, 큐인가, 덱인가?"를 판단하는 감각이 더 중요합니다.

스택: 가장 최근의 상태를 기억하는 구조

스택은 접시를 쌓아 올린 모습과 비슷합니다. 접시를 하나씩 위에 올리고, 꺼낼 때도 가장 위에 있는 접시부터 꺼냅니다. 즉, 마지막에 들어온 데이터가 가장 먼저 나갑니다. 이런 방식을 LIFO, 즉 Last In First Out이라고 부릅니다.

코딩 테스트에서 스택은 "가장 최근에 등장한 것"을 기준으로 판단해야 할 때 특히 강력합니다. 최근에 열린 괄호, 최근에 방문한 위치, 아직 짝을 찾지 못한 값, 이전 상태로 되돌아가기 위한 기록 등이 대표적인 예입니다.

파이썬에서는 보통 리스트를 스택처럼 사용합니다.

stack = []

stack.append(10)  # push
stack.append(20)

x = stack.pop()   # pop, 20

append()와 pop()은 리스트의 뒤쪽에서 동작할 때 평균적으로 O(1)에 처리됩니다. 따라서 스택 문제에서는 리스트를 그대로 사용해도 충분한 경우가 많습니다.

괄호 검사: 스택의 가장 기본적인 얼굴

스택을 처음 익힐 때 가장 좋은 문제는 괄호 검사입니다. 예를 들어 문자열 "({[]})"는 올바른 괄호 문자열이지만, "([)]"는 올바르지 않습니다. 왜 그럴까요?

괄호의 규칙은 단순합니다. 나중에 열린 괄호가 먼저 닫혀야 합니다. (를 열고 그 안에서 [를 열었다면, [가 먼저 닫히고 그다음 (가 닫혀야 합니다. 이것은 스택의 LIFO 구조와 정확히 맞아떨어집니다.

풀이 흐름은 다음과 같습니다.

• 여는 괄호가 나오면 스택에 넣습니다.

• 닫는 괄호가 나오면 스택의 맨 위 괄호와 짝이 맞는지 확인합니다.

• 끝까지 처리한 뒤 스택이 비어 있으면 올바른 괄호 문자열입니다.

코드로 쓰면 다음과 같습니다.

def is_valid_parentheses(s):
    stack = []
    pairs = {
        ')': '(',
        ']': '[',
        '}': '{'
    }

    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack:
                return False
            if stack.pop() != pairs[ch]:
                return False

    return not stack

여기서 핵심은 닫는 괄호를 만났을 때 전체 문자열을 다시 살펴보지 않는다는 점입니다. 지금 필요한 정보는 "가장 최근에 닫히지 않은 여는 괄호" 하나뿐입니다. 그 정보를 스택이 정확히 제공해 줍니다.

이 문제를 배열 인덱스와 조건문만으로 처리하려고 하면 금방 복잡해집니다. 하지만 스택을 사용하면 규칙이 그대로 코드가 됩니다. 좋은 자료구조를 고른다는 것은 바로 이런 뜻입니다.

이전 상태를 복원하는 문제

스택은 "되돌리기"에도 자주 사용됩니다. 문서 편집기의 실행 취소, 웹 브라우저의 뒤로 가기, 문자열 폭발 문제, 커서 이동 문제 등은 모두 이전 상태를 저장하고 필요할 때 되돌아가는 흐름을 가집니다.

예를 들어 문자열에서 #이 나오면 바로 앞 문자를 지우는 문제가 있다고 해 봅시다.

입력이 다음과 같다면,

ab#c

a를 넣고, b를 넣은 뒤, #을 만나면 b를 제거합니다. 이후 c를 넣으면 결과는 ac가 됩니다.

이 흐름도 스택으로 자연스럽게 표현됩니다.

def apply_backspace(s):
    stack = []

    for ch in s:
        if ch == '#':
            if stack:
                stack.pop()
        else:
            stack.append(ch)

    return ''.join(stack)

여기서 스택은 현재까지 완성된 문자열 상태를 저장합니다. #은 가장 최근에 입력된 문자를 지우므로 pop()과 잘 맞습니다. 만약 문자열을 매번 직접 잘라서 처리하면 길이가 긴 입력에서 비효율적일 수 있습니다. 반면 스택은 각 문자를 한 번씩만 처리하므로 전체 시간 복잡도는 O(n)입니다.

단조 스택: 쌓되, 규칙을 유지하며 쌓는다

스택 문제 중 조금 더 어려운 유형으로 단조 스택이 있습니다. 단조 스택은 스택 내부의 값들이 증가하거나 감소하는 상태를 유지하도록 관리하는 패턴입니다. "단조"라는 말은 한쪽 방향으로만 변한다는 뜻입니다. 예를 들어 스택 안의 값이 아래에서 위로 갈수록 점점 커지거나, 반대로 점점 작아지게 유지합니다.

단조 스택은 보통 다음과 같은 질문에 등장합니다.

• 각 원소의 오른쪽에서 처음으로 자신보다 큰 값은 무엇인가?

• 각 날짜 이후 며칠 뒤에 더 따뜻한 날이 오는가?

• 막대 그래프에서 만들 수 있는 가장 큰 직사각형은 무엇인가?

• 현재 값 때문에 이전 값들의 답이 결정되는가?

예를 들어 "오른쪽에 있는 첫 번째 큰 수"를 찾는 문제를 생각해 봅시다. 배열 [2, 1, 5, 3, 4]가 있을 때, 각 위치에서 오른쪽으로 가며 처음 만나는 더 큰 수를 찾아야 합니다. 2의 오른쪽 첫 번째 큰 수는 5, 1의 오른쪽 첫 번째 큰 수도 5, 5의 오른쪽에는 더 큰 수가 없으므로 -1입니다.

단순하게 각 위치마다 오른쪽을 끝까지 검사하면 O(n²)이 됩니다. 배열 길이가 100,000이면 위험합니다. 단조 스택을 사용하면 각 원소가 스택에 한 번 들어가고 한 번 나오므로 O(n)에 처리할 수 있습니다.

def next_greater_elements(arr):
    n = len(arr)
    answer = [-1] * n
    stack = []  # 아직 더 큰 값을 찾지 못한 인덱스 저장

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            answer[idx] = arr[i]
        stack.append(i)

    return answer

이 코드에서 스택에는 "아직 답을 찾지 못한 인덱스"가 들어 있습니다. 현재 값 arr[i]가 스택 맨 위 인덱스의 값보다 크다면, 그 인덱스의 답은 현재 값으로 결정됩니다. 왜냐하면 왼쪽에서 오른쪽으로 차례대로 보고 있으므로, 현재 값이 오른쪽에서 처음 만난 더 큰 값이기 때문입니다.

단조 스택을 처음 보면 while문 때문에 O(n²)처럼 느껴질 수 있습니다. 하지만 각 인덱스는 스택에 최대 한 번 들어가고 최대 한 번 빠져나옵니다. 따라서 전체적으로 보면 O(n)입니다. 이 관점은 코딩 테스트에서 매우 중요합니다. 반복문이 중첩되어 있어도, 실제로 각 원소가 몇 번 처리되는지 따져 보면 더 정확한 시간 복잡도를 판단할 수 있습니다.

큐: 먼저 온 것을 먼저 처리하는 구조

큐는 줄 서기와 같습니다. 먼저 온 사람이 먼저 서비스를 받습니다. 이런 방식을 FIFO, 즉 First In First Out이라고 부릅니다. 코딩 테스트에서는 대기열, 작업 처리, 순서대로 확산되는 과정, 최단 거리 탐색 등에 자주 사용됩니다.

파이썬에서 큐를 구현할 때는 collections.deque를 사용하는 것이 좋습니다.

from collections import deque

queue = deque()

queue.append(10)      # 뒤에 삽입
queue.append(20)

x = queue.popleft()   # 앞에서 제거, 10

리스트에서도 pop(0)으로 앞에서 제거할 수는 있습니다. 하지만 리스트의 맨 앞 원소를 제거하면 뒤의 원소들을 한 칸씩 앞으로 당겨야 하므로 O(n)이 걸립니다. 반면 deque.popleft()는 O(1)에 처리됩니다. 입력 크기가 커질수록 이 차이는 치명적입니다.

큐를 써야 하는 문제는 보통 다음과 같은 문장으로 나타납니다. "먼저 들어온 작업부터 처리한다", "대기열에서 하나씩 꺼낸다", "현재 위치에서 인접한 위치로 퍼져 나간다", "1초마다 다음 상태로 이동한다" 같은 표현입니다. 이런 문장을 보면 큐를 떠올려야 합니다.

작업 처리와 시뮬레이션

큐의 가장 직관적인 예는 작업 처리 문제입니다. 예를 들어 프린터에 여러 문서가 들어 있고, 앞에서부터 확인하면서 우선순위가 더 높은 문서가 뒤에 있으면 현재 문서를 다시 뒤로 보내는 문제가 있다고 해 봅시다.

이 문제는 배열만으로도 풀 수 있지만, 실제 흐름은 큐와 거의 같습니다. 맨 앞 문서를 꺼내고, 출력할 수 있으면 처리하고, 아니면 다시 뒤에 넣습니다.

from collections import deque

def printer_order(priorities, target):
    queue = deque()

    for i, priority in enumerate(priorities):
        queue.append((i, priority))

    printed = 0

    while queue:
        idx, priority = queue.popleft()

        if any(priority < other_priority for _, other_priority in queue):
            queue.append((idx, priority))
        else:
            printed += 1
            if idx == target:
                return printed

이 코드는 문제의 설명을 거의 그대로 옮긴 것입니다. 앞에서 하나를 꺼내고, 조건을 확인하고, 다시 넣거나 처리합니다. 이처럼 큐는 복잡한 시뮬레이션을 "꺼낸다, 판단한다, 넣는다"라는 반복 구조로 바꿔 줍니다.

물론 위 코드의 any()는 매번 큐 전체를 검사하므로 최악의 경우 효율이 좋지 않을 수 있습니다. 입력 크기가 크다면 우선순위 개수를 따로 세거나, 최대 힙 같은 다른 자료구조를 함께 고려해야 합니다. 중요한 것은 큐가 흐름을 표현하고, 추가 자료구조가 성능을 보완한다는 점입니다.

BFS의 기본 구조

큐가 가장 빛나는 대표적인 알고리즘은 BFS입니다. BFS는 Breadth-First Search의 줄임말로, 너비 우선 탐색이라고 부릅니다. 시작점에서 가까운 곳부터 차례대로 탐색하는 방식입니다.

미로에서 최단 거리를 구하는 상황을 떠올려 봅시다. 한 칸에서 상하좌우로 이동할 수 있고, 모든 이동 비용이 1이라면 시작점에서 가까운 칸부터 탐색해야 최단 거리를 보장할 수 있습니다. 이때 큐가 사용됩니다.

BFS의 기본 구조는 다음과 같습니다.

from collections import deque

def bfs(start, graph):
    visited = set()
    queue = deque()

    visited.add(start)
    queue.append(start)

    while queue:
        current = queue.popleft()

        for next_node in graph[current]:
            if next_node not in visited:
                visited.add(next_node)
                queue.append(next_node)

큐를 사용하면 먼저 발견한 노드가 먼저 처리됩니다. 시작점에서 거리 1인 노드들이 먼저 들어가고, 그다음 거리 2인 노드들이 들어갑니다. 따라서 큐에서 꺼내는 순서가 곧 거리 순서가 됩니다.

그래프 탐색은 뒤의 장에서 더 자세히 다루겠지만, 여기서는 큐의 역할만 기억하면 됩니다. 큐는 "동시에 퍼져 나가는 흐름"을 순서 있게 관리하는 장치입니다. 불이 번지는 문제, 토마토가 익는 문제, 바이러스가 퍼지는 문제, 게임 맵에서 최단 이동 횟수를 찾는 문제는 대부분 이 구조를 기반으로 합니다.

덱: 양쪽 문을 모두 열어 둔 큐

덱은 Double-Ended Queue의 줄임말입니다. 이름 그대로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 큐는 보통 뒤로 넣고 앞으로 빼지만, 덱은 앞에도 넣을 수 있고 뒤에서도 뺄 수 있습니다.

파이썬에서는 큐와 마찬가지로 collections.deque를 사용합니다.

from collections import deque

dq = deque()

dq.append(10)      # 오른쪽 삽입
dq.appendleft(20)  # 왼쪽 삽입

dq.pop()           # 오른쪽 제거
dq.popleft()       # 왼쪽 제거

덱은 스택처럼도 쓸 수 있고 큐처럼도 쓸 수 있습니다. 하지만 덱의 진짜 강점은 양방향 처리가 필요한 문제에서 드러납니다. 예를 들어 카드 뭉치의 위아래를 번갈아 조작하거나, 회전하는 큐에서 목표 원소를 최소 횟수로 꺼내거나, 앞뒤로 이동 가능한 명령을 처리하는 문제에서 덱이 자연스럽습니다.

배열로도 양쪽 조작을 흉내 낼 수는 있습니다. 하지만 리스트의 앞쪽 삽입이나 삭제는 O(n)이므로 반복되면 시간 초과가 나기 쉽습니다. 덱은 양쪽 끝 삽입과 삭제가 O(1)이기 때문에 이런 유형에서 안정적입니다.

양방향 처리 문제를 단순하게 만들기

예를 들어 정수들이 들어 있는 덱에서 특정 값을 순서대로 뽑아야 하는 문제가 있다고 해 봅시다. 한 번의 연산으로 왼쪽으로 회전하거나 오른쪽으로 회전할 수 있고, 맨 앞에 목표 값이 오면 꺼낼 수 있습니다. 목표 값을 꺼내기 위해 최소 회전 횟수를 구해야 합니다.

이런 문제는 덱을 사용하면 실제 조작을 그대로 구현할 수 있습니다.

from collections import deque

def min_rotations(n, targets):
    dq = deque(range(1, n + 1))
    count = 0

    for target in targets:
        idx = dq.index(target)

        if idx <= len(dq) // 2:
            while dq[0] != target:
                dq.append(dq.popleft())
                count += 1
        else:
            while dq[0] != target:
                dq.appendleft(dq.pop())
                count += 1

        dq.popleft()

    return count

핵심은 목표 값이 앞쪽에 가까우면 왼쪽으로 회전하고, 뒤쪽에 가까우면 오른쪽으로 회전하는 것입니다. 덱은 양쪽 회전을 모두 효율적으로 지원하므로 코드가 문제의 움직임과 비슷해집니다.

코딩 테스트에서 시뮬레이션 문제를 풀 때는 "문제 설명에 나온 동작을 그대로 구현해도 되는가?"를 먼저 생각해 보아야 합니다. 동작 횟수와 입력 크기가 충분히 작다면 그대로 구현하는 것이 가장 안전합니다. 다만 앞쪽 삽입과 삭제가 자주 일어난다면 리스트가 아니라 덱을 선택해야 합니다.

슬라이딩 윈도우와 덱 최적화

덱은 슬라이딩 윈도우 최적화에서도 자주 등장합니다. 슬라이딩 윈도우는 일정한 크기의 구간을 오른쪽으로 한 칸씩 이동시키며 답을 구하는 기법입니다. 예를 들어 길이가 k인 모든 연속 구간의 최댓값을 구한다고 해 봅시다.

배열이 [1, 3, -1, -3, 5, 3, 6, 7]이고 k = 3이라면, 처음 구간 [1, 3, -1]의 최댓값은 3입니다. 다음 구간 [3, -1, -3]의 최댓값도 3입니다. 이렇게 모든 구간의 최댓값을 구해야 합니다.

단순하게 매 구간마다 최댓값을 다시 구하면 O(nk)가 됩니다. n과 k가 크면 시간 초과가 나기 쉽습니다. 이때 덱을 사용하면 O(n)에 해결할 수 있습니다.

아이디어는 덱에 "최댓값 후보의 인덱스"를 저장하는 것입니다. 덱 안에서는 앞쪽에 가장 큰 값의 인덱스가 오도록 유지합니다. 새 값이 들어올 때, 덱 뒤쪽에 있는 값들 중 새 값보다 작거나 같은 값은 더 이상 최댓값 후보가 될 수 없습니다. 새 값이 더 오른쪽에 있고 더 크기 때문입니다.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()  # 인덱스 저장
    result = []

    for i, num in enumerate(nums):
        # 윈도우 범위를 벗어난 인덱스 제거
        while dq and dq[0] <= i - k:
            dq.popleft()

        # 현재 값보다 작거나 같은 값은 후보에서 제거
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

이 코드는 처음에는 조금 낯설 수 있습니다. 하지만 원리는 단순합니다. 덱의 앞에는 현재 구간에서 가장 큰 값의 인덱스가 있고, 뒤에는 앞으로 최댓값이 될 가능성이 있는 후보들이 순서대로 있습니다.

여기서도 중요한 시간 복잡도 감각이 필요합니다. 안쪽에 while문이 두 개 있지만, 각 인덱스는 덱에 한 번 들어가고 한 번 나옵니다. 따라서 전체 시간 복잡도는 O(n)입니다. 단조 스택과 비슷하게 "각 원소가 몇 번 들어가고 나오는가"로 생각하면 이해하기 쉽습니다.

자료구조 연산의 시간 복잡도

스택, 큐, 덱 문제에서 시간 초과가 나는 가장 흔한 이유는 알고리즘 아이디어가 틀려서가 아니라, 연산의 시간 복잡도를 잘못 선택해서입니다. 특히 파이썬에서는 리스트를 큐처럼 사용할 때 조심해야 합니다.

대표적인 연산을 정리하면 다음과 같습니다.

스택은 리스트로 충분한 경우가 많습니다. 뒤에 넣고 뒤에서 빼는 연산이 빠르기 때문입니다. 하지만 큐처럼 앞에서 자주 빼야 한다면 리스트 대신 덱을 사용하는 것이 안전합니다. 덱은 앞뒤 양쪽 끝 연산이 모두 빠릅니다.

다만 덱이 모든 면에서 리스트보다 좋은 것은 아닙니다. 리스트는 인덱스로 특정 위치에 접근하는 작업이 빠르고 간단합니다. 반면 덱은 중간 원소에 자주 접근하는 용도에는 적합하지 않습니다. 따라서 다음처럼 선택하면 됩니다.

• 뒤에서만 넣고 뺀다면 리스트를 스택으로 사용합니다.

• 앞에서 빼고 뒤에 넣는 흐름이라면 덱을 큐로 사용합니다.

• 앞뒤 양쪽에서 넣고 빼야 한다면 덱을 사용합니다.

• 중간 인덱스 접근과 정렬이 핵심이라면 리스트가 더 자연스럽습니다.

자료구조 선택은 단순한 취향 문제가 아닙니다. 같은 알고리즘도 pop(0)을 반복하느냐, popleft()를 반복하느냐에 따라 통과와 시간 초과가 갈릴 수 있습니다.

문제를 읽을 때 떠올려야 할 신호들

코딩 테스트에서는 문제를 읽는 순간 자료구조 후보를 빠르게 떠올리는 능력이 중요합니다. 스택, 큐, 덱은 각각 잘 맞는 표현이 있습니다.

스택을 의심해야 하는 경우는 "최근 것부터 처리"해야 할 때입니다. 괄호 짝 맞추기, 뒤로 가기, 실행 취소, 이전 상태 복원, 오른쪽에서 처음 만나는 큰 값 같은 표현이 나오면 스택을 떠올려 보세요.

큐를 의심해야 하는 경우는 "먼저 온 것부터 처리"해야 할 때입니다. 대기열, 작업 순서, 순차 처리, 같은 시간대의 확산, 최단 거리 탐색 같은 표현이 나오면 큐가 유력합니다.

덱을 의심해야 하는 경우는 "양쪽 끝을 모두 조작"하거나 "구간의 후보를 유지"해야 할 때입니다. 앞뒤 회전, 양방향 명령, 카드 뒤집기, 슬라이딩 윈도우 최댓값과 최솟값 같은 문제가 대표적입니다.

이 신호들을 기계적으로 외우는 것보다 더 중요한 것은 데이터의 이동을 그림으로 그려 보는 것입니다. 값이 들어오는 입구와 나가는 출구가 어디인지 표시해 보세요. 출구가 하나이고 최근 값이 먼저 나가면 스택입니다. 입구와 출구가 반대쪽이고 먼저 들어온 값이 먼저 나가면 큐입니다. 양쪽 끝이 모두 열려 있으면 덱입니다.

실전 구현에서 자주 하는 실수

스택, 큐, 덱은 개념은 쉽지만 구현 실수는 자주 발생합니다. 특히 빈 자료구조에서 꺼내려고 하거나, 값을 저장해야 하는데 인덱스를 저장하지 않아 답을 계산하지 못하는 경우가 많습니다.

괄호 문제에서는 닫는 괄호가 나왔을 때 스택이 비어 있는지 먼저 확인해야 합니다. 비어 있는데 pop()을 하면 런타임 에러가 납니다. 단조 스택 문제에서는 값만 저장할지 인덱스를 저장할지 신중히 결정해야 합니다. 답 배열의 특정 위치를 갱신해야 한다면 대부분 인덱스를 저장하는 편이 좋습니다.

큐 문제에서는 방문 처리를 언제 할지도 중요합니다. BFS에서는 보통 큐에 넣는 순간 방문 처리하는 것이 안전합니다. 꺼낼 때 방문 처리하면 같은 노드가 큐에 여러 번 들어갈 수 있어 불필요한 연산이 늘어납니다.

덱 문제에서는 회전 방향을 정할 때 기준을 잘 잡아야 합니다. 목표 인덱스가 덱 길이의 절반보다 앞에 있으면 왼쪽 회전이 유리하고, 뒤에 있으면 오른쪽 회전이 유리한 경우가 많습니다. 다만 문제마다 연산 비용이 다를 수 있으므로 조건을 그대로 믿기보다 작은 예제로 확인하는 습관이 필요합니다.

작은 예제로 흐름을 검증하라

스택, 큐, 덱 문제는 손으로 한두 번만 시뮬레이션해도 실수를 많이 줄일 수 있습니다. 예를 들어 단조 스택 문제를 풀 때는 길이 5 정도의 배열을 직접 만들어 스택에 어떤 인덱스가 남는지 적어 보세요. BFS 문제라면 큐에 들어가는 순서를 거리별로 적어 보면 방문 처리 위치가 맞는지 확인할 수 있습니다.

좋은 검증 예제는 너무 평범하지 않아야 합니다. 다음과 같은 경우를 일부러 넣어 보는 것이 좋습니다.

• 입력이 비어 있거나 원소가 하나뿐인 경우

• 모든 값이 증가하거나 모두 감소하는 경우

• 같은 값이 반복되는 경우

• 목표 값이 맨 앞이나 맨 뒤에 있는 경우

• 정답이 존재하지 않는 경우

이런 예제들은 자료구조의 경계 조건을 건드립니다. 경계 조건에서 코드가 안전하다면 실제 테스트에서도 훨씬 안정적으로 동작합니다.

핵심 정리

스택, 큐, 덱은 복잡한 알고리즘처럼 보이지 않을 수 있습니다. 하지만 코딩 테스트에서는 이 세 가지가 문제의 형태를 바꾸는 강력한 도구가 됩니다. 복잡해 보이는 시뮬레이션도 적절한 자료구조를 만나면 간단한 반복문으로 정리됩니다.

스택은 가장 최근의 상태를 다룰 때 사용합니다. 괄호 검사, 되돌리기, 단조 스택처럼 "아직 해결되지 않은 것"을 쌓아 두는 문제에 잘 맞습니다. 큐는 먼저 들어온 것을 먼저 처리할 때 사용합니다. 대기열, 작업 처리, BFS처럼 순서대로 확산되는 문제에서 핵심 역할을 합니다. 덱은 양쪽 끝을 모두 다뤄야 할 때 사용합니다. 회전, 양방향 처리, 슬라이딩 윈도우 최적화에서 특히 유용합니다.

마지막으로, 자료구조를 고를 때는 반드시 연산의 시간 복잡도를 함께 생각해야 합니다. 리스트의 pop(0)처럼 겉보기에는 간단하지만 실제로는 O(n)인 연산이 숨어 있을 수 있습니다. 코딩 테스트에서 좋은 풀이는 아이디어뿐 아니라 구현 선택까지 정확해야 합니다.

문제를 읽고 나서 바로 코드를 쓰기 전에 잠깐 멈춰 보세요. "이 문제에서 데이터는 어디로 들어오고, 어디로 나가는가?" 이 질문에 답할 수 있다면 스택, 큐, 덱 중 무엇을 써야 할지도 자연스럽게 보이기 시작할 것입니다.