코딩 테스트 문제 해설들을 읽다보면 가끔씩 나오는 말, 피보나치 수

피보나치 수란 무엇일까?

전세계인의 백과사전, 위키백과에서 검색해봤습니다.

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

즉 아래와 같은 수열입니다.

<aside> 💡 (0) 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 ...

</aside>

코딩 테스트에서의 피보나치 수

코딩 테스트 문제를 가지고 와봤습니다.

2747번: 피보나치 수

val n = readLine()!!.toInt()

fun main() {
    var pair = Pair(0, 1)
    for (i in 0 until n) {
        pair = Pair(pair.second, pair.first + pair.second)
    }
    println(pair.first)
}

val n = readLine()!!.toInt()
var fibonacci = mutableListOf<Int>(0, 1)

fun main() {
    if (n in 0..1) {
        println(fibonacci[n])
    } else {
        for (j in 2..n) {
            fibonacci(j)
        }
        println(fibonacci[n])
    }
}

fun fibonacci(index : Int) {
    fibonacci.add(fibonacci[index - 1] + fibonacci[index - 2])
}

위 두 코드처럼 반복문과 재귀함수를 사용할 수 있습니다.

(물론 반복문 코드가 전 더 마음에 드네요.)

피보나치 수는 다른 문제들에도 숨어있습니다.

예시로는 백준 2193번 이친수가 있습니다.

2193번: 이친수

아래는 입력과 출력의 값입니다.