1. 다익스트라, 최단거리를 탐색하게 해주다 강남역의 교통 체증 여부를 예측했으니, 이제 내비게이션으로 최적의 경로를 찾을 일만 남았습니다. "강남역으로 안내해줘"라는 명령에 따라 내비게이션은 과연 어떻게 강남역까지 최적의 경로를 찾을 수 있을까요? 최단 경로를 찾는 알고리즘 중에서 가장 유명한 것은 아마 다익스트라 알고리즘(Dijkstra's Algorithm)일 것입니다. 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 대학원생이던 1956년 여자친구와 함께 커피숍에 갔다가 20분만에 고안해서 만든 알고리즘으로 알려져 있습니다. 커피숍에서 냅킨에 적을 수 있을 만큼, 단순한 법칙이 가장 뛰어나다는 오컴의 면도날을 증명하는 대표적인 알고리즘이기도 합니다. 물론 당시에 그는 이렇게 단순한 경로 계획 알고..
1. 가중치에 음수가 포함된 경우 모든 간선의 비용이 양수일때는 다익스트라 알고리즘을 사용하면 특정 노드에서 다른 노드까지 최단 거리로 가는 비용을 효과적으로 구해준다 다음에서 1번 노드에서 다른 노드까지 가는 최단 비용은 얼마일까? 다익스트라 알고리즘을 이용해서 구하면 최단거리를 간단히 구할 수 있다 import heapq INF = 10000000000000000000000 dist = [INF]*7 graph = [[],[(2,6),(3,2)],[(3,2),(4,2)],[(5,1)],[(6,2)],[(2,1),(4,3),(6,4)],[]] q = [] heapq.heappush(q,(0,1)) dist[1] = 0 while q: d,u = heapq.heappop(q) if dist[u] < d:..
1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..
1. 실제 최단 경로 역추적 지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다 어떻게 하면 구할 수 있을까? 결론부터 말하자면 경로를 역추적해서 구한다 어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고, 다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때, u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때 "b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다 모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고, G와 가장 가까운 정점이 F이고 F와 가장 가까운 정점이 E이고, ... C와 가장 가까운 정점이 ..
1. 개요 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"에 사용할 수 있는 알고리즘이다. -------------------------------------------------------------------------------------------------------- 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하면서 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘은 또한 단계마다 "거쳐 가는 노드"를 기준으로 ..
1. 문제 1249. [S/W 문제해결 응용] 4일차 - 보급로 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2차원 배열에서 (0,0)에서 (n-1,n-1)로 가는데, 경로에 쓰이는 숫자들의 합이 최소가 되도록 갈때, 그 최솟값을 구하는 문제 2. 풀이 2차원 배열에서도 다익스트라 알고리즘을 사용할 수 있을까? 그대로 사용하면 된다 2차원 배열을 하나의 그래프로 바꿀려고 시도한 적이 있었는데 그럴 필요도 없다 다익스트라 알고리즘이 distance 배열을 무한으로 초기화하고, 출발 위치는 0으로 시작한 다음에 현재 위치에서 인접한 곳으로 이동을 해보고, 거리가 최소가 되면 di..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
