거듭제곱1 n의 거듭제곱 구하기 (큰 수의 큰 제곱수 구하기) n의 제곱을 구할 때 for문을 이용하여 n번 제곱하면 시간복잡도가 O(n)이다. (아래의 코드는 5를 1000제곱 했을 때의 계산을 구하고자 하는데, 이럴 경우 for문으로 1000번을 돌려야 한다.) int n = 5, k = 1000; long long result = 1; for(int i = 0; i < k; i++) result *= n; k가 작은 수라면 문제가 없지만 k가 1000도 아닌 100,000,000처럼 큰 수이면 어떻게 될까? 그럴 때에는 아무리 O(n)이라도 시간이 꽤 오래 걸릴 것이다. 이럴 때 연산 시간을 O(logn)까지 줄이는 방법이 있다. 재귀함수 등 여러가지 방법이 있으나 이번에는 지수 계산을 이용한 방법으로 해결해보았다. 간단한 예시로 2를 10번 제곱한다고 생각해.. 2020. 1. 6. 이전 1 다음