알고리즘
알고리즘 공부 순서
01. STL 1: 기초 자료구조 (큐, 스택, 힙, 벡터, 데큐, 맵, 셋 ...) 02. STL 2: 기초 알고리즘 (이분 탐색, 정렬, ...) 03. 그래프 1: BFS, DFS 04. 전수탐색과 재귀호출 05. Greedy 기초 06. Dijkstra, Floyd, 벨만-포드 07. DP 1 08. 문자열 기초 (KMP, Manacher) 09. 수학 1: 정수론 기초 10. DP 2: 다차원, 메모이제이션, 분할정복 11. 기하 기초 12. 그래프 2: SCC, 2-SAT 13. DP 3: 비트마스크, 기댓값 14. Network Flow, 이분 매칭 15. Segment Tree와 BIT (+ 2D BIT) 16. 문자열 응용 (아호 코라식, Suffix Array) 17. MCMF 18. ..
분할정복을 이용한 거듭제곱(a^n 계산을 O(log n)으로)
Binary exponentiation(또는 Exponentiation by squaring)이라는 기법을 써주면 O(log n)의 시간복잡도로 a^n을 구할 수 있다. 분할정복을 이용한 거듭제곱이라고 부를 수 있다. typedef long long ll; ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res *= a; a = a * a; b >>= 1; } return res; } 반복문으로 짠 버전입니다. a(base)를 squaring을 하고, 동시에 b는 오른쪽 쉬프트를 해서 절반씩 줄여나간다. b&1일 때 해당 base를 곱해준다. ll binpow_recur(ll a, ll b) { if (b == 0) return 1; ll ..