피보나치 수열
-
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제곱을 구하는..
-
Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basicC 자료구조/1. 재귀함수 2020. 7. 28. 19:28
1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피보나치 수열의 점화식이다. 2. 구현 구현에 앞서서, 각 행렬들을 구조체로 정의하고, 행렬들 간의 곱셈을 하는 함수들을 만들어보자. 프로그램 실행결과 3. 헤더 파일 & 소스 파일 위의 내용을 이해했으면 아래로 가보자. designatedroom87.tistory.com/49 Fibonacci Sequence - 행렬을 이용한 분할 정복 방법 advanced 1. 개념 designatedroom87.tistory.com/41?category=868275 Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basic 1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피..
-
3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기C 자료구조/1. 재귀함수 2020. 6. 8. 12:10
피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피보나치 수열 ) 아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 designatedroom87.tistory.com 아래는 memoization 방법을 이용해 피보나치 수열을 구할 알고리즘이다. 앞서, 피보나치 수열을 구할 때, 이미 구한 항의 값을 다시 구하는 것이 문제라 하였는데, 여기서 기록을 통해 이를 해결하고자 한다. 즉, 기록한 항이 있으면 그 값을 리턴하면 되고,..
-
2. Fibonacci Sequence( 피보나치 수열 )C 자료구조/1. 재귀함수 2020. 6. 8. 11:48
아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 수열의 4번째 항을 중복으로 구한다. 즉, 이미 알아낸 항의 값을 다시 구하려고 한다. 이에 대한 한 가지 방법은 뒤에서 설명하도록 한다. 아래로 이동해서 중복을 제거하는 방법을 알아보자. designatedroom87.tistory.com/4 3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기 피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피..