:: ADVANCE ::

[Binary Search] 이진 탐색 이진 탐색 Binary Search (이분 탐색이라고도 한다.) 이진 탐색은 순차 탐색과 달리 모든 경우를 다 탐색하지 않습니다.이진 탐색이란 한번 비교를 거칠 때 탐색 범위를 반으로 줄여가며 탐색을 하는 방법입니다.따라서 이진 탐색의 시간 복잡도는 O(logN)입니다. 이진 탐색의 경우 조건은 앞으로의 탐색 과정을 보면 알겠지만, 값이 정렬되어 있어야 한다는 것이다.배열에 값이 저장되어 있던, 어떤 특정한 값을 찾던지 간에 탐색해 가는 과정에서 범위를 줄이기 위해서는 정렬을 통해 더이상의 가능성이 존재하지 않는다는 보장이 되어 있어야 하기 때문이다. 이진 탐색의 탐색 과정 245791012152125 위와 같이 정렬된 배열에서 이진 탐색 알고리즘을 적용하여 데이터..

BAEKJOON ONLINE JUDGE 1261 알고스팟 https://www.acmicpc.net/problem/1261 입력이 0일 경우에는 벽을 부술 필요 없이 바로 이동하면 되므로 DFS이건 BFS이건 탐색을 하면 된다.입력이 1일 경우에는 벽을 부수어야 하기 때문에 바로 이동을 하면 안된다. 단계별로 나누면1. 바로 갈 수 있는 곳은 바로간다.2. 더이상 갈 수 없으면 벽을 부순다.3. 벽을 부순 후 갈 수 있는만큼 이동한다.이걸 반복해서 마지막 장소에 도착하면 된다. 풀이 1. 입력이 0인 곳은 DFS, 그 중 벽을 만나면 queue에 저장DFS가 끝난 후 queue에 저장된 벽을 부순 후 다시 DFS를 타서 바로 갈 수 있는 곳은 이동이동하면서 다시 벽을 만나면 queue에 저장 123456..

BAEKJOON ONLINE JUDGE 1915 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 DP!! 풀이 1. 수학 + 구현 1000x1000 이므로 일단 input을 한번씩 탐색하는 것은 가능하다.but, 탐색하면서 정사각형인지를 판단할 때 배열을 다시 탐색하는 일은 아마도 Time Limit이 발생할 것이다.따라서, 정사각형인지를 판단하는 여부를 줄였다. 정사각형의 면적은 한 변의 제곱이다.또한 입력은 0아니면 1이기 때문에 배열에 해당하는 값의 합(면적)이 한 변의 제곱과 같으면정사각형이라고 판단하였다. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위 입력에서 표시한 지점의 입력의 합 4이며 변이 2인 정사각형의 면적과 같다. 면적을 구할 때 또..

BAEKJOON ONLINE JUDGE 2580 스도쿠 https://www.acmicpc.net/problem/2580 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include typedef struct tagpoint { int x; int y;}POINT; POINT p[90];int size;int nemo[9][10];int horizon[9][10];int vertical[9][10];int ma..

BAEKJOON ONLINE JUDGE 11444 피보나치 수 6 https://www.acmicpc.net/problem/11444 input이 매우 크기 때문에 그냥 구할 수 없다.피보나치 행렬과 제곱의 이진수 응용을 이용해서 구해야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include using namespace std; #define Namuge 1000000007 vector multipleMatrix(vector &first, vector &second){ long long int t; long long int temp; vect..

[수학][피보나치] 피보나치 수 피보나치 수 * 피사노 주기피보나치 수를 k로 나눈 나머지는 주기를 가진다.이 때의 주기를 피사노 주기라 한다. * 피보나치 수 행렬 응용 피보나치 관련 문제피보나치 수피보나치 수 2피보나치 수 3피보나치 수 4피보나치 수 5피보나치 수 6피보나치 수의 확장피사노 주기피보나치 수의 합피보나치 수의 제곱의 합홀수번째 피보나치 수의 합짝수번째 피보나치 수의 합피보나치 수와 최대공약수

BAEKJOON ONLINE JUDGE 10830 행렬 제곱 https://www.acmicpc.net/problem/10830 행렬 곱을 반복반복을 분할 정복 또는 이진수 응용법으로 시간을 단축할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include using namespace std; int n;long long int m;vector in; void input(){ int num; scanf("%d %lld", &n, &m); for (int i = ..

[수학][Matrix] 행렬 Matrix 1. 행렬 덧셈12345for(int i = 0; i

[수학][제곱] a^n 제곱 a의 n제곱 빠르게 구하기 1. 단순 반복문 -> 시간 복잡도 O(n)1234int ans = 1;for(int i = 1; i > n의 이진수 중 1에 해당할 때 곱하여 나간다.1234567891011int times(int a, int n){ int ans = 1; while(n > 0) { if(n % 2) ans *= a; a *= a; n /= 2; } return ans;}cs >> a는 반복문을 돌 때마다 (이진수의 자리수를 옮길 때 마다)a *= a를 통해서 제곱을 해 준다. 관련 문제https://www.acmicpc.net/problem/1629

BAEKJOON ONLINE JUDGE 2004 조합 0의 개수 https://www.acmicpc.net/problem/2004 조합 nCm의 0의 개수는n!의 0의 개수 - (m!의 0의 개수 + (n - m)!의 0의 개수)이는 (n!의 min(2개수, 5개수) - ((m!의 min(2개수, 5개수) + ((n - m)!의 min(2개수, 5개수))를 하여 구할 수 있다. n!의 2의 개수, 5의 개수 구하는 방법은 [1676 팩토리얼 0의 개수] 참고 위 참고에서 첫 번째 개수를 구하는 방법으로는 [2004 조합 0의 개수]문제를 풀 수가 없다. (문제의 입력 범위가 매우 크기 때문에 time limit가 난다. 따라서 두번째 제시한 방법으로 구하면 아무런 문제 없이 문제를 풀 수 있다. 1234..