golang, 피보나치 수열 함수 예제 2

golang, 피보나치 수열 함수 예제 2

 

앞에서 다룬 피보나치 수열 함수와 비교해보자.

 

package main

import (
  "fmt"
)

// 피보나치 수열 값 구하는 함수
func fibonacci(n int) int {
  if n <= 1 {
    return n
  }
  prev, current := 0, 1
  for i := 2; i <= n; i++ {
    prev, current = current, prev+current
  }
  return current
}

// 동적 메모이제션(재활용)으로 피보나치 수열 값 구하는 함수
var memo = make(map[int]int)

func fibonacci_mdp(n int) int {
  if n <= 1 {
    return n
  }

  if val, ok := memo[n]; ok { // 동적 메모이제이션으로 저장된 값이 있으면 돌려줌
    return val
  }

  memo[n] = fibonacci_mdp(n-1) + fibonacci_mdp(n-2) // 메모이제이션으로 계산하며 찾기
    return memo[n]
}

func main() {
  for i := 1; i <= 10; i++ {
    fmt.Printf("%d : %d, %d\n", i, fibonacci(i), fibonacci_mdp(i))
  }
}

 

 

mod 파일 생성: 

go mod init project_go/fibonacci

 

main 빌드: 

go build main.go

 

실행:

./main.exe

 

[실행 결과]

1 : 1, 1
2 : 1, 1
3 : 2, 2
4 : 3, 3
5 : 5, 5
6 : 8, 8
7 : 13, 13
8 : 21, 21
9 : 34, 34
10 : 55, 55