.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
DP, 211104
문제
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}
C++
복사
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
•
fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
•
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
•
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
•
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
•
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
•
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
•
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
예제 입력 1
3
0
1
3
Plain Text
복사
예제 출력 1
1 0
0 1
1 2
Plain Text
복사
예제 입력 2
2
6
22
Plain Text
복사
예제 출력 2
5 8
10946 17711
Plain Text
복사
My solution
기본 디버깅 툴 사용방법
fibo의 파라미터 n이 '0'인 상태이며 문자열 0이기 때문에 if(n === 0)에서 걸리지 않았던 것을 확인할 수 있다. 이것 때문에 maximum call stack exceed 에러가 났었다.
기존에 input은 const로 선언해서 배열로 그냥 사용했었지만 문자열인 숫자가 들어오므로 shift()연산 이후에 만들어진 배열을 map으로 순회해서 전부 숫자로 바꾸어줄 필요가 있었다. 새 배열 반환이므로 input에 재할당해준다.
map() 메서드는 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
let input = i.toString().trim().split("\n");
input.shift();
input = input.map((v) => +v);
JavaScript
복사
메모제이션을 안쓰면, 시간복잡도는 O(2^N)이다.
n이 커질수록 어마어마하게 시간이 오래걸린다는것을 알 수 있다.
하지만, 메모제이션 방법을 사용하면 시간복잡도는 O(N)으로 급격히 줄어든다.
출처:
다이나믹 프로그래밍을 염두에 두고 data 배열을 0으로 초기화시켜둔 다음 처음 보는 값이면 해당 인덱스에다 그 값을 할당하면서 return 해주고 아닌 경우 data 배열에서 값을 꺼내오는 식으로 아래와 같이 구현했다.
function solution(i) {
let input = i.toString().trim().split("\n");
input.shift();
input = input.map((v) => +v);
let data = [...Array(40)].fill(0);
let result = [0, 0];
function fibo(n) {
if (n === 0) {
result[0]++;
return 0;
}
if (n === 1) {
result[1]++;
return 1;
}
// return fibo(n - 1) + fibo(n - 2);// 이게 조건에 따라 다르게 실행되어야 개선된다.
if (data[n] === 0) return (data[n] = fibo(n - 1) + fibo(n - 2));
else return data[n];
}
let answer = [];
for (let x of input) {
fibo(x);
answer.push(result.join(" "));
result = [0, 0];
}
return answer.join("\n");
}
JavaScript
복사
그런데 이렇게 하면 2번째 TC에서 틀리는 이유가 0과 1이 몇번 찍히는지 확인하는 것인데 이미 아는 값이라고 그 값의 내부에 있는 0과 1의 리턴문을 만나러 가지 않기 때문이다. 그래서 이걸 의도적으로 다시 만나러 가게끔 메모이제이션을 뺄 필요가 있었다.
하지만 시간 제한이 엄격하기 때문에 메모이제이션도 빼지 않고 해결할 방법을 찾아야 했다.
일단은 피보나치 값을 구하는 것이 주가 아니다. 0과 1을 리턴하는 횟수가 0과 1보다 큰 수를 분리해서 타고 들어갔을 때 몇번이냐를 측정할 수가 없었다. 따라서 0과 1을 각각 어떤 수를 타고 들어갔을 때 몇번 참조(리턴)하게 되는지를 계산하는 재귀 함수를 구현해야 했다. 주어진 조건에서
N은 40보다 작거나 같은 자연수 또는 0이다.
라고 했기 때문에 0 ~ 40까지만 for문을 돌면서 각 숫자들이 0과 1을 얼마나 반환할 필요가 있는지를 연산해볼 수 있다. 초기값은 이미 알고 있기 때문에 이 초기값(이전값)들을 더해서 앞의 값을 구해나가는 점화식의 형태를 쓴다.
data0 배열 : 0이 쓰인 횟수를 구해서 저장할 배열
data1 배열 : 1이 쓰인 횟수를 구해서 저장할 배열
위의 배열이 data0인데 0번 인덱스가 1로 되어 있는 것은 0을 1번 사용했다는 가정하에 2번 인덱스(값)부터 0을 몇번 호출하는가를 누적한 값을 저장한다. 마찬가지로 아래의 data1 배열은 1번 인덱스가 1로 되어 있는 것은 1을 1번 사용했다는 가정하에 2번 인덱스(값)부터 1을 몇번 호출하는가를 누적한 값을 저장한다.
이 값을 미리 다 구해놓는다는 것은 피보나치 함수의 재귀 속에 빠질 필요가 없다는 것을 의미한다. 메모이제이션을 빼기에는 시간 초과가 걸리고 메모이제이션을 그대로 두면 2이상의 값에서 0,1을 몇번씩 호출하는지 알 방법이 없었다. 그래서 위 방법을 사용하면 이미 정해진 범위 내에서 0, 1이 각각 얼마나 호출되어지는지를 구할 수 있다.
소스코드
function solution(i) {
let input = i.toString().trim().split("\n");
input.shift();
input = input.map((v) => +v);
let data0 = [1, 0];
let data1 = [0, 1];
for (let i = 2; i <= 40; i++) {
data0.push(data0[i - 2] + data0[i - 1]);
data1.push(data1[i - 2] + data1[i - 1]);
}
let answer = "";
for (let x of input) {
answer += `${data0[x]} ${data1[x]}\n`;
}
console.log(answer);
return answer;
}
// & : 디버깅 해보기.
// solution(`3
// 0
// 1
// 3`);
test("solution", () => {
expect(
solution(`3
0
1
3`)
).toStrictEqual("1 0\n0 1\n1 2\n");
expect(
solution(`2
6
22`)
).toStrictEqual(`5 8
10946 17711\n`);
});
JavaScript
복사
