PS/자료구조 & 알고리즘
최소 신장 트리 (Minimum Spanning Tree, MST) 최소 신장 트리는 가중치 무방향 그래프에서 최소 비용으로 모든 정점을 연결하는 트리이다.사이클이 없음 : 그래프의 모든 정점을 포함하면서 사이클이 없는 그래프 형태로 구성된다. 특징 MST는 연결 그래프에서 정의되며 그래프가 연결되지 않은 경우 MST를 구할 수 없다.간선의 개수가 항상 V-1(정점의 개수 - 1)이다.MST는 유일하지 않을 수 있으며, 동일한 가중치를 가지는 여러 MST가 존재할 수 있다. 크루스칼 알고리즘 (Kruskal's Algorithm) 모든 노드를 연결할 때 필요한 최소 간선 수는 N-1개이며, 이것이 최소 신장 트리의 요구사항이다. 따라서 총 N-1개의 간선을 선택해야 한다.간선을 가중치 순으로 정렬한 뒤,..
위상 정렬(Topological Sort) 사이클이 없는 그래프에서 노드의 순서를 찾는 알고리즘그래프 내의 노드들 간의 선후 관계를 결정하여, 어떤 작업들이 먼저 수행되어야 하는지 순서를 정하는 것이 목표이다.작업의 선후 관계를 결정해야 하거나 특정 순서로 작업을 처리해야 하는 문제에서 사용된다. 특징위상 정렬은 방향 그래프에서 사용된다. 노드들 간의 방향성이 있는 의존 관계를 표현하기 위해서 위상 정렬을 수행하는 것이기 때문이다.그래프에 사이클이 없어야 한다. 사이클이 존재하면 위상 정렬이 불가능하다.이 점을 이용하여 반대로 위상 정렬을 수행하여 사이클을 탐지할 수 있다.위상 정렬 결과는 항상 유일하지는 않다. 즉 동일한 그래프에 대해 여러 가지 정렬 결과가 나올 수 있다.시간 복잡도는 O(V+E), ..
유니온-파인드(Union-Find) 유니온-파인드 알고리즘은 집합을 결합(Union, 합집합)하고 해당 Element가 소속된 집합을 찾아내는(Find) 알고리즘이다.서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.그래프에서도 유용하게 사용되어 노드 간의 연결 관계를 확인하는 등으로 응용되어 자주 사용된다. 해당 알고리즘은 두 가지 기본 연산으로 구성된다.Union 연산: 여러 노드 중 두 노드를 선택하여 이들을 하나의 집합으로 연결한다. 이 연산을 통해 서로 연결된 노드들이 같은 집합에 속하게 된다.Find 연산: 특정 노드의 대표 노드를 찾아낸다. 두 노드의 대표 노드를 찾아낸다면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다. 유니온-파인드의 용도 집합 소속 여부 판단: 임의..
플로이드 워셜( Floyd-Warshall)가중치가 존재하는 그래프의 시작 정점으로부터 다른 정점들까지의 최단 거리를 구하는 알고리즘. 모든 정점 쌍 사이의의 최단 거리를 탐색한다. 특징시작 정점으로부터 나머지 정점의 최단거리를 알아내는 다익스트라나 벨만-포드와 달리 모든 정점들 간의 거리를 탐색한다.Edge 가중치가 음수일 경우에도 사용 가능 (단 음수 싸이클이 있으면 안됨)시간 복잡도 : O(N^3) (N = 노드의 개수) → 노드의 개수가 200개 내외로 주어지는 경우에 사용을 고려할 수 있다.동적 계획법을 활용하여 부분해를 활용하여 문제를 해결하는 방식을 사용한다.A -> B -> C의 최단 거리를 구할 때, A->B와, B->C의 최단 거리를 안다면, A->B->C의 최단 거리를 알 수 있다. ..
벨만-포드 (Bellman-Ford)가중치가 존재하는 그래프의 시작 정점으로부터 다른 정점들까지의 최단 거리를 구하는 알고리즘 출발 노드로부터의 모든 노드의 최단 거리를 탐색한다. 활용 다익스트라와 달리 Edge의 가중치가 음수일 때도 사용 가능하다. 그래프에서 음수 사이클의 존재 여부를 판단하는 문제에 활용할 수 있다. 과정 그래프 구현 벨만 포드 알고리즘은 Edge를 중심으로 동작한다 -> 그래프를 Edge List로 구현 초기화 최단 거리 배열(D)를 초기화한다. 모든 정점의 최단 경로 값을 INF로 초기화, 시작 정점의 최단 경로 값을 0으로 설정 최단 거리 갱신 그래프의 모든 Edge에 대해 (정점 수 - 1)번 반복하여 최단 경로 값을 갱신.음수 사이클이 없을 때 특정 두 노드의 최단 거리를..
다익스트라 (Dijkstra)가중치가 존재하는 그래프의 시작 정점으로부터 다른 정점들까지의 최단 거리를 구하는 알고리즘출발 노드로부터의 모든 노드의 최단 거리를 탐색한다.제약 조건 : Edge의 가중치가 모두 양수일 때만 사용할 수 있다. 과정 그래프 구현주로 인접 리스트를 사용하여 그래프를 구현한다. N의 크기가 클 경우를 대비하여 인접 리스트를 선택하는 편이 좋은 경우가 많다.최단 거리 배열 초기화최단 거리 배열(distance)을 초기화한다.출발 노드는 0으로 설정하고, 다른 모든 노드는 무한대(INF)로 초기화한다.가장 작은 값을 가진 노드 선택 및 최단 거리 배열 업데이트현재 방문하지 않은 노드 중 distance가 가장 작은 노드를 선택한다. 선택 노드의 최단 거리 배열 값 + 해당 노드..
그래프(Graph) 그래프는 정점들과, 정점들을 연결하는 간선들로 구성된 자료 구조이다. 최단 경로 찾기, 네트워크 구성, 검색 엔진, 스케줄링 등 다양한 분야의 컴퓨터 과학에서 응용되어 사용되고 있다. 그래프 탐색 그래프 구조에서 정점(Vertex)과 간선(Edge)을 따라 이동하는 과정이다. 그래프 탐색는 주로 시작 정점에서 출발하여 인접한 정점을 탐색하는 방법을 사용하며, 그 종류는 다음과 같다.깊이 우선 탐색(DFS, Depth-First Search): 가능한 한 깊숙한 곳까지 이동한 후 다시 돌아와 다음 가능한 경로를 탐색한다.너비 우선 탐색(BFS, Breadth-First Search): 시작 정점에서 가까운 정점부터 차례로 방문하며 넓게 탐색한다. 시작 정점이 1일 때 두 가지 방법의 ..
그래프(Graph) 그래프는 정점들과, 정점들을 연결하는 간선들로 구성된 자료 구조이다. 최단 경로 찾기, 네트워크 구성, 검색 엔진, 스케줄링 등 다양한 분야의 컴퓨터 과학에서 응용되어 사용되고 있다. 그래프 이론 그래프의 정의 정점(Vertex)와 간선(Edge)의 집합표현 : G = (V, E) (V=정점의 집합, E=간선의 집합) 그래프의 종류 방향그래프 : 간선에 방향이 있는 그래프표현 : (a, b) = 정점 a와 b를 연결하는 간선무방향그래프 : 간선에 방향이 없는 그래프표현 : = 정점 a와 b를 연결하는 간선 가중치 그래프 : 간선에 가중치가 부여된 경우 그래프 용어차수(Degree) : 정점에 인접한 간선의 수방향그래프 : 진입차수와 진출차수로 구분경로(Path) : 시작 정..
그리디와 우선순위 큐 그리디 알고리즘은 매번의 선택의 순간에서의 최선인 답을 도출하면서 결과를 도출하는 방법이다. 매 순간에 최선의 해답을 판단해야 할 때, 우선순위 큐가 유용하게 사용될 수 있다.우선순위 큐는 그리디에서 매 순간의 최적의 선택이 이전의 결정에 의해 영향을 받을 경우, 그 선택의 후보군들을 저장해 둘 수단으로서 유용하게 사용될 수 있다.PS문제에서 우선순위 큐와 그리디와 함께 사용되는 경우가 매우 많다. 이러한 방법들을 사용한 문제들을 풀어보도록 하자. 그리디 알고리즘의 개념https://sjh9708.tistory.com/216 [알고리즘/JAVA] 그리디 (Greedy) : 개념 (동전, 단어 수학, 허프만 코딩)그리디 알고리즘 (Greedy) 나는 미래를 위해서 지금 어떤 행동을 ..
