[Python] 코딩 테스트 필수 STL 1탄 (중요도와 사용 빈도 기준)

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

[자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

 

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 정렬 알고리즘 총 정리

[자료구조 & 알고리즘] 정렬 알고리즘 총 정리

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 탐색 알고리즘 총 정리 (feat. 이진탐색, DFS, BFS)

[자료구조 & 알고리즘] 탐색 알고리즘 총 정리 (feat. 이진탐색, DFS, BFS)

---

 

Python 코딩 테스트 필수 STL (중요도와 사용 빈도 기준)

파이썬은 다양한 문제 풀이와 코딩 테스트에 적합한 표준 라이브러리(STL, Standard Template Library)를 제공합니다. 특히 코딩 테스트에서는 자료 구조, 정렬, 탐색과 같은 핵심 기능을 빠르게 구현해야 하므로 이러한 모듈들을 잘 활용하는 것이 중요합니다. 이번 포스팅에서는 파이썬의 필수 STL을 하나씩 소개하겠습니다. 각 기능은 문제의 유형에 따라 필요성이 다를 수 있지만, 특히 자료 구조, 탐색, 정렬, 입출력에 자주 활용되는 모듈과 함수들이 우선시됩니다.

---

1. sys.stdin.readline (입력 속도 최적화 - 매우 자주 사용)

• 코딩 테스트에서는 입력 속도가 매우 중요합니다. 특히 입력 데이터가 많은 경우, 기본 input()보다 빠른 sys.stdin.readline()을 사용합니다.
• sys.stdin.readline은 문자열로 입력을 받기 때문에 데이터 타입과 띄어쓰기를 직접 처리해줘야 합니다. 기본적으로 한 줄 단위로 입력을 받고, 문자열 끝에는 개행 문자(\n)가 포함되어 있습니다.
  • • 입력된 문자열에서 끝에 있는 개행 문자를 제거하려면 strip() 메서드를 사용해야 합니다.

import sys

input = sys.stdin.readline
n = int(input().strip())
print(n)

 

---

2. collections.deque (BFS/DFS 등 탐색에서 필수 - 매우 자주 사용)

• 큐와 스택을 효율적으로 구현할 수 있는 양방향 자료 구조입니다.
• BFS(너비 우선 탐색)에서 큐를 구현할 때 거의 필수적으로 사용됩니다.
• 삽입과 삭제가 O(1) 시간 복잡도를 가집니다.

2.1. deque 주요 메서드

메서드	설명	시간 복잡도
append(x)	오른쪽에 요소 추가	O(1)
appendleft(x)	왼쪽에 요소 추가	O(1)
pop()	오른쪽에서 요소 제거 및 반환	O(1)
popleft()	왼쪽에서 요소 제거 및 반환	O(1)
extend(iterable)	오른쪽에 여러 요소 추가	O(k)
extendleft(iterable)	왼쪽에 여러 요소 추가(역순으로 추가됨)	O(k)

---

2.2. 메서드 사용 예시

 

1) 오른쪽 추가 및 제거

from collections import deque

dq = deque([1, 2, 3])
dq.append(4)  # 오른쪽에 4 추가
print(dq)     # 출력: deque([1, 2, 3, 4])

dq.pop()      # 오른쪽에서 4 제거
print(dq)     # 출력: deque([1, 2, 3])

 

2) 왼쪽 추가 및 제거

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)  # 왼쪽에 0 추가
print(dq)         # 출력: deque([0, 1, 2, 3])

dq.popleft()      # 왼쪽에서 0 제거
print(dq)         # 출력: deque([1, 2, 3])

---

2.3. 큐(Queue) 구현 예시

 

큐는 선입선출(FIFO) 구조로, deque를 사용하여 효율적으로 구현할 수 있습니다.

from collections import deque

queue = deque()

# 큐에 요소 추가
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # 출력: deque([1, 2, 3])

# 큐에서 요소 제거 (왼쪽에서 제거)
queue.popleft()
print(queue)  # 출력: deque([2, 3])

 

---

2.4. 스택(Stack) 구현 예시

 

스택은 후입선출(LIFO) 구조로, deque의 append()와 pop()을 사용하여 구현할 수 있습니다.

from collections import deque

stack = deque()

# 스택에 요소 추가
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)  # 출력: deque([10, 20, 30])

# 스택에서 요소 제거 (오른쪽에서 제거)
stack.pop()
print(stack)  # 출력: deque([10, 20])

---

2.5. 양방향 큐(Deque) 구현 예시

 

deque는 양쪽에서 추가 및 삭제가 가능하므로 양방향 큐를 쉽게 구현할 수 있습니다.

