피보나치 수열이 무엇인지 아주아주 간략하게 적어보면
f(n) = f(n-1) + f(n-2) 이다.
1, 1, 2, 3, 5, 8, 13, ... ... 이런 식으로 전개되는 수열이다.
어떤 언어이든 코딩 공부할 때 피보나치 수열을 코딩해보라는 문제는 꽤 자주 나온다.
피보나치 수열은 재귀호출을 이용해서 간단하게 구현할 수 있다.
// 재귀호출을 이용한 피보나치 수열
func Fibonacci1(x int) int {
if x <= 2 {
return 1
} else {
return Fibonacci1(x-1) + Fibonacci1(x-2)
}
}
간단하게 구현할 수 있지만, 이 알고리즘에는 맹점이 있는데 성능이 매우 구리다는 것이다. Fibonacci1(5)을 알고 싶다고 할 때, 이를 계산하기 위해서는 Fibonacci1(4) + Fibonacci1(3)을 알아야하고, Fibonacci1(4)를 알기 위해 또 Fibonacci1(3)과 Fibonacci1(2)를 알아야하고, Fibonacci1(3)을 알기 위해 Fibonacci1(2)와 Fibonacci1(1)을 알아야한다. 계산에 계속해서 중복이 들어간다. 그렇기 때문에 숫자가 커지면 성능이 아주 구려진다. 성능을 개선하기 위해서는 코드가 덜 간결해질 수는 있지만 반복문을 쓰는 것이 좋다.
// 재귀호출이 아닌 반복문을 통한 피보나치 수열
func Fibonacci2(n int) int {
var index int
var last1 int
var last2 int
var result int
if n <= 2 {
return 1
}
last1 = 1
last2 = 1
for index = 2; index < n; index++ {
result = last1 + last2
last1 = last2
last2 = result
}
return result
}
이른 바 동적 프로그래밍을 활용한 알고리즘이다. 둘의 동작시간을 비교해보면
package main
import (
"fmt"
"time"
)
func main() {
// 두 알고리즘의 실행시간 비교
// 재귀호출의 경우
startTime := time.Now()
result := Fibonacci1(50)
runTime := time.Since(startTime)
fmt.Printf("재귀호출을 이용한 피보나치 수열 알고리즘 결과는 %d입니다\n", result)
fmt.Printf("실행시간은 %s입니다\n", runTime)
startTime = time.Now()
result = Fibonacci2(50)
runTime = time.Since(startTime)
fmt.Printf("반복문을 이용한 피보나치 수열 알고리즘 결과는 %d입니다\n", result)
fmt.Printf("실행시간은 %s입니다\n", runTime)
}
// 재귀호출을 이용한 피보나치 수열 알고리즘 결과는 12586269025입니다
// 실행시간은 1m1.4258082s입니다
// 반복문을 이용한 피보나치 수열 알고리즘 결과는 12586269025입니다
// 실행시간은 0s입니다
100번째까지도 실행시켜보려고 했는데 드럽게 오래걸려서 그냥 껐다. 속도는 비교할 수 없을 정도로 후자가 빠르다. '누워서 읽는 알고리즘'을 보다가 golang으로 끄적여봤다. 그리고 기존에 tucker님 강의 보다가 재귀호출을 이용한 코드를 짜봤는데 오류가 있는 것을 오늘의 독서 덕분에 발견하여 바로잡아봤다.
