일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- SQL_Injection
- RSA
- 웹
- 코드업
- ReflectedXSS
- 심층학습
- C언어
- 프로그래머스
- codeup
- Cross Site Scripting
- 보안
- dsa
- 딥러닝
- dvwa
- 기계학습
- 암호학
- 공개키
- 파일구조
- 인공지능
- XSS
- RVA
- Database
- 디피헬먼
- StoredXSS
- db
- SQL
- 알고리즘
- injection
- 머신러닝
- ImageBase
- Today
- Total
Ye0ngJae
[CodeUp] 1916번 "피보나치 수열 (Large)" C언어 풀이 본문
문제
피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다. 첫 번째 수와 두 번째 수는 모두 11이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치수열을 나열해 보면 다음과 같다.
자연수 NN을 입력받아 NN번째 피보나치 수를 출력하는 프로그램을 작성하시오.
단, NN이 커질 수 있으므로 출력값에 10,00910,009를 나눈 나머지를 출력한다.
입력 예시
7
출력 예시
13
답안
코드
#include <stdio.h>
int arr[201];
int f(int a){
if(a < 3)
return 1;
if(arr[a] != 0)
return arr[a];
return arr[a] = (f(a - 1) + f(a - 2)) % 10009;
}
int main(){
int a;
scanf("%d", &a);
printf("%d", f(a));
return 0;
}
풀이
처음 피보나치수열을 풀기 위하여 문제에 접근할 때, 시간 복잡도를 생각하지 않고 접근했었습니다. 따라서 아래와 같이 코드를 작성하였는데
#include <stdio.h>
int sum=1;
int f(int a){
if(a < 3){
return 1;
}
return f(a-1) + f(a-2) % 10009;
}
int main(){
int a;
scanf("%d", &a);
printf("%d\n", f(a));
return 0;
}

시간 초과가 뜨는 대참사가 나버렸다. 따라서 해당 문제를 해결하기 위해 열심히 구글링을 해본 결과
메모리제이션이라는 개념을 알아내었습니다.
따라서 메모리제이션 기법을 이용하여 피보나치 수열 알고리즘을 다시 작성한 결과 아래와 같이 코드를 완성 하였습니다.
#include <stdio.h>
int arr[201];
int f(int a){
if(a < 3)
return 1;
if(arr[a] != 0)
return arr[a];
return arr[a] = (f(a - 1) + f(a - 2)) % 10009;
}
int main(){
int a;
scanf("%d", &a);
printf("%d", f(a));
return 0;
}
우선 계산한 값을 담을 arr 배열을 선언해주고, 계산한 결과를 해당 배열에 저장해줍니다. 만일 해당 배열 값이 이미 계산한 적이 있는 값이라면 해당 값을 그대로 return해줍니다. 만일 해당 배열 값이 계산한 적이 없는 값이라면 계산하고 배열에 저장해줍니다. 따라서 시간 복잡도를 매우 획기적으로 줄일 수 있었습니다.
메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)
이번 포스팅에서 다루는 memoization 메모이제이션은 DP 동적 계획법 알고리즘에서 핵심이 되는 기술로 중복 계산을 제거함으로써 프로그램의 전체적인 실행 속도를 빠르게, 성능을 향상할 수 있
wondytyahng.tistory.com
https://ssminji.github.io/2020/02/05/the-cake-thief/
[알고리즘] Memoization(메모이제이션) 꿀이해
Memoization(메모이제이션) Memoization은 주어진 입력값에 대한 결과를 저장함으로써 같은 입력값에 대해 함수가 한 번만 실행되는 것을 보장한다(보통 딕셔너리에 저장한다). 예를 들어보자. n번째
ssminji.github.io
'알고리즘 > C언어' 카테고리의 다른 글
[BOJ] 10872번 "한수" C언어 풀이 (0) | 2022.04.14 |
---|---|
[BOJ] 10872번 "팩토리얼" C언어 풀이 (0) | 2022.04.14 |
[CodeUp] 1566번 "함수로 거듭제곱 리턴하기" C언어 풀이 (0) | 2022.04.12 |
[CodeUp] 1555번 "함수로 n까지의 합 리턴하기" C언어 풀이 (0) | 2022.04.12 |
[CodeUp] 1535번 "함수로 가장 큰 값 위치 리턴하기" C언어 풀이 (0) | 2022.04.12 |