Coding Interview Prep · 강의

스택 구현과 활용

push/pop/peek 기능을 갖춘 스택을 구현한 뒤 valid-parentheses, min-stack, 역폴란드 표기법 평가 문제를 해결합니다.

스택 구현과 활용은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Stack 자료 구조

스택은 후입선출(LIFO) 자료 구조입니다. 가장 나중에 넣은 요소가 가장 먼저 꺼내집니다. 접시를 쌓아 둔 모습을 생각해 보십시오. 위쪽에서만 추가하거나 제거할 수 있습니다. 핵심 연산은 push(위에 추가), pop(위에서 제거), peek(제거하지 않고 맨 위를 읽기)입니다. 잘 구현된 스택에서는 세 연산 모두 O(1)입니다.

파이썬에서는 리스트가 완벽한 스택 역할을 합니다. append는 push이고, pop()은 pop이며, [-1]은 peek입니다.

stack = []

# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack)  # [10, 20, 30]

# Peek
print('Top:', stack[-1])       # 30

# Pop
print('Popped:', stack.pop())  # 30
print('After pop:', stack)     # [10, 20]

push, pop, peek, isEmpty를 사용하는 Stack 클래스

리스트를 클래스로 감싸면 더 깔끔한 인터페이스를 제공하고, insert나 맨 위가 아닌 위치의 인덱싱처럼 스택에 맞지 않는 연산을 실수로 사용하는 일을 막을 수 있습니다. 이는 "스택을 처음부터 구현해 보라"는 요청을 받았을 때 면접관이 기대하는 구현 방식입니다.

class Stack:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError('pop from empty stack')
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty stack')
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek())  # 3
print(s.pop())   # 3
print(len(s))    # 2

유효한 괄호(LeetCode 20)

LeetCode 20 '유효한 괄호': 괄호 문자열이 균형을 이루는지 판별합니다. 여는 괄호를 만날 때마다 push합니다. 닫는 괄호를 만날 때는 스택의 맨 위가 짝이 맞는 여는 괄호인지 확인합니다. 그렇지 않거나 스택이 비어 있으면 거짓을 반환합니다. 마지막에 스택이 비어 있으면 문자열은 유효합니다. 이는 코딩 면접에서 스택을 적용하는 가장 대표적인 첫 사례입니다.

def isValid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(isValid('()[]{}'))    # True
print(isValid('([)]'))      # False
print(isValid('{[]}'))      # True
print(isValid(']'))         # False

최소 스택(LeetCode 155)

LeetCode 155 '최소 스택': push, pop, peek, getMin을 모두 O(1)에 지원하는 스택을 설계합니다. 핵심 방법은 모든 시점의 최솟값을 추적하는 두 번째 스택을 유지하는 것입니다. 값을 push할 때 새 값이 현재 최솟값보다 작거나 같으면(또는 최소 스택이 비어 있으면) 최소 스택에도 push합니다. 값을 pop할 때 꺼낸 값이 현재 최솟값과 같으면 최소 스택에서도 pop합니다.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

후위 표기법 계산하기

LeetCode 150 '후위 표기법 계산하기'(후위 표기): 피연산자를 push하고, 연산자를 만나면 피연산자 두 개를 pop하여 연산한 다음 결과를 push합니다. 뺄셈과 나눗셈에서는 순서가 중요합니다. 처음 pop한 값이 오른쪽 피연산자이고, 두 번째로 pop한 값이 왼쪽 피연산자입니다.

def evalRPN(tokens):
    stack = []
    ops = set(['+', '-', '*', '/'])
    for tok in tokens:
        if tok not in ops:
            stack.append(int(tok))
        else:
            b = stack.pop()  # right operand
            a = stack.pop()  # left operand
            if tok == '+':
                stack.append(a + b)
            elif tok == '-':
                stack.append(a - b)
            elif tok == '*':
                stack.append(a * b)
            else:             # division truncated toward zero
                stack.append(int(a / b))
    return stack[0]

print(evalRPN(['2','1','+','3','*']))     # 9
print(evalRPN(['4','13','5','/','+']))    # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+']))  # 22

문자열 디코딩(LeetCode 394)

LeetCode 394 '문자열 디코딩': 3[a2[c]]와 같은 인코딩된 문자열을 accaccacc로 확장합니다. 두 개의 스택을 사용합니다. 하나는 반복 횟수용이고, 다른 하나는 누적 문자열용입니다. 숫자를 만나면 전체 숫자를 구성합니다. [를 만나면 현재 문자열과 횟수를 push합니다. ]를 만나면 pop한 뒤 현재 구간을 반복합니다. 문자를 만나면 현재 문자열에 추가합니다.

def decodeString(s):
    count_stack = []
    str_stack   = []
    current_str = ''
    current_num = 0
    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)
        elif ch == '[':
            count_stack.append(current_num)
            str_stack.append(current_str)
            current_str = ''
            current_num = 0
        elif ch == ']':
            repeats = count_stack.pop()
            current_str = str_stack.pop() + current_str * repeats
        else:
            current_str += ch
    return current_str

print(decodeString('3[a]2[bc]'))    # 'aaabcbc'
print(decodeString('3[a2[c]]'))     # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'

일일 기온(단조 스택 미리 보기)