from collections import deque

dq = deque()

# 양쪽에서 추가
dq.append(5)         # 오른쪽에 추가
dq.appendleft(1)     # 왼쪽에 추가
print(dq)            # 출력: deque([1, 5])

# 양쪽에서 제거
dq.pop()             # 오른쪽에서 제거
dq.popleft()         # 왼쪽에서 제거
print(dq)            # 출력: deque([])

 

---

 

3. heapq (우선순위 큐 구현 - 빈번히 사용)

• 다익스트라, A* 알고리즘과 같은 우선순위 큐가 필요한 문제에서 자주 사용됩니다.
• 기본적으로 최소 힙(min-heap)을 제공하며, 삽입과 삭제가 O(log n) 시간 복잡도를 가집니다.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
print(heapq.heappop(heap))  # 출력: 1

---

3.1. 주요 메서드

메서드	설명	코드	출력
heapq.heappush(heap, x)	힙에 요소 x를 추가	heapq.heappush(heap, 3)	heap = [3]
heapq.heappop(heap)	힙에서 최소값 제거 및 반환	heapq.heappop(heap)	최소값 반환
heapq.heapify(iterable)	리스트를 힙으로 변환	heapq.heapify(data)	힙으로 변환된 리스트
heapq.heappushpop(heap, x)	요소 x를 삽입 후, 즉시 최소값 제거	heapq.heappushpop(heap, 1)	최소값 반환
heapq.nlargest(n, iterable)	n개의 가장 큰 요소 반환	heapq.nlargest(2, data)	[5, 4]
heapq.nsmallest(n, iterable)	n개의 가장 작은 요소 반환	heapq.nsmallest(2, data)	[1, 2]

 

---

3.2. 사용 예시

1) 기본 사용법 (최소 힙)

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print(heap)              # 출력: [1, 3, 8, 5] (최소 힙 구조)
print(heapq.heappop(heap))  # 출력: 1 (최소값 제거)
print(heap)              # 출력: [3, 5, 8]

• 설명:
  힙은 항상 최솟값이 루트에 위치하며, heappop()을 호출할 때 최솟값이 제거됩니다.

---

2) 최대 힙 구현

• heapq는 기본적으로 최소 힙만 제공하므로, 최대 힙을 구현하려면 값을 음수로 변환하여 사용합니다.

import heapq

heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -3)
heapq.heappush(heap, -8)

print(-heapq.heappop(heap))  # 출력: 8 (최대값)

---

3) 리스트를 힙으로 변환 (heapify())

• 기존 리스트를 힙 구조로 변환합니다. 시간 복잡도는 **O(n)**입니다.

data = [4, 1, 7, 3, 8, 5]
heapq.heapify(data)
print(data)  # 출력: [1, 3, 5, 4, 8, 7] (최소 힙 구조)

---

4) 최댓값/최솟값 여러 개 추출

• heapq.nlargest()와 heapq.nsmallest()는 리스트에서 가장 큰/작은 요소를 반환합니다.

data = [10, 20, 15, 5, 25, 30]
print(heapq.nlargest(2, data))  # 출력: [30, 25]
print(heapq.nsmallest(2, data)) # 출력: [5, 10]

---

3. 코딩 테스트에서의 활용 예시

1) 다익스트라 알고리즘 (최단 경로 탐색)

• 우선순위 큐를 사용하여 최단 경로를 효율적으로 탐색합니다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # 우선순위 큐 (거리, 노드)

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        # 이미 처리된 노드라면 무시
        if current_distance > distances[current_node]:
            continue

        # 인접 노드 탐색
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 더 짧은 경로가 발견되면 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 그래프 예시
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))  # 출력: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

---

2) K번째 최소값/최대값 찾기

• 우선순위 큐를 사용하여 K번째 최소값 또는 최대값을 효율적으로 찾습니다.

import heapq

data = [7, 10, 4, 3, 20, 15]
k = 3

# K번째 최소값
print(heapq.nsmallest(k, data)[-1])  # 출력: 7

# K번째 최대값
print(heapq.nlargest(k, data)[-1])  # 출력: 10

 

---

4. collections.Counter (빈도 계산 문제 - 자주 사용)

• 주어진 데이터에서 요소의 등장 횟수를 쉽게 계산할 수 있습니다.
• 아나그램 판별이나 최빈값 찾기와 같은 문제에서 유용합니다.

 

 

4.1. 주요 메서드 및 속성

메서드/속성 설명 예시 코드 출력

