좌: Union-Find 수행 이후 서로소 관계를 파악 가능 / 우: 부모 노드(!= 루트 노드)만을 저장한다.
서로소 집합 자료구조에서는 손쉽게 집합의 형태로 연결 여부를 확인할 수 있다.
기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
오른쪽 그림의 예시에서는, 노드 3의 루트를 찾기 위해서 노드 2 -> 노드 1 순서로 접근해야 한다.
구현: 기본적인 형태
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
if parent != x:
return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# Union 연산
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합(루트 노드) 출력하기
for i in range(1, v + 1):
print(find_parent(parent, i))
기본적인 구현 방법의 문제점
출처: 유튜브 캡쳐
Union 연산이 편향되게 이루어 지는 경우 Find 연산이 비효율적으로 동작한다.
최악의 경우 Find 연산이 모든 노드를 다 확인해야 하므로 시간 복잡도가 O(V)이다.
이것을 개선하기 위해 `경로 압축`이 필요하다.
구현: 경로 압축
Find 연산을 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
Find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신한다.
def find_parent(parent, x):
if parent != x:
parent[x] = find_parent(parent, parent[x]) # 부모 테이블을 즉시 갱신
return parent[x]
경로 압축 기법을 적용하면 부모 노드 테이블이 루트 노드를 가리킨다.
경로 압축의 과정에서, 각 Find 연산이 수행될 떄마다 경로 상의 모든 노드를 루트로 직접 연결하면서 트리의 높이를 평탄화한다.
(이때 부모 노드는 곧 루트 노드이다.)
경로 압축을 적용했을 때 Union-Find 연산의 시간 복잡도는 `O(α(N))`이다.
`α(x)`는 애커만 함수의 역함수이다.
애커만 함수는 재귀 함수의 일종으로 입력 값이 작더라도 매우 빠르게 증가한다.
반대로 역 애커만 함수는 x가 2^65536 일때 그 값이 4 ~ 5 정도이다. 거의 상수 시간이라고 할 수 있다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
if parent != x:
return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union_parent(parent, a, b)
if cycle:
print("사이클 발생")
else:
print("사이클 발생하지 않음")
신장 트리 Spanning Tree
출처: 유튜브 캡쳐
정의
모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
최소 신장 트리 MST, Minimum Spanning Tree
출처: 유튜브 캡쳐
최소한의 비용으로 구성되는 신장 트리
크루스칼 알고리즘 Kruskal Algorithm
출처: 위키피디아
정의
최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘.
대표적인 최소 신장 트리 알고리즘.
그리디 알고리즘으로 분류.
동작 과정
간선 데이터를 비용에 따라 오름차순으로 정렬
간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
사이클이 발생하지 않는 경우, 최소 신장 트리에 포함
사이클이 발생하는 경우, 최소 신장 트리에 포함하지 않음
모든 간선에 대하여 2번의 과정을 반복
구현
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (v + 1)
edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용
for i in range(1, v + 1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
edges,append((cost, a, b))
edges.sort() # 간선을 비용 순으로 정렬
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b): # 사이클이 발생하지 않는 경우 집합에 포함
union_parent(parent, a, b)
result += cost # 비용 더하기
print(result)
특징
간선의 개수가 E개일 때 `O(ElogE)`의 시간 복잡도를 갖는다.
가장 많은 시간을 요구하는 곳은 간선을 정렬하는 부분이다.
위상 정렬 Topological Sorting
출처: tutorialhorizon
정의
사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열.
순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정하는 알고리즘이다.
예컨대, 라면을 끓이려면 물이 먼저 끓어야 한다. 특정 과목을 수강하려면 선수 과목을 수강해야 한다.
진입차수와 진출차수
출처: 유튜브 캡쳐
진입차수: 특정한 노드로 들어오는 간선의 개수
진출차수: 특정한 노드에서 나가는 간선의 개수
동작 과정: 큐 (진입 차수)
진입차수가 0인 모든 노드를 큐에 넣는다.
큐가 텅 빌 때까지 다음의 과정을 반복한다.
큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
결과적으로 각 노드가 큐에 들어온 순서가, 위상 정렬을 수행한 결과와 같다.
구현: 큐
from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v + 1) # 모든 노드에 대한 진입차수는 0으로 초기화
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 노드 A에서 B로 이동 가능
indegree[b] += 1
def queue_topological_sort():
result = []
q = deque()
for i in range(1, v + 1):
if indegree[i] == 0: # 진입차수가 0인 노드를 큐에 삽입
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1 # 현재 노드와 연결된 노드의 진입 차수 1 빼기
if indegree[i] == 0: # 새롭게 진입 차수 0이 된 노드 큐에 삽입
q.append(i)
for i in result:
print(i, end=" ")
topological_sort()
동작 과정: 스택 (진출 차수)
방문하지 않은 임의의 노드에서 출발한다.
DFS를 수행하며 방문하는 노드를 스택에 담는다.
모든 정점을 방문할 때까지 1번을 반복한다.
모든 정점을 방문했다면 스택에 담긴 정점을 출력한다.
DFS는 깊이 우선 탐색이라는 사실을 떠올려보자.
하나의 노드에서 DFS를 수행하면 결국 리프 노드까지 내려갈 것이다.
리프 노드는 진출 차수가 0이다.
즉, 가장 마지막에 수행되어야 하는 작업이다.
가장 깊은 리프 노드가 스택에 먼저 담기고,
루트 노드가 가장 나중에 스택 최상단에 담길 것이다.
LIFO 형태의 스택을 차례대로 출력하면 위상 정렬의 결과와 같다.
임의의 노드를 선택해도 상관이 없는 이유는,
DFS는 선택한 노드보다 늦게 수행되어야 할 노드(더 깊은 노드)만 방문하는 원리이다.
탐색 중인 그래프가 DAG인지 확인하기 위해 사이클 유무를 판단할 수 있어야 한다.
방문 처리된 노드를 DFS 호출 과정에서 만나면 사이클이 존재한다는 뜻이다.
구현: 스택
v, e = map(int, input().split())
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트
visited = [False] * (v + 1) # 방문 처리
stack = []
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 노드 A에서 B로 이동 가능
def dfs(v):
visited[v] = True
for next in graph[v]:
if not visited[next]:
dfs(next)
stack.append(v)
def stack_topological_sort():
for i in range(1, v + 1):
if not visited[i]:
dfs(i)
while stack:
print(stack.pop(), end=" ")
stack_topological_sort()
위상 정렬 특징
시간 복잡도는 `O(V + E)`이다.
차례대로 모든 노드를 확인하며, 각 노드에서 나가는 간선을 차례대로 제거해야 한다.
위상 정렬은 DAG(Direct Acyclic Grpah, 방향이 있는 비순환 그래프)에 대해서만 수행 가능하다.
최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화 (각 노드에 대한 현재까지의 최단 거리 정보를 갖고 있음)
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
3번에서 선택한 노드를 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
모든 노드를 방문할 때까지 3번과 4번을 반복
구현1. 기본적인 다익스트라
INF = int(1e9) # 무한의 거리를 나타내기 위해 10억을 설정
n, m = map(int, input().split())
start = int(input()) # 시작 노드
graph = [[] for _ in range(n+1)] # 연결 정보 담는 리스트
visited = [False] * (n+1) # 방문 체크 리스트
distance = [INF] * (n+1) # 시작 노드부터 특정 노드까지의 최단 거리 테이블. INF로 초기화.
for _ in range(m): # 모든 간선 정보 입력
a, b, c = map(int, input().split()) # a번 노드 -> b번 노드 (비용 c)
graph[a].append((b, c))
def get_smallest_node(): # 방문하지 않은 노드 중, 최단 거리가 최소인 노드 반환
min_value = INF
index = 0 # 최단 거리가 최소인 노드의 인덱스
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]: # 현재 노드의 최단 거리보다 짧고 && 방문하지 않음
min_value = distance[i]
index = i
return index
def dijkstra(start):
distance[start] = 0 # 시작 노드부터 시작 노드까지의 최단 거리는 0으로 갱신
visited[start] = True # 방문 처리
for adjacent_node_of_start in graph[start]: # 시작 노드와 인접한 노드의 최단 거리 갱신
distance[adjacent_node_of_start[0]] = adjacent_node_of_start[1]
for i in range(n-1): # n-1인 이유. 시작 노드X. 마지막 노드X
now = get_smallest_node() # 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드
visited[now] = True # 방문 처리
for adjacent_node in graph[now]: # 선택한 노드와 인접한 노드 확인
cost = distance[now] + adjacent_node[1] # 시작~선택 + 선택~인접
if cost < distance[adjacent_node[0]]: # cost가 시작~인접보다 작을 경우 갱신
distance[adjacent_node[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print("도달할 수 없는 신기루")
else:
print(distance[i])
1번 방법의 특징
O(V)번에 걸쳐서 get_smallest_node()를 호출하여, 매번 선형 탐색을 해야 한다.
부모 노드의 key(노드가 저장하는 값)가 자식 노드의 key보다 항상 작은-최소 힙(큰-최대 힙) 상태의 이진 트리.
이진 트리 binary tree
이진 트리의 종류 (출처: tutorialcup)출처: velog.io/@dlgosla
모든 노드가 둘 이하(0, 1, 2)의 자식을 가진 트리이다.
위 그림과 같이 다양한 종류가 있다.
많은 자료 구조를 만나고 왔다.
이진 트리 -> 완전 이진 트리 -> 힙 -> 우선 순위 큐 -> 개선된 다익스트라 알고리즘.
이렇듯 여러 단계를 거쳐 다익스트라를 개선시킬 수 있다.
핵심은 단계마다 방문하지 않은 노드 중에서, 시작 노드로부터 최단 거리가 가장 짧은 노드를 선택하기 위해 힙을 사용하는 것이다.
구현2. 개선된 다익스트라
import heapq
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
# 방문 처리 배열을 만들지 않는다. 단계마다 순차 탐색하는 것이 아니라 우선순위 큐에서 pop()하므로.
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start)) # 시작 노드 -> 시작 노드의 최단 거리는 0으로 갱신. 큐에 삽입.
distance[start] = 0
while q: # 큐가 텅텅 빌 때까지 반복
dist, now = heapq.heappop() # 최단 거리(dist)를 기준으로 우선순위 큐에서 bubble pop
if distance[now] < dist: # distance[now] == 현재까지 확정된 최소 거리, dist == 현재 탐색에서 최소 거리
continue # 확정된 최소 거리가 더 짧으면, 이미 방문한 셈 치고 continue
for adjacent_node in graph[now]:
cost = dist + adjacent_node[1] # 현재 탐색에서, 탐색 중인 노드의 최소 거리 + 인접 노드의 최소 거리
if cost < distance[adjacent_node[0]]: # cost가 인접 노드의 확정된 최소 거리보다 짧다면 갱신
distance[adjacent_node[0]] = cost
heapq.heappush(q, (cost, adjacent_node[0]])
dijkstra(start)
for i in ragne(1, n+1):
if distance[i] == INF:
print("영영 닿을 수 없음")
else:
print(distance[i])
개선된 방법의 특징
시간 복잡도는 O(ElogV)이다.
E는 E dge(간선), V는 Vertex(정점, 노드).
모든 노드를 검사하는 while문은 간선의 개수 E에 따라 실행 횟수가 결정된다.
왜 why? 간선의 개수만큼 큐에 넣으니까.
전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산(O(logN))과 유사하다.
E개의 원소에 대하여 O(logE)의 연산을 수행한다.
즉, 시간 복잡도는 O(ElogE)이다.
동시에 이것은 O(ElogV)와 같다.
왜 why? 실제 그래프에서 모든 노드가 서로 연결되어 있다면, 최대 간선 수는 V*(V-1)/2이다.
따라서 다음의 식이 성립한다.
O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)
플로이드-워셜 Floyd-Warshall
플로이드 워셜. 단순 연결 관계로 초기화한 상태. (출처: 유튜브 캡처)
요약
모든 노드에서다른 모든 노드로 가는 최단 경로를 모두 계산.
다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행.
단, 단계마다 방문하지 않는 노드 중 최단 거리 노드를 찾는 과정은 필요X (다익스트라에서 get_smallest_noe()로 수행했던 그것)
2차원 테이블에 최단 거리 정보를 저장.
다이나믹 프로그래밍 유형에 속함.
동작 과정
2차원 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화
각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인
a -> b 최단 거리보다, a -> k + k -> b가 더 짧은지 검사
점화식(D는 거리): Dab = min(Dab, Dak + Dkb)
모든 노드를 방문할 때까지 2번을 반복
구현: 플로이드 워셜
INF = int(1e9)
n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단 거리 정보를 저장할 2차원 리스트 INF로 초기화
for a in range(1, n+1): # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
for _ in range(m): # 각 간선에 대한 정보를 입력 받아, 최단 거리 테이블 갱신
a, b, c = map(int, input().split())
graph[a][b] = c # a에서 b로 가는 비용을 c라고 설정
for k in range(1, n+1): # 점화식에 따라 플-워 수행
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print("INFINITY", end = " ")
else:
print(graph[a][b], end = " ")
print()
플로이드 워셜의 특징
노드의 개수가 N개일 때 알고리즘을 N번 수행한다.
각 단계마다 O(N^2)의 연산을 통해, 현재 선택된 노드를 거쳐 가는 모든 경로를 고려한다.
메모리를 사용하여, 처리 시간을 단축하는 방법이다. 이를 메모이제이션(Memoization)이라고 한다.
조건
최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
중복되는 부분 문제 (Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 사용하여 해결해야 한다.
접근 방식
하향식(Top-Down): 큰 문제로 시작하여, 풀리지 않는 작은 문제를 만나면 재귀적으로 해결.
상향식(Bottom-Up ): 작은 문제를 모아서 큰 문제를 해결하는 방식.
Top-Down 접근 방식을 메모이제이션(Memoization)이라고도 부른다.
계산 결과를 메모리에 저장하여 중복 계산을 방지한다.
주로 재귀 함수를 반복적으로 호출하여 문제를 해결한다.
Bottom-Up 접근 방식은 타뷸레이션(Tabulation)이라고 한다.
테이블에 기록한다는 느낌.
주로 반복문으로 구현한다.
따라서 재귀 호출에 따른 오버헤드 혹은 스택 오버플로우 위험이 없다.
기본적으로 Bottom-Up으로 접근하는 것이 더 직관적이다.
일단 그렇게 하고, 막히면 Top-Down으로 풀이하자.
DP인지 어떻게 판단?
가장 중요한 문제이다.
주어진 입력값의 범위가 너무 크면 의심해본다.
완탐, 그리디로 풀리지 않으면 의심해본다.
상술된 조건을 이용한다. (quick sort가 왜 DP가 아닌지 떠올리면 더 좋다. 최적 부분 구조는 맞지만, 중복되는 부분 문제는 없다.)
피보나치 수열을 DP로 구현
피보나치 수열의 구조. (출처: 유튜브 캡쳐)
피보나치 수열이 뭔지는 생략하지 않지 않지 않겠다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
An = An-1 + An-2의 규칙을 반복하는 수열이다.
그림과 같은 방식으로 풀이하면, 중복 계산이 발생하여 지수 시간복잡도를 갖는다.
그래서 DP로 풀이하기 딱 좋은 유형이다.
f(6)을 구하기 위해, 작은 문제로 나눌 수 있다. 작은 문제를 합치면 f(6)을 구할 수 있다. (최적 부분 구조)
f(2)와 같이 작은 문제가 중복 계산되고 있다. (중복되는 부분 문제)
햐향식 Top-Down 접근
dp = [0] * 100 # 계산된 결과를 메모이제이션 하기 위한 리스트
def fibo(x):
if x == 1 or x == 2:
return 1
if dp[x] != 0: # 이미 계산된 결과는 즉시 return. 중복 계산 방지. 상수 시간 소요.
return dp[x]
dp[x] = fibo(x - 1) + fibo(x - 2) # 새로운 문제는 재귀적으로 구함.
return dp[x]
print(fibo(10)) # 55
상향식 Bottom-Up 접근
# 엥 이것도 메모이제이션 아니에요?
# 동의하는 부분.. 다만 탑다운에서 이미 계산된 결과는 즉시 반환하는 등 명시적으로 다루고 있어서 구분 짓나 보다.
dp = [0] * 100
d[1] = 1
d[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[10]) # 55
예제 1. 개미 전사
# DP인지 판단
# 최적 부분 구조가 가능한가?
# 특정 구간의 최대 조합이 있을 것이다. 그것은 구간을 확장해도 조합이 바뀌지 않을 것이다.
# 중복되는 부분 문제가 있는가?
# 특정 구간의 조합이 다음 구간에 영향을 주므로 (1칸 이상 떨어져야 함) 중복되는 문제가 있다고 보아야 한다.
# 메모이제이션 - 탑 다운으로 풀이해보자
# 배열의 크기가 1일 때는? a1
# 2일 때는? max(S1, a2)
# 3일 때는? max(S2, S1 + a3)
# 4일 때는? max(S3, S2 + a4)
# 5일 때는? max(S4, S3 + a5)
# 6일 때는? max(S5, S4 + a6)
# n일 때는? max(Sn-1, Sn-2 + an)
# S1 = arr[0]
# S2 = max(arr[1], arr[0])
# Sn = max(Sn-1, Sn-2 + an)
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 10
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])
def get_food(n):
if dp[n] != 0:
return dp[n]
dp[n] = max(dp[n - 1], dp[n - 2] + arr[n])
return dp[n]
print(get_food(n - 1))
print(dp)
예제 2. 1로 만들기
# 최적 부분 구조
# 맞다. 특정 수를 만드는 최소 연산 회수는 정해져 있다.
# 중복되는 부분 문제
# 맞다. 특정 수까지의 최소 연산 회수가 정해져 있으므로, 계산 과정에서 반복적으로 사용한다.
# 조건
# 5로 나눈다.
# 3으로 나눈다.
# 2로 나눈다.
# 1로 뺸다.
# 풀이
# 항상 큰 수로 나누는 것이 유리한가?
# 그렇지만, 순서의 차이는 있다. 16의 경우 16 -> 15 -> 3 -> 1 (3번) / 16 -> 8 -> 4 -> 2 -> 1 (4번)). 그리디처럼 풀이하는 것은 아니다.
# 반대로 1부터 dp 테이블 해당 인덱스를 구하기 위한 최소 연산 회수로 채워가는 것은 어떤가?
# [0, 1, 2, 3, 4, 5, 6, 7, ...]
# [0, 0, 1, 1, 2, 1, 2, 3, ...]
# 7을 살펴보자. 다음과 같은 방법으로 만들 수 있다.
# 6 + 1
# 6을 살펴보자.
# 5 + 1, 3 * 2, 2 * 3
# 10을 살펴보자.
# 9 + 1, 5 * 2, 2 * 5
# Sn = min(Sn-1 + 1, Sn//5 + 1, Sn//3 + 1, Sn//2 + 1)이다.
# if n이 어떤 수로 나누어 떨어지느냐에 따라 if 조건문으로 나누면 풀이할 수 있을 것이다.
# n = 1 return 1
# n = 2 return 1
# n = 3 return 1
# n = 5 return 1
# if n % 5 == 0
# min(Sn-1 + 1, Sn//5 + 1)
# elif n % 3 == 0
# min(Sn-1 + 1, Sn//3 + 1)
# elif n % 2 == 0
# min(Sn-1 + 1, Sn//2 + 1)
# else
# Sn-1 + 1
n = int(input())
dp = [0] * 30001
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[5] = 1
for i in range(4, n + 1):
dp[i] = dp[i-1] + 1
if i % 5 == 0:
dp[i] = min(dp[i], dp[i//5] + 1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
print(dp[n])
예제 3. 효율적인 화폐 구성
# 최적 부분 구조
# 맞다. 특정 값을 구성하기 위한 최소 화폐 개수는 정해져 있다.
# 중복되는 부분 문제
# 해당 구조가 여러 번 반복된다.
# 풀이
# 무조건 고액 화폐를 많이 사용하는 것이 옳은가?
# 그렇지 않다. 700을 고려해보자. 300 + 300 + ...? / 300 + 200 + 200
# 1로 만들기 문제처럼, 100부터 목표 값까지 최소 화폐 개수를 채워나가보자.
# coins = [200, 300]
# [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
# [ 0, 1, 1, 2, 2, 2, 3, 3, 3, 4]
# 쉬운 듯?
# min(Sn-300 + 1, Sn-200 + 1)
# if 조건문으로 모든 케이스를 검증하며 풀이해보자. 아니다. 조건문조차 필요가 없다.
# dp = [0] * 10001
# for coin in coins:
# dp[coin] = 1
# for i in range(min(coins), m + 1)
# for coin in coins:
# if i > coin:
# dp[i] = min(dp[i], dp[i - coin] + 1)
# -1 if dp[m] == 1 else dp[m]
n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [10001] * (m + 1)
dp[0] = 0
for i in range(n): # 화폐 단위
for j in range(coins[i], m+1): # 목표 금액
if dp[j - coins[i]] != 10001:
dp[j] = min(dp[j], dp[j-coins[i]] + 1)
if dp[m] == 10001:
print(-1)
else:
print(dp[m])
예제 4. 금광
# 최적 부분 구조
# 맞다. 전체의 문제를 한 열씩 나눠서 판단할 수 있다.
# 특정 구간 최적 경로는 전체 구간에서 봐도 그렇다.
# 중복되는 부분 문제
# 하나의 최적 경로를 구하는 문제이므로, 같은 구간이 중복되어 계산된다.
# 풀이
# 무작정 3방향 중 최대값을 선택하면 되는가?
# 안 된다. 그건 그리디이다. 이동 범위 밖에 있는 최적 경로가 존재할 수 있다.
# 전체 행에서 최대값을 선택하는 것도 불가능하다. 이동이 불가능할 수도 있으므로.
# 2차원 배열을 탐색하며 이전 3방향의 최대값을 더해주는 방식으로 배열을 갱신해야겠다.
# 현재 인덱스의 값은, 이전 3방향 값 중 최대값을 더한 값이다.
# 즉, 다음과 같다.
# dp[i][j] = dp[i - 1][j] + matrix[i][j-1]
# if i > 0:
# dp[i][j] = max(dp[i][j], dp[i-1][j-1] + matrix[i][j])
# if i + 1 < n
# dp[i][j] = max(dp[i][j], dp[i+1][j-1] + matrix[i][j])
tc = int(input())
for k in range(tc):
n, m = map(int, input().split())
arr = list(map(int, input().split()))
matrix = []
for i in range(0, len(arr), m):
matrix.append(arr[i : i + m])
dp = [[0] * m for _ in range(n)]
for i in range(n):
dp[i][0] = matrix[i][0]
for j in range(1, m):
for i in range(n):
if i == 0:
left_up = 0
else:
left_up = dp[i - 1][j - 1]
if i == n - 1:
left_down = 0
else:
left_down = dp[i + 1][j - 1]
left = dp[i][j - 1]
dp[i][j] = matrix[i][j] + max(left_up, left, left_down) # 2차원 탐색 문제는 이렇게
result = 0
for i in range(n):
result = max(result, dp[i][m-1])
print(result)
예제 5. 병사 배치하기
# 최적 부분 구조
# 나눠서 풀 수 있는가?
# 연속되는 구간 별로 나눠서 특정 병사를 제외했을 때, 그것이 최선이 되는가?
# 직관적으로 생각나지는 않지만, 딱히 반례가 떠오르는 것도 아니다.
# 중복되는 부분 문제
# 하나의 최적 배열을 구하는 것이므로, 부분 문제가 중복된다고 할 수 있다.
# 풀이
# 최장 연속 부분 수열? 그런 유형인 듯하다.
# 내림차순이 성립하지 않는 모든 수만 제거하면 되는가? 그럼 문제가 발생한다.
# [15 11 2 10 9] 이런 배열이 있다면 내림차순이 성립함에도 불구하고, 2를 제거하는 것이 옳다.
# [9 8 7 6 5 4 3 2 10 5 9 8 7] 이런 경우에는 4 3 2 5를 제거해야 한다.
n = int(input())
arr = list(map(int, input().split()))
arr.reverse()
dp = [1] * n
for i in range(1, n):
for j in range(0, i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
위 문제는 가장 긴 연속하는 부분 수열(Longest Increasing Subsequence, LIS) 유형이다.
LIS의 점화식은 다음과 같다.
# D[i] = array[i]를 마지막 원소로 포함하는, 부분 수열의 최대 길이
모든 0 ≤ j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4
시간 복잡도
매 단계에서 탐색 범위를 절반으로 줄여나가므로 탐색 횟수는 로그 스케일로 증가한다.
따라서 평균, 최악의 상황에서 O(logN)의 시간복잡도를 갖는다.
공간 복잡도
반복문 구현: O(1). 추가적인 저장 공간이 필요하지 않다.
재귀적 구현: O(logN). 재귀 호출로 인한 스택이 필요하다.
예제 1: 떡볶이 떡 만들기
n, m = map(int, input().split())
heights = list(map(int, input().split()))
result = 0
start = 0
end = max(heights)
while start <= end:
total = 0
mid = (start + end) // 2
for hei in heights: # 기준치 보다 자르려는 떡의 긴 경우에만, 차이만큼 total에 더한다.
if hei > mid:
total += hei - mid
if total < m: # 조건을 만족하지 못 하면, 기준치를 줄여, 남는 떡의 길이를 늘린다.
end = mid - 1
else: # 조건을 만족한 경우 result를 갱신한다. 기준치를 줄이고, 남는 떡의 길이를 늘려 최적값을 찾는다.
result = mid
start = mid + 1
print(result)
예제 2-1: 특정 수 개수: 일반
def count_by_value(array, x): # 정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
n = len(array) # 데이터의 개수
first_idx = first(array, x, 0, n-1) # x가 처음 등장한 인덱스
if first_idx == None: # 수열에 x가 존재하지 않는 경우
return 0 # 값이 X인 원소의 개수는 0개이므로 0 반환
last_idx = last(array, x, 0, n-1) # x가 마지막으로 등장한 인덱스
return last_idx - first_idx + 1
def first(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# target == mid인 동시에, mid - 1은 target보다 작은 경우
# 조건을 만족하는 가장 왼쪽에 있는 인덱스인 경우
if target == array[mid] and (mid == 0 or target > array[mid - 1]):
return mid
elif target <= array[mid]:
return first(array, target, start, mid - 1)
else:
return first(array, target, mid + 1, end)
def last(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target and (mid == 0 or array[mid + 1] > target):
return mid
elif array[mid] > target:
return last(array, target, start, mid - 1)
else:
return last(array, target, mid + 1, end)
n, x = map(int, input().split())
array = list(map(int, input().split()))
count = count_by_value(array, x)
print(count if count > 0 else -1)
예제 2-2: 특정 수 개수: 라이브러리
from bisect import bisect_left, bisect_right
def get_count_by_bisect(array, x):
left = bisect_left(array, x)
right = bisect_right(array, x)
return right - left
n, x = map(int, input().split())
array = list(map(int, input().split()))
count = get_count_by_bisect(array, x)
if count == 0:
print(-1)
else:
print(count)
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘.
각 탐색마다 결정될 자리를 먼저 선택하고, 자리에 올 값을 찾는 과정이라고 생각하면 좋다.
구현
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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] # 탐색이 끝나면 스왑
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
시간 복잡도
N + (N - 1) + (N - 2) + ... + 2 # 마지막 원소는 이미 확정되었으므로 정렬을 하지 않아도 괜찮다.
데이터의 개수가 N개라고 했을 때,
첫 번째 탐색에서 비교횟수: 1 ... N-1 => N-1
두 번째 탐색에서 비교횟수: 2 ... N-1 => N-2
...
(N-1) + (N-2) + .... + 2 => N(N-1) / 2 - 1
시간복잡도는 O(N^2)이다.
최선, 평균, 최악의 경우 모두 같다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(N)이다.
특징
제자리 정렬 (in-place sorting)
불안정 정렬 (unstable sorting)
삽입 정렬 insertion sort
삽입 정렬 (출처: GimunLee)
요약
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 알고리즘.
선택 정렬에 비해 구현 난도는 높지만, 일반적으로 더 효율적.
구현
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)): # 1번째 원소는 결정된 것으로 간주하고, 2번째 원소부터 정렬
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 # 작지 않을 경우 해당 자리에서 멈춤
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
시간 복잡도
N + (N - 1) + (N - 2) + ... + 1 # 마지막 원소까지 정렬해야 함
최악, 평균의 경우: 선택 정렬과 마찬가지로 O(N^2)
최선의 경우: O(N)
이미 정렬이 되어 있을 경우, 한 번씩만 비교한다.
즉, 상수 시간이 소요된다.
전체 배열 탐색 + 탐색마다 한 번씩 비교만 하면 되므로 O(N)
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해 수행되므로,O(1)이다.
추가적인 메모리가 필요하지 않다.
특징
대부분의 원소가 정렬되어 있는 경우, 매우 효율적이다.
제자리 정렬 (in-place sorting)
안정 정렬 (stable sorting)
퀵 정렬 quick sort
주황색이 pivot (출처: GimunLee)
요약
기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.
분할 정복(divide and conquer) 방법을 사용한다.
병합 정렬과 더불어 대부분 언어의 기본 정렬 라이브러리의 근간이다.
구현1: 일반적인 방식
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 첫 번째 원소를 피봇으로
left = start + 1 # 왼쪽 포인터의 인덱스
right = end # 오른쪽 포인터의 인덱스
while left <= right:
while left <= end and array[left] <= array[pivot]: # 왼쪽 출발. pivot보다 큰 값을 찾을 때까지.
left += 1
while right > start and array[right] >= array[pivot]: # 오른쪽 출발. 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) # 분할divide 이후 각각 재귀적으로 정렬
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
print(array)
구현2: pythonic한 방식
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <= 1: # 리스트 원소가 1개라면 재귀 끝 !
return array
pivot = array[0] # 첫 번째 원소를 피봇
tail = array[1:] # 피봇을 제외하고 나머지 배열
left_side = [x for x in tail if x <= pivot] # filter를 사용하듯, pivot 보다 작은 원소만
right_side = [x for x in tail if x > pivot] # pivot 보다 큰 원소만
# 재귀적으로 반복하면, left_side에는 min이, right_side에는 max만 남고 return을 시작한다.
# 차곡차곡 min + 1, max - 1 -> min + 2, max - 2 ... 쌓이고, 정렬이 완성된다.
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array)
시간 복잡도
출처: gyoogle
데이터의 크기가 N이라면,
각 순환 호출 단계의 비교 연산: O(N)
총 호출의 횟수: O(logN)
따라서 평균, 최선의 시간복잡도는 O(NlogN)이다.
출처: gyoogle
최악의 경우는 O(N^2)이다.
정렬하고자 하는 배열이 이미 오름차순 혹은 내림차순으로 정렬이 되어있는 경우,
각 호출 단계 비교 횟수 O(N), 총 호출 횟수 O(N)이 되어 O(N^2)이다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해 수행된다.
재귀 호출 깊이 만큼 추가적인 공간이 필요하므로 O(logN)이다.
최악의 경우 O(N)이다.
특징
불안정 정렬
불균형 분할 (분할이 항상 절반으로 뚝 나뉘는 것이 아니다. 최악의 경우 시간 복잡도의 비효율을 초래한다.)
계수 정렬 Counting sort
반복문을 활용한 방식 (출처: manishsundriyal)누적합을 활용한 방식 (출처: spagnuolocarmine)
요약
비교하지 않는 정렬이다.
데이터의 값 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
위 조건에서는 매우 빠르게 동작한다.
구현1: 카운트한 값만큼 반복하는 방식
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
result = []
count = [0] * (max(array) + 1) # 값의 모든 범위를 포함하는 카운터 배열. 0으로 초기화
for i in range(len(array)):
count[array[i]] += 1 # array 원소의 개수를 센다.
for i in range(len(count)):
for j in range(count[i]): # 현재 원소가 count된 수만큼 반복해서 추가한다.
result.append(i)
print(result) # [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]
구현2: 누적합을 사용하는 방식 (다소 직관적이지 않다)
def counting_sort(arr):
# 1단계: 입력 배열에서 최대값 찾기
max_val = max(arr)
count = [0] * (max_val + 1) # 각 숫자의 등장 횟수를 저장할 배열 초기화
# 각 숫자의 등장 횟수 세기
for num in arr:
count[num] += 1
# 2단계: 누적합 계산
for i in range(1, len(count)):
count[i] += count[i - 1]
# 3단계: 정렬된 배열을 생성하기 위한 임시 배열
output = [0] * len(arr)
# 원본 배열을 거꾸로 순회하며 정렬된 위치에 숫자 배치
for num in reversed(arr):
idx = count[num] - 1 # 정렬된 배열에서의 위치 계산. 누적합에서 1을 빼야 0부터 시작하는 인덱스 반영.
output[idx] = num
count[num] -= 1 # 다음 같은 숫자가 올 위치를 위해 누적합 감소
return output
# 예제 배열
arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 4, 5, 7]
시간 복잡도
데이터의 개수가 N / 정수의 최대값이 K라면,
카운터 배열의 초기화: O(N)
카운터 배열의 누적합을 만드는 과정: O(K)
O(N + K)의 시간 복잡도를 갖는다.
O(N)이 아닌 이유는 [1, 999999] 배열을 정렬할 경우, N = 2임에도 K의 크기만큼 누적합을 계산해야 하기 때문에.
공간 복잡도
누적합 배열: O(K)
정렬된 배열: O(N) 따라서 추가적으로 필요한 공간은 O(N + K)이다.
비교 기반 알고리즘과 다르게 동작하기 때문에, 정렬된 배열을 위한 공간 O(N)이 필요하다는 것을 기억하자.
