#AIL_23.12.02 // Programmers_피보나치 수
## AIL_ 피보나치 수
*** 문제 설명
피보나치 수는 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, ... 와 같이 이어집니다.
## solution.JavaScript
1. 문제의 접근 방식
주어진 문제는 주어진 규칙에 따라 피보나치 수열을 생성하고, n 번째 항을 1234567로 나눈 나머지를 반환하는 문제입니다.
1) 초기값 설정
F(0)과 F(1)의 값을 알아야 합니다. 주어진 조건에 따라 F(0)은 0, F(1)은 1입니다
2) 반복문을 통한 피보나치 수열 계산
주어진 조건에 따라 F(n) = F(n-1) + F(n-2)를 사용하여 반복문을 통해 피보나치 수열을 계산합니다.
3) 나머지 연산
피보나치 수열이 커질 경우, 계산된 값이 매우 큰 수가 될 수 있습니다. 따라서 결과를 1234567로 나눈 나머지를 반환합니다.
2. 문제풀이
function solution(n) {
// 초기값 설정
const answer = [0, 1];
// 반복문을 통한 피보나치 수열 계산
for (let i = 2; i <= n; i++) {
// 현재 항은 이전 두 항의 합
const fibo = answer[i-1] + answer[i-2];
// 계산된 항을 배열에 추가
answer.push(fibo % 1234567);
}
// n번째 항의 값을 1234567로 나눈 나머지 반환
return answer[n] % 1234567;
}
/*
테스트 1
입력값 〉 3
기댓값 〉 2
실행 결과 〉 테스트를 통과하였습니다.
테스트 2
입력값 〉 5
기댓값 〉 5
실행 결과 〉 테스트를 통과하였습니다.
*/
1. answer 배열에 초기값으로 [0, 1]을 설정합니다. 피보나치 수열의 0번째와 1번째 항이 각각 0과 1입니다.
2. for 반복문은 2부터 n까지 돌며 피보나치 수열을 계산합니다.
3. answer[i-1]과 answer[i-2]는 각각 i-1번째와 i-2번째 항을 나타냅니다.
4. const fibo = answer[i-1] + answer[i-2];을 통해 현재 항을 이전 두 항의 합으로 계산합니다.
5. 계산된 항을 push하여 배열 answer에 추가합니다.
6. return answer[n] % 1234567;을 통해 n번째 항의 값을 1234567로 나눈 나머지를 반환합니다.
3. 다른사람의 문제풀이 및 접근방식 분석
function solution(n) {
let [a, b] = [0, 1]; // 초기값 설정: a = 0, b = 1
while (--n) { // n이 0이 될 때까지 반복
[a, b] = [b, (a + b) % 1234567]; // 배열 비구조화 할당을 사용하여 a와 b를 갱신
}
return b; // 최종적으로 n번째 피보나치 수를 1234567로 나눈 나머지 반환
}
/*
테스트 1
입력값 〉 3
기댓값 〉 2
실행 결과 〉 테스트를 통과하였습니다.
테스트 2
입력값 〉 5
기댓값 〉 5
실행 결과 〉 테스트를 통과하였습니다.
*/
1. 초기값 설정 `let [a, b] = [0, 1];`을 통해 `a`는 0, `b`는 1로 초기화해서 피보나치 수열의 0번째와 1번째 항을 나타냅니다.
2. while 루프는 `while (--n)`은 n이 0이 될 때까지 반복합니다. ` --n`을 사용하여 루프 진입 전에 n을 감소시키고 루프 내부에서 `[a, b] = [b, (a + b) % 1234567];`을 통해 현재 항과 다음 항을 갱신합니다. `a`는 이전의 `b`로, `b`는 `(a + b) % 1234567`로 갱신됩니다.
3. 결과로 `return b`;는 최종적으로 n번째 피보나치 수를 1234567로 나눈 나머지를 반환합니다.
# 두 번째 방법 풀어쓰면
let a = 0
let b = 1
while (n){
--n;
let temp = a;
a = b;
b = (temp=a)%1234567
}
return b;
1. 변수 초기화
a와 b를 각각 0과 1로 초기화합니다. 이는 피보나치 수열의 0번째와 1번째 항을 나타냅니다.
2. while 루프
while (n)은 n이 0이 될 때까지 반복하고 --n을 사용하여 루프 진입 전에 n을 감소시킵니다.
3.변수 갱신
let temp = a;: 현재 a 값을 temp에 저장하고 a = b;: a를 b로 갱신합니다. b = (temp = a) % 1234567;: (temp = a)를 통해 이전의 a 값을 temp에 할당하고, 그 값을 1234567로 나눈 나머지를 b에 저장합니다. 이 부분에서 (temp = a)는 단순히 temp에 a 값을 할당하고, 그 값을 다시 반환합니다.
4.반복 및 결과 반환
위 과정을 n이 0이 될 때까지 반복하며 최종적으로 return b;를 통해 n번째 피보나치 수를 1234567로 나눈 나머지를 반환합니다.