정렬된 배열 내에서 중간점 위치 데이터와 비교하며 반복적으로 절반씩 좁혀가며 찾는다
O(log n)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif target < array[mid]:
end = mid - 1
else:
start = mid + 1
return -1
주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘
최적화 문제(최댓값 x = ?) -> 결정문제(x일 경우 최댓값?)로 바꾸어 풀 수 있다.
# 최적화문제: 24시간을 7시간마다 배고파지는 사람이 최소 몇끼니를 먹어야 배부르게 지낼수있는가?
# 결정문제: 7시간마다 배고파지는 사람이 x끼니를 먹으면 24시간을 배부르게 지낼 수 있다.
def parametricSearch(start, end) {
mid = (start + end) / 2
currentValue = mid
while (start <= end):
if (24 / mid) > 7:
start = mid + 0.1
elif (24 / mid) < 7:
end = mid - 0.1
else
return currentValue
return mid
}
큰 문제를 작은 문제로 나눌 수 있는 경우 동일문제를 중복되지 않게 계산하는 방법
Bottom up(반복문), Top down(재귀) 방식
메모이제이션: 계산된 결과들을 메모하는 기법 (캐싱)
O(n)
d = [0] * 100
def pibo(x):
d[1] = 1
d[2] = 1
for i in range(3, x+1):
d[i] = d[i-1] + d[i-2]
시작 노드로부터 각 노드까지의 최단거리 알고리즘 (음의 간선이 없는 경우)
반복적으로 최소 최단거리의 노드를 선택하며 테이블을 갱신 (heapq 사용)
O(E log V)
V
: 노드수, E
: 간선수visited
: [False] * (n+1)distance
: [INF] * (n+1)def dijkstra(graph, startNode):
distance = [INF]*(len(graph)+1)
distance[startNode] = 0
q = []
# q: (distance, node), distance 가 적은 node 순으로 정렬된다
heapq.heappush(q, (0, startNode))
while q:
currentDistance, currentNode = heapq.heappop(q)
# currentNode 의 distance 가 갱신된적이 있는 경우 무시
if distance[currentNode] < currentDistance:
continue
# currentNode 의 인접노드들 확인
for node in graph[currentNode]:
nodeNum = node[0]
nodeCost = node[1]
newDistance = currentDistance + nodeCost
if newDistance < distance[nodeNum]:
distance[nodeNum] = newDistance
heapq.heappush(q, (newDistance, nodeNum))
return distance
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
startNode = int(input())
graph = [[] for i in range(n+1)]
for _ in range(m):
from, to, cost = map(int, input().split())
graph[from].append((to, cost))
distance = dijkstra(graph, startNode)
for i in range(1, n+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
여러개의 from, to 노드간 최단거리 구하기 알고리즘
점화식: AtoB = min(AtoB, AtoK + KtoB)
k, a, b 순차적으로 3중 for 구조
O(n^3)
def floydWarshall(graph):
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])
graph[b][a] = graph[a][b]
import sys
input = sys.stdin.readline()
INF = int(1e9)
n, m = map(int, input().split())
graph = [[]]*(n+1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
graph[b][a] = 0
for _ in range(m):
a, b, cost = map(int, input().split())
graph[a][b] = cost
graph[b][a] = cost
floydWarshall(graph)
for a in range(1, n+1):
for b in range(1, n+1):
val = graph[a][b] if graph[a][b] != INF else "INF"
print(val, end=" ")
print()
공통 원소가 없는 집합이 필요한 경우
하나의 집합으로 합치는 union
과 원소가 속한 집합을 알려주는 find
연산이 필요
union
의 경우 작은 노드값
이 집합의 값이 된다.
# 노드값과 집합값이 같을때까지 재귀적으로 호출
def findParent(parents, x):
if parents[x] != x:
parents[x] = findParent(parents, parants[x])
return parents[x]
def unionParent(parents, a, b):
setA = findParent(parents, a)
setB = findParent(parents, b)
if setA < setB:
parents[b] = setA
else:
parents[a] = setB
v, e = map(int, input().split())
parents = [i for i in range(v+1)]
for _ in range(e):
a, b = map(int, input().split())
unionParent(parents, a, b)
for i in range(1, v+1):
print(findParent(parents, i), end=" ")
print()
유향
그래프: DFS
알고리즘
무향
그래프: 서로소
집합 알고리즘
# 무향그래프에서 사이클 판별
v, e = map(int, input().split())
parents = [i for i in range(v+1)]
cycle = False
for i in range(e):
a, b = map(int, input().split())
if findParent(parents, a) == findParent(parents, b):
cycle = True
break
else:
unionParent(parents, a, b)
if cycle:
print("사이클 발생")
else:
print("사이클 비발생")
경로를 최소한의 비용으로 연결하는 알고리즘
모든 간선에 대해 비용값 기준 정렬, 사이클이 발생하지 않는 간선부터 집합에 포함
무향 그래프이므로 find, union 을 통해 사이클 여부 판별 후 간선비용 총합
O(E log E)
v, e = map(int, input().split())
parents = [i for i in range(v+1)]
edges = [(a, b, cost) for _ in range(e) a, b, cost = map(int, iniput().split())]
result = 0
edges.sort()
for edge in edges:
cost, a, b = edge
if findParent(parents, a) != findParent(parents, b):
unionParent(parents, a, b)
result += cost
print(result)
우선순위(선후관계)에 따라 방향성에 거스르지 않도록 순서대로 나열
진입차수 테이블과 deque가 필요
deque가 빌때까지 각 노드부터 출발하는 간선을 제거하며 진입차수가 0인 노드를 삽입
O(V+E)
def topologySort(graph, indegree):
result = []
q = deque()
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
while q:
node = q.popleft()
result.append(node)
for i in graph[node]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
return result
from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v+1)
graph = [[] for i in range(v+1)]
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
sorted = topologySort(graph, indegree)
for n in result:
print(n, end=" ")