설명
- 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘
- 퀵 정렬, 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환 문제가 대표적
설계 전략
- 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눔
- 정복(Conquer) : 나눈 작은 문제를 각각 해결
- 통합(Combine) : (필요하다면) 해결된 해답을 모음
거듭 제곱 (Exponentiation)
- O(n)
# 반복문을 이용한 거듭제곱
def Iterative_Power(x, n):
result = 1
for i in range(1, n+1):
result *= x
return result
- O(logn)
# 분할 정복을 이용한 거듭제곱
def Recursive_Power(x, n):
if n == 1: return x
if n % 2 == 0:
y = Recursive_Power(x, n//2)
return y * y
else:
y = Recursive_Power(x, (n-1)//2)
return y * y * x
'Algorithm' 카테고리의 다른 글
Linear Queue (선형 큐) (0) | 2021.03.03 |
---|---|
Quick Sort (퀵 정렬) (0) | 2021.03.02 |
Backtracking (백트래킹) (0) | 2021.02.25 |
DFS (Depth First Search, 깊이 우선 탐색) (0) | 2021.02.24 |
Memoization & DP (Dynamic Programming) (메모이제이션 및 동적 계획법) (0) | 2021.02.24 |