스파르타코딩클럽 강의
최단경로 & 다익스트라 알고리즘
최단경로:
- 그래프로 표현. 각 지점은 노드, 도로는 간선.
- 다익스트라, 플로이드-워셜.
- 지도 어플 등에서 많이 쓰임.
다익스트라 알고리즘
1. 각 노드에 써있는 숫자는 출발지에서부터 드는 최소비용. (일단은 모두 무한대)
2. 인접노드를 살폈을 때 t 10, y 5의 비용으로 가능.
3. t와 y의 최소비용을 각각 10과 5로 업데이트 후 현재 노드를 방문처리.
3. 나머지 방문 안 한 모든 노드에 대해서 가장 비용이 적은 노드를 골라서 반복 진행.
구현1
INF = int(1e9)
def dijkstra_naive(graph, start):
def get_smallest_node():
min_value = INF
idx = 0
for i in range(1, N):
if dist[i] < min_value and not visited[i]:
min_value = dist[i]
idx = i
return idx
N = len(graph)
visited = [False] * N
dist = [INF] * N
visited[start] = True
dist[start] = 0
for adj, d in graph[start]:
dist[adj] = d
# N개의 노드 중 첫 노드는 이미 방문했으므로,
# N-1번 수행하면 된다.
for _ in range(N - 1):
# 가장 가깝고 방문 안한 녀석을 고르고,
cur = get_smallest_node()
visited[cur] = True
# 최단거리를 비교, 수정한다.
for adj, d in graph[cur]:
cost = dist[cur] + d
if cost < dist[adj]:
dist[adj] = cost
return dist구현2
import heapq
def dijkstra_pq(graph, start):
N = len(graph)
dist = [INF] * N
q = []
# 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
# 첫 번째 방문 누적 비용은 0이다.
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
# 누적 비용이 가장 작은 녀석을 꺼낸다.
acc, cur = heapq.heappop(q)
# 이미 답이 될 가망이 없다.
if dist[cur] < acc:
continue
# 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
for adj, d in graph[cur]:
cost = acc + d
if cost < dist[adj]:
dist[adj] = cost
heapq.heappush(q, (cost, adj))
return dist구현1 vs. 구현2
구현1(이중 for문): O(V^2)
구현2(우선순위큐) O(ElogV)
예제
// TODO
페어 프로그래밍
문제풀이
1. 최대공약수와 최소공배수
4일차 문제들 중 최소공배수 문제 풀이를 그대로 가져와서 조금 수정만 해줬다.
풀이
- a나 b 중 한 수가 다른 수의 배수일 경우: 최대공약수는 큰 수, 최소공배수는 작은 수
- a와 b의 최소공배수를 구해서 출력 (최소공배수가 없으면 1)
전체 코드
a, b = map(int, input().split())
if b % a == 0:
print(a, b, sep='\n')
elif a % b == 0:
print(b, a, sep='\n')
else:
c = b if b < a else a
d = 1
for j in range(2, c+1):
if a % j == 0 and b % j == 0:
d = j
print(d, (a*b) // d, sep='\n')2. 파도반 수열
수열의 규칙을 알아내면 쉬운 문제다.
풀이
- P[5]부터는 (이전 P의 값)과 (5개 전 P의 값)의 합
- 따라서 P(N)의 최대 값인 100개만큼 배열에 0으로 초기화.
- 4번째 인덱스까지는 1, 1, 1, 2, 2 할당
- 5번째 인덱스부터 끝까지 1번 연산을 반복
- 마지막 인덱스에 저장된 값 출력
전체 코드
T = int(input())
dp = [1, 1, 1, 2, 2] + [0] * 95
for i in range(T):
n = int(input())
for j in range(5, n):
dp[j] = dp[j-5] + dp[j-1]
print(dp[n-1])3. RGB거리
처음에 문제 이해를 잘못 해서 한참 헤맸다.
풀이
- 모든 집의 색을 dp 리스트에 추가
- 1번 집부터 마지막 집까지 r, g, b을 시작점으로 두고 이전 집의 색과 비교하여 최솟값 누적:
2-1. i번 집의 [0](r)에 [1](g), [2](b) 중 최솟값 누적
2-2. i번 집의 [1](g)에 [0](r), [2](b) 중 최솟값 누적
2-3. i번 집의 [2](b)에 [0](r), [1](g) 중 최솟값 누적 - 마지막 집의 [0](r), [1](g), [2](b) 중 최솟값 출력
전체 코드
N = int(input())
dp = []
for i in range(N):
dp.append(list(map(int, input().split())))
for i in range(1, len(dp)):
dp[i][0] += min(dp[i-1][1], dp[i-1][2])
dp[i][1] += min(dp[i-1][0], dp[i-1][2])
dp[i][2] += min(dp[i-1][0], dp[i-1][1])
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))
4. 정수 삼각형
이전 문제랑 같은 원리로 풀었고 조건이 몇 가지 추가가 되었다.
풀이
- 1개의 입력값 받기(첫 줄(0번째)에는 값이 하나, 각 줄의 길이는 새로 입력받을 때마다 1씩 증가)
- 1번째 줄의 0번째와 1번째에는 0번째 줄의 0번째 값 저장
- 2번째 줄부터 마지막 줄까지 반복:
3-1. 줄의 0번째 요소에는 전 줄 0번째 값 누적
3-2. 줄의 마지막 요소에는 전 줄 마지막 값 누적
3-3. 그 외에는 전 줄의 같은 인덱스와 전 인덱스 중 최댓값 누적 - 마지막 줄에서 최댓값 출력
전체 코드
n = int(input())
triangle = []
triangle.append(list(map(int, input().split())))
if n >= 2:
triangle.append(list(map(int, input().split())))
triangle[1][0] += triangle[0][0]
triangle[1][1] += triangle[0][0]
for i in range(2, n):
triangle.append(list(map(int, input().split())))
for j in range(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][0]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][-1]
else:
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
print(max(triangle[-1]))
n = int(input())
prev = [-1] * n
curr = [-1] * n
curr = list(map(int, input().split()))
if n >= 2:
prev = curr
curr = list(map(int, input().split()))
curr[0] += prev[0]
curr[1] += prev[0]
for i in range(2, n):
prev = curr
curr = list(map(int, input().split()))
for j in range(i+1):
if j == 0:
curr[j] += prev[0]
elif j == i:
curr[j] += prev[i-1]
else:
curr[j] += max(prev[j-1], prev[j])
print(max(curr))
COYG🔴⚪