[코드잇] 알고리즘 연습 level1 02. 거듭 제곱 빠르게 계산하기 Python

거듭 제곱 빠르게 계산하기.py

실습과제
거듭 제곱을 계산하는 함수 power를 작성하고 싶습니다. power는 파라미터로 자연수 x와 자연수 y를 받고, x^yx
​
y
​
​
를 리턴합니다.


가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 xx를 yy번 곱해 주는 방법입니다.


def power(x, y):
    total = 1
    
    # x를 y번 곱해 준다
    for i in range(y):
        total *= x
    
    return total

이 알고리즘의 시간 복잡도는 O(y)O(y)인데요. O(\lg{y})O(lgy)로 더 빠르게 할 수는 없을까요?


주의: return x ** y는 답이 아닙니다. 우리는 거듭 제곱을 구하는 원리를 파악하여 효율적인 ‘알고리즘’을 구현하고 싶은 것입니다.



정답
생각 과정
거듭제곱 하는 문제를 부분문제로 나누어 보앗다
basecase는
y ==1 인 경우이다 그런경우는 x*y를 return하면 끝남


가장 작은 경우의 수
power(2,2) 의 부분 문제는 power(2,2//2)*power(2,2//2)
짝수의 경우라면 이런식으로 전부 해결가능

ex 홀수라면 나머지가 남기때문에 나머지도 곱해주면 된다
power(2,5) 의 부분 문제는 power(2,2//2)*power(2,2//2)*power(2,2%2)

홀수에서는 basecase에 0이 추가된다
0일때는 1을 반환하면 된다




def power(x, y):
    # 코드를 작성하세요.
    if y ==0:
        return 1
    if y == 1:
        return x*y

    return power(x,y//2)*power(x,y//2)*power(x,y%2)

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


###정답으로 나왓지만 사실 틀린거 같음 왜냐하면 재귀를 해서 같은 시간 복잡도가 나와서
#정답의 포인트는 재귀를 얼마나 덜 쓰냐이다
#subresult = power(x, y // 2)를 사용해서 계산을 훨씬 덜했다...
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


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