시간복잡도1 [알고리즘] 분할 정복(Divide and Conquer) 1. 정의 - 작은 문제로 분할하여 문제를 해결하는 방법 1) 분할 : 본 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 나누기 2) 정복 : 하위 문제를 각각을 재귀적으로 해결 3) 조합 : 하위 문제들의 답을 합쳐서 본 문제를 해결 2. 상세설명 - 특정 수나 행렬의 거듭제곱을 구할 때 사용 => 시간 복잡도 O(n)에서 O(logN)으로 줄일 수 있음 3. 적용 사례 3-1) 거듭제곱 long long power(long long n, long long m) { long long ret = 1; while (m) { if (m & 1) ret = ret * n % MOD; m = m / 2; n = n * n % MOD; } return ret; } 3-2) 행렬 거듭제곱 long long m.. 2022. 12. 8. 이전 1 다음
