문제 링크->https://programmers.co.kr/learn/courses/30/lessons/12945
코딩테스트 연습 - 피보나치 수
피보나치 수는 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) =
programmers.co.kr
피보나치 수는 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 이하인 자연수입니다.
------------------------------------------------------------풀이------------------------------------------------------------------
먼저 저의 풀이입니다.
- 피보나치수열은 f(n)= f(n-1) + f(n-2)입니다.
class Solution {
fun solution(n: Int): Int = search(arrayListOf<Int>(0, 1), n, 2)
fun search( f : ArrayList<Int>, target : Int, now : Int) : Int = if( now != target) {
f.add((f[now-2]%1234567+f[now-1]%1234567)%1234567)
search(f, target, now+1)
}
else{
f.add((f[now-2]%1234567+f[now-1]%1234567)%1234567)
f.last()
}
}
1. 0과 1은 고정시켜놓고 target 과 현재 index를 입력받아 재귀함수로 구현합니다.
풀이를 보시면 각 index의 value값에 1234567을 나누어서 나머지를 저장합니다. 이부분은 뒤에서 말씀드릴겠습니다.
첫 번재로 불통한 코드
class Solution {
fun solution(n: Int): Int {
var f = arrayListOf<Int>(0, 1)
for( i in 2..n){
f.add(f[i-2]+f[i-1])
}
return f.last()%1234567
}
}
처음에 에이 쉽네 하고 풀었다가 뒤통수 시게맞은 코드입니다. 7번부터 전부 에러더군여.
왤까 하고 생각하다가 value값 크기에 대해 생각했습니다. int형은 4바이트로 표현값이
-2,147,483,648 ~ 2,147,483,647입니다.
근데 피보나치 수열을 쭉 그냥 뽑아봤는데
47번째부터 -값이 나옵니다. 2,147,483,647을 넘는 순간 -2,147,483,648부터 시작하기 때문이었습니다.. 자료형의 데이터 범위를 생각하지 않아서 그런것이었습니다.
그럼 어떻게 하냐
위 문제에서 1234567로 나눈 나머지를 return하라고 되어있습니다.
학교에서 언뜻 배운게 생각나서
f(n) = f(n-2) + f(n-1) 이니까
f(n)%1234567 = f(n-2)%1234567 + f(n-1)1234567 이었던거 같은데 하고 해보니 틀렸습니다... 값을 뽑아보니
f(n)%1234567 = ( f(n-2)%1234567 + f(n-1)1234567 )%1234567 이렇게 마지막에 한번 더 해줘야 하더라구여
그래서 맨위에 코드가 탄생했습니다!
* 원래는 불통한 코드처럼 람다를 사용하지 않았는데 람다식에 익숙해질겸 해서 람다로 변경한 코드입니다.
위에 사용된 식이 모듈러 정리라고 하는데 궁금하신분들은 구글에 검색하시면 엘리트 개발자 분들이 블로그에 많이 정리해놓으셨습니다 ㅎㅎ
------------------------------------------------------------결과------------------------------------------------------------------
- 문제에 대한 질문 댓글 환영!
- 중간에 잘못된 부분이 있다면 댓글로 남겨주세요. 수정하겠습니다.
'Kotlin(프로그래머스) > Level 2' 카테고리의 다른 글
[프로그래머스/kotlin] 튜플 (0) | 2022.04.21 |
---|---|
[프로그래머스/Kotln] n^2 배열 자르기 (0) | 2022.04.21 |
[프로그래머스/Kotlin] JadenCase 문자열 만들기 (0) | 2022.04.18 |
[프로그래머스/Kotlin] N개의 최소 공배수 (0) | 2022.04.18 |
[프로그래머스/kotlin] 가장 큰 수 (0) | 2022.04.17 |
댓글