리그캣의 개발놀이터

optimal substructure - 피보나치 수 본문

알고리즘/백준

optimal substructure - 피보나치 수

리그캣 2018. 2. 1. 22:19

피보나치 수를 구하다 보면

겹치는 호출이 생기게 된다



이럴땐 다음과 같이 메모하여 저장해 줄 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int memo[100];
 
 
int fibonacci(int n){
 
    if (n <= 1){
 
    return n;
 
    } else {
 
        if(momo[n]>0){
 
            return memo[n];
 
        }
 
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
 
    return memo[n]
 
    }
 
}
cs


저작자표시

'알고리즘 > 백준' 카테고리의 다른 글

다이나믹 프로그래밍 이해하기 - 피보나치  (0) 2018.02.02
백준 알고리즘 1149번 - RGB 거리  (0) 2018.02.01
백준 알고리즘 1003번 - 피보나치 함수  (0) 2018.02.01
백준 알고리즘 10845 - 큐  (0) 2018.01.30
백준 알고리즘 2747번 - 피보나치 수  (0) 2018.01.30
'알고리즘/백준' Related Articles more
Comments