[프로그래머스] Lv.2 피보나치 수 - JavaScript

윤지·2024년 11월 23일

코딩테스트

목록 보기

8/10

📍 문제

피보나치 수는 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, ... 와 같이 이어집니다.

🥔 내 코드

1차 - 실패 (숫자가 너무 커져서 오버플로우 발생) ❌

function solution(n) {
let a = 0;
let b = 1;
let temp = null;
let arr = []
for(let i = 0 ; i <= n ; ++i){
  arr.push(a);
  temp = a;
  a = b;
  b = temp + a
} return arr.pop() % 1234567
}

풀이

변수 a와 b를 선언하고 각각 0과 1로 초기화
temp 변수를 선언하여 임시 저장소로 사용
빈 배열 arr 생성
반복문을 통해 n까지 순회하면서:
배열에 a값을 추가
temp에 a값을 임시 저장
a에 b값을 할당
b에 temp + a 값을 할당하여 다음 피보나치 수 계산
마지막으로 배열의 마지막 값을 꺼내서 1234567로 나눈 나머지를 반환

2차 - 실패 (오버플로우) ❌

function solution(n) {
let arr = [0, 1]
for(let i = 0 ; i <= n - 2 ; i++){
    arr.push(arr[i] + arr[i + 1])
} return arr.pop() % 1234567
}

풀이(배열 활용)

초기값으로 [0, 1]이 담긴 배열 생성
n-2만큼 반복하면서 이전 두 수를 더한 값을 배열에 추가
마지막으로 배열의 마지막 값을 꺼내서 1234567로 나눈 나머지를 반환

3차 - 실패 (오버플로우) ❌

function solution(n) {
let arr = [0, 1]
for(let i = 2 ; i <= n ; i++){
    arr[i] =  arr[i - 1] + arr[i - 2]
} return arr[n] % 1234567
}

풀이(배열 인덱스 활용)

배열의 0번째와 1번째 인덱스에 초기값 [0, 1] 할당
2부터 n까지 반복하면서 i번째 인덱스에 이전 두 수의 합을 할당
마지막으로 n번째 인덱스의 값을 1234567로 나눈 나머지를 반환

4차 성공 🎉

function solution(n) {
let arr = [0, 1]
for(let i = 2 ; i <= n ; i++){
    arr[i] =  (arr[i - 1] + arr[i - 2]) % 1234567
} return arr[n]
}

💫 실패 이유

3차까지 테스트7부터 실패가 떠서 아니 대체 왜…를 반복하다가 이런 글을 발견하게 된다

👽 요약

일반적인 프로그래밍 언어의 int 자료형(4byte)은 -2,147,483,648 ~ 2,147,483,647 범위만 표현 가능

범위를 벗어나면 오버플로우가 발생해 예상치 못한 결과가 나옴

(예: 2,147,483,647 + 1 = -2,147,483,648)

하지만 (A + B) % C = ((A % C) + (B % C)) % C라는 모듈러(나머지) 연산 성질을 이용하면 오버플로우 없이 정확한 결과를 얻을 수 있음

본문: 여기

즉, 마지막에만 나머지 연산을 수행 시 이미 이전 단계에서 오버플로우가 발생해 잘못된 결과가 나올 수 있음. 따라서 계산 과정 중간중간 나머지 연산을 통해 오버플로우 방지가 필요함

✅ 나머지 연산

장점: 자료형이 엄격한 다른 언어에서도 오버플로우 방지와 연산 시간 단축 가능

공식

더하기

(A + B) % M = (A % M + B % M) % M

곱하기

(A × B) % M = (A % M × B % M) % M

빼기

(A - B) % M = (A % M - B % M + M) % M

최종 답안

function solution(n) {
let arr = [0, 1]
for(let i = 2 ; i <= n ; i++){
    arr[i] =  (arr[i - 1] + arr[i - 2]) % 1234567
} return arr[n]
}

💡 다른 사람의 코드

function solution(n) {
   var result = [0 , 1];
   while ( result.length !== n + 1) {
       var fibonacci = (result[result.length - 2] + result[result.length - 1]) % 1234567
       result.push(fibonacci);
   }
    return result[n];
}