거듭제곱 연산

거듭제곱 연산의 활용

알고리즘 문제를 풀다 보면 종종 거듭제곱을 활용하여 문제를 해결해야 할 때가 있다. 이러한 문제를 log(n)만큼의 복잡도로 해결할 수 있는 방법을 정리하려고 한다.

재귀함수를 활용해서 중복된 연산을 생략한다. (base case:
if (n == 0) -> return 1;)

예시 코드 (자바)

public static int pow(int a, int n) {
    if (n == 0) {
        return 1;
    } else {
        return a * pow(a, n - 1);
    }
}