[ 프로그래머스 ] 피보나치 수

 

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

 

문제 설명

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

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

 

 

문제 풀이

나의 풀이

첫번째 중첩함수 풀이 → 실패!

func solution(_ n:Int) -> Int {
    
    func f(_ n: Int) -> Int {
        if n == 0 {
            return 0
        }else if n == 1 {
            return 1
        }else {
            return f(n-1) + f(n-2)
        }
    }
    
    return f(n) % 1234567
}

 

 

n 값의 최대값이 100,000이기 때문에 너무 많은 중첩함수는 시간에러가 나는 것
나의 첫번째 풀이는 f(100,000) → f(99,999) + f(99,998) … 결국 2의 100,000번을 연산하는 셈

 

연산 횟수가 1억번을 넘어가면 시간 초과가 뜰 가능성이 존재하므로 n의 값이 50일 때의 연산 횟수는 2의 50승인 1,125,899,906,842,624 번이다. n값이 50을 넘어서 부터 이미 시간초과가 뜰 가능성이 있는 것이다.

 

그래서 for문으로 돌리기로 했다.

 

두번째 for문 풀이 → 실패!

func solution(_ n:Int) -> Int {
    
    var x = 0
    var y = 1
    
    for i in 1...n/2 {
        x = x + y
        y = y + x
    }
    
    return n % 2 == 0 ? x % 1234567 : y % 1234567
}

 

 

연산횟수가 O(n/2)로 줄어든다. 시간초과를 해결을 했다 하지만 실패 (signal: illegal instruction (core dumped)) 가 뜬다.

이는 Int 범위를 벗어난 연산 오류인 것 같았다.

 

F(10,000)의 값은 2.6863810024486E+208

F(100)의 값은 2.1892299583456E+20

F(50)의 값은 7,778,742,049

F(48)의 값은 2,971,215,073

 

n이 48일 때, Int의 최댓값인 2,147,483,647을 넘는다.

Int 타입으로는 이미 n이 48이 되었을 때부터 값을 초과가 하여 계산을 할 수 없다.

문제에서 1234567로 나눈 나머지를 구하라는 데는 이유가 있을 것이다.

 

나머지 연산을 뜯어보자.

이상하게 생긴 동그라미에 작대기를 그은 함수는 n의 나머지를 나타낸다.

모듈러 산술의 덧셈 공식에서

a+b 가 모듈러 n에서 c와 동치 관계를 나타낼 때, a를 n으로 나눈 나머지 + b를 n으로 나눈 나머지는 c를 n으로 나눈 나머지와 같다는 것이다. 전공때 배운거라 가물가물..

그래서 찾아봤더니 더 쉽게 설명한 나머지 연산의 성질이 있었다.

 

 

위의 성질을 바탕으로 다시 문제를 풀어보자.

 

세 번째 for문과 나머지 성질을 이용한 풀이 → 정답!

func solution(_ n:Int) -> Int {
    
    var x = 0
    var y = 1
    
    for i in 1...n/2 {
        x = ( x + y ) % 1234567 
        y = ( y + x ) % 1234567
    }
    
    return n % 2 == 0 ? x % 1234567 : y % 1234567
}

 

x와 y가 계산 될 때마다 나머지 연산을 해주어 Int값을 넘지 않도록 연산을 해준다.

사실 쉬운 문제인줄 알았더니 30분이나 걸렸다..

 

 

다른 사람 풀이

struct matrix2x2 {
    var _00, _01, _10, _11: Int

    init(_00: Int, _01: Int, _10: Int, _11: Int) {
        self._00 = _00 % 1234567
        self._01 = _01 % 1234567
        self._10 = _10 % 1234567
        self._11 = _11 % 1234567
    }

    init(m: matrix2x2) {
        self._00 = m._00 % 1234567
        self._01 = m._01 % 1234567
        self._10 = m._10 % 1234567
        self._11 = m._11 % 1234567
    }
}

func *(left: matrix2x2, right: matrix2x2) -> matrix2x2 {
    return matrix2x2(_00: left._00 * right._00 + left._10 * right._01,
                     _01: left._00 * right._10 + left._10 * right._11,
                     _10: left._10 * right._00 + left._11 * right._01,
                     _11: left._10 * right._10 + left._11 * right._11)
}

func solution(_ n:Int) -> Int {
    var m = matrix2x2(_00: 1, _01: 0, _10: 0, _11: 1)
    var fibo = matrix2x2(_00: 1, _01: 1, _10: 1, _11: 0)
    var val = n

    while val > 0 {
        if val % 2 == 1 {
            m = m * fibo
        }

        fibo = fibo * fibo
        val /= 2
    }

    return m._01
}

분할정복 피보나치라는데.. 전 수학과.. 안하고 컴퓨터 공학과 하겠습니다.. ㅠ