Kotilin (2) - 코틀린 피보나치 수열 및 1..10 정리 (백준 11727)

코틀린을 코틀린답게 사용하는것이 목표인 Loner 입니다.

오늘은 코틀린에서 피보나치 수열을 구하는 방법들을 정리해보도록 하겠습니다.

 

피보나치 수열이란?

1 1 2 3 5 8 13 21 34 55 .....
현재항과 이전항을 더해서 값이 꾸준이 올라가는 공식 입니다. 

 

1+1 = 2 (여기서 1 = 2)이 아래로 바뀐다.

1+2 = 3 (여기서 2 = 3)이 아래로 내려간다. 

2+3 = 5 .... 이렇게 무한 반복해서 끊임없이 숫자를 더 해가는 공식입니다.

 

알고리즘을 시작하려는 분들은 피보나치 수열은 꼭 알고가야하는 기본지식이라고 생각합니다. 

(응용할데가 너무 많아..)

 

피보나치 수열에 대한 설명은 이미 구글링을 하는 순간 엄청나게 많은 관련자료들이

이미 많기 때문에 간략하게 설명을 적어놨으니 따로 살펴보시면 좋을것 같습니다.

 

https://m.blog.naver.com/PostView.naver?blogId=alwaysneoi&logNo=100134567659&proxyReferer=https:%2F%2Fwww.google.com%2F 

[피보나치 수열] 피보나치 수열의 이해

 

이 포스팅에서는 Kotlin으로 피보나치 수열을 만드는 여러 경우들을 한번 살펴보도록 하겠습니다. 

이 포스팅은 재귀와 같은 개념들은 최대한 함축 설명하고

코틀린에서 피보나치 수열을 구하는 코드 설명 위주로 작성되었습니다.

 

1. 대표적인 방법 재귀로 계산하기

 

//재귀
private fun fibonacciDefalut(n: Int): Int {
return if (n <= 2) 1
else fibonacciDefalut(n - 1) + fibonacciDefalut(n - 2)
}

println(fibonacciDefalut(10)) 출력: 55

 

재귀는 return if(n<= 2) 와 같이 함수 탈출구를 하나 정해놓고 탈출 조건이 아닐때 똑같은 함수가

n이 바뀌어서 계속 호출되도록 하는 것 입니다. 이렇게 재귀를 호출하면 스택에 여러값이 쌓이는데, 마지막에 

if 문 탈출 조건에 걸리는 순간 스택에 쌓였던 결과 값들이 스택에서 pop이 시작됩니다. 

(그러면 마지막으로 호출된 값부터 올라옵니다.)

https://deftkang.tistory.com/36

[알고리즘] 재귀(Recursion)함수를 이해하고 팩토리얼 계산 구현

혹시 재귀를 모르시는분 이라면 위 링크를 참고하면 좋을것 같습니다.

 

1-2. 코틀린에서의 꼬리재귀 

 

1번의 재귀 방식은 함수를 호출하면서 f(n-1) + f(n-2) 라는 + 연산이 한번 더 호출되는데

이 연산 한번때문에 엄청나게 많은 함수들이 계산을 해야되서 만약 재귀함수(50) 만 해도

거의 1분 가까이 되서야 결과값이 출력이 될정도로 느려집니다.

 

그래서 연산하지않고 재귀 함수만 호출해서 수열을 하는것이 꼬리 재귀 방식입니다.

자세한 사항은 

https://velog.io/@dldhk97/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%99%80-%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80#%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80

재귀함수와 꼬리 재귀

보시면 좋을 것 같습니다.

 

코틀린에서 효율적으로 꼬리재귀를 사용하는 방법은 아래와 같은 코드가 있습니다. 

 

//코틀린에서의 꼬리재귀
fun fibonacciAt(n: Int) = run {
    tailrec fun fibonacciAcc(n: Int, a: Long, b: Long): Long {
       return when (n == 0) {
             true -> b
            false -> fibonacciAcc(n - 1, a + b, a)
        }
    }
    fibonacciAcc(n, 1, 0)
}

println(fibonacciAt(10)) 출력: 55

코틀린에서 tailrec 이라는 것이 존재하는데, tailrec는 해당 함수가 꼬리재귀 방식 일때

