50. Pow(x, n)

50. Pow(x, n)

 

Time Limit Exceeded

class Solution:
    def myPow(self, x: float, n: int) -> float:        

        res = 1
        if n>0:
            for i in range(1, n+1):
                res *= x
        elif n <0: 
            for i in range(1, -1*n + 1):
                res /= x

        return res

 

이진 분할(분할 정복) 기법을 활용하여 효율적으로 해결할 수 있습니다. 이는 반드시 이진 트리를 명시적으로 사용하는 것은 아니지만, 개념적으로 재귀적으로 문제를 반으로 나누는 방식이 이진 트리의 구조와 유사합니다.

 

 

def myPow(x: float, n: int) -> float:
    # 음수 지수 처리
    if n < 0:
        x = 1 / x
        n = -n
    
    def helper(x, n):
        if n == 0:  # x^0 = 1
            return 1.0
        half = helper(x, n // 2)  # x^(n//2)
        if n % 2 == 0:  # 짝수 지수
            return half * half
        else:  # 홀수 지수
            return half * half * x
    
    return helper(x, n)

 

이진 트리와의 연관성

이 알고리즘의 재귀 호출 구조는 이진 트리의 왼쪽/오른쪽 하위 트리로 나뉘는 구조와 유사합니다:

• 짝수/홀수를 기준으로 하위 문제로 분할됩니다.
• 각 하위 문제는 재귀적으로 처리되며, 최종 결과를 병합합니다.