분할 정복
-
Fibonacci Sequence - 행렬을 이용한 분할 정복 방법 advancedC 자료구조/1. 재귀함수 2020. 7. 29. 17:36
1. 개념 designatedroom87.tistory.com/41?category=868275 Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basic 1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피보나치 수열의 점화식이다. 2. 구현 구현에 앞서서, 각 행렬들을 구조체로 정의하고, 행렬들 간의 곱셈을 하는 함수들을 만들어보�� designatedroom87.tistory.com 앞에서 피보나치 수열을 구할 때, 행렬의 연산을 통해 했는데, 좀 더 빠른 연산을 수행할 수 있도록 변경해보자. 기본적인 아이디어는 거듭 제곱에 쓰인 방식과 같다. 2. 구현 기존에 만든 FiboMatPower 함수만 수정하면 된다. 이 함수의 역할은 FiboMat행렬의 n제곱을 구하는..
-
거듭 제곱 구하기 - 분할 정복 방법C 자료구조/1. 재귀함수 2020. 7. 28. 18:59
아래의 내용을 먼저 보고 오는 것도 좋다. designatedroom87.tistory.com/47?category=868275 거듭 제곱 구하기 - basic 1. 개념 거듭 제곱은 아래와 같은 점화식으로 표현된다. 우리가 위의 C^n을 구하기 위해서는 C^(n-1)을 구하면 된다. 2. 구현 프로그램 실행결과 3. 소스 파일 위의 내용을 이해했으면 분할 정복 방법 designatedroom87.tistory.com 1. 설명 위의 점화식에서, n이 홀수일 때의 []기호는 가우스 기호이다. 위의 식에 n을 8이라고 두면 위의 식에서, n = 8일 때의 값을 구하려면, C의 제곱을 먼저 구한 뒤에 두 번 더 반복해서 제곱을 하면 된다. 결국, 3번의 곱셈을 하면 된다. n이 만약에 홀수라면 (예를 들어 ..