프로그래머스 피보나치 수 Swift

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

Foma's 풀이

 

피보나치 수열은 F(n) = F(n-1) + F(n-2) 가 적용됩니다. 

 

고로 n-1번째와 n-2번째 적용된 수를 저장하는 것이 핵심이라고 생각됩니다. (n-1번째를 before로 n-2번째를 beforebefore로 부르겠습니다.)

 

우선 2이상의 n이 입력되므로 가장 최솟값이 2를 넣는다고 가정하면 F(2)를 구하기 위해선

 

before는 F(1) beforebefore는 F(0)를 더한 값이 될 것입니다. 

 

고로 before의 초기값을 1으로 beforebefore의 초기값을 0으로 설정하겠습니다. -> var before = 1

var beforebefore = 0

 

또한 n값을 저장할 numbers는 최소값이 2이므로 초기값을 2로 설정하겠습니다. -> var numbers = 2

 

또한 before값을 사전에 저장할 beforeCopy라는 변수도 만들어줍니다. -> var beforeCopy = 1

 

파라미터로 b(before)와 bb(beforebefore)와 n을 갖는 fibo라는 함수도 만들어주겠습니다. -> func fibo(_ b:Int,_ bb:Int,_ n:Int) -> Int{ ... }

 

beforeCopy 값을 b로 (before값이 변화되므로 미리 값을 저장해둡니다.) before값을 (bb + b) % 1234567로 나눈값 beforebefore를 before를 저장한 beforeCopy로 바꿔줍니다. ->

    beforeCopy = b

    before = (bb + b)%1234567

    beforebefore = beforeCopy

 

numbers를 1 증가시켜줍니다. (while문의 논리와 동일) ->  numbers += 1

 

numbers가 n보다 작다면 b에 before값을 bb에 beforebefore값을 n에 n을 넣어주고 재귀시켜주고 아니라면 before(n-1)과 beforebefore(n-2)를 더한것에서 1234567로 나눠준 나머지 값을 반환해줍니다.

 

if numbers < n {

        return fibo(before, beforebefore, n)

    }else{

        return (before + beforebefore)%1234567

    }

 

전체코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

var numbers = 2 var before = 1 var beforebefore = 0 var beforeCopy = 1   func solution(_ n:Int) -> Int {     return fibo(before, beforebefore, n) }   func fibo(_ b:Int,_ bb:Int,_ n:Int) -> Int{     beforeCopy = b     before = (bb + b)%1234567     beforebefore = beforeCopy           numbers += 1          if numbers < n {         return fibo(before, beforebefore, n)     }else{         return (before + beforebefore)%1234567     } } Colored by Color Scripter

헷갈린점

n번째 피보나치수를 1234567로 나눠준 나머지값을 반환하라길래 반복하다가 마지막 n번째만 나누면 되는줄 알았는데 모든 과정에서 1234567로 나눠준 나머지 값으로 설정해주어야했다.

func fibo(_ b:Int,_ bb:Int,_ n:Int) -> Int{

    ...

    before = (bb + b)%1234567

    ...

}

이 부분