본문 바로가기

IT/Algorithm

(5)
[Greedy] Floyd Algorithm 플로이드 알고리즘 최단거리를 찾는 알고리즘입니다. 한 노드를 고정시키고 나머지 노드들의 경로의 기존 값과 고정노드를 통한 값을 비교하고 수정합니다. 모든 노드를 거치면 완료됩니다. Ak[i,j] = min ( Ak-1[i,j] , Ak-1[i,k] + Ak-1[k,j] ) ex) A0 N1 N2 N3 N4 N1 0 7 ∞ 3 N2 2 0 ∞ ∞ N3 5 1 0 ∞ N4 8 ∞ 2 0 A1 = 1 고정 (1행 & 1열 & 대각 고정) 다른 노드들의 기존 값과 노드1을 거쳐가는 경우를 비교 A1[2,3] = min( A0[2,3], A0[2,1] + A0[1,3] ) = min( ∞, 2 + ∞ ) = ∞ A1[2,4] = min( A0[2,4], A0[2,1] + A0[1,4] ) = min( ∞, 2 +..
[Greedy] Dijkstra Algorithm 다익스트라 알고리즘 최단거리를 찾는 알고리즘입니다. { 최소거리 노드 고정, 고정되지 않은 노드들의 거리를 수정 } 을 반복합니다. ex) start A -> A 0 고정 A B C D E F 0 4 2 ∞ ∞ ∞ -> C 2 고정, 나머지 수정 A B C D E F 0 3 2 9 ∞ ∞ -> B 3 고정, 나머지 수정 A B C D E F 0 3 2 9 6 ∞ -> E 6 고정, 나머지 수정 A B C D E F 0 3 2 8 6 11 -> D 8 고정, 나머지 수정 A B C D E F 0 3 2 8 6 9 -> F 9 고정 A B C D E F 0 3 2 8 6 9
[Greedy] Kruskal Algorithm 크루스칼 알고리즘 최소 비용 신장트리를 찾는알고리즘 중 하나로 { 노드 연결들중 최소비용 연결을 선택 } 을 반복합니다. 연결시 사이클이 이루어지면 선택하지 않습니다. ex) 5, 5, 7, 8, 9, 13, 15, 20 -> 5 (A-D) 연결 -> 5 (C-E) 연결 -> 7 (C-D) 연결 -> 8 (B-F) 연결 -> 9 (D-E) 사이클로 연결X -> 13 (A-B) 연결
[Greedy] Prim's Algorithm 프림 알고리즘 최소 비용 신장트리를 찾는알고리즘 중 하나로 특정 시작점부터 { 연결될 수 있는 노드들중 최소비용 노드를 연결 } 을 반복합니다. 연결시 이미 만난 노드라면 연결하지 않습니다. 단점 : 연결되지 않은 두개의 트리가 있을 시에는 최소신장을 찾을 수 없습니다. ex) Start A (5, 13) -> 5 D 연결 A, D (7, 9, 13) -> 7 C 연결 A, D, C (5, 9, 13, 20) -> 5 E 연결 A, D, C, E (9, 13, 15, 20) -> 9 중복 -> 13 B 연결 A, D, C, E, B (8, 15, 20) -> 8 F 연결 A, D, C, E, B, F
Sort Algorithm Sort Algorithm 주어진 값들을 정렬하는 알고리즘 버블 Bubble 시간복잡도 O(n) ~ O(n^2) 공간복잡도 O(1) 가까운 두개 값을 비교하는걸 반복 for i in 0..