[알고리즘] 피보나치 수열

오늘은 피보나치 수열을 풀어보겠습니다.

 

피보나치 수열이란?

앞의 두개의 숫자를 합하여 다음 숫자가 되는 수열입니다.

1, 1, 2, 3, 5 .... 이렇게 되겠죠.

 

n번째 까지의 피보나치 수열을 구하는 문제를 풀어봅시다.

구현 방법은 간단합니다.

배열을 하나 만들고 for문을 이용해서 해결했습니다.

피보나치 수열에 첫번째와 두번째 값은 항상 1, 1이기 때문에 0번째와 1번째 인덱스에는 1을 넣어줬습니다.

 

for문을 이용해 풀면 간단한데

재귀함수를 이용해서 풀어보겠습니다.

마찬가지로 첫번째와 두번째는 1이 들어가니 1은 고정으로 넣어줍니다

그리고 앞의 두개 숫자를 더해주면서 재귀함수를 호출합니다.

 

단, n이 5처럼 적은 숫자가 들어갔을때는 빠르게 연산이 되지만 45처럼 큰 숫자가 들어가면

뒤로 갈수록 결과값이 느리게 찍힙니다.

재귀함수를 이용해 풀게 되면 그림과 같이 같은 함수를 몇번씩 반복하게 됩니다

fib(1)만 해도 3번을 호출했네요

이러한 과정이 숫자가 커질수록 많아지게 되고 처리 속도가 느려지게 됩니다.

 

여기서 메모이제이션이란것을 사용해 봅시다.

 

메모이제이션이란(Memoization)?

동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써

중복 계산을 방지할 수 있게 하는 기법입니다.

동적 계획법(Dynamic Programming, DP)을 구현하는 방법 중 하나입니다.

캐싱(caching)이라고도 합니다.

 

동적 계획법(Dynamic Programming, DP)이란?

• DP란 '동적 계획법'이라고도 불리는 알고리즘
• 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 / 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
• DP는 다음의 조건을 만족할 때 사용할 수 있음
  1. 최적 부분 구조 (Optimal Substructure)
     큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미
  2. 중복되는 부분 문제 (Overlapping Subproblem)
     동일한 작은 문제를 반복적으로 해결해야 하는 경우

 

그럼 메모이제이션을 사용하여 다시 코드를 짜 보면

fibo라는 배열로 한번 계산했던 것들을 저장할 곳을 만들어 줬습니다.

그리고 fibo[n]에 값이 들어가 있다면 0보다 클태니

(fibo 배열 크기를 동적으로 할당해주면 안에 값들이 0으로 되어있습니다)

fibo[n]에 저장된 값들을 꺼내 쓸수 있습니다.

 

그럼 위에서 몇번씩 반복했던 작업들을 저장된 값에서 가져오면 되니 이렇게 확 줄일수 있습니다.

 

for문으로 풀었을 때와 재귀함수로 풀었을 때 어떤 차이가 있을까요

 

먼저 bottom up 방식과 top down 방식에 대해 알아보겠습니다

탑다운(Top-Down)

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
• 탑다운(메모이제이션) 방식은 '하향식'이라고도 한다.
• 점화식을 이해하기 쉬운 장점이 있다.

※ DP와 메모이제이션 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하므로 DP와는 별도의 개념이다. --> 한 번 계산된 결과를 담아 놓기만 하고 DP를 위해 활용하지 않을수도 있다.

 

바텀업(Bottom-Up)

• 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
• 바텀업 방식은 '상향식'이라고도 한다.
• 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.

 

 

For문으로 풀었을 때

시간복잡도 O(n)

Bottom up 방식

 

재귀함수로 풀었을 때

시간복잡도 O(2ⁿ) 메모이제이션을 사용 했을 시 O(n)

Top down 방식

 

 

시간복잡도는 O(n)이어도 for문을 사용하는게 아무래도 함수 호출하고 stack 사용하고 하는 재귀함수보다

성능상 더 좋습니다.

 

 

 

출처 : https://velog.io/@kimdukbae/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming

이미지 출처 : 나무위키