종만북 7장 [w/ Python] - 분할정복 예제

- 가장 가까운 수 찾기

 

# 정렬된 n개의 숫자 중 정수 m과 가장 가까운 값 찾기
 
# 재귀 없이 풀이
def findNum(n, m):
    # 시작 인덱스와 끝 인덱스
    start = 0
    end = len(n)-1
    while True:
        mid = (start+end)//2
        # 중간 값이 타겟과 같을 때 출력
        if n[mid] == m :
            return n[mid]
        # 종료 조건, 요소가 2개만 남았을 때 차이가 작은 것 출력
        elif end - start == 1:
            if abs(m-n[start]) > abs(n[end]-m):
                return n[end]
            else:
                return n[start]
        if n[mid] < m :
            start = mid
        else :
            end = mid
 
 
# 재귀로 풀이
def getNearestNum(n,m):
    if len(n) == 1:
        return (n[0],n[0])
    elif len(n) == 2:
        return (n[0],n[1])
    
    mid = len(n)//2
 
    if n[mid] >= m:
        # mid가 포함 될 수 있으므로 항상 mid가 범위에 포함 되어야 한다.
        return getNearestNum(n[:mid+1],m)
    else :
        return getNearestNum(n[mid:],m)
        
def getNumber(n,m):
    cknum1, cknum2 = getNearestNum(n,m)
    if abs(cknum2-m)>abs(m-cknum1):
        return cknum1
    else:
        return cknum2
 
 
n = list(map(int,input().split()))
m = int(input())
 
print(getNumber(n,m))

 

- 거듭제곱 구하기

# m^n 구하기
LIMIT_NUMBER = 1000000007
 
def getPower(m, n):
    # return getPower(m,n-1) * m 은 O(N) 의 선형 시간이 걸려 속도가 느리다.
    # n이 짝수일 때와 홀수일 때로 나눈다.
    # 기저 조건(n == 1이면 반환을 시작한다)을 만들어야한다.
    # 기저 조건을 n == 1이 아니라 n == 0 이면 1로 하였다.
    # 기저 조건이 n == 1이면 recursive depth 오류가 발생한다.
    if n == 0:
        return 1
    
    if n % 2 == 0:
        half = getPower(m, n//2)
        return  (half * half) % LIMIT_NUMBER
    else:
        half = getPower(m, (n-1)//2)
        return (half * half * m) % LIMIT_NUMBER

 

 

 

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략