알고리즘

[정의] 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 기본적으로 사이클이 발생하는 경우는 고려하지 않는다. 진입 차수라는 개념에 대해서 알아야할 필요성이 있다. 진입 차수란 특정한 노드로 들어오는 간선의 갯수를 의미한다. 경제학원론은 선수 과목이 없다. ( 진입 차수가 0 ) 경제수학은 1 개의 선수 과목을 가지고 있다. ( 진입 차수가 1 ) 중급 미시 경제학은 두 개의 선수 과목을 가지고 있다. ( 진입 차수가 2 ) 다음을 위상 정렬 하게 되면 ' 경제 학원론 -> 경제 수학 -> 중급 미시 경제학 ' 이 될 것이다. [위상 정렬] 마치 BFS 같이 하면 된다. 노드 1 2 3 4 5 6 7 진입 차수 0 1 1 2 1 2 1 다음의 그래프에서 먼저 진입차수가 0인..

[신장 트리] 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라고 한다. 아래는 원래의 그래프(위)에 대한 부분 그래프(아래), 신장 트리의 예 이다. [크루스칼 알고리즘] 그래프의 간선에 비용이 적혀있다고 하자. 신장 트리의 모든 간선에 대하여, 비용이 합이 가장 적겠끔 하는 신장 트리를 구하는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘이 있다. 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선 3, 4 4, 7 4, 6 6, 7 1, 2 2, 6 2, 3 5, 6 1, 5 비용 7 13 23 25 29 34 35 53 75 간선을 하나 하나 체크해가며 그래..

[플로이드 워셜 알고리즘] 모든 노드에서 다른 모든 노드 까지 최단 경로를 모두 계산한다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없게 됐다. 각 단계마다 \( O(N^2) \) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 시간 복잡도는 \( O(V^2) \) 다이나믹 프로그래밍 유형에 속합니다. K 번째 단계에 대한 점화식 : \( D_{ab} = min(D_{ab},D_{ak} + D_{kb} ) \) - A에서 B로가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신 INF = int(1e9) n, m = map(int,input().split()) # 노드의 갯수, 간선의 갯수 graph = [[INF]*(n+1) for _ ..

[간단한 다익스트라 최단 경로 알고리즘] 음의 간선이 없을 때 정상적으로 동작한다. 실제로 GPS 소프트웨어의 기본 알고리즘으로 많이 채택된다고 한다. 다익스트라는 최단 경로를 다루는 알고리즘이지만 코테에는 최단 거리가 주로 나오기 때문에 일단 최단 거리만을 책에서 다루겠다고 한다. 노드 1을 출발점으로 해서 최단 거리를 찾아나간다. 노드 1과 이어진 가장 짧은 간선을 찾는데, 다른 노드까지는 현재 무한으로 초기화 된 상태이다. 이미 탐색한 노드를 제외하고, 탐색하지 않은 노드 중 출발지로 부터 거리가 가장 가까운 노드부터 해서 탐색해나가며, 최단 거리를 갱신한다. 거리가 최솟값인 지점부터 탐색하기 때문에 이미 탐색한 노드와의 거리는 굳이 갱신할 필요가 없게 된다. ( 빨간색으로 표시 ) => 마지막 노..