내부적으로 반복문으로 바꿔서 재귀함수가 호출될때의 스택을 더 아낄수 있습니다. 

fibonacciAt 의 리턴으로 run 함수를 지정해주면 run 특성상 맨마지막 구문을 return을 해주기 때문에 

fibonacciAcc(n,1,0)을 리턴합니다. 

 

그래서 main 함수에서 fibonacciAt()  사용하면 finonaaciAcc가 호출됩니다. 

 

1-3 배열을 사용한 재귀

 

//재귀 배열 버전
private fun fibonacciArr(n: Int): Int {
    Array(n) { 0 }.also {
       it[0] = 1
       it[1] = 1
  for (i in 2 until it.size) {
      it[i] = it[i - 1] + it[i - 2]
   }
    return it.last()
  }
}

println(fibonacciArr(10)) 출력: 55

 

위에서는 also를 이용했습니다. also의 특성으로 run과 마찬가지로 마지막 구문을 리턴해줍니다. 

 

 

2. 시퀀스를 이용한 방법

private fun useSequence() {
var result = generateSequence(1 to 1) { it.second to it.first + it.second }
.map { it.first }
println(result.take(10).toList().last())
}

출력:55

시퀀스로 피보나치 수열이 사용이 가능합니다. 


result.take(10).forEach {
println(it)
}



이렇게 출력하면 아래와 같이 나옵니다.

1
1
2
3
5
8
13
21
34
55

 

 

3. steam 함수를 전체 합 구하기 (피보나치 수열X) 

 

이 부분은 피보나치 수열의 방식이 아니라 0+1+2+3+4..+10으로 계속 값을 더하는 방식입니다.

 

이 방법은 크게 2가지가 있습니다. (이 방법 말고도 여러가지 방법이 있을 수 있습니다.) 

바로 kotlin의 큰 장점인 콜렉션 함수를 이용하는 것 입니다.

코드는 아래와 같습니다.

 

//Reduce을 이용한 피보나치
fun fibonacciReduce(n: Int): Int {
val arr = (0..n).toList().toIntArray()
return arr.reduce { acc, v -> acc + v }
}

 

첫번째로 Reduce를 이용하는 방법입니다.

맨처음에 n 값을 받아서 intRange를 만들고 배열로 만들어줍니다.

acc와 v 두가지 인자가 있는데

 

acc는 계속 값이 쌓이는 것이고

v는 원래의 값을 뜻합니다. 

 

로그를 찍으면 아래와 같습니다. 

acc:0 v:1
acc:1 v:2
acc:3 v:3
acc:6 v:4
acc:10 v:5
acc:15 v:6
acc:21 v:7
acc:28 v:8
acc:36 v:9
acc:45 v:10

출력:55

//fold를 이용한 피보나치
fun fibonacciFold(n: Int): Int {
val arr = (1..n).toList().toIntArray()
return arr.fold(0) { acc, v -> acc + v }}

 

acc:0 v:0
acc:0 v:1
acc:1 v:2
acc:3 v:3
acc:6 v:4
acc:10 v:5
acc:15 v:6
acc:21 v:7
acc:28 v:8
acc:36 v:9
acc:45 v:10
출력: 55

fold는 reduce와 달리 초기값을 설정하고 시작합니다. 그래서 fold(0)으로 설정했기 때문에

초기값 acc 0과 엘리먼트값 0으로 맨처음에 계산후 acc:0 v:1 ... 순으로 이어집니다. 

 

피보나치 수열은 1 1 2 3 5 8 순으로 이전항과 현재항을 연산하지만 위 스트리밍 함수는 

값이 쌓여가는 result에 acc에 기존 value를 연산하는 방식입니다. 

 

4. 시퀀스를 이용한 dp 알고리즘 풀어보기 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

1x2 , 2x1 , 2x2 가 있을 때 3가지 타일로 2 x n 일때 만들 수 있는 경우의 수를 나타낸다.

 

시퀀스를 사용하면 아래와 같이 풀 수가 있다.

private fun dp11727() {
val n = readLine()!!.toInt()
   if (n < 2) {
       println(1)
       return
    }
val result = generateSequence(Pair(1, 3). {  Pair(it.second, (it.second + it.first * 2) % 10007) }).map { it.first } 
   println(result.take(n).toList().last())

}

 

 

 

정답!!