The Way

세그먼트 트리는 그냥 일반 알고리즘 수업만 들은 사람이랑 PS를 한다는 사람을 구분짓는 가장 대표적인 알고리즘이 아닐까 싶다. (CLRS 책에 안나와서 그러려나) 인터넷에 쳐보면 그야말로 넘쳐날 정도의 세그먼트 트리 글이 있지만, 아주 쉬운 구현을 발견해서 이를 포함해서 정리 겸 써본다.세그먼트 트리는 기본적으로 i) 구간에 대한 정보 쿼리, ii) 구간을 한번에 업데이트 시키기 두 가지에 아주 적합한 자료구조이다. 세부적으로 약간 차이가 있지만, 크게 3가지 타입이 있을 것 같다. i) 단일 업데이트, 구간 쿼리업데이트가 일어날 때는 하나의 원소만 변경되고, 쿼리는 구간에 대해서 묻는 질의이다.대표적으로 https://www.acmicpc.net/problem/2042과 같은 문제가 있다. 대표적인 세..

둘이서 베스킨라빈스 31 게임을 해본 사람이 있는가?다들 알다시피, 베스킨라빈스 31은 1부터 시작해 숫자를 최대 3개씩 부를 수 있고, 31을 먼저 외치는 사람이 지며, 먼저 시작한 사람에게 필승 전략이 존재한다. 왜 그런지 게임이 끝나는 상황부터 거꾸로 되돌아가보자.베스킨라빈스 31 게임은 30을 말하는 사람이 무조건 이기게 된다.30을 말하려면, 26을 외쳐야 한다. 26을 외치면, 다음사람이 어떤 수를 외치든 (4 - 외친수)만큼의 수를 말하면, 30을 만들 수 있기 때문이다. 즉, 26을 외치는 사람이 필승한다.반복적으로 26을 외치려면 22를 외쳐야 하고, 18, 14, 10, 6, 2...까지 간다. 따라서, 먼저 시작한 사람이 1, 2를 외치기만 하면 이미 게임은 끝난 상태인 것이다. 이러..

추상대수학 시간에 배운 소수판정법인데, 아주 유용하여 기록해놓는다. Miller-Rabin 소수 판별법은 확률에 의존하는 소수판정법인데, 라그랑주 정리를 이용한다. 라그랑주 정리는 p가 소수이면, $f(x) \equiv 0 ( \text{mod}\:p)$는 최대 $deg(f(x))$개의 incongruent solution을 가진다는 정리이다. 라그랑주 정리에 따르면, $x^2 \equiv 1 ( \text{mod}\: p)$는 최대 두 개의 해를 가진다. 그런데 우리는 두 가지의 자명해를 알고있다. 바로 $\pm1$이다. (단, p > 2라 하자) 따라서, 만약 자명해가 아닌 $x^2 \equiv 1 ( \text{mod}\: p)$를 만족하는 해를 발견한다면, p는 소수가 아니라는 것을 알 수 있다...

운영체제 프로젝트 1은 스도쿠 푸는 프로그램을 작성하는 과제였다. 운영체제 수업에서 왜 스도쿠를 푸는지는 잘 모르겠으나.. 프로젝트를 하면서 많은 것을 배우게 되었으니 정리해본다. 스도쿠는 단 한 가지의 정답만 가져야 한다는 있다는 말도 있는데, 꼭 필요한 조건은 아니라고 생각한다. 물론 손으로 풀 때 답이 여러가지이면 굉장히 열받겠지만, 진정한 프로그램이면 어떠한 경우에서도 해답을 찾아낼 수 있어야 한다고 생각한다. https://www.acmicpc.net/problem/2580 참고로 백준 스도쿠 문제의 테스트 케이스 중에도 스도쿠 판을 채우는 방법이 여럿인 경우가 있다고 명시되어 있다. 답이 유일한 스도쿠를 찾는다면, http://staffhome.ecm.uwa.edu.au/~00013890/su..

메르센 소수의 소수 판별 알고리즘은 일반적인 PS에서 출제되는 알고리즘은 아니지만.. 상당히 흥미로운 알고리즘이다.엄청나게 큰 메르센 소수의 소수 판별을 빠르게 할 수 있고, 그래서 알려진 큰 소수 중 상위권은 항상 메르센 소수가 먹는다.https://en.wikipedia.org/wiki/Largest_known_prime_number(작성일 기준 1~7등이 모두 메르센 소수이다) 1. Trial Factoring먼저 두 가지 정리를 미리 알아두고 가자.정리 1. $2^p - 1$이 소수이면, p도 소수이다.정리 2. $2^p - 1$의 인수는 모두 $2kp + 1$의 형태이며, 8로 나누었을 때 나머지가 1 또는 7이다. 정리 1과 2를 통해 $2^p - 1$의 인수가 될 만한 수의 후보를 추려낸 후..

