[코딩 테스트/Python] 코딩 테스트에서 자주 사용되는 Python 표준 라이브러리

코딩 테스트에서 자주 사용되는 알고리즘에는 해시(hash), 탐욕법(greedy), 정렬(sort), 동적 계획법(Dynamic Programming), 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 있다.

 

이 알고리즘들은 직접 구현할 수도 있지만, 그렇게 하기엔 코드도 너무 길어지고 시간이 오래 걸린다. 코딩 테스트에서 시간은 생각보다 여유 있지 않을 뿐더러, 각 알고리즘 별 직접 구현 코드를 늘 외우고 있기도 어렵다.

 

이럴 때 Python에서 제공하는 표준 라이브러리를 사용하면 각 알고리즘을 보다 쉽게 구현할 수 있다. 이 글에서는 각 알고리즘 별 표준 라이브러리를 사용해 구현하는 법을 간단히 정리하고자 한다.

 

1. 해시(hash)

해시의 경우, 라이브러리를 따로 임포트하지 않고 기본 자료구조형으로도 구현할 수 있다. 딕셔너리와 집합(set)을 이용해 해시 알고리즘을 구현한다. 주로 해당 값의 존재 여부를 판단해야 하는 문제에 사용한다.

# 딕셔너리 선언
hash_map = {}

# 값 추가
hash_map["apple"] = 1
hash_map["banana"] = 2

# 값 접근
print(hash_map["apple"])  # 1

# 값 존재 확인
if "banana" in hash_map:
    print("banana가 존재합니다.")

# 값 삭제
del hash_map["banana"]

 

데이터 요소 별 개수 세기 - Collections.Counter

여러 개의 데이터가 담긴 배열이 있을 때, 각 요소 별 개수를 세어 딕셔너리 형태로 리턴해주는 함수가 있다. collections의 counter 모듈을 사용하면 반복문을 돌며 딕셔너리를 만들 필요가 없다.

import collections

list1 = [1, 2, 10, 1, 4, 10, 2, 1, 1, 10]
c = collections.Counter(list1)
print(c)

>>>
Counter({1: 4, 10: 3, 2: 2, 4: 1})

# 딕셔너리 메서드도 이용 가능
c.get(1)

>>> 4

 

중복 허용하지 않을 경우 집합 사용

# 집합 선언
hash_set = set()

# 값 추가
hash_set.add(1)
hash_set.add(2)

# 값 존재 확인
if 1 in hash_set:
    print("1이 존재합니다.")

# 값 삭제
hash_set.remove(1)

 

2. 탐욕법(Greedy)

탐욕법 문제는 주로 배열 등을 정렬한 뒤, 문제의 조건을 만족하는 값을 하나씩 선택하는 방식으로 풀이한다. 문제에 따라 정렬이 필요 없거나 필요가 적을 수도 있지만, 정렬이 중요할 경우(최소/최대 값 등을 지속적으로 이용해야 할 경우) Python 표준 라이브러리의 'heapq' 모듈을 이용하면 우선순위 큐를 쉽게 구현할 수 있다.

import heapq

# 힙 선언
heap = []

# 힙에 값 추가
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 힙에서 최소값 꺼내기
print(heapq.heappop(heap))  # 1

 

3. 정렬(Sort)

Python에서는 Timsort(관련문서: https://d2.naver.com/helloworld/0315536) 기반의 정렬 함수를 제공한다. 크게 두 가지 함수를 사용할 수 있다.

• sorted(): 원본 리스트를 변경하지 않음
• list.sort(): 원본 리스트 자체를 정렬함

# 리스트 정렬
arr = [5, 2, 9, 1]

# sorted()는 새로운 정렬된 리스트 반환
sorted_arr = sorted(arr)  # [1, 2, 5, 9]

# list.sort()는 리스트 자체를 정렬
arr.sort()  # arr가 [1, 2, 5, 9]로 변경됨

# 역순 정렬시
arr.sort(reverse=True)

# 특정 키를 기준으로 정렬 (lambda 함수 사용)
# ex) 배열의 두 번째 값 기준으로 정렬
arr.sort(key= lambda x: x[1])

 

4. 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍은 재귀적 방법으로 문제를 풀이할 때 중복 계산을 피하기 위해 작은 문제들로 나눠 풀이한 뒤, 해당 값들을 다시 이용하는 방법으로 구현된다. 일반 재귀적 방법을 이용할 때보다 시간 복잡도가 줄어드는 효과를 가져온다.

# 예시: 피보나치 수열
# 메모이제이션 방법 사용
# memo라는 이름의 딕셔너리 내 이미 계산된 항목의 값 저장
# memo 내 이미 계산된 값이 있을 경우 꺼내서 사용
def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))  # 55

 

functools의 lru_cache 모듈 이용하기

이 방법을 사용하면 위 코드의 memo처럼 딕셔너리 자료형을 구현하지 않고, 이전 계산 결과를 캐싱하여 중복 계산을 피한다.

from functools import lru_cache

@lru_cache(maxsize=None)  # maxsize는 캐시할 수 있는 최대 항목 수
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# 피보나치 수열 계산
print(fibonacci(10))  # 55

 

5. 깊이 우선 탐색 및 너비 우선 탐색(DFS & BFS)

깊이 우선 탐색 문제에서는 스택(또는 재귀적 구현), 너비 우선 탐색에서는 큐가 주로 사용된다. 특히 BFS의 경우 파이썬의 collections.deque 모듈을 이용해 쉽게 구현할 수 있다.

# DFS(재귀적 구현)
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 그래프 표현 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

dfs(graph, 1)  # 1 2 4 3 5

 

 

# BFS (큐 사용)
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 그래프 표현 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

bfs(graph, 1)  # 1 2 3 4 5

 

6. 순열, 조합(Permutation, Combination) - itertools 사용

n개를 조합한 값이 m인 조합을 찾거나, 특정 순서를 맞춰서 배치해야 하는 문제의 경우 itertools의 조합형 이터레이터들이 큰 도움이 될 수 있다.

 

permutations(iterable, r=None) - 원소 개수가 r인 순열

from itertools import permutations

l = ['A', 'B', 'C']

for i in permutations(l): #r을 지정하지 않을 시 최대 길이의 순열을 리턴함
	print(i)
    
# 튜플 형태로 반환됨
>>>
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

 

combinations(iterable, r) - 원소 개수가 r인 조합

from itertools import combinations

l = [10,20,30]

for i in combinations(l,2):
	print(i)
    
# 튜플 형태로 반환
# 원소 중복 허용하지 않음
>>>
(10, 20)
(10, 30)
(20, 30)

 

combinations_with_replacement(iterable, r) - 원소 개수가 r인 중복 조합

from itertools import combinations_with_replacement

l = [1, 2, 3]

for i in combinations_with_replacement(l,2):
	print(i)
    
# 튜플 형태로 반환
# 원소 중복 허용
>>>
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)

 

product(*iterable, repeat=1) - 여러 iterable들 간의 조합

from itertools import product

A = [10, 20, 30]
B = [3, 4, 5]

for i in product(A,B,repeat=1): #A, B의 모든 쌍을 지어 반환
	print(i)
    
# 튜플 형태로 반환
>>>
(10, 3)
(10, 4)
(10, 5)
(20, 3)
(20, 4)
(20, 5)
(30, 3)
(30, 4)
(30, 5)