PS/자료구조 & 알고리즘
위상 정렬(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) 나는 미래를 위해서 지금 어떤 행동을 ..
이진 탐색 (Binary Search)정렬된 배열 또는 리스트를 반으로 나누어 가면서 원하는 값을 찾는 알고리즘이다. 배열이나 리스트가 정렬되어 있어야만 사용할 수 있다.이진 탐색은 시간 복잡도가 O(log n)으로 매우 빠르다. 따라서 큰 데이터 집합에서도 빠르게 원하는 값을 찾을 수 있다 이진 탐색의 과정탐색 범위 설정: 탐색 범위를 설정한다. 일반적으로는 전체 배열이나 리스트의 처음과 끝을 사용한다.중간 값 찾기: 설정된 범위에서 중간에 위치한 값을 찾는다.중간 값과 비교: 중간 값과 Key(찾고자 하는 값)의 크기를 비교한다.탐색 범위 업데이트: 중간 값과 Key의 크기에 따라 탐색 범위를 업데이트한다. 중간 값이 Key값보다 작을 경우 : 중간 값의 오른쪽 부분을 탐색 범위로 재설정한다.중간..
