0. 들어가기 전에공부한 내용을 간략하게 정리하는 느낌으로 작성한 글이다. 1. 디닉 알고리즘 (Dinic's Algorithm)최대 유량 문제를 더 빠르게 해결하기 위해 등장한 알고리즘이다.에드몬드-카프 알고리즘의 시간 복잡도가 $O(VE^2)$이었다면, 디닉 알고리즘은 $O(V^2 E)$로 동작한다고 한다. 그러면 어떻게 더 빠르게 동작할 수 있었을까?핵심 아이디어는 다음과 같다.현재 그래프에서 BFS를 통해 각 정점의 레벨을 구한다. 이를 통해 레벨 그래프를 만들어서, 레벨이 증가하는 모든 흐름을 찾을 수 있게 한다.레벨이 증가하는 방향으로만 DFS를 수행하면서, 가능한 모든 유량을 추가한다. 에드몬드-카프 알고리즘에서는 증가 경로를 한 번 찾을 때마다 BFS를 수행한다. 반면 디닉 알고리즘에서는 ..
Algorithm
정수론 관련 주요 알고리즘을 어딘가에 기록해두면 좋을 거 같아서, 코드 위주로 한번 모아봤다. (알고리즘에 대한 설명은 거의 없음) 1. 최대공약수 (GCD, Greatest Common Divisor)(1) 유클리드 호제법 이용using ll = long long;ll get_gcd(ll a, ll b) { while (b != 0) { ll r = a % b; a = b; b = r; } return a;} 관련 게시글 (유클리드 호제법) : https://infikei.tistory.com/46 2. 최소공배수 (LCM, Largest Common Multiple)(1) 최대공약수 이용$a \times b = \operatorname{GCD}(a..
0. 들어가기 전에최대 유량 문제, 포드-풀커슨 알고리즘, 에드몬드-카프 알고리즘에 대해서는 이미 잘 설명된 글들이 많기 때문에, 공부한 내용을 간략하게 정리한다는 느낌으로 남겨보려고 한다. 1. 최대 유량 문제 (Maximum Flow Problem)소스 정점과 싱크 정점이 정해진 방향 그래프가 주어지는 상황에서, 소스 정점에서 싱크 정점으로 흐를 수 있는 최대 유량을 구하는 문제이다. 여기서 소스(source), 싱크(sink), 용량(capacity), 유량(flow)라는 개념이 등장한다.소스(source) 정점은 유량을 발생시킬 수 있는 정점이고, 싱크(sink) 정점은 유량을 흡수하는 정점을 의미한다. 그 외 정점들에서는 유량을 발생시키거나 흡수할 수 없으며, 자신이 받은 유량만큼 다시 흘려보내..
1. 펜윅 트리(Fenwick Tree)펜윅 트리(Fenwick Tree)는 주로 수열의 구간 합을 빠르게 구하기 위해 사용되는 자료 구조이다.바이너리 인덱스 트리(Binary Index Tree)라고도 불리며, 줄여서 BIT라고도 한다. 2. 누적 합 VS 펜윅 트리예를 들어, 주어진 정수 배열 arr 에 대해 arr[i] 부터 arr[j] 까지의 구간 합을 반복적으로 구하는 문제를 가정하자.누적 합을 이용하면 주어진 정수 배열 arr 로 누적 합 배열 prefix_sum 을 미리 구해놓은 후, 각각의 쿼리에 대해 단 1번의 연산만으로 답을 구할 수 있다. ( prefix_sum[j] - prefix_sum[i - 1] ) 그러나 기존 정수 배열에서 구간 합을 구하는 쿼리가 들어오면서, 중간중간 기존 ..
이번 카카오 공채 1차 코딩테스트를 응시한 소감을 짤막하게라도 남겨보려고 한다. 1번 (스포방지)문제를 처음 읽었을 때 살짝 복잡하게 느껴졌다. 그런데 막상 풀이를 작성하다보니 그렇게 복잡하지는 않은 구현 문제였던 것 같다. 2번 (신호등)각 신호등마다 일정한 주기가 존재하므로, 나머지 연산을 활용하면 특정 시간에 신호등이 무슨 색인지 판별할 수 있을 것이라 생각했다. 또한 신호등 개수의 최댓값과 신호등 주기의 최댓값이 크지 않아서, 최소공배수를 구한 후 최소공배수 이하의 모든 값을 조사하는 방식이 시간 안에 가능할 것이라고 생각했다. 수학 + 완전탐색? 3번 (분배노드 그래프)이런 문제에 나름 강한 편이라고 생각했기 때문에 시간을 들여서 풀이를 구상해봤다. 여러 가지 방법을 생각해봤는데, 증명이 쉽게 ..
1. 유클리드 호제법유클리드 호제법(또는 유클리드 알고리즘, Euclidean Algorithm)은 두 양의 정수의 최대공약수를 구하는 방법 중 하나이다.여기서 호제라는 말은 서로 나눈다는 것을 의미한다. 2. 최대공약수의 정의최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 정수의 공통 약수 중 가장 큰 양의 정수이다.또한 최대공약수가 $1$인 두 정수를 서로소(coprime)라고 한다. ($0$과 어떤 정수 $a$의 최대공약수는 $a$로 정의할 수 있다. $0$은 모든 정수의 배수이기 때문이다.) 3. 최대공약수의 특징두 정수 $a$와 $b$의 최대공약수 $\gcd(a, b)$에 대해, $ax + by = \gcd(a, b)$를 만족하는 정수 $x$, $y$가 존재한다...
1. 버블 정렬이란?서로 인접한 두 원소를 비교하고, swap 연산을 수행하면서 정렬하는 방식이다.가장 큰 값이 배열의 끝으로 이동하는 과정이 물방울이 수면으로 떠오르는 듯한 모습을 보이기 때문에 버블 정렬이라는 이름이 붙었다. 2. 버블 정렬의 동작 과정배열의 처음부터 끝까지 순회하면서 인접한 두 원소를 차례대로 선택한다.인접한 두 원소를 비교하여 정렬 순서와 맞지 않다면, 서로 자리를 교환한다.배열의 끝에 가장 큰 값이 정렬되면, 다음 반복에서는 그 값을 제외하고 정렬한다.배열이 완전히 정렬될 때까지 1~3 과정을 반복한다. 3. 버블 정렬의 구현 코드아래는 버블 정렬을 구현한 코드이다.void bubble_sort(vector &nums) { int n = nums.size(); for ..
2의 거듭제곱을 외우고 있다고 말하면 그걸 왜 외우냐는 질문이 가장 많이 들어온다.어릴 적에 심심해서 외웠던 게 시작이었던 것 같다. 어릴 적에 10제곱까지 외웠다가 20제곱까지 늘렸던 기억이 난다.대학교 와서 27제곱까지 외웠던 것 같다.뇌 용량의 한계로 더 이상 외우려고 하지 않았는데,최근에 알고리즘 공부하고 코드 짜다보니 그 유명한 2^31 - 1 = 2147483647을 자주 접하게 되었다.그래서 내친김에 32제곱까지 외워버렸다. 2^1 = 22^2 = 42^3 = 82^4 = 162^5 = 32 2^6 = 642^7 = 1282^8 = 2562^9 = 5122^10 = 1024 2^11 = 20482^12 = 40962^13 = 81922^14 = 163842^15 = 32768 2^16 = 6..
