Doby's Lab

[창의력에 대한 이데올로기] 근 1년간 PS(Problem Solving)를 공부하면서 저의 명확한 공부법이 없었습니다. 하지만, 지금껏 써온 블로그 글을 읽어보면 어떤 공부법이라 말할 수가 없었을 뿐이지 나름의 규칙(?)을 파악할 수 있었습니다. 공부법을 소개하기 앞서 PS에 대한 필자의 이데올로기를 말해드리고 싶습니다. PS나 코딩 테스트는 개개인의 알고리즘 지식과 이를 응용한 개개인의 창의력을 확인하는 대회 혹은 테스트라고 생각합니다. 그중에 창의력은 '자기 자신의 라이브러리'에 얼마나 많은 지식이 있으며 이를 어떻게 활용하는지에 따라 드러난다고 봅니다. 즉, '창의력은 갑자기 번뜩이는 아이디어가 아니라 개개인의 베이스에서 여러 가지가 응용 or 융합되어 나온다'는 이데올로기를 가지고 있다고 말씀드..

Pollard's Rho를 공부해보기 전에 직접 인수 분해 (소인수 분해) 알고리즘 코드를 작성해봤습니다. #include #include #include using namespace std; vector getPrime(int n){ vector isPrime(n, false); vector ret; for(int i = 2; i n; auto res = factorization(n); // n's factor for(auto factor : res) cout

Miller-Rabin에 대해 공부해봤습니다. 정리까지 끝냈으나 포스팅은 늦어질 거 같아서 코드 먼저 올려두겠습니다. [N의 범위가 int일 때] // Miller-Rabin, N이 int의 범위 일때 #include #include using namespace std; int base[3] = {2, 7, 61}; int power(int a, int k, int mod){ if(k == 0) return 1; else if(k == 1) return a; else{ int value = power(a, k / 2, mod) % mod; if(k % 2 != 0){ return (((value * value) % mod) * (a % mod)) % mod; } else{ return value * va..

Bitmasking 비트 마스킹이란 어떤 집합에 대해 어떤 값이 있는지 없는지에 대한 유무를 효율적으로 확인하는 방법이다.(시간 단축, 간결한 코드, 더 작은 메모리 사용) 어떤 정수형 변수를 선언하여 이를 집합으로 사용하고 N번째 비트를 켜고, 끄고, 켜져 있는지 꺼져있는지 확인을 비트 연산을 통해 하면서 비트 마스킹을 사용할 수 있다. (궁금한 점이 있는데 int형 변수를 사용하면 범위가 2^31 - 1인 점을 고려하여 30개의 비트 밖에 사용 못 하지 않나?) 아래에는 기본적인 비트마스킹 연산에 대해 정리해두었다. 볼 때마다 왜 이런 것인지에 대해 생각해내기 위해 따로 이유는 적지 않겠다. n번째 비트 켜기 bit |= (1

확장 유클리드 알고리즘(Extended Eucildean Algorithm)이란 ax + by = c 같은 부정방정식이 주어졌을 때, (x, y)의 정수해를 알아내는 알고리즘입니다. 증명은 따로 하지 않으며 배운 곳까지만 작성하겠습니다. 증명 자료를 찾으려니 이해가 안 되는 부분들이 꽤나 많았습니다. [사전 지식] ax + by = c와 같이 미지수의 개수가 식의 개수보다 많아서 근이 일정하지 않은 방정식을 부정방정식(Underdetermined Equation)이라고 합니다. 그리고, ax + by = c에서 정수해를 구한다고 하였는데 부정방정식에서 정수해를 구하는 방정식을 디오판토스 방정식(Diophantine Equation)이라고 합니다. => 사실 이 용어는 그닥 중요하지 않습니다. ax + b..

유클리드 호제법(Euclidean Algorithm)은 MOD 연산을 이용하여 두 수 간의 GCD(Greatest Common Divisior)를 빠르게 구하는 방법입니다. 코드로 구현하는 방법에도 반복과 재귀가 있습니다. 각 방법에 대하여 장단점이 있으며 두 방법 모두 MOD 연산을 사용하기 때문에 작은 수에서 큰 수로 MOD 연산을 하게 될 경우 알아서 swap이 되는 특징이 있으므로 따로 swap을 필요로 하지는 않습니다. #include using namespace std; int gcd1(int a, int b){ int temp; while(b){ temp = b; b = a % b; a = temp; } return a; } int gcd2(int a, int b){ // recursive ..

Coordinate Compression이란 1차원 직선상에 N개의 점(1 n; for(int i = 0; i > value; v.push_back(value); temp.push_back(value); } // 정렬이 되어있어야 unique 함수를 통해 중복된 값을 지울 수 있다. // unique함수는 중복된 값들은 전부 다 뒤로 보낸다. // 그리고, unique함수는 중복되는 값이 시작되는 index의 iterator를 반환하므로 // 해당 iterator부터 끝까지 지워버리면 temp에는 값의 순서들만 남게된다. sort(temp.begin(), temp.end()); temp.erase(unique(temp.begin(), temp.end()),..

ll POW(ll a, ll b) { if (b == 0) {//지수가 0이면 모든 수가 1이 된다. return 1; } ll value = POW(a, b / 2); // 여기서 분할적으로 나뉘어짐 value = value * value; if (b % 2 == 0) {// b가 짝수일 때 return value; } else {// b가 홀수일 때 return value * a; } }