CHAPTER 3. 핵심 선형 자료구조 (큐, 스택, 해시)

데이터를 일렬로 나열하여 관리하는 선형 자료구조 중 코딩테스트에 매번 출제되는 큐(Queue), 스택(Stack), 해시(Hash/Dict)의 성능적 차이와 시그니처 활용 패턴을 다뤄보고자 한다.

 

3-1. 큐 (Queue & Deque)

가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출 (FIFO, First-In First-Out) 구조.

 

1. 왜 list.pop(0) 대신 deque.popleft()를 써야 하는가?

 

• list.pop(0) (O(N)): 맨 앞 원소를 빼면 뒤에 있는 모든 원소들이 앞으로 한 칸씩 이동해야 하므로 데이터가 많을 때 시간 초과의 주범이 됨.
• deque.popleft() (O(1)): 양방향 연결 리스트 구조로 되어 있어 위치 이동 없이 맨 앞 원소를 즉시 제거함.

from collections import deque

# 1. 큐 생성 및 데이터 집어넣기 (append)
queue = deque([1, 2, 3])
queue.append(4)  # deque([1, 2, 3, 4])

# 2. 가장 먼저 들어온 데이터 꺼내기 (popleft)
first_item = queue.popleft()  # 1 반환, deque에는 [2, 3, 4] 남음

print(f"꺼낸 원소: {first_item}")
print(f"현재 큐 상태: {queue}")

 

 

3-2. 스택 (Stack)

나중에 들어온 데이터가 가장 먼저 나가는 후입선출 (LIFO, Last-In First-Out) 구조.

 

1. 핵심 특징 및 활용 패턴

• 사용 문법: 별도 라이브러리 없이 파이썬 기본 리스트의 append()와 pop()을 사용합니다. 둘 다 맨 끝에서 동작하므로 O(1)로 매우 빠름.
• 시그니처 패턴: "올바른 괄호 짝 맞추기", "최근 데이터와 비교해 연속 중복 제거", "되돌리기(Ctrl+Z)" 문제

2. 올바른 괄호 검사 문제 → 기본 템플릿

def is_valid_parentheses(s):
    stack = []
    
    for char in s:
        if char == "(":
            stack.append(char)  # 여는 괄호는 스택에 차곡차곡 쌓음
        elif char == ")":
            if stack:
                stack.pop()     # 닫는 괄호가 나오면 가장 최근의 여는 괄호와 짝을 맞춰 제거!
            else:
                return False    # 짝 맞출 여는 괄호가 없으면 잘못된 괄호
                
    # 문자를 다 돌았을 때 스택이 완전히 비어있어야 올바른 괄호!
    return len(stack) == 0

# --- 실행 예시 ---
print(is_valid_parentheses("(())()"))  # True
print(is_valid_parentheses("(()"))     # False

 

3-3. 해시 (Hash / Dict)

Key-Value 쌍으로 데이터를 저장하며, Key 값을 hash() 함수로 변환하여 메모리 주소를 직접 찾아가는 자료구조.

 

1. 탐색 속도 단축 원리 (O(N) → O(1))

• 리스트에서 값 찾기 (if x in my_list): 처음부터 끝까지 다 뒤져야 하므로 O(N) 소요.
• 딕셔너리에서 값 찾기 (if x in my_dict): Key를 주소로 바로 변환해 찾으므로 데이터 크기와 무관하게 O(1) 소요.

2. 해시 필수 테크닉 (dict & Counter)

from collections import Counter

# 1. dict.get(key, default) - 안전하게 개수 세기
words = ["apple", "banana", "apple", "orange"]
count_dict = {}

for w in words:
    # Key가 없으면 0을 반환하고 1을 더해줌 (KeyError 방지)
    count_dict[w] = count_dict.get(w, 0) + 1

print(count_dict)  # {'apple': 2, 'banana': 1, 'orange': 1}


# 2. Counter - 한 줄로 빈도수 집계하기 (파이썬 치트키)
counter_result = Counter(words)
print(counter_result)            # Counter({'apple': 2, 'banana': 1, 'orange': 1})
print(counter_result["apple"])   # 2