[알고리즘 일기] 34. 거듭 제곱 빨리 구하기

728x90

 

 

문제 34. (2021-06-03)

 

거듭 제곱 빨리 구하기

거듭 제곱을 계산하는 함수 power를 작성하고 싶습니다. power는 파라미터로 자연수 x와 자연수 y를 받고, xy를 리턴합니다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법입니다.

위 알고리즘의 시간 복잡도는 O(y)인데요. O(lgy)로 더 빠르게 할 수 있는 알고리즘을 구현하시오.

 

 

주의사항

return x ** y는 답이 아닙니다. 우리는 거듭 제곱을 구하는 원리를 파악하여 효율적인 ‘알고리즘’을 구현하십시오.

 

 

 

❧ 테스트 셋

def power(x, y):
    # Code

# Test
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

 

 

❧ 출력 예시

243
15625
40353607

 

---

❧ 정답

def power(x, y):
    if y == 0:
        return 1
    if y % 2:
        return x * power(x, y // 2) * power(x, y // 2)
    else:
        return power(x, y // 2) * power(x, y // 2)


print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

 

1️⃣ 시간 복잡도 : O(logn)

2️⃣ 분할 정복

3️⃣ 홀수인 경우, x를 한번 더 곱해줌