동빈나 님의 이코테 2021 강의 몰아보기 를 보면서 공부한 내용을 정리하고 있습니다. 더 자세한 내용은 이것이 취업을 위한 코딩 테스트다 with 파이썬 을 참고해주세요 학습 도구로는 리플렛 을 사용하고 있고 원본 소스코드는 동빈님의 Github 에서 확인할 수 있고 스스로 공부한 소스코드는 Github 에서 확인할 수 있습니다.최단경로문제
•
가장 짧은 경로를 찾는 알고리즘을 의미한다.
•
다양한 문제상황
◦
한 지점 -> 다른 한 지점까지의 최단 경로
◦
한 지점 -> 다른 모든 지점까지의 최단 경로
◦
모든 지점에서 다른 모든 지점까지의 최단 경로
•
각 지점은 그래프에서 노드로 표현하고
•
지점 간 연결된 도로는 그래프에서 간선으로 표현한다.
다익스트라 최단경로 알고리즘
•
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
•
다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작함
◦
현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.
◦
현실 세계의 길찾기 문제에서 사용될 수 있다!
•
다익스트라 최단경로 알고리즘은 그리디 알고리즘으로 분류된다.
◦
매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
◦
기본적으로 길찾기 문제는 다익스트라 알고리즘을 이용하는 셈이다.
동작과정
1.
출발 노드를 설정한다.
2.
최단 거리 테이블을 초기화한다.
•
자기 자신은 0으로 초기화
3.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
•
그리디 알고리즘의 유형으로 분류한다.
4.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5.
위 과정에서 3번과 4번을 반복한다.
동작과정 살펴보기
•
초기 상태
◦
그래프를 준비하고 출발노드를 설정한다.
◦
거리가 짧은 노드인 1을 선택
◦
나머지는 무한으로 초기화
•
가장 거리가 짧은 1번 노드부터 방문하지 않은 노드까지의 최단거리값을 계산해본다.
•
현재값과 1번노드를 거쳐서 갈때의 최소값을 비교해서 갱신할지 말지 여부를 정한다.
◦
2 : 무한대 > 0+2 = 갱신!
◦
3 : 무한대 > 0+5 = 갱신!
◦
4 : 무한대 > 0+1 = 갱신!
•
같은 방법으로 현재 노드 중에서 가장 최단 거리가 짧은 4를 선택한다.
•
4번을 거쳐서 가는 3번과 5번 노드의 최단거리값을 비교한다.
◦
3번 : 5 > 1+3 = 갱신!
◦
5번 : 무한 > 1+1 = 갱신!
•
3번과 5번 모두 1->4를 거쳐서 가는 값이 최단경로에 가까우므로 값을 갱신한다.
•
현재 노드들 중 가장 거리가 짧은 노드는 2와 5이다.
◦
어느 노드를 선택해도 상관 없지만, 일반적으로 수가 작은 노드를 선택한다.
◦
2번을 선택한다.
•
2번노드를 거쳐 갈 수 있는 노드는 3번과 4번이다.
◦
3번 : 4 < 2+3 -> 갱신안함!
◦
4번 : 1 < 2+2 -> 갱신안함!
•
이제 가장 짧은 노드는 5이다.
•
5에서는 3번과 6번을 갈 수 있다.
◦
3번 : 4 > 1+1+1 = 갱신!
◦
6번 : 무한 > 1+1+2 = 갱신!
•
3번과 6번 모두 갱신된다.
•
남아있는 3번을 선택한다.
•
3번에서는 2번과 6번을 갈 수 있는데 두 경우 모두 계산결과 이미 최단거리값을 가지고 있다. 따라서 갱신되지 않는다.
•
마지막 노드는 나아갈 수 있는 노드가 없기 때문에 처리하지 않아도 된다.
특징
•
그리디 알고리즘 : 매 상황에서 장문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
•
단계를 거치면서 한번 처리된 노드의 최단 거리는 고정되어 더이상 바뀌지 않는다.
◦
한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
•
다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단거리 정보가 저장된다.
◦
완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.
간단한 구현방법
•
단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해서 매 단계마다 1차원 테이블의 모든 원소를 확인(순차탐색) 합니다.
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [ [] for i in range(n+1) ]
visited = [False] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
a, b, c = map(int, input().split())
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 visited[start] = True for i in graph[start]:
distance[i[0]] = i[1]
for j in range(n-1):
now = get_smallest_node()
visited[now] = True for k in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start);for i in range(1, n+1):
if distance[i] == INF:
print('INFINITY')
else:
print(distance[i])
Python
복사
다익스트라 알고리즘의 성능분석
•
총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다. (여기서 V는 ㅌ)
•
전체 시간 복잡도는 O(V^2)이 된다.
•
일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 해결할 수 있다.
◦
5000 * 5000 = 25,000,000
◦
python 에서 1초당 연산횟수 평균 : 20,000,000
◦
하지만 노드의 개수가 10,000개를 넘어가는 문제라면 어떻게 해야할까?
우선순위 큐 자료구조
•
우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
•
예를 들어서 여러개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야하는 경우에 우선순위 큐를 이용할 수 있다.
◦
python, C++, Java 를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.
◦
자료구조 : 추출되는 데이터
◦
stack : 가장 나중에 삽입된 데이터
◦
queue : 가장 먼저 삽입된 데이터
◦
priority queue : 가장 우선순위가 높은 데이터
▪
heap
힙 Heap
•
우선순위 큐를 구현하기 위해서 사용하는 자료구조 중 하나이다.
•
최소 힙과 최대 힙이 있다.
•
다익스트라 최단경로 알고리즘을 포함해서 다양한 알고리즘에서 사용된다.
•
구현방식
◦
리스트
▪
삽입시간 : O(1)
▪
삭제시간 : O(N)
◦
힙 :
▪
삽입시간 : O(logN)
▪
삭제시간 : O(logN)
# 최소 힙import heapq
def heapsort(iterable):
h = []
result = []
for i in iterable:
heapq.heappush(h, i)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
array = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
result = heapsort(array)
print(result)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Python
복사
# 최대 힙import heapq
def max_heap(iterable):
h = []
result = []
for i in iterable:
heapq.heappush(h, -i)
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result
array = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
result = max_heap(array)
print(result)
# [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Python
복사
다익스트라 알고리즘의 개선된 구현방법 (feat. heap)
•
단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해서 힙(heap) 자료구조를 이용함
•
다익스트라 알고리즘이 동작하는 기본 원리는 동일
◦
현재 가장 가까운 노드를 저장해놓기 위해서 힙 자료구조를 추가적으로 이용한다.
◦
현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
•
java
◦
priority queue library 이용하기
◦
offer(), poll()
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
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))
distance[start] = 0 while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print('INFINITY')
else:
print(distance[i])
Python
복사
개선된 구현방법의 성능분석
•
힙 자료구조를 이용하는 다 익스트라 알고리즘의 시간 복잡도는 O(ElogV)
•
노드를 하나씩 꺼내 검사하는 반복문은 노드 개수 V이상의 횟수로는 처리되지 않는다.
◦
결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
•
직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사함
◦
시간 복잡도를 O(ElogV) 로 판단할 수 있다.
◦
중복 간선을 포함하지 않는 경우에 이를 O(ElogV) 로 정리할 수 있다.
▪
O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)
플로이드 워셜 알고리즘 개요
•
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다
•
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
◦
다만 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
•
플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장함
•
플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.
•
각 단계마다 특정한 노드 K를 거쳐 가는 경우를 확인한다.
◦
a->b로 가는 최단 거리보다 a->k->b 가 더 짧은지 검사한다.
플로이드 워셜 알고리즘 동작과정 살펴보기
•
현재 1번 노드를 거쳐가는 경우를 고려하기에 1번행, 1번열과 자기 자신으로 향하는 케이스들은 모두 갱신대상에서 제외된다.
•
2번, 3번, 4번의 경우를 모두 같은 방식으로 고려한다.
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에게 가는 비용은 0으로 초기화for a in range(1, n+1):
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
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()
Python
복사
플로이드 워셜 알고리즘 성능 분석
•
노드 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행
◦
각 단계마다 O(N^2) 의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
•
따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)
◦
노드의 개수가 적을때에 주로 사용하고 (500개 이하)
◦
노드 개수가 많을 때는 다익스트라 알고리즘을 사용한다.
전보 문제
문제
•
어떤 나라에 N개의 도시가 있음. 도시 간에는 통로로 연결되어있어서 메시지를 보내고 받을 수 있음
•
어느날 C도시에서 위급상황이 발생했다. 도시 C의 위급사항을 최대한 많은 도시에 알리고자 한다.
•
이 도시에서 출발하여 각 도시 사이에 설치된 경로를 거쳐 최대한 많이 퍼져나가도록 한다.
•
이때 도시 C에서 보낸 메시지를 받게 되는 도시는 총 몇 개이며 모든 도시들이 메시지를 받는 데 걸리는 시간은 얼마인지 구하라!
•
입력조건
◦
첫째줄
▪
도시 개수 N (1이상 30,000 이하)
▪
통로개수 M (1이상 200,000 이하)
▪
메시지 보내고자 하는 도시 C (1이상 N이하)
◦
둘째줄 ~ M+1
▪
X, Y, Z 공백으로 나뉘어 입력됨
▪
각각 출발도시, 도착도시, 메시지가 전달되는 시간
•
출력조건
◦
도시 C의 메시지를 받는 총 도시의 개수
◦
총 걸리는 시간을 공백으로 구분하여 출력하도록 함
해결방법
•
한 도시에서 다른 도시까지의 최단 거리 문제
•
N, M의 범위가 꽤 크므로 우선순위큐 활용한 다익스트라 알고리즘으로 구현을 해야한다!
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m, c = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0 while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(c)
print(distance)
total_num_of_cities = 0max_distance = 0for i in distance:
if i == INF:
continue total_num_of_cities += 1 max_distance = max(max_distance, i)
# 출발지인 C를 제외하고 출력print(total_num_of_cities -1, max_distance)
# 3 2 1# 1 2 4# 1 3 2# distance = [1000000000, 0, 4, 2]# 2 4
Python
복사
미래도시 문제
문제
•
미래도시에는 1번부터 N번까지의 회사가 있다.
•
특정 회사끼리는 서로 도로를 통해서 연결되어있고 연결된 두 회사는 양방향으로 이동이 가능하다.
•
도시 간의 거리는 1이다.
•
판매원 A씨는 1번회사에 있으며 X번 회사에 방문해 물건을 판매하고자 한다.
•
가는 길에 소개팅 상대를 만나기 위하여 K번 회사를 들렀다가 가려고 한다. (1 -> K -> X)
•
판매원 A씨가 가능한 한 빠르게 이동하고자 할 때, 이동하게 되는 최소 시간을 계산해라!
•
입력조건
◦
첫째줄
▪
N, M 공백 구분 (N과 M은 1이상 100이하)
◦
둘째줄 ~ M+1
▪
연결된 두 회사의 정보가 공백으로 구분되어 나열됨
◦
M+2 째 줄
▪
X 와 K가 공백으로 구분되어 나열됨
•
출력조건
◦
최소 이동시간을 출력한다.
◦
도달할 수 없다면 -1 출력
해결
•
N이 최대 100이하이므로 플로이드 워셜 알고리즘을 이용하여 효율적으로 계산할 수 있다.
•
플로이드 알고리즘 수행 후 1K 최단거리 + KX 까지의 최단거리 출력하면 정답인정!
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (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] = 0for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = 1 graph[b][a] = 1x, k = map(int, input().split())
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])
distance = graph[1][k] + graph[k][x]
if distance == INF:
print(-1)
else:
print(distance)
# 5 7# 1 2# 1 3# 1 4# 2 4# 3 4# 3 5# 4 5# 4 5# 3
Python
복사