파이썬 코딩테스트
코딩테스트 준비
시간 제한이 1초이고, 데이터의 개수가 100만 개라면 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용해야 한다.
자료구조
: 데이터를 표현하고 관리하고 처리하기 위한 구조.
스택
: 박스 쌓기처럼, 마지막에 들어온 자료가 가장 먼저 나가는 구조. (후입선출)
파이썬에서는 별도로 스택을 구현하지 않아도 된다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
큐
: 대기줄처럼, 처음 들어온 자료가 가장 먼저 나가는 구조. (선입선출)
파이썬에서 큐를 구현할 때는 collections모듈에서 제공하는 deque 자료구조를 활용한다.
deque객체를 리스트 자료형으로 변경하고자 한다면 list()메서드를 이용한다.
그리디
: 매 순간 가장 좋아보이는 것을 고르는 방법.
기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다. 대체로 이러한 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있다.
최선의 답을 보장하지 않는다. 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 효과적이다. 따라서 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
문제 유형을 파악하기 어렵다면, 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 그리디 알고리즘으로 풀 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘을 의심해본다.
구현
: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
주로 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 푸는 데 불리하다.
- 완전 탐색 : 모든 경우의 수를 전부 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
파이썬 코드는 1초에 2,000만 번의 연산을 수행한다고 가정하면 된다.
일반적으로 확인(탐색)해야 할 전체 데이터의 수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.
방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.
파이썬에서 2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적이다.
DFS / BFS
그래프는 노드와 간선으로 표현된다. 두 노드가 간선으로 연결되어 있다면 ‘인접하다’라고 표현한다.
-
인접 행렬 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식.
INF = 9999999999 # 거리 무한 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ]메모리를 낭비하지만, 속도가 빠르다.
-
인접 리스트 방식 : 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식.
graph = [[] for _ in range(3)] # 노드 0 graph[0].append((1, 7)) # 노드 1이 7의 거리로 연결됨 graph[0].append((2, 5)) # 노드 1 graph[1].append((0, 7)) # 노드 2 graph[2].append((0, 5))속도가 느리지만, 메모리를 효율적으로 사용한다.
DFS
: 깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색한다.
특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙히 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색한다.
스택 자료구조를 이용하며, 아래와 같이 동작한다.
① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
③ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
실제 코드에서는 스택을 쓰지 않고 재귀를 사용한다.
def dfs(graph, v, visited):
visited[v] = True # 현재 노드 방문 처리
print(v, end=' ')
# 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i ,visited)
graph = [
[1],
[0, 2],
[1, 3],
[2]
]
visited = [False] * 4 # 각 노드가 방문된 정보
dfs(graph, 1, visited)
BFS
: 너비 우선 탐색. 그래프에서 현재 노드와 가까운 노드부터 탐색한다.
선입선출 방식인 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣으면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.
동작 방식은 아래와 같다.
① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
③ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
v = queue.popleft()
print(v, end=' ')
# 해당 노드와 연결된, 아직 방문하지 않은 노드들을 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[1],
[0, 2],
[1, 3],
[2]
]
visited = [False] * 4 # 각 노드가 방문된 정보
bfs(graph, 1, visited)
코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다.
정렬
: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것.
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다.
선택 정렬
: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복한다.
array = [7, 5, 9, 0, 3, 1, 6]
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
선택 정렬은 O(N²)의 시간 복잡도를 가진다.
삽입 정렬
: 데이터를 하나씩 확인하며, 적절한 위치에 삽입한다.
필요할 때만 위치를 바꾸기 때문에 ‘데이터가 거의 정렬되어 있을 때’ 매우 효율적이다.
array = [7, 5, 9, 0, 3, 1, 6]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else
break
삽입 정렬은 O(N²)의 시간 복잡도를 가지지만, 최선의 경우 O(N)이다.
퀵 정렬
: 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나눈다.
피벗 : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준.
※ 호어 분할 (리스트에서 첫 번째 데이터를 피벗으로 정한다.)
왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다.
array = [7, 5, 9, 0, 3, 1, 6]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and array[left] <= array[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right:
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
퀵 정렬은 O(NlogN)의 시간 복잡도를 가진다. 단, 최악의 경우 O(N²)이다. 퀵 정렬은 데이터가 이미 정렬되어 있다면 매우 느리다.
계수 정렬
: 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
데이터의 크기 범위가 제한되어 정수 형태로 표현할 때만 사용할 수 있다. 최악의 경우에도 O(N + K)를 보장하는 매우 빠른 정렬 알고리즘이다.
조건이 있는 이유는 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다.
array = [7, 5, 9, 0, 3, 1, 6]
count = [0] * (max(array) + 1) # 모든 범위를 포함하는 리스트
for i in range(len(array)):
count[array[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
데이터의 범위가 한정되어 있고, 넓지 않다면 사용할 수 있으며 매우 빠르게 동작한다.