이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Floyd-warshall(플로이드-워셜) 알고리즘그래프에서 모든 꼭지점 사이의 최단 경로의 거리를 구하는 알고리즘이다.동적 계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최소 비용을 구한다.여기에 경유지를 기록하면 최소 비용 경로까지 구할 수 있다. 플로이드-워셜 알고리즘은 다음과 같은 접근으로 설계되었다.- 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.- 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.이는 중첩된 부분문제로 볼 수 있으며 동적 계획법을 적용하여 효과적으로 접근할 수 있다. 한편 비용을 구하는 김에, 어떤 경유지를 지..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Dijkstra(다익스트라) 알고리즘 어떤 변수 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.다익스트라 알고리즘은 각각의 꼭지점 v에 대해서 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다.알고리즘 시작 시에 d[s] = 0이고, s가 아닌 다른 모든 꼭지점 v에 대해서는 d[v] = ∞ 로 놓아 다른 꼭지점에 대해서는 아직 최단 경로를 모른다는 사실을 표기한다.알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.출처 : 위키백과 - 음수 가중치가 없다고 가..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Shortest Path(최단 경로)최단 경로 문제란 가장 짧은 경로에서 두 꼭지점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치의 합이 최소가 되도록 하는 경로를 찾는 문제이다.예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.보통은 주어진 가중 그래프에서 (V는 꼭지점, E는 변, 가중치 함수 f : E → R)가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.출처 : 위키백과 최단 경로 문제의 유형 - Single-Source : one to all하나..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Prim(프림)의 알고리즘가중치가 있는 연결된 무향 그래프의 모든 꼭지점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다.변의 개수를 E, 꼭지점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 프림의 알고리즘은 아래의 순서대로 작동한다.1. 그래프에서 하나의 꼭지점을 선택하여 트리를 만든다.2. 그래프의 모든 변이 들어 있는 집합을 만든다.3. 모든 꼭지점이 트리에 포함되어 있지 않은 동안1) 트리와 연결된 변 가운데 트리 속의 두 꼭지점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Kruskal(크루스칼) 알고리즘크루스칼 알고리즘은 아래의 순서대로 작동한다.1. 그래프의 각 꼭지점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F을 만든다.2. 모든 변을 원소로 갖는 집합 S를 만든다.3. S가 비어있지 않는 동안1) 가장 작은 가중치의 변을 S에서 하나 빼낸다.2) 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 나무로 만든다.3) 그렇지 않다면 그 변은 버린다.알고리즘이 종료됐을 때, 숲 F는 하나의 최소비용 생성나무만을 가지게 된다.크루스칼 알고리즘의 다른 형태가 있다. 그래프에서 변을 제거하는 방식이다.1) 그래프에서 꼭지점 또는 나무를 분리해 내지 않는 최대 가중치의..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. MST(Minimum Spanning Tree, 최소비용신장트리)예 : 입력 : n개의 도시, 도시와 도시를 연결하는 비용출력 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다.- 무방향 가중치 그래프 G=(V, E)- 각 에지 (u, v)∈E 에 대해서 가중치 w(u, v)- 문제 : 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라.1. T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다.2. 가중치의 합 ∑ w(u, v) 이 최소가 된다. - 왜 트리라고 부르나?싸이클이 없는 연결된(connected) 무방향 그래프를 트리라고 부른다.MST 문제의 답은 항상 트리가 된다.노드가 n개인 트리..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. DAG(Directed Acyclic Graph)와 Topological Ordering(위상정렬)DAG(Directed Acyclic Graph)- DAG는 방향 사이클(directed cycle)이 없는 방향그래프예 : 작업들의 우선순위 Topological Ordering(위상정렬)유향 그래프의 Vertex(꼭지점)들의 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해서 위상 정렬을 이용할 수 있다.정렬의 순서는 유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있다.위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다...
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. DFS(Depth-First Search, 깊이우선탐색)맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(Level)의 한 개의 자식노드를 첨가하여, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식노드의 첨가 과정을 반복해가는 방식이다. 장점 : - 단지 한 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.- 목표노드가 깊은 단계가 있을 경우 해를 빨리 구할 수 있다. 단점 : - 해가 없는 경로에 깊이 빠질 가능성이 있다. - 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Graph Traversal(그래프 순회)Traversal(순회) : 그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법 - BFS(Breath-First Search, 너비우선순회)- DFS(Depth-First Search, 깊이우선순회) BFS(Breath-First Search, 너비우선순회)맹목적 탐색방법의 하나로 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 탐색하는 방법이다.더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. 장점 : - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 : - 경로가 매우 길 경우에는 탐색 가..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Graph Algorithms(그래프 알고리즘)Graph(그래프) : 일련의 꼭지점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다. - (무방향) 그래프 G = (V, E)- V : Node(노드) 혹은 Vertax(정점)- E : 노드 쌍을 연결하는 Edge(에지) 혹은 Link(링크)- Object(개체)들 간의 이진 관계를 표현- n = |V|, m = |E|출처 : 위키백과 V = {1, 2, 3, 4, 5, 6}E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}n = 6, m = 7 Directed Graph(방향 그래프)와 Weighted Graph..