Counter(iterable)	요소들의 빈도를 카운트하는 객체 생성	Counter('aabbc')	Counter({'a': 2, 'b': 2, 'c': 1})
.most_common(n)	가장 빈도가 높은 요소 n개 반환	cnt.most_common(2)	[('a', 2), ('b', 2)]
.elements()	요소들을 빈도만큼 반복 가능한 객체로 반환	list(cnt.elements())	['a', 'a', 'b', 'b', 'c']
.update(iterable)	요소들의 빈도 업데이트	cnt.update('bbc')	Counter({'b': 4, 'a': 2, 'c': 2})
.subtract(iterable)	요소들의 빈도를 감소시킴	cnt.subtract('abc')	Counter({'b': 3, 'a': 1, 'c': 1})
cnt[key]	특정 요소의 빈도를 반환	cnt['a']	1
+ 연산자	두 개의 Counter 객체를 합침	cnt1 + cnt2	합산된 Counter
- 연산자	빈도가 0 이하인 요소는 제외한 차집합 반환	cnt1 - cnt2	차집합 Counter

---

4.2. 예시 및 설명

1) 기본 사용법

• 문자열, 리스트, 튜플 등 반복 가능한 객체(iterable)에서 각 요소의 등장 횟수를 세어줍니다.

from collections import Counter

data = "aabbccc"
cnt = Counter(data)
print(cnt)  # 출력: Counter({'c': 3, 'a': 2, 'b': 2})

---

2) most_common() 메서드

• 가장 빈도가 높은 요소를 반환합니다. 인수 n을 통해 반환할 요소의 개수를 지정할 수 있습니다.

cnt = Counter("aabbccc")
print(cnt.most_common(2))  # 출력: [('c', 3), ('a', 2)]

---

3) elements() 메서드

• 요소를 빈도만큼 반복하는 **이터레이터(iterator)**를 반환합니다.

cnt = Counter("aabbc")
print(list(cnt.elements()))  # 출력: ['a', 'a', 'b', 'b', 'c']

---

4) update() 메서드

• 기존 Counter에 새로운 데이터의 빈도를 추가합니다.

cnt = Counter("abc")
cnt.update("bcc")
print(cnt)  # 출력: Counter({'c': 3, 'b': 2, 'a': 1})

---

5) subtract() 메서드

• 기존 요소의 빈도를 감소시킵니다. 빈도는 음수가 될 수 있습니다.

cnt = Counter("aabbc")
cnt.subtract("abc")
print(cnt)  # 출력: Counter({'b': 1, 'a': 1, 'c': 0})

---

4.3. 코딩 테스트에서 활용 예시

1) 아나그램 판별 문제

• 두 문자열이 아나그램인지 판별할 때, 두 문자열의 빈도 카운트가 동일한지 비교합니다.

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

print(is_anagram("listen", "silent"))  # 출력: True
print(is_anagram("apple", "papel"))    # 출력: True
print(is_anagram("hello", "world"))    # 출력: False

---

2) 최빈값 찾기 문제

• 배열에서 가장 자주 등장하는 요소를 찾습니다.

from collections import Counter

data = [1, 2, 2, 3, 3, 3, 4]
cnt = Counter(data)
most_common = cnt.most_common(1)
print(most_common[0][0])  # 출력: 3 (가장 빈도가 높은 요소)

---

3) 문자열의 각 문자의 빈도를 출력하는 문제

from collections import Counter

s = "aabbcde"
cnt = Counter(s)
for char, freq in cnt.items():
    print(f"{char}: {freq}")

# 출력:
# a: 2
# b: 2
# c: 1
# d: 1
# e: 1

 

---

 

 

중요도 및 빈도 기준 요약

 

(1탄)

1. sys.stdin.readline – 입력 속도가 중요한 문제에서 필수
2. collections.deque – BFS/DFS와 같은 탐색 알고리즘에서 필수
3. heapq – 우선순위 큐가 필요한 문제에서 자주 사용
4. collections.Counter – 요소의 빈도 계산이 필요한 문제에서 빈번히 사용

(2탄)

1. bisect – 정렬된 리스트에 대한 삽입/탐색에서 자주 사용
2. itertools – 완전 탐색 문제에서 경우의 수 계산 시 자주 사용
3. functools.lru_cache – 재귀 기반 DP 문제에서 중복 호출 방지
4. math – 최대공약수(GCD), 팩토리얼 등 수학적 문제에서 사용
5. collections.defaultdict – 기본값을 자동 설정하는 딕셔너리

---

마무리

이번 포스팅에서는 Python 코딩 테스트 필수 STL들을 중요도와 사용 빈도에 따라 정리했습니다. 

2탄으로 계속 이어나가겠습니다!

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.