알고리즘5 [알고리즘] 위상 정렬(Topological Sort) 위상 정렬(Topological Sort) 순서가 정해져 있는 작업을 어떠한 차례로 수행해야 하는지 결정해주는 알고리즘이다. 즉, 방향 그래프에 존재하는 정점들의 선행 순서를 위반하지 않고 모든 정점을 나열하는 것이다. 위상 정렬은 한 방향 그래프에서 여러 위상 정렬이 가능하다. 즉, 답이 여러가지일 수 있다는 것이다. 위 방향그래프에서 위상 정렬을 한 결과를 생각해보면 다음과 같다. 1 → 6 → 2 → 5 → 4 → 3 6 → 2 → 1 → 5 → 4 → 3 6 → 1 → 2 → 5 → 4 → 3 과정 진입 차수가 0인 정점을 큐에 저장한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 이후 진입 차수가 0인 정점을 큐에 저장한다. 큐가 빌 때까지 반복한다. 이때, 모든 원소를 방문하.. Algorithm 2022. 9. 10. [알고리즘] 이분 그래프(Bipartite Graph) 이분 그래프란? 정점을 두 그룹으로 나눌 수 있으면서, 같은 그룹끼리는 간선으로 이어지지 않은 그래프이다. 트리가 아닌 그래프이므로, 사이클이 있어도 상관없으나, 같은 색상의 정점끼리 연결은 있어서는 안된다. 간선이 단 한도 없고 정점만 있는 상태도 이분 그래프이다. 여기에서 알 수 있듯이, 모든 정점이 꼭 연결되있어야 하는 것이 아니다. 이분 그래프 구현 이분 그래프는 DFS 또는 BFS를 사용하여 구현할 수 있다. 나는 BFS가 더 익숙하여 BFS를 사용할 것이다. 백준의 1707번 이분 그래프 문제를 예시로 들어보자. import java.util.* import kotlin.collections.ArrayList private lateinit var color: IntArray private la.. Algorithm 2022. 8. 16. [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm)은 다이나믹 프로그래밍을 활용하는 대표적인 최단 경로를 찾는 알고리즘이다. 다만 다익스트라 알고리즘은 음의 간선을 포함할 수 없다. 즉, 음의 간선이 하나라도 포함되어 있다면, 다익스트라 알고리즘을 사용할 수 없다. 원래 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다. 하지만, 일반적으로 한 꼭짓점을 루트(root) 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만든다. 동작 단계 출발 노드를 설정한다. 최단 거리를 저장할 테이블을 초기화해준다.(보통 무한대(아주 큰 값)로 초기화한다.) 현재 위치하고 있는 노드의 인접 노드 중 비용이 가장 적은 노드를 선택한다. 해당 .. Algorithm 2022. 8. 3. [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com 퀵 정렬 왼쪽 피벗 저번에는 피벗을 중앙으로 잡았을 때를 알아봤었다. 이번에는 피벗을 맨 왼쪽으로 잡았을 때를 알아보도록 하자. 맨 앞의 원소를 pivot으로 하고, left를 pivot의 한칸 뒤 원소로 잡는다. 또한 right는 맨 뒤의 원소로 잡는다. 이제 left가 pivot보다 클 때까지 증가시키고, right는 pivot보다 작아.. Algorithm 2022. 4. 13. [알고리즘] Brute Force Algorithm(전수 조사 알고리즘) Brute Force Algorithm(전수 조사 알고리즘) 모든 경우를 다 조사해보는 방법이다. 처음부터 끝까지 계산을 해나가며 해답을 찾는데, 이는 경우의 수가 제한적일 경우에만 사용 가능하다. 하지만 컴퓨터가 계산을 해나가기 때문에 생각보다 범위가 크다. Brute Force의 종류 선형 구조 - 순차 탐색 비선형 구조 - DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 순차 탐색이 흔히 말하는 Brute Force라고 생각이 된다. DFS와 BFS는 후에 따로 설명을 하겠다. 전수 조사 방법 전수 조사는 보통 재귀적으로 구현한다. 하지만 모든 재귀는 반복문을 이용해 동일한 기능을 구현할 수 있으므로, 반복문을 통해서도 구현이 가능하다. 가능한 모든 경우의 수를 전부 조사하는 방법이라 단순한 접.. Algorithm 2022. 4. 4. 이전 1 다음 728x90
