피보나치 수
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12945
풀이
피보나치 수는 간단하다.
1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 의 공식이 적용되는 수이다.
따라서
- 피보나치 값을 저장할 배열을 생성하고 0과 1 값을 초기화한다.
- n 값을 구하기 위해 반복문으로 n-1과 n-2의 값을 계속 더해서 배열에 넣는다.
- 마지막 값을 1234567로 나눈 나머지를 반환한다.
import java.util.ArrayList;
class Solution {
public int solution(int n) {
ArrayList<Integer> fibo = new ArrayList<>();
fibo.add(0);
fibo.add(1);
for (int i=2; i<=n; i++){
fibo.add(fibo.get(i-1) + fibo.get(i-2));
}
int answer = fibo.get(n);
return answer % 1234567;
}
}과연 결과는 ?!
테스트 1 〉 통과 (0.02ms, 100MB)
테스트 2 〉 통과 (0.02ms, 81.7MB)
테스트 3 〉 통과 (0.03ms, 73.1MB)
테스트 4 〉 통과 (0.04ms, 77.3MB)
테스트 5 〉 통과 (0.04ms, 75MB)
테스트 6 〉 통과 (0.04ms, 80.4MB)
테스트 7 〉 실패 (0.94ms, 76MB)
테스트 8 〉 실패 (0.70ms, 72.6MB)
테스트 9 〉 실패 (0.33ms, 91.6MB)
테스트 10 〉 실패 (0.71ms, 96.7MB)
테스트 11 〉 실패 (0.28ms, 73.3MB)
테스트 12 〉 실패 (0.48ms, 69.9MB)
테스트 13 〉 실패 (13.61ms, 86.2MB)
테스트 14 〉 실패 (12.99ms, 76.6MB)실패가 떴다. 😢
실패의 이유 1
내가 생각한 실패의 이유는 바로 자료형이라고 생각했다.
n은 2 이상 100,000 이하인 자연수입니다.100,000번의 피보나치의 수는 굉장히 클 것이라고 생각했고, 얼마 정도고 그에 맞춰서 자료형을 변경해야겠다 생각했지만..
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아..
애초에 피보나치 수열을 계산해주는 사이트도 10000까지만 한계를 두고 있는걸 보고.. 자료형의 문제가 아니라고 생각했다.
그리고 당연히 자료형을 long으로 변경해도 동일하게 해결할 수 없었다.
import java.util.ArrayList;
class Solution {
public int solution(int n) {
ArrayList<Long> fibo = new ArrayList<>();
fibo.add(0L);
fibo.add(1L);
for (int i=2; i<=n; i++){
fibo.add(fibo.get(i-1) + fibo.get(i-2));
}
long answer = fibo.get(n);
return (int) (answer % 1234567);
}
}테스트 1 〉 통과 (0.09ms, 70.6MB)
테스트 2 〉 통과 (0.08ms, 87.2MB)
테스트 3 〉 통과 (0.08ms, 85.3MB)
테스트 4 〉 통과 (0.08ms, 80MB)
테스트 5 〉 통과 (0.12ms, 87.2MB)
테스트 6 〉 통과 (0.08ms, 77.5MB)
테스트 7 〉 실패 (0.61ms, 82.4MB)
테스트 8 〉 실패 (0.49ms, 86.5MB)
테스트 9 〉 실패 (0.35ms, 91.9MB)
테스트 10 〉 실패 (0.62ms, 78.8MB)
테스트 11 〉 실패 (0.36ms, 82.3MB)
테스트 12 〉 실패 (0.37ms, 84.5MB)
테스트 13 〉 실패 (13.63ms, 78.7MB)
테스트 14 〉 실패 (13.96ms, 78.5MB)다른 방법을 생각해보자. 😢
실패한 이유 2
마지막에 1234567로 나누는 이유가 바로 배열 내에 들어가는 값이 너무 커서 그랬었다.
그렇다면 마지막에 나누지 말고, 애초에 나머지 값으로 계산하면 어떨까?
a+b = c 라면 (a+b) % 1234567 = c % 1234567 이 성립할 것이다.
따라서 피보나치 수를 구할 때마다 그의 나머지 값을 배열에 넣는 것이다.
import java.util.ArrayList;
class Solution {
public int solution(int n) {
ArrayList<Integer> fibo = new ArrayList<>();
fibo.add(0);
fibo.add(1);
for (int i=2; i<=n; i++){
fibo.add((fibo.get(i-1) + fibo.get(i-2)) % 1234567);
//이미 나머지 값으로 계산
}
int answer = fibo.get(n);
return answer;
}
}테스트 1 〉 통과 (0.02ms, 73.6MB)
테스트 2 〉 통과 (0.03ms, 75.9MB)
테스트 3 〉 통과 (0.02ms, 91.4MB)
테스트 4 〉 통과 (0.02ms, 75.7MB)
테스트 5 〉 통과 (0.04ms, 79.9MB)
테스트 6 〉 통과 (0.03ms, 89MB)
테스트 7 〉 통과 (0.62ms, 81.9MB)
테스트 8 〉 통과 (0.35ms, 85.1MB)
테스트 9 〉 통과 (0.27ms, 80.5MB)
테스트 10 〉 통과 (0.72ms, 82.4MB)
테스트 11 〉 통과 (0.23ms, 72.7MB)
테스트 12 〉 통과 (0.39ms, 72.1MB)
테스트 13 〉 통과 (13.25ms, 86.5MB)
테스트 14 〉 통과 (20.13ms, 76.6MB)야호 드디어 통과했다 ! 👏
그 전 값에도 똑같은 수를 나누면 상관 없다는 것이.. 생각하기 어려웠다.
최적화
더 빠른 속도를 내기 위해서, 컬랙션이 아닌 배열을 사용해보자.
ArrayList<Integer>가 아닌 int [] array 를 사용하는 것이다.
그렇다면 배열이 길어질 때마다 재할당 받는 과정과 int를 래퍼 클래스로 박싱하는 과정도 없어지기 때문에 더 빨라질 것이다!
import java.util.ArrayList;
class Solution {
public int solution(int n) {
int [] fibo = new int[n+1];
fibo[0] = 0;
fibo[1] = 1;
for (int i=2; i<=n; i++) {
fibo[i] = (fibo[i-1] + fibo[i-2]) % 1234567;
}
int answer = fibo[n];
return answer;
}
}테스트 1 〉 통과 (0.02ms, 83.1MB)
테스트 2 〉 통과 (0.02ms, 90.3MB)
테스트 3 〉 통과 (0.02ms, 88.7MB)
테스트 4 〉 통과 (0.02ms, 74.7MB)
테스트 5 〉 통과 (0.02ms, 78.5MB)
테스트 6 〉 통과 (0.02ms, 93MB)
테스트 7 〉 통과 (0.10ms, 94.4MB)
테스트 8 〉 통과 (0.06ms, 80.7MB)
테스트 9 〉 통과 (0.02ms, 91.5MB)
테스트 10 〉 통과 (0.10ms, 89.7MB)
테스트 11 〉 통과 (0.02ms, 76MB)
테스트 12 〉 통과 (0.05ms, 73.9MB)
테스트 13 〉 통과 (3.71ms, 83.3MB)
테스트 14 〉 통과 (2.38ms, 85.3MB)20ms까지 걸렸던 마지막 테스트가 0.1배 빨라진 것을 확인할 수 있다!
🥰
