14-01 분할 정복(Divide and Conquer)

 

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

.분할정복 알고리즘

 1)정의

 -분할 정복이란 크고 방대한 문제를 풀기 용이하게  조금씩 나누고 풀이한 다음

 다시 합쳐 해결하는 알고리즘.

 

2.병합 정렬(Merge Sort)

 1)정의

 -분할정복 알고리즘을 기반으로 둔 정렬 알고리즘.

 2)작동 방식

 -분할 및 병합 과정

 -정렬 과정

3.거듭 제곱 계산(Exponentiation)

 1)개요

 -거듭 제곱은 같은 수나 식을 거듭 곱하는 일

 -거듭제곱은 같은 수의 반복이기에 한번 계산한 값이 있다면 그대로 수식에 적용 시킬 수 있다.

 -수학에서 식을 치환하여 쉽게 볼 수 있게 만드는 것은 분할정복과 같다.

 -C는 거듭제곱할 수 n 거듭제곱 수.

4.피보나치의 수 구하기

 1)피보나치의 수(Fibonacci numbers)

 -첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열.

 2)공식

 -F(n)는 n번째 항의 피보나치의 수.

3)행렬 풀이

 -피보나치의 수를 2x2 정사각 행렬 변환.

-정사각 행렬을 n번 곱하면 거듭 제곱같이 식을 얻을 수 있다.