프로그래머스 피보나치수열 코틀린 다이나믹 프로그래밍활용

https://programmers.co.kr/learn/courses/30/lessons/12945

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

안녕하세요!

 

프로그래머스에서 피보나치 수 문제를 풀어봤습니다!

이 문제는 2단계 문제입니다!

 

문제 설명

피보나치 수는 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

---

 

사실 이 문제는 효율성 체크를 하지 않아서 그냥 단순한 재귀함수를 이용해서 문제를 풀어도 풀수 있는 문제였습니다

 

그래도 다이내믹 프로그래밍으로 풀면 좀 더 좋은 빠른 결과를 얻을 수 있기도 하고 좀 더 저에게 도움이 될거같아서 다이나믹 프로그래밍으로 풀었습니다!

 

다이나믹 프로그래밍(동적 계획법에 대해서 간략하게 설명하면)

 

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

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

추가적으로 설명을 보태자면, 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.

동적프로그래밍의 장점으로 모든 작은 문제들에 대해 한번씩만 풀면서 정답을 어딘가에 저장해 둡니다. 이를 활용하여 보다 큰 문제를 풀어 나갈때 똑같은 작은 문제에 대해 앞서 저장한 메모의 결과값을 이용합니다.

이러한 동적 프로그래밍 기법 중 하나로 메모이제이션(Memoization)이 있습니다.

 

 

이 문제는 좀 특이 했던 점은 아무 생각없이 풀면 테스트 13,14 테스트케이스가 런타임 에러가 뜹니다...

아마 제 생각에는 재귀 호출의 깊이가 초과 되어서 런타임 에러가 나온걸로 추측하고 있습니다!

그래서 num의 값이 1,2,3 일때는 재귀호출을 하지 않고 바로 해당 값을 리턴하는 방식으로 구현해야합니다! 

즉 1 과 2일때는 1 리턴

3일때는 재귀를 호출하는 것이 아닌 바로 2를 리턴합니다!

이와 마찬가지로 5는 재귀 호출이 아닌 5를 바로 리턴합니다

 

class Solution {
    companion object{
        lateinit var memo : IntArray
    }
    fun solution(n: Int): Int {
        var answer = 0
        memo = IntArray(n+1)
        answer = fibonacci(n)

        return answer
    }

    fun fibonacci(num: Int) : Int{
        return if(num==0){
            0
        } else if(num<=2){
            1
        }else if(num==3){
            2
        }else if(num==5){
            5
        } else{
            if(memo[num]!=0){
                memo[num]
            }else{
                memo[num] = (fibonacci(num-1)+fibonacci(num-2))%1234567
                memo[num]
            }
        }
    }
}



fun main(){
        println(Solution().solution(3))
}