우선순위 큐를 이용한 다익스트라 알고리즘의 구현. 출처는 책 알고리즘 트레이닝. 특이한 점으로는 pq에 동일한 원소들이 추가되도록 방치한다는 것이다. 어차피 나중에 continue가 포함된 if문에서 다 걸러지게 된다. 느긋한 삭제라고 부른다. 코드는 다음과 같다. #include using namespace std; typedef pair ii; // index는 0 ~ v - 1 // v은 vertex 갯수, s는 시작점 // edge에 (번호, 거리)로 저장 int v, s; vector edge(v); vector dist(v, INF); dist[s] = 0; priority_queue pq; pq.push(ii(0, s)); while (!pq.empty()) { ii now = pq.top(..

초보자들에게 이항 계수는 보통 DP를 이용하여 계산하는 것이 정석이라 여겨진다. 하지만 어느 정도 문제를 풀다보면 DP의 메모리 범위 이상의 숫자들을 더 빠르게 계산해야 한다. 이번 AtCoder Grand Contest 025 B번 문제에서도 이를 이용하는 문제가 있었는데, 버벅이다가 결국 못풀었다. 따라서 이항계수를 구하는 방법들을 간단하게 공부해보았다. 이 분야의 한줄기 빛과도 같은 구사과님의 블로그를 참고하였다. 1. DP 생략. 시간, 공간 복잡도가 $O(n^2)$이라 쓸모가 없다. 대신 여기서 사용하는 점화식 $_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$은 많은 아이디어의 기반이 되니 기억하자. * 아래 2~4번의 방법은 MOD가 N보다 크다고 가정하자. 예기치 못한 오류가..

c++ algorithm 라이브러리에서는 next_permutation 함수를 기본적으로 제공한다. 그 기능은 일반적인 순열의 순서로 배열 등의 순서를 바꾸어주고,순열이 최종적으로 끝나면(완전히 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해주는 함수이다.예를 들어서1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false 반환) 1 2 3 4순으로 작동한다. 또, 중복된 수가 있을 경우 제외해준다.즉, 만약 5가 5개 있다고 치면 5!개의 결과가 나오는 것이 아니라 1개만 나온다는 것이다. 함수를 쓰다보니 함수의 시간 복잡도는 어떤지, 어떤 알고리즘으로 작동하는지가 살짝 미심쩍어서해당 부분 함수 코드를 살펴보았고, 알고리즘이..

$f(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$이라는 다항식이 있을 때, 이 값은 선형 시간에 계산할 수 있다. 간단한 변환을 거치면 쉽게 알아차릴 수 있는데, $f(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n + 0)))$으로 변환 가능하기 때문이다. 코드는 다음과 같다. 길이 n+1의 배열은 $a_0,\;a_1,\;a_2,...,a_n$이 저장되어있는 배열이라고 하자 int poly(int x, int* arr, int n) { // n은 배열의 길이 (최고차항+1) int r = 0; for (int i = n; i > 0; --i) { r += arr[i]; r *= x; } r += arr[0]; return r; }

어떠한 알고리즘의 시간 복잡도를 구하기 위해서는 (특히 분할 정복 알고리즘의 경우) 점화식을 풀게 될 때가 많다.가령, 병합 정렬의 알고리즘 복잡도를 구하기 위해서는 다음과 같은 점화식을 풀어야 한다. $$T(n) = \begin{cases}\Theta(1)\;(n=1)\\2T(n/2) + \Theta(n)\;(n>1) \end{cases}$$ 재귀 트리를 작성한다면 직관적으로 복잡도가 $\Theta(n\log n)$임을 알 수 있지만, 마스터 정리를 이용하면 일반적인 경우의 풀이가 쉬워진다. 1. 마스터 정리$T(n) = aT(n/b) + f(n)$형태의 점화식이 있을 때, i) $f(n) = O(n^{\log_b a - \epsilon})$이면 $T(n) = \Theta(n^{\log_b a})$ii..