문제 설명
피보나치 수는 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,... 와 같이 이어집니다.
풀이
이전 수를 더해가는 피보나치 수입니다. 만드는 공식은 문제에 나와있으므로 그대로 만들어 주면 되지만 숨겨져 있는 제약사항이 2가지 있습니다. 풀어가면서 찾아봅시다.
class Solution {
fun solution(n: Int): Int {
var answer = 0
return fibo(n) % 1234567
}
fun fibo(n: Int): Int{
if(n == 0)
return 0
else if(n == 1)
return 1
return fibo(n-1) + fibo(n-2)
}
}
우선 첫 번째 풀이입니다. 간단한 재귀 함수를 이용해서 풀었습니다. 테스트 코드도 통과했습니다.
결과는 7번부터 14번까지 시간 초과가 떴습니다. 시간 초과가 떴다는 거는 재귀 함수의 깊이가 너무 깊다는 의미입니다. 이를 해결하려면 중간 값을 저장할 필요가 있습니다.
class Solution {
val fibos = Array<Int>(1000000){i -> 0}
fun solution(n: Int): Int {
var answer = 0
fibos[1] = 1
return fibo(n) % 1234567
}
fun fibo(n: Int): Int{
if(n == 0)
return fibos[0]
else if(fibos[n] != 0)
return fibos[n]
fibos[n] = fibo(n-1) + fibo(n-2)
return fibos[n]
}
}
클래스 프로퍼티로 배열을 선언해서 중간값을 저장했습니다. 배열의 인덱스가 1일 때 1을 넣었습니다. fibos배열에서 값이 0이 아닐 경우에만 리턴해줘야 하므로 조건문으로 걸러줍니다. 다만 0번째 인덱스는 0을 리턴하는 조건을 추가해줍니다.
이번에도 실패입니다. 시간 초과를 해결했지만 실패했다는 것은 놓친 부분이 있다는 의미입니다. 이쯤에서 다시 제한 사항을 볼 필요가 있습니다.
n은 2 이상 100,000 이하인 자연수입니다.
피보나치 1,000번째 수는 뭘까요?
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
입니다. 1000번째 피 보나 치수조차 Integer의 범위를 넘어가는데 100,000번째는 아득히 넘어설 것입니다. 이런 경우엔 -2^63 ~ 2^63-1의 범위인 Long타입도 쓸모가 없어요. 위와 같이 아~~~ 주 큰 수의 산술 연산을 하려고 한다면 BigInteger을 이용해야 합니다.
class Solution {
val fibos = Array<BigInteger>(1000000){i -> BigInteger.ZERO}
fun solution(n: Int): Int {
var answer = 0
fibos[1] = BigInteger.ONE
return fibo(n).remainder(BigInteger("1234567")).toInt()
}
fun fibo(n: Int): BigInteger{
if(n == 0)
return fibos[0]
else if(fibos[n] != BigInteger.ZERO)
return fibos[n]
fibos[n] = fibo(n-1) + fibo(n-2)
return fibos[n]
}
}
BigInteger를 이용한 풀이입니다.
추가
다른 사람의 풀이를 보다가 BigInteger를 쓰지 않아도 풀어질 거 같아서 적용해봤는데 풀었네요
import java.math.BigInteger
class Solution {
val fibos = Array<Int>(1000000){i -> 0}
fun solution(n: Int): Int {
var answer = 0
fibos[1] = 1
return fibo(n)
}
fun fibo(n: Int): Int{
if(n == 0)
return fibos[0]
else if(fibos[n] != 0)
return fibos[n]
fibos[n] = (fibo(n-1) + fibo(n-2) ) % 1234567
return fibos[n]
}
}
어차피 결과값은 1234567로 나눈 나머지가 들어가야 되니까 n번째에 저장할 때 나눈 나머지를 넣어줬습니다.
다른 사람의 풀이
class Solution {
fun solution(n: Int): Int = if(/*n == 1 ||*/ n == 2) 1 else fib(n, 1, 1)
tailrec fun fib(n: Int, a: Int, b: Int): Int = if(n == 1) a else fib(n - 1, b % 1234567, (a + b) % 1234567)
}
꼬리 재귀를 이용한 풀이입니다. if문의 n == 1은 어차피 패러미터로 들어오는 n의 값은 2 이상이므로 주석 처리했습니다.
꼬리 재귀는 추가적인 연산 없이 스스로 호출하다가 어떤 값을 리턴하는 함수를 말합니다.
위 풀이는 주어진 n 만큼 피보나치 수를 더해가는 형태로 풀었습니다. 1234567을 나눈 나머지를 넣은 이유는 정수 범위를 벗어나지 않기 위해 넣은 것 같습니다. 다음번에 재귀를 활용할 일이 있다면 꼬리 재귀를 이용해 보는 것도 좋아 보입니다.
class Solution {
fun solution(n: Int): Int {
var ans = Array(n+1) { i -> 0 }
ans[1] = 1
for(i in 2..n) ans[i] = (ans[i-1] + ans[i-2])%1234567
return ans[n]
}
}
꼬리 재귀 풀이와 전체적인 틀은 같습니다. n번째 까지 반복문을 통해 피보나치 수를 더해가는 형태입니다. 피보나치 == 재귀라는 공식을 깨는 좋은 예제네요
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
N개의 최소 공배수 (0) | 2022.09.20 |
---|---|
멀리 뛰기(Lv.2) (0) | 2022.09.19 |
이진변환 반복하기(Lv.2) (0) | 2022.09.16 |
JadenCase 문자열 만들기(Lv.2) (1) | 2022.09.15 |
최댓값과 최솟값(Lv.2) (1) | 2022.09.14 |