[알고리즘] 19. 분할 정복 알고리즘

공부한 날짜: 2021. 11. 07

 

-분할 정복 알고리즘: 문제를 더 이상 나눌 수 없을 때까지 나누고, 나눠진 문제들을 각각 풂으로써 전체 문제의 답을 얻는 알고리즘

핵심: '문제 잘게 쪼개기'

 -요령

(1)분할(divde): 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다

(2)정복(conquer): 하위 문제가 분할 가능하면 (1) 반복, 분할 되지 않는다면 하위 문제를 푼다

(3)결합(combine): (2) 과정에서 정복된 답을 취합한다

 

1. 병합 정렬 : 나누고 합쳐라

(1) 정렬한 데이터 집합을 반으로 나눈다

(2) 나누어진 하위 데이터 집합의 크기가 2 이상이면 하위 데이터 집합에 대해 (1)을 반복

(3) 하위 데이터 집합 둘을 하나로 병합하고, 이때 원소는 순서에 맞춰서 정렬한다

 

(3)-1 두 데이터 집합을 합한 것 만큼의 비어 있는 데이터 집합을 마련

(3)-2 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가. 그리고 새 데이터 집합에 추가된 요소는 원래의 데이터 집합에서 삭제

(3)-3 양쪽 데이터 집합이 빌 때가지 (3)-2 과정 반복

 

2. 거듭 제곱

 

3. 피보나치 수열