[백준 알고리즘] Node.js 1003. 피보나치 함수
2023. 7. 18. 15:40ㆍ코딩연습
1. 문제
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
2. 풀이
1) 처음엔 그냥 문제에 주어진 대로 문제풀이를 진행했다. 아래는 그 코드이다.
const [T, ...inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);
// answer array에 0이 되는 회수와 1이 되는 회수를 만듬.
const answer = Array.from({length : T}, () => [0,0]);
// C++로 만든 함수를 JS로 바꿈. 이후 0과 1이 될 때마다 해당 array의 값 증가.
const fib = (idx, n) => {
if(n === 0){
answer[idx][0]++;
return 0;
} else if(n === 1){
answer[idx][1]++;
return 1;
} else {
return fib(idx, n-1) + fib(idx, n-2);
}
}
// 테스트케이스만큼 반복.
for(let i = 0; i < T; i++){
let num = inputs[i];
fib(i, num);
}
// 결과 출력.
let result = "";
answer.forEach(item => {
result += `${item.join(" ")}\n`;
})
console.log(result)
- 시간 초과났다. 이번 문제는 DP 를 이용해야하는 문제였기 때문이다. 혹시나 했는데 역시 안된다 ^^;;;;
2) 이번엔 DP를 이용해보자.
- 이전에 피보나치 관련 문제를 푼 기억이 났다. 관련 문제는 백준 24416번 문제!!
- 0일때 0을 출력하는 횟수와 1을 출력하는 횟수, 1일때 0을 출력하는 횟수와 1을 출력하는 횟수를 기본으로 둔다.
- 만약 2라면 0과 1을 1번씩 출력한다. 3이라면 0을 1번, 1을 2번 출력.
- 이를 통해 알 수 있는 사실은
fibonacci[i] = [
fibonacci[i-1][0] + fibonacci[i-2][0], // 0이 등장하는 횟수
fibonacci[i-1][1] + fibonacci[i-2][1] // 1이 등장하는 횟수
]
로 표현이 가능하다!!
const [T, ...inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);
for(let i = 0; i < T; i++){
const num = inputs[i];
const fibo = [[1,0], [0,1]];
for(let j = 2; j <= num; j++){
fibo[j] = [
fibo[j-1][0] + fibo[j-2][0],
fibo[j-1][1] + fibo[j-2][1]
];
}
console.log(fibo[num].join(" "));
}
3. 정리
- DP 어렵다. DP의 핵심은 "메모이제이션" 이라고 한다~
'코딩연습' 카테고리의 다른 글
[백준 알고리즘] Node.js 10866. 덱 (0) | 2023.07.21 |
---|---|
[백준 알고리즘] Node.js 10845. 큐 (0) | 2023.07.21 |
[백준 알고리즘] Node.js 12852. 1로 만들기 2 (0) | 2023.07.04 |
[백준 알고리즘] Node.js 1806. 부분합 (0) | 2023.06.28 |
[프로그래머스] 롤케이크 자르기 (0) | 2023.06.26 |