728x90 반응형 BASE/Alogorithm15 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 1. 최단 경로 알고리즘 최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제 단일 도착 (single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다. 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 2) 주요 알고리즘 BFS (완전탐색 알고리.. 2021. 2. 3. 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 1. 단절점이란? 무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두 개의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점이다. 예를 들어 5에 있는 간선들을 모두 제거해도 그래프가 두 개로 나누어지지 않기 때문에 5는 단절점이 아니다. 그러나 4에 있는 간선들을 모두 제거할 경우 두 개의 연결 그래프로 나뉘어지기 때문에 단절점이다. 2. 단절점 찾기 - 무향 연결 그래프 G에서 어떤 정점 A에 연결된 정점들에 대해서 우회 경로 (정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. orderV : 정점 V의 방문순서 lowV : 정점 V의 low (V 이후에 방문하는 정점들 중 .. 2021. 2. 3. 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라 갈 때 처음 공통으로 만나게 되는 정점이다. 정점 A혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 8과 9의 공통 조상들은 1, 2, 4 / 8과 9의 최소 공통 조상은 4 3과 6의 공통 조상들은 1, 3 / 3과 6의 최소 공통 조상은 3 8과 5의 공통 조상들은 1, 2 / 8과 5의 최소 공통 조상은 2 [ 최소 공통 조상 구하기 ] - 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. - 정점의 부모를 따라 하나씩 올라가 LCA를 찾는다. 시간복잡도 : 트리의 깊이.. 2021. 2. 3. 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) jina-developer.tistory.com/114 자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 jina-developer.tistory.com 1. 크루스칼 알고리즘(Kruskal's Algorithm) 1) 순서 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연.. 2021. 2. 2. 알고리즘 - 위상정렬 (Topological Sort) 알고리즘 - 위상정렬 (Topological Sort) DAG(비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 알고리즘으로 위상정렬은 각 정점을 우선순위에 따라 배치한다. 일반적으로 결과는 유일하지 않다. jina-developer.tistory.com/112 자료구조 - DAG (Directed Acyclic Graph) 1. Directed Acyclic Graph란? DAG란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. - 선행자(predecessor), 후행자(successor) : DAG에서 어떤 정점 v.. jina-developer.tistory.com 각 노드들의 진입 차수 계산 진입 차수가 0인 노드들.. 2021. 2. 2. 알고리즘 - 에라토스네스의 체 알고리즘 - 에라토스네스의 체 1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수라고 한다. 에라토스네스의 체란, 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식으로 프로그래밍에서는 상당히 효율적인 방법론이다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.) 2부터 시작하여 남아있는 수.. 2021. 2. 2. 이전 1 2 3 다음 728x90 반응형
