목표는 백준 플레티넘 5이고 이 정도 만들어놓으면 나중에 필요할 때 감만 다시 익히면 될거라고 생각했다. 백준 단계별 풀기 에 있는 문제들을 풀면서 정리했다.
자료구조
스택, 큐, 덱
# 스택
stack = []
stack.append(1)
if stack:
stack.pop() # 1
# 큐
from collections import deque
q = deque([1, 2])
q.append(3)
q.popleft() # 1
# 데크(dequeue)
from collections import deque
q = deque([1, 2])
q.append(3)
ㄹ
# stack
q.pop() # 3
# queue
q.popleft() # 1
우선순위큐
우선순위 큐는 가중치가 가장 큰 값을 우선으로 pop 하는 자료구조이다. 힙 구조를 사용하는데 이 때 push하거나, pop하는 과정에서 시간복잡도가 $O(logN)$이 소요된다. 힙(Heap) 은 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나로 이진 탐색 트리의 형태로 구현되어 있으며 최소 힙과 최대 힙이 있다. 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 가지며 트리의 루트 노드에 최소값이 위치한다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지며 트리의 루트 노드에 최대값이 위치한다.
# 오름차순으로 값을 가져올 때
import heapq
def heapsort(array):
h = []
result = []
for value in array:
heapq.heappush(h, value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
파이썬 heapq 모듈은 기본적으로 최소힙으로 구현되어 있기 때문에 내림차순으로 값을 가져오고 싶을 땐 다음처럼 구현한다.
# 내림차순으로 값을 가져올 때
import heapq
def heapsort(array):
h = []
result = []
for value in array:
heapq.heappush(h, -value)
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result
그래프
일반적으로 그래프를 다음과 같이 정의하여 문제를 풀었다.
# 표현 1
graph = {
1: [2, 3, 4],
2: [1, 2, 3],
# ...
}
트리
트리는 사이클이 없는 무방향 그래프이다.
유니온 파인드
예를들어 n명의 사람들이 파티에 왔을 때 생일이 같은 사람들끼리 팀을 구성하라고 했을 때 이 상황을 어떻게 자료구조로 표현할 수 있을까? 유니온 파인드 자료구조는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 집합을 하나의 트리로 구성하고 find 할 때는 각 원소의 루트를 찾아 같은지 비교하고, union할 때는 한 루트의 자식 노드로 연결한다. 이때 사용될 수 있는 최적화가 두가지가 있는데, 트리의 높이가 계속 늘어나는 것을 방지하여 높이가 작은 트리를 큰 트리에 연결하거나, find 연산을 거치면서 올라간 노드의 parent를 루트로 바꿔주어 트리의 높이를 낮춘다. 유니온 파인드 자료구조를 사용하는 대표적인 예시로 무방향 그래프의 사이클을 판별하는데 사용할 수 있다. 참고로 방향 그래프에서 사이클 여부는 DFS를 이용하여 판별할 수 있다.
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.depth = [1 for _ in range(n)]
def find(self, x):
if x == self.parent[x]:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx = self.find(x)
ry = self.find(y)
if rx == ry:
return
if self.depth[rx] < self.depth[ry]:
self.parent[rx] = ry
elif self.depth[rx] > self.depth[ry]:
self.parent[ry] = rx
else:
self.parent[ry] = rx
self.depth[rx] += 1
Trie(트라이)
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
class Node:
def __init__(self, key, depth=0):
self.key = key
self.depth = depth
self.data = None
self.children = {}
class Trie:
def __init__(self):
self.head = Node(None)
def insert(self, array):
cur_node = self.head
for string in array:
if string in cur_node.children:
next_node = cur_node.children[string]
else:
next_node = Node(string, cur_node.depth+1)
cur_node.children[string] = next_node
cur_node = next_node
next_node.data = string # data가 있을 때 문자열의 끝을 의미
strings = ["abc", "ab", "ac"]
trie = Trie()
for s in strings:
trie.insert(s)
세그먼트 트리(구간트리)
def build_segment_tree(array, node, node_lidx, node_ridx):
if node_lidx == node_ridx:
segment_tree[node] = array[node_lidx]
return segment_tree[node]
node_midx = (node_lidx + node_ridx) // 2
segment_tree[node] = build_segment_tree(array, node_lidx, node_midx, node*2) + build_segment_tree(array, node_midx+1, node_ridx, node*2+1)
return segment_tree[node]
def query_segment_tree(lidx, ridx, node, node_lidx, node_ridx):
if ridx < node_lidx or lidx > node_ridx:
return 0
if lidx <= node_lidx and node_ridx <= ridx:
return segment_tree[node]
node_midx = (node_lidx + node_ridx) // 2
return query_segment_tree(lidx, ridx, node*2, node_lidx, node_midx) + query_segment_tree(lidx, ridx, node*2+1, node_midx+1, node_ridx)
def update_segment_tree(idx, value, node, node_lidx, node_ridx):
if idx < node_lidx or idx > node_ridx:
return
segment_tree[node] += value
if node_lidx != node_ridx:
node_midx = (node_lidx + node_ridx) // 2
update_segment_tree(idx, value, node*2, node_lidx, node_midx)
update_segment_tree(idx, value, node*2+1, node_midx+1, node_ridx)
array = [1, 2, 3, 4, 5]
segment_tree = [0 for _ in range(len(array))]
build_segment_tree(array, 1, 0, n-1)
update_segment_tree(0, 100, 1, 0, n-1) # 0번째 index의 값을 100으로 변경
query_segment_tree(2, 4, 1, 0, n-1) # 2에서 4번째 index의 합을 구하기
딕셔너리, 셋
파이썬의 dictionary는 해시테이블(Hashtable)로 key를 검사하는 시간복잡도가 $O(1)$ 이므로 적극 사용해보자. 자료구조를 이용하는 것만으로도 속도를 개선할 수 있다 (ex. 백준 10815번 참고)
파이썬의 set 함수는 다음과 같이 사용할 수 있다.
s1 = set([1, 2, 3])
s2 = set([2, 3, 4])
# 교집합
s1 & s2
s1.intersection(s2)
# 합집합
s1 | s2
s1.union(s2)
# 차집합
s1 - s2
s1.difference(s2)
s1.add(4) # {1, 2, 3, 4}
s1.update([3, 4, 5]) # {1, 2, 3, 4 ,5}
s1.remove(2) # {1, 3}
그리디 알고리즘
그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘은 처음 아이디어를 떠올리는 것이 중요하다 (ex. 백준 1931번) 그리고 바로 떠오르는 아이디어로 시간 내에 풀 수 없을 때 그리디 알고리즘을 한번 떠올려봐도 좋다 (백준 13305번) 그리디 알고리즘은 해법이 중요한데, 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다 (코테에서는 대부분의 그리디 문제는 최적의 해가 되는 상황에서 문제가 출제된다) 그리디 알고리즘의 아이디어는 간단하지만 강력해서 다른 알고리즘에서 당연하게 사용되기도 한다. 예를들어 최소 스패닝 트리 문제를 풀 때 사용하는 크루스칼 알고리즘 또는 프림 알고리즘 모두 간선이 하나도 없는 상태에서 시작해 트리에 간선을 하나씩 추가해가는 그리디 알고리즘의 일종이다.
탐색 알고리즘
브루트포스(완전탐색)
가능한 경우를 모두 대입해서 구하는 방식이다. 예를들어 2차 방정식의 해를 구할 때 가능한 해를 전부 대입해보는 식으로 풀 수 있다. 백준 19532번 , 1436번 을 참고하자.
백트래킹
이분탐색(binary search, 이진탐색)
정렬된 리스트에서 $O(log_2N)$의 시간복잡도로 원하는 값을 찾을 수 있다.
import bisect
def binary_search(array, start_idx, end_idx, target):
# 종료 조건
if start_idx > end_idx:
return None
mid_idx = int((start_idx + end_idx) / 2)
if array[mid_idx] == target:
return mid_idx
if target < array[mid_idx]:
return binary_search(array, start_idx, mid_idx-1, target)
else:
return binary_search(array, mid_idx+1, end_idx, target)
# 이 때 array는 정렬된 리스트이다.
array = [1, 2, 5, 8, 10]
binary_search(array, 0, len(array)-1, 5) # 2
# bisect_left 구현하기
# - 해당 값이 리스트에 있을 때 해당 index 반환
# - 해당 값이 리스트에 없을 때 해당 값이 들어갈 index 반환
def binary_left(array, start_idx, end_idx, target):
if start_idx > end_idx:
return start_idx
mid_idx = (start_idx + end_idx) // 2
if array[mid_idx] >= target:
return binary_left(array, start_idx, mid_idx-1, target)
else:
return binary_left(array, mid_idx+1, end_idx, target)
binary_left(array, 0, len(array)-1, target)
bisect.bisect_left(array, target)
# bisect_right 구현하기
# - 해당 값이 리스트에 있을 때 해당 index+1 반환
# - 해당 값이 리스트에 없을 때 해당 값이 들어갈 index 반환
def binary_right(array, start_idx, end_idx, target):
if start_idx > end_idx:
return end_idx+1
mid_idx = (start_idx + end_idx) // 2
if array[mid_idx] <= target:
return binary_right(array, mid_idx+1, end_idx, target)
else:
return binary_right(array, start_idx, mid_idx-1, target)
binary_right(array, 0, len(array)-1, target)
bisect.bisect_right(array, target)
이분 탐색은 최대 또는 최소를 구하는데도 사용될 수 있는데 대표적으로 LIS(Longest Increasing Subsequence) 문제를 효율적으로 해결할 수 있다. DP의 유형 중 하나로 정리한 LIS에 보면 이분탐색에 대한 내용도 같이 정리했으니 참고하자. 또 이분 탐색 백준 1300번 문제를 보면 이분탐색이 참 다양하게 꼬아서 출제될 수 있겠다 싶다.
다이나믹 프로그래밍
전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제해결방식이다. 큰 문제를 작은 문제로 나눈 후 작은 문제의 답을 모아 큰 문제를 해결할 수 있고 동일한 작은 문제를 반복적으로 해결할 수 있을 때 DP를 적용해볼 수 있다. DP 문제 접근 방법은 다음과 같다.
- 먼저 주어진 문제가 DP 문제임을 파악하는게 중요하다.
- 먼저 그리디, 구현, 완점 탐색 등의 아이디어로 해결할 수 있는 문제인지 검토한다.
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 DP 고려한다.
- 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에(탑다운으로), 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선한다 (참고로 재귀는 트리구조를 생각하면 순서를 파악하기 쉽다)
DP와 그리디 알고리즘과 비교: 가능한 모든 방법을 검토하는 것이 때로는 장점, 때로는 단점이 될 수 있는데, 이 단점을 극복하고자 할 때는 그리디 알고리즘을 사용할 수 있다.
DP와 분할정복 알고리즘과 비교: DP와 분할정복 둘다 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황(최적 부분 구조)일 때 사용할 수 있다. 차이점은 부분 문제의 중복이다. DP 문제에서는 각 부분 문제들이 중복되지만, 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
피보나치 수열 구현
# 방식 1) 재귀
d = [0] * 100
def fibo(n):
if n == 1 or n == 2:
return 1
if d[n] != 0:
return d[n]
d[n] = fibo(n-1) + fibo(n-2)
return d[n]
# 방식 2) DP
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
n! 구현
# 방식 1) 반복문
def factorial(n):
v = 1
if n in [0, 1]:
return v
for i in range(n):
v = v * (i + 1)
return v
재귀문을 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다는 장점이 있지만, 다른 사람이 이해하기 어려운 코드가 될 수 있다. 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있다.
# 방식 2) 재귀문
def factorial(n):
if n in [0, 1]:
return 1
return n * factorial(n-1)
for문 돌면서 이전에 계산했던 값을 쓸 필요가 없으니, 아래처럼 dp로 굳이 풀지 않아도 되지만 그래도 남겨놓는다.
# 방식 3) dp
def factorial(n):
d p = [0] * 100
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = i * dp[i-1]
return dp[n]
LCS(Longest Common Subsequence, 최장 공통 부분 수열)
LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)
원소 n개의 수열에서 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. LIS의 간편한 방법으로 DP가 있지만 $O(n^2)$으로 비효율적이다. 이분탐색을 활용한 LIS는 $O(blogS)$로 해결할 수 있다.
# DP로 LIS 풀이 (백준 14002 참고)
n = int(input().strip()) # 5
seq = list(map(int, input().strip().split())) # 1 3 5 2 6
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if seq[i] > seq[j]:
dp[i] = max(dp[j] + 1, dp[i])
result = []
max_dp_val = max(dp)
i = dp.index(max_dp_val)
while i >= 0:
if dp[i] == max_dp_val:
result.append(seq[i])
max_dp_val -= 1
i -= 1
print(result) # 1 3 5 6
# binary serach로 LIS 풀이 (백준 14003 참고)
n = int(input().strip())
seq = list(map(int, input().strip().split()))
dp = [seq[0]]
diff = []
for i in range(n):
if dp[-1] < seq[i]:
dp.append(seq[i])
else:
idx = bisect.bisect_left(dp, seq[i])
diff.append((idx, dp[idx]))
dp[idx] = seq[i]
for t in diff[::-1]:
idx, v = t
if idx == len(dp)-1 and idx-1 >= 0 and dp[idx-1] < v:
dp[idx] = v
elif idx == 0 and idx+1 <= len(dp)-1 and dp[idx+1] > v:
dp[idx] = v
elif idx-1 >= 0 and idx+1 <= len(dp)-1 and dp[idx-1] < v < dp[idx+1]:
dp[idx] = v
배낭 문제
물건을 쪼갤 수 있는 경우는 그리디 알고리즘를 사용하고 물건을 쪼갤 수 없는 경우는 DP를 사용하자.
누적합
1차원, 2차원 배열에서 각각 누적합 구할 수 있어야하는데 1차원 배열은 백준 11659번 , 2차원 배열은 백준 25682번 을 참고하자.
행렬의 제곱 문제
정렬
선택 정렬
가장 작은 데이터를 선택하고 맨 앞의 데이터와 바꾼다. 시간복잡도는 $O(N^2)$ 이다.
array = [5, 2, 7, 2, 5, 0, 1, 8]
for i in range(len(array)):
min_idx = i
for j in range(i, len(array)):
if array[min_idx] > array[j]:
min_idx = j
array[i], array[min_idx] = array[min_idx], array[i]
삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 시간 복잡도는 $O(N^2)$ 이지만 현재 리스트가 거의 정렬되어있다고 하면 선택 정렬보다 더 효율적이다.
array = [5, 2, 7, 2, 5, 0, 1, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j-1], array[j] = array[j], array[j-1]
else:
break
분할 정복 알고리즘
투포인터 알고리즘
위상정렬
그래프 관련 알고리즘
그래프 탐색: DFS
깊이우선"탐색"으로 깊은 부분을 우선적으로 탐색한다. 스택 자료구조(혹은 재귀함수)를 이용한다.
방법 1) 재귀를 이용한 방식
graph = [
[],
[2, 3, 8], # 1번에 인접한 노드
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
v = 1
visited = [0] * 9
def dfs(graph, v, visited):
visited[v] = 1
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5
방법 2) 스택을 이용한 방식
from collections import deque
graph = [
[],
[2, 3, 8], # 1번에 인접한 노드
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [0] * 9
def dfs(graph, v, visited):
stack = [v]
visited[v] = 1
while stack:
v = stack.pop()
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
stack.append(i)
visited[i] = 1
dfs(graph, 1, visited)
그래프 탐색: BFS
너비우선"탐색"으로 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐 자료구조를 이용한다.
from collections import deque
graph = [
[],
[2, 3, 8], # 1번에 인접한 노드
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [0] * 9
def bfs(graph, v, visited):
queue = deque([v])
queue.append(v)
visited[v] = 1
while len(queue) != 0:
v = queue.popleft()
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = 1
bfs(graph, 1, visited)
최소 스패닝 트리(Minimum spanning tree, MST)
스패닝 트리는 그래프 내의 모든 정점을 포함하는 트리를 말한다. 최소 스패닝 트리는 spanning tree의 한 종류로서 사용되는 간선의 가중치 합이 최소인 트리를 말한다. 당연히 간선의 수가 최소라고해서 최소 비용은 아니다. MST를 구현하는 대표적인 알고리즘이 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이다. 이 두 알고리즘은 접근 방법이 아주 달라 보이지만 결국 같은 방법으로 증명할 수 있다. 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해가는 그리디 알고리즘으로 본질적으로 같은 방법으로 증명할 수 있다. N개의 정점의 그래프를 최소 간선으로 연결하기 위해서는 트리 형태여야 하고(트리의 간선의 수는 N-1) 이 때 최소 가중치를 가지려면 MST를 구하면 되기 때문에 어떤 임의의 그래프에서 최소 회선 수를 가지면서 최소 가중치를 가지는 회선을 구하라고 하면 MST를 구하면 된다.
크루스칼 알고리즘은 유니온 파인드 자료구조의 좋은 사용 예이기도 하다. 그래프의 모든 간선을 가중치의 오름차순으로 정렬하고 스패닝 트리에 하나씩 추가해가는데 사이클 여부만 확인하면 된다. 이 때 이 사이클 여부를 유니온 파인드 자료구조를 활용하여 판별할 수 있다.
parent = [i for i in range(n)]
depth = [1 for _ in range(n)]
def find(p1):
if p1 == parent[p1]:
return p1
parent[p1] = find(parent[p1])
return parent[p1]
def union(p1, p2):
r1, r2 = find(p1), find(p2)
if depth[r1] < depth[r2]:
parent[r1] = r2
elif depth[r1] > depth[r2]:
parent[r2] = r1
else:
depth[r1] += 1
parent[r2] = r1
size = 0
distances = sorted(distances) # 그래프 사이의 거리를 오름차순으로 정렬
for _, t in enumerate(distances):
distance, p1, p2 = t
r1, r2 = find(p1), find(p2)
# 사이클이 있는지 확인
if r1 != r2:
union(r1, r2)
size += distance
프림 알고리즘은 다익스트라 알고리즘과 거의 같은 형태를 띄고 있는데, 비슷한 알고리즘으로 다른 문제를 어떻게 해결하는지에 중점을 두고 보자.
최단 경로 알고리즘
최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 한 지점에서 다른 한 지점까지의 최단 경로, 한 지점에서 다른 모든 지점까지의 최단 경로, 모든 지점에서 다른 모든 지점까지의 최단 경로를 구할 때 사용할 수 있다. 대표적으로 다익스트라 알고리즘 (가중치 양수일 때), 벨만-포드 알고리즘 (가중치 음수도 포함), 플로이드 워셜 알고리즘 등이 있다.
다익스트라 알고리즘의 핵심은 경로 비용이 양수일 때 사용할 수 있다. 최단 거리 테이블을 초기화하고 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하고, 해당 노드에서 다른 노드로 가는 비용을 계산하고 최단 거리 테이블을 업데이트 하는 과정으로 진행된다. 다익스트라 알고리즘은 본질적으로 그리디 알고리즘을 활용한 것이며 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 단계를 거치며 한번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않고 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
최단 경로 문제에서 전체 노드 개수가 5000개 이하라면 $O(N^2)$ 시간복잡도 알고리즘으로 풀 수 있지만, 노드 개수가 10000개가 넘어가면 어떻게 해야할까? 우선순위 큐를 사용한다.
우선순위 큐를 이용하는 다익스트라 알고리즘의 시간 복잡도는 $O(ElogV)$이다. 노드를 하나씩 꺼내 검사하는 반복문은 노드 개수 V 이상의 횟수로는 처리되지 않는다. 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들은 확인하는 총 횟수로는 최대 간선의 개수만큼 연산이 수행될 수 있다. 직관적으로 전체과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다. 시간 복잡도를 $O(ElogE)$로 판단할 수 있음. 중복 간선을 포함하지 않는 경우에 이를 $O(ElogV)$로 정리할 수 있음. $O(ElogE)$ -> $O(ElogV^2)$ -> $O(2ElogV)$ -> $O(ElogV)$
# A지역에서 B지역으로 갈 때 드는 버스 비용의 최소값 구하기(백준 1916번을 참고하자)
from collections import defaultdict
INF = int(1e9)
n = int(input()) # n: 지역 개수
m = int(input()) # m: 버스 개수
graph = defaultdict(list)
for _ in range(m):
graph[n1].append((n2, price))
def dijkstra(start_idx):
distance = [INF for _ in range(n)]
distance[start_idx] = 0
q = [(distance[start_idx], start_idx)]
while q:
cur_distance, cur_idx = heapq.heappop(q)
for t in graph[cur_idx]:
next_idx, price = t
if cur_distance + price < distance[next_idx]:
distance[next_idx] = cur_distance + price
heapq.heappush(q, (distance[next_idx], next_idx))
return distance
start_idx = 0
end_idx = n-1
dijkstra(start_idx)[end_idx] # min distance
벨만-포드 알고리즘
플로이드 워셜 알고리즘
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단거리 정보를 저장하며 DP 유형에 속한다. 노드의 개수가 N개 일 때 알고리즘상으로 N번의 단계를 수행한다. 각 단계마다 $O(N^2)$의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 $O(N^3)$이다.
트리
이진트리(binary tree) 순회
이진 트리(binary tree) 의 순회방법은 다음과 같다.
- preorder traversal(전위 순회): “현재 노드” -> 왼쪽 자식 -> 오른쪽 자식 순서로 순회한다. 트리의 구조를 복제하거나, 루트노드로부터 작업을 수행할 때 유용하다.
- inorder traversal(중위 순회): 왼쪽 자식 -> “현재 노드” -> 오른쪽 자식 순서로 순회한다. binary search tree에서 노드 값을 오름차순으로 정렬된 순설르 얻을 때 유용하다.
- postorder traversal(후위 순회): 왼쪽 자식 -> 오른쪽 자식 -> “현재 노드” 순서로 순회한다. 자식을 모두 방문한 후에 부모 노드를 방문해야할 때 사용하는데 예를들어 디렉토리와 파일의 크기를 합산할 때 유용하다.
# 참고: 백준 1991번(트리 순회)
n = int(input().strip())
graph = {}
for _ in range(n):
p, l, r = input().strip().split()
graph[p] = [l, r]
def preorder(v):
if v != ".":
print(v, end="")
preorder(graph[v][0])
preorder(graph[v][1])
def inorder(v):
if v != ".":
inorder(graph[v][0])
print(v, end="")
inorder(graph[v][1])
def postorder(v):
if v != ".":
postorder(graph[v][0])
postorder(graph[v][1])
print(v, end="")
preorder("A")
print()
inorder("A")
print()
postorder("A")
print()
실제로 트리 순회 문제가 나왔을 때 left, right의 subtree로 나누어 생각하는 것이 중요하다. 백준 2263번 참고하자. 서브 트리를 생성하여 문제를 풀 수 있다.
트리의 지름 구하기
트리의 지름이란 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름이 a, b라고 했을 때 임의의 점에서 가장 긴 노드를 찾으면 a 또는 b가 된다. 즉 임의의 노드에서 dfs를 돌려서 가장 길게 나왔던 노드에서 다시 한번 더 dfs를 돌려 가장 길게 나오는 노드를 선택한다. 백준 1167번 , 1967번 을 참고하자.
문자열
문자열 집합에서 한개의 문자열을 탐색할 때 trie 또는 binary search 를 참고하자.
KMP 알고리즘
def pattern_table(string):
pt_tb = [0 for _ in range(len(string))]
pidx = 0
for idx in range(1, len(string)):
while pidx > 0 and string[pidx] != string[idx]:
pidx = pt_tb[pidx-1]
if string[pidx] == string[idx]:
pidx += 1
pt_tb[idx] = pidx
return pt_tb
def kmp(source, target):
result = []
pt_tb = pattern_table(target)
j = 0
for i in range(len(source)):
while j > 0 and target[j] != source[i]:
j = pt_tb[j-1]
if target[j] == source[i]:
j += 1
if j == len(target):
result.append((i-(j-1), i))
j = pt_tb[j-1]
파이썬 팁
2차원 리스트 순회하기
맵이 주어질 때, dx, dy를 이용해서 좌표를 나타내보자. 코드가 간단해진다.
dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1] # 상, 하, 좌, 우를 다음과 같이 나타냄
n x m 2차원 리스트 만들기
visited = [[0 for _ in range(m)] for _ in range(n)]
2차원 리스트에서 column 추출
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
list(zip(*a)) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
한 줄에 여러 정수 혹은 실수 입력받기
list(map(int, input().split()))
# 입력: 1 2 3 4 5
# 출력: [1, 2, 3, 4, 5]
두 변수 값 바꾸기
# a, b 값 바꾸기
a, b = b, a
deque 사용하기
queue 자료형을 구현할 때 리스트의 pop(0)으로도 가져올 수 있지만 나머지 원소들을 한칸씩 옮겨야해서 시간복잡도 O(N)이 소요된다. 표준라이브러리 collections의 deque를 사용하면 O(1)의 시간복잡도가 소요된다.
# 시간복잡도 O(N)
queue = [1, 2, 3, 4, 5]
queue.pop(0) # 1
queue # [2, 3, 4, 5]
# 시간복잡도 O(1)
from collection import deque
queue = deque([1, 2, 3, 4, 5])
queue.popleft() # 1
queue # [2, 3, 4, 5]
특정 키 기준으로 딕셔너리 정렬 후 리스트 반환
dictionary = {1: 3, 2:1, 3: 2}
# key를 기준으로 정렬
sorted(dictionary.items(), key=lambda x: x[1]) # [(2, 1), (3, 2), (1, 3)]
# value, key 순서로 정렬
sorted(dictionary.items(), key=lambda x: (x[1], x[0])) # [(2, 1), (3, 2), (1, 3)]
정렬된 리스트에서 이진탐색으로 탐색 및 값 삽입(bisect)
정렬된 리스트에서 값을 찾거나 삽입할 때 단순 순회탐색이 아닌 이진 탐색을 자동으로 지원하는 라이브러리로 시간복잡도는 O(logN)으로 매우 효율적이다.
import bisect
array = [1, 2, 2, 3, 5, 5]
# 숫자 4가 어디에 위치해야하는지 index 가져오기
bisect.bisect_left(array, 4) # 4
# bisect_left는 그 숫자의 가장 왼쪽 index
# bisect_right는 그 숫자의 가장 오른쪽 index
bisect.bisect_left(array, 5) # 4
bisect.bisect_left(array, 5) # 6
표준 입력으로 시간 단축하기
다음 코드로 입력 시간을 줄일 수 있다.
import sys
input = sys.stdin.readline
num = int(input())
이 때 sys.stdin.readline은 줄바꿈 문자를 포함하여 입력받기때문에 strip()을 포함해주도록 하자. 문자열을 제외한 정수형이나 실수형 등으로 변환할 때는 줄바꿈 문자를 자동으로 생략하여 캐스팅되기 때문에 strip()을 생략할 수 있다.
아스키코드 관련 함수
for i in range(26):
print(chr(97 + i)) # a, b, ..., z
for i in range(26):
print(chr(65 + i)) # A, B, ... , Z
ord("a") # 97
정규표현식
위키독스 참고하기
data = "park 010-1234-1234"
import re
p = re.compile(r"(\w+)(\s+)(\d+[-]\d+[-]\d+)")
m = p.match(data)
print(m.group(4)) # 010-1234-1234
파이썬 리스트 내의 item 개수 세기
a = [1, 1, 3, 4]
a.count(0) # 0
a.count(1) # 2
a.count(3) # 1
재귀 깊이 제한 설정하기
파이썬 재귀 깊이 제한 풀어주기. 이 때 그냥 무작정 큰 수를 대입하면 메모리 초과가 발생할 수 있으니 주의하자. 백준 2263번 에서 실제로 재귀 제한 값을 $10^6$으로 했다가 메모리 초과가 떴다. 노드 개수 + 1 로 넣어주니까 대부분 잘 통과했다.
import sys
sys.setrecursionlimit(10 ** 6)
순열과 조합
import itertools
arr = ["a", "b", "c"]
permus = itertools.permutations(arr, 2)
print(list(permus)) # [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
combis = itertools.combinations(arr, 2)
print(list(combis)) # [('a', 'b'), ('a', 'c'), ('b', 'c')]
코테 팁
문제를 풀다보면 변수 명에 시간을 쓰는게 아까울 때가 많았다. 자주 사용했던 변수명을 정리해두자.
- graph, dp, matrix, size