[ 프로그래머스 - Kotlin ] 피보나치 수 ( 코틀린 )

( 연습문제 / 피보나치 수 )

[문제]

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2)가 적용되는 수입니다.

예를 들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

 

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

• n은 1 이상, 100000 이하인 자연수입니다.

입출력 예시

n	return
3	2
5	5

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

[풀이]

먼저 n + 1 크기의 배열을 1로 초기화합니다.

이후 3부터 n까지 반복을 통하여 2칸 이전의 수와 1칸 이전의 수를 더하여 현재 칸에 값을 넣어주며 반복합니다.

마지막으로 구하고자 하는 n번째 피보나치 수를 배열의 n번째 칸에서 꺼내어 출력합니다.

---

[주의]

피보나치수를 쉽게 구하는 방법은 재귀를 사용하는 방법도 있지만 이미 수행한 연산을 반복적으로 수행하여 시간 복잡도가 O(2^n)이 됩니다.

아래 그림은 5번째 피보나치를 재귀를 통하여 구할 때 2번째 피보나치 수를 3번이나 구하게 되는 과정을 그림으로 표현한 것입니다.

 

재귀로 구현시 걸리는 시간복잡도를 이해하기 위한 그림입니다.

이 문제의 경우 n이 100,000까지 이므로 재귀로 구현했을 경우 대략 2^100,000이라는 말도 안 되는 시간 복잡도가 나옴으로 메모리제이션을 통해서 구현해야 합니다.

---

[코드]

class Solution {
    fun solution(n: Int): Int {
    	// n+1 크기의 배열을 1로 초기화
        var answer = IntArray(n + 1){ 1 }
        // 3부터 n까지 반복하며 피보나치 수를 배열에 저장해 줍니다.
        (3..n).forEach{ answer[it] = (answer[it - 2] + answer[it - 1]) % 1234567 }
        // 배열에 n번 칸에 들어있는 숫자를 반환합니다.
        return answer[n]
    }
}

문제 링크

코딩테스트 연습 - 피보나치 수

 

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