WEEK02- TIL 분할정복

분할정복법 (Divide & Conquer): 큰 문제를 작은 문제로 분할해 재귀적으로 해결

☞ 간단히, 큰 문제 보다는 작은 문제를 해결하기 쉬우니까~

 

base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않아도 바로 답을 알 수 있는 경우

recursive case: 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우

 

간단 예제(맛보기) ex.

Q. 1~8까지의 합을 구하라 [recursive case라고 생각하며 풀어보기]

→ 과정

1. 1-4 와 5-8로 쪼개서 구해보자. //그래도 너무 크다?

2. 1-4범위를 1-2와 3-4로 또 쪼개서 구해봄 //근데도 아직 큰거야..

3. 1-2범위를 1과 2로 쪼개서 구해본다! // 1에서 1을 구하고 2에서 2를 구하는 걸 보니 너무 쉽네? == base case

 

- 분할 정복 기반의 알고리즘

def RecursivePower(c,n):
    if n==1:
        return c
    if n%2==0:
        y = RecursivePower(c,n/2)
        return y*y
    else:
        y= RecursivePower(c,(n-1)/2)
        return y*y*c