[99클럽 코테 스터디 2일차 TIL] 백준 피보나치 비스무리한 수열 Swift

오늘의 문제

- 백준 피보나치 비스무리한 수열

- https://www.acmicpc.net/problem/14495

오늘의 학습 키워드

- 재귀함수의 문제점, 다이나믹 프로그래밍 (DP) 방식, 피보나치 수열

 

 

잘못된 접근 

1. 단순하게 재귀 함수로 f(n) = f(n-1) + f(n-3) 로 도전해보았으나 런타임 에러가 발생했다.

- 일반적으로 함수 호출이 많아질 경우에는 런타임 에러가 발생한다.

- 함수 호출 스택이 쌓이기 때문에 제한이 되는게 아닐까 싶다.

2. 중간에 계산한 결과를 Array 에 저장하고 빠르게 반환하도록 했지만, 함수 호출이 많아 런타임 에러로 실패했다.

3. 1 <= n <= 116 으로 배열의 크기를 117로 설정했어야 하는데 116으로 해서 index error 가 발생했다.

해결 방법

- 재귀 함수가 아닌 반복문을 이용해 피보나치 비스무리한 수열의 값을 계산했다.

- 반복문을 돌면서 해당 인덱스의 값을 계산하고, 배열에 값을 미리 저장해뒀다. (매번 계산하면 시간 초과가 발생할 수 있기 때문에)

 

import Foundation

func fibonachi(_ n: Int) -> Int {
    var fibonachiArray = Array(repeating: 0, count: 117)

    if n == 1 || n == 2 || n == 3 {
        return 1
    } else {
        for i in 1...3 {
            fibonachiArray[i] = 1
        }
        for i in 4...n {
            fibonachiArray[i] = fibonachiArray[i-1] + fibonachiArray[i-3]
        }
    }

    return fibonachiArray[n]
}

if let input = readLine(), let n = Int(input) {
    let result = fibonachi(n)
    print(result)
}

 

 

오늘의 회고

1. 오랜만에 하니 readLine() 도 헷갈려서 헤맸었다.

2. 동적 계획법 (Dynamic Programmin) 은 큰 문제를 작은 문제로 나누어 푸는 문제로 어떤 경우에 적용되는지 정리가 필요해보인다.

- 부분 문제의 중복 : 각 항은 이전 항들의 합 "f(n) = f(n-1) + f(n-3)" 으로 정의되는것이 부분 문제가 반복된다고 볼 수 있다.

- 메모이제이션(memoization) : 동적 계획법은 이미 계산된 값을 저장해서 동일한 계산을 반복하지 않도록 한다. 이전에 계산한 값을 이용한다는 점에서 힌트를 얻을 수 있다.

- 점화식 사용 : "f(n) = f(n-1) + f(n-3)" 로 정의되는 점화식을 사용하는것 자체가 작은 부분 문제로 나누어 해결할 수 있다는 뜻이다.