[1-2][DP] 거듭제곱 빠르게 구현하기

다이나믹 프로그래밍

재귀적 호출을  power(x, y - 1) 대신 power(x, y // 2) 로 바꿔줌으로써

시간복잡도를 O(n)에서 O(lgn) 으로 줄일 수 있다.

홀수와 짝수를 나누어서 계산한다.

# 시간복잡도 O(n)

def power(x, y):
    if y == 0:
        return 1

    return power(x, y - 1) * x
    

# 시간복잡도 O(lgn)

def power(x, y):
    if y == 0:
        return 1
    # 계산을 한 번만 하기 위해서 변수에 저장
    subresult = power(x, y // 2)

    # 문제를 최대한 똑같은 크기의 문제 두 개로 나눈다.
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult

# y가 8이면 4번, y가 32면 6번 호출, 즉 lg y + 1번 호출

#테스트
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))