분할 정복 알고리즘 {병합 정렬, 거듭 제곱 계산, 피보나치 수 구하기 }

분할정복 알고리즘: 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나뉜 문제들을 각각 풀어서 결국 전체 문제의 답을 얻는 기법이고 핵심은 문제를 잘게 나누는 것이다.

대략적인 순서

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

2) 정복: 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 1을 수행하고 그렇지 않다면 하위 문제를 푼다.

3) 결합: 2번을 통해 구한 답을 취합한다.

분할 정복 알고리즘을 구현할 때 재귀 호출을 많이 사용하는데 이 때문에 문제를 잘게 나누어 얻은 알고리즘의 효율성이

재귀 호출 비용 때문에 깎이기도 한다.

병합정렬: 데이터를 나눈 후 정렬하면서 합치는 알고리즘.

순서

1) 정렬한 데이터를 반으로 나눈다

2) 나뉜 하위 데이터의 크기가 2 이상이면 이 하위 데이터에 1번을 반복한다.

3) 동일한 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단, 병합할 때 데이터의 원소는

정렬 기준에 다라 정렬한다.

4) 데이터가 원래대로 모두 하나가 될 때까지 3번을 반복한다.

병합 정렬에서 정렬을 수행하는 방식

1) 두 데이터를 합친 만큼 비어있는 공간을 마련.

2) 두 데이터의 첫번째 요소들을 비교하여 작은 요소를 새 공간에 추가, 추가된 요소는 원래 데이터에서 삭제

3) 양쪽 데이터가 빌 때까지 단계 2를 반복.

거듭제곱 계산: 거듭 제곱 시 C^n을 계산하려면 일반적으로 C자신을 n번 곱해야 하는데

거듭제곱을 활용하면 효율적으로 계산할 수 있다.

C^8 = C^4 x C^4 = (C^4)^2 = ((C^2)^2)^2으로 표현이 가능함

이런 식으로 지수를 반으로 나눠가며 계산하면 C를 8번 곱하지 않고 C^2에 제곱을 두 번 더 반복하면 결과를 얻을 수 있음.

이렇게 지수를 반으로 나눠 가는 알고리즘 수행 시간은 O(log n)이며 처음의 O(n) 보다 성능이 비약적으로 향상됨.

피보 나치 수 구하기

기본적인 피보나치 수열은 다음과 같이 정의된다.

이 수열은 다음과 같은 행렬 곱으로 표현될 수 있다.

정사각형 행렬 A에 대해서는 다음과 같은 성질이 있다 n=m일 때

이런 성질을 이용하면 n번째 피보나치 수를 구할 때 n/2번째 행렬을 제곱하면 된다.

2/n번째 피보나치 수는 n/2 / 2번째 피보나치 수를 제곱하면 된다.

예시) 피보나치 수 7을 구하기

행렬의 0,0이 7이 되려면 n은 6으로 계산하면 된다.

M^6 = (M^3)^2 ,

M^3 = M^2 x M

결과

이런 식으로 계산하면 M^6의 0,0 자리에는 m^7인 13이 결과.

피보나치 수 7 = 13

나는아직배고프다