Algorithm/이론
-
강한 연결 요소(SCC, Strongly Connected Component)Algorithm/이론 2020. 12. 2. 21:21
강한 연결 요소(SCC, Strongly Connected Component) 방향이 있는 그래프에서 다음 조건을 만족하는 부분집합 (1) SCC 내부의 임의의 정점 u, v는 직, 간접적으로 서로 도달이 가능하다. (2) SCC 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다. SCC는 Maximal한 성질을 가지고 있어 형성될 수 있는 가장 큰 집합으로 형성된다. SCC를 추출하는 대표적인 알고리즘은 코사라주 알고리즘(구현이 쉬움)과 타잔 알고리즘(적용이 쉬움)이 있다. 필요한 자료구조 & 변수 변수 설명 List graph, reverseGraph 정방향 & 역방향 그래프 int[] visited 방문 여부 체크 배열 Stack stack DFS 호출 시작점을 찾기위한 stack..
-
위상 정렬(Topological Sort)Algorithm/이론 2020. 11. 29. 19:04
위상 정렬 방향이 있는 그래프의 순서 정렬 위상 정렬이 가능하려면 DAG(Directed Acycle Graph, 방향성이 있으며 사이클이 없는 그래프)이여야 한다. 위상 정렬을 구현하는 방법에는 DFS를 사용하거나 indegree 배열을 사용하여 구현하는 방법이 있다. 본 포스팅에서는 후자를 선택하여 구현하는 방법을 알아볼 것이다. 필요한 자료구조 & 변수 변수 설명 List graph 그래프 관계 표현을 위한 2차원 인접 리스트 int[] indegree 해당 노드를 가리키는 간선의 갯수를 담기 위한 배열 Queue q indegree 값이 0이 된 노드를 담기 위한 Queue List result 결과를 담기 위한 리스트 Flow 1. indegree가 0인(=나를 가리키는 노드가 없는) 노드들을 ..
-
다익스트라 알고리즘(Dijkstra's Algorithm)Algorithm/이론 2020. 8. 25. 18:46
다익스트라 알고리즘 정점 하나를 시작점으로 하여 나머지 정점들 간의 최단거리를 구하는 알고리즘 그래프는 무향이거나 유향이나 대부분 유향인 경우가 많으며, 간선 간의 이동거리가 존재한다. 또한 거리값이 음수가 아닐 때만 사용할 수 있다. 시간복잡도는 인접리스트로 구현했을 경우 O(ElogV), 인접행렬로 구현했을 경우 O(V^2)가 된다. 동작 과정 1. 준비물 int E, V, K // 간선 수, 정점 수, 시작점 class Node // Comparable {weight 오름차순 비교} List graph int[] distance // 거리 정보 저장 int[] prev // 최단 거리 경로 저장 boolean[] visited PriorityQueue pq 2. init() graph에 v+1개의 ..
-
이분 탐색 (Binary Search)Algorithm/이론 2020. 4. 24. 16:14
이분 탐색 (Binary Search) 이분 탐색 알고리즘의 큰 골자를 이루는 로직은 1. 오름차순으로 정렬 되어 있는 자료 구조에서 특정값을 찾을 때, 2. 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것이다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. www.acmicpc.net 위 문제를 이분 탐색으로 풀어보았다. 배열의 중..
-
누적합(Cumulative sum) 2Algorithm/이론 2020. 4. 14. 21:48
2차원 누적합 누적합의 개념을 2차원으로 확장시킬 수 있다. 1차원 배열(arr)은 2차원으로 확장되고, 누적합 수열도 2차원 배열(sumArr) 형태로 확장된다. 직사각형 형태의 배열에 포함되는 직사각형 구간의 모든 원소의 합을 빠르게 구할 수 있다. 2차원 누적합 수열 만들기 a(i, j)에서 가로 방향으로 누적합을 계산해서 s(i, j) 수열이 되고, 계산한 결과를 세로 방향으로 누적합을 구해서 최종적인 S(i, j) 수열이 된다. 2차원 구간합 계산하기 S(i, j)는 위에서 설명한 방법대로 a(i, j) 배열의 누적합을 계산한 배열이다. 초록색으로 표시된 작은 사각형의 구간합을 구하기 위해서는 S(3, 3)에서 시작한다. S(3, 3) 값에서 S(1, 3) 값과 S(3, 1) 값을 뺀 뒤에 S(..
-
누적합(Cumulative sum)Algorithm/이론 2020. 4. 14. 17:12
누적합의 필요성 알고리즘 문제에서 배열의 부분합을 빠르게 구해야 하는 경우에 누적합을 이용하면 연속된 누적합을 O(N)만에 구할 수 있다. 누적합의 성질 1. S(n) = 배열 a의 1번째 요소 부터 n번째 요소까지의 누적합 2. S(1) = a(1) 3. S(i) = S(i-1) + a(i) 4. a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) // 누적합을 활용한 빠른 구간합 계산 1차원 누적합 누적합의 4번 성질을 이용하여 아래 문제들을 해결할 수 있다. 1. 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
-
Merge Sort (합병 정렬)Algorithm/이론 2020. 3. 30. 22:03
Merge Sort 분할 정복 알고리즘의 하나 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략 분할정복은 대개 재귀 호출을 이용하여 구현한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge) 하는 단계이다. Merge Sort는 크기 N인 배열을 입력으로 받아, 배열을 절반으로 두 개로 나눈 후, 각 작은 배열을 재귀적으로 정렬하고, 그 결과를 Merge한다. 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트..
-
BFS와 DFSAlgorithm/이론 2019. 10. 6. 17:58
BFS(Breadth-First Search) 너비 우선 탐색 이란 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 최단 경로를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용한다. - Queue 자료구조를 사용한다. 알고리즘 1. 시작 노드를 큐에 삽입하면서 시작한다. 동시에 시작노드를 방문했다고 알리는 방문 처리 2. 큐에서 하나의 노드를 꺼낸다. 3. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 4. 큐가 빌 때 까지 DFS(Depth-First Search) 깊이 우선 탐색이란 탐색을 함에 있어 보다 깊은 것을 우선적으로 하여 탐색..