Go로 재귀 함수 없이 피보나치 함수 만들기 with 백준 1003

백준 사이트의 1003번의 문제는 문제에서 보여주는 피보나치 함수를 사용하면 100% 시간 초과가 날것입니다.

시간이 초과되는 이유는 재귀함수의 사용이라는 것은 대부분 감이 오실 것입니다.

 

하지만  재귀 없이 피보나치 만들기는 처음에는 당황스럽지만 재귀를 배열로 표현한다고

생각하시면 쉽게 이해하실 것입니다.

 

위 문제에서 fibonacci(3), fibonacci(2), fibonacci(1)를 배열로 생각해봅시다.

 

그러면 아래와 같은 코드로 표현이 가능해집니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
    // cmd로 입력받기 위한 bufio 선언
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)
	result := fibonacci(n)
	fmt.Fprintf(writer, "%d \n", result[n])
}

func fibonacci(n int) (result []int) {
	// 슬라이스 선언
	// result[0] = fibonacci(0), result[1] = fibonacci(1)
	result = []int{0, 1}
    
	for re := 2; re < n+1; re++ {
    	// go에서 슬라이스는 내부적으로 특정 크기를 넘을 경우 새로 배열을 복사합니다. 
        // 그로 인해 발생하는 버그 및 문제를 위해 다시 슬라이스에 할당해줍시다.
        // re가 2일 경우 result[2] = result[1] + result[0]
		result = append(result, result[re-1]+result[re-2])
	}
	return
}

 

이 문제는 1003에 정답은 아니며 단지 피보나치수열의 특정 번호 값을 가져오는 함수입니다.

 

하지만 위 피보나치에서 결과 값으로 나오는 값이 바로 1의 합입니다.

여기서  0의 개수를 구하려면 result의 배열 값의 순서를 바꾸면 됩니다.