거듭 제곱 빠르게 계산하기

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

def power(x, y):
    # 여기에 코드를 작성하세요
    # Base case
    if y == 0:
        return 1
    
    # 계산을 한 번만 하기 위해 변수에 저장
    subresult = power(x, y // 2)
    
    # Recursive Case
    # 문제를 문제 두 개로 나눠준다.(짝수인 경우, 홀수인 경우)
    # y가 무조건 한번은 홀수가 된다.
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult


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

 

 

 

해결과정

문제에서 소개된 반복문 솔루션을 그대로 재귀적으로 바꿔 보았지만, 이 알고리즘 역시 O(y)이다.

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

    # Recursive Case
    return x * power(x, y - 1)

---

재귀적인 O(y) 솔루션은 문제 크기를 1씩 줄여나갔다. O(lgy)를 위해서 문제를 나누어야한다.

 

재귀적 호출이 power(x, y-1)대신 power(x, y//2)와 같은 형태

 

짝수 / 홀수 인 경우를 나눠서 계산

---

def power(x, y):
    # 여기에 코드를 작성하세요
    # Base case
    if y == 0:
        return 1
    
    # 계산을 한 번만 하기 위해 변수에 저장
    subresult = power(x, y // 2)
    
    # Recursive Case
    # 문제를 문제 두 개로 나눠준다.(짝수인 경우, 홀수인 경우)
    # y가 무조건 한번은 홀수가 된다.
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult


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

이렇게 로직을 짜고 보니, 재귀의 개념이 아직 잘 이해가 가지 않는 것 같았다.

 

예를들어 2^8이라고 했을 때,

 

2^8 = 2^4 * 2^4

2^8 = (2^2 * 2^2) * (2^2 * 2^2)

2^8 = ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))

이렇게 되는 건 알겠지만, base case가 y == 0일경우 2^0으로 넘어가는 경우에는 1로 된다.

 

그렇다면 2^1승에서 다시 나뉘어서 2^0승 16번 이런식으로 넘어가지는 않는 것인가?

 

그렇게 되면 각각의 값이 1이 되어 버리는데 거기서 다시 bottom-up으로 올라가게 되면 값이 문제가 생기는 건 아닌지 궁금했다.

 

처음부터 하나씩 로직을 생각해보니 이해가 되었다.

 

2^7을 계산해보려고 한다.

 

power(2, 7)은 재귀 호출 해보면 2 * (2 * power(2, 1) * power(2, 1)) * (2 * power(2, 1) * power(2, 1))로 계산할 수 있다.

 

power(2, 1)을 호출해보면, 먼저 subresult = power(2, 0)이기 때문에 y == 0 Base case에 적용되므로 1을 반환한다.

 

그렇다면 1 % 2는 1이기 때문에 x * subresult * subresult로 계산되어 2 * 1 * 1이 된다.

 

따라서 power(2, 1)은 2가 return되므로

power(2, 7)은  2 * (2 * 2 * 2) * (2 * 2 * 2)가 된다.