[프로그래머스 lv2] 피보나치 수

코딩테스트 연습 - 피보나치 수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 피보나치 수

 

문제점 : 테스트케이스 7번부터 시간초과가 뜸

매번 정수의 범위에 신경쓰지 않아서 이런 일이 발생!!!!!!!!!!!!

#include <string>
#include <vector>

using namespace std;

int fibo=0;
int solution(int n) {
    int answer = 0;
    if(n==0)
    {
        fibo=0;
    }else if(n==1)
    {
        fibo=1;
    }else
    {
        fibo=solution(n-2)+solution(n-1);
    }
    
    answer=fibo%1234567;
    
    return answer;
}

 

해결 : 재귀를 이용한 방법은 시간이 오래 걸리고 비효율적임. 중복연산이 발생하여 계산이 기하급수적으로 늘어남

이를 방지하기 위해 사용하는 것이 메모이제이션

#include<string>
#include<vector>
using namespace std;
 
int F[100010];
 
int solution(int n)
{
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        F[i] = F[i - 1] + F[i - 2];
        F[i] = F[i] % 1234567;
    }
    return F[n];
}

 

- 메모이제이션: 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산을 피하고 계산 속도를 향상시켜주기 위한 기법

메모이제이션은 배열을 하나 만들어서 연산된 값을 저장하여 기억하고, 중복된 연산이 나왔을 때, 해당 연산을 생략함으로써 계산 속도를 보다 원활하고 빠르게 하기 위해 사용

 

- 다이나믹프로그래밍(DP): 큰 문제를 작은 문제로 분할하여 계산하는 방식. TOP-DOWN, BOTTOM-UP 방식이 있음.

 

다이나믹 프로그래밍은 연산 속도와 메모리 공간을 최대한으로 활용하고 싶을 때 생각할 수 있음.

동적 계획법이라고도 불리며 DP는 다음 조건을 만족할 때 사용

1. 최적 부분 구조 (Optimal Substructure)
   큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미
2. 중복되는 부분 문제 (Overlapping Subproblem)
   동일한 작은 문제를 반복적으로 해결해야 하는 경우

 

반복문을 이용해서 작은 값부터 순차적으로 값을 구해서 가는 DP의 BOTTOM-UP 방식 사용

 

 

 

 

 

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) (velog.io)

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

[ 프로그래머스 피보나치 수(Lv2) ] (C++) :: 얍문's Coding World.. (tistory.com)

[ 프로그래머스 피보나치 수(Lv2) ] (C++)