LeetCode 739 '일일 기온': 각 날짜에 대해 더 따뜻한 날까지 며칠이 걸리는지 찾습니다. 무차별 대입 방법은 O(n²)입니다. 스택을 사용하면 기온을 순회하면서 각 날짜에 대해 오늘보다 기온이 낮은 스택 항목(날짜 인덱스)을 모두 pop합니다. 이렇게 pop한 날짜들의 답은 오늘 날짜와 해당 날짜의 차이입니다. 현재 날짜를 push합니다. 더 따뜻한 날을 찾지 못한 나머지 스택 항목의 답은 0입니다.

def dailyTemperatures(temps):
    result = [0] * len(temps)
    stack  = []  # stores indices
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

DFS 순회를 위한 스택

재귀적 DFS의 호출 스택은 명시적인 스택으로 대체하여 알고리즘을 반복형으로 만들 수 있습니다. 루트를 push하고, 스택이 비어 있지 않은 동안 노드를 pop하여 처리한 다음 자식 노드를 push합니다(왼쪽에서 오른쪽으로 처리하려면 오른쪽 자식을 먼저 push). 이 반복형 DFS는 재귀적 DFS와 동작이 같지만, 깊은 트리에서 파이썬의 재귀 한도를 피할 수 있습니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)  # push right first
        if node.left:
            stack.append(node.left)   # so left is processed first
    return result

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root))  # [1, 2, 4, 5, 3]

시간 및 공간 복잡도

모든 스택 연산(push, pop, peek, isEmpty)은 분할 상환 O(1)입니다. n개 요소로 스택을 만드는 데는 O(n)이 걸립니다. 모든 요소가 저장되는 최악의 경우 공간은 O(n)입니다. 단조 스택을 사용하는 문제에서는 각 요소가 최대 한 번 push되고 한 번 pop되므로, 모든 반복을 합친 전체 시간은 O(n)입니다. 순진하게 바깥쪽 반복문만 보고 예상하는 O(n²)이 아닙니다.

# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total

def count_ops(n):
    pushes = pops = 0
    stack = []
    for i in range(n):
        while stack and stack[-1] < i:  # simulated decreasing condition
            stack.pop()
            pops += 1
        stack.append(i)
        pushes += 1
    return pushes, pops

p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}')  # <= 2000

히스토그램에서 가장 큰 직사각형(미리 보기)

LeetCode 84 '히스토그램에서 가장 큰 직사각형'은 가장 어려운 고전적인 스택 문제입니다. 각 막대가 기준이 될 수 있는 직사각형은 왼쪽으로는 더 짧은 막대를 만날 때까지, 오른쪽으로는 더 짧은 막대를 만날 때까지 확장됩니다. 단조 스택은 높이가 증가하는 순서로 막대의 인덱스를 추적합니다. 더 짧은 막대를 만나면 pop하고, pop한 막대의 높이를 사용해 직사각형을 계산합니다. 스택을 사용하면 pop 한 번당 O(1)에 왼쪽과 오른쪽 경계를 구할 수 있습니다.

def largestRectangleArea(heights):
    stack  = []  # indices, increasing heights
    result = 0
    heights = heights + [0]  # sentinel forces all pops
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width  = i if not stack else i - stack[-1] - 1
            result = max(result, height * width)
        stack.append(i)
    return result

print(largestRectangleArea([2,1,5,6,2,3]))  # 10
print(largestRectangleArea([2,4]))           # 4

스택 문제를 위한 면접 전략

스택 문제는 종종 '안쪽에서 바깥쪽 순서로 처리하기' 또는 '다음으로 큰/작은 요소 찾기'라는 형태로 모습을 바꿔 제시됩니다. 스택이 도움이 될 수 있다는 신호는 가장 최근에 본 요소가 필요하거나, 쌍(괄호, 태그)을 짝지어야 하거나, 순진한 방법으로는 O(n²) 중첩 반복문이 필요하지만 O(n)으로 해결하고 싶은 경우입니다. 특히 단조 스택은 '모든 요소에 대해 가장 가까운 더 큰/작은 요소 찾기' 문제를 O(n²)에서 O(n)으로 바꿉니다.

면접에서는 스택 불변식을 명확하게 말해 보십시오. "높이가 내림차순인 인덱스 스택을 유지하겠습니다."라고 설명하면 됩니다.

빠른 확인

이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보십시오.

수업 요약

이 수업에서는 다음을 배웠습니다. 파이썬 리스트는 O(1)의 push/pop/peek를 구현하므로 스택으로 사용하기에 적합합니다. 유효한 괄호와 최소 스택은 스택 면접 문제의 대표적인 두 유형입니다. 또한 단조 스택은 각 요소를 최대 한 번 push하고 pop하여 다음으로 큰 요소 문제를 O(n)에 해결합니다. 다음에는 파이썬의 deque로 큐를 만들고 슬라이딩 윈도우 최댓값 문제를 해결합니다.

자주 묻는 질문

“스택 구현과 활용” 강의는 무료인가요?

네 — “스택 구현과 활용” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“스택 구현과 활용”에서 뭘 배우나요?

push/pop/peek 기능을 갖춘 스택을 구현한 뒤 valid-parentheses, min-stack, 역폴란드 표기법 평가 문제를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“스택 구현과 활용” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Coding Interview Prep(으)로 돌아가기