코딩 테스트 3일차

2일차 복습

1002번 문제는 두 점의 접점을 구하는 코드를 만드는 테스트 였습니다

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin')

1. 둘 이상 받을때 이용을 할때 받아야 합니다

2. 내접하는 월까지 고려해 계산을 해야 합니다.

 

3일차 시작

오늘은 약속이 있어 낮에 했어요

1003번 : 다음 소스는 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);
    }
}

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이다.

 

이것이 문제인데 피보나치란?

1 1 2 3 5 8 13 ... 처럼 전 수와 합하여 나오는 수인데 흠 학교 다닐때 보고 오랜만에 본다

def fib(n):
    if n == 0 or n == 1:
        return n
    
    return fib(n-2) + fib(n-1)

파이썬 코드라고 합니다. 

 

그럼 이 코드는 n을 입력해 값이 어떻게 나오는지 확인해 보았습니다.

 

0을 넣었을 경우 0 이렇게 나왔습니다

1을 넣었을 경우 1 이렇게 나왔습니다.

3을 넣었을 경우 1 0 1 이렇게 나왔습니다

 

문제는 0과 1이 나온 횟수를 띄어쓰기 구분해 결과를 알려달라고 했습니다

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split("\n");
//const input = ["3" , "0" , "1" ,"22"];
const testCount = Number(input[0]);

for (let i = 1; i <= testCount; i++) {
  const number = Number(input[i]);
  let zeloCount = 0;
  let oneCount = 0;

  const fib = (n) =>{
    if (n===0) {
      // console.log("0");
      zeloCount++;
      return n;
    }else if (n === 1) {
      // console.log("1");
      oneCount++;
      return n;
    }
    return fib(n-1) + fib(n-2);
  }

  fib(number );
  console.log(`${zeloCount} ${oneCount}`);
}

 

우선 제가 작성한 코드입니다. 하지만 시간 초과로 탈락했습니다

 

그래서 다른 분들의 작성 코드와 gpt에게 물어봐 코드를 개선했습니다

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split("\n");
//const input = ["3" , "0" , "1" ,"22"];
const testCount = Number(input[0]);

for (let i = 1; i <= testCount; i++) {
  const number = Number(input[i]);

  // 각 피보나치 수에 대해 0과 1이 나타나는 횟수를 저장할 배열을 초기화합니다.
  let fib = Array.from({length: number + 1}, () => [0, 0]);

  // 피보나치 수열의 첫 번째 항(0)에 대해 0이 한 번, 1이 0번 나타나므로 이를 배열에 저장합니다.
  fib[0] = [1, 0];

  // 피보나치 수열의 두 번째 항(1)에 대해 0이 0번, 1이 한 번 나타나므로 이를 배열에 저장합니다.
  if (number > 0) {
    fib[1] = [0, 1];
  }

  // 피보나치 수열의 세 번째 항부터는 이전 두 항의 0과 1의 개수를 더하여 계산합니다.
  for (let j = 2; j <= number; j++) {
    fib[j] = [fib[j-1][0] + fib[j-2][0], fib[j-1][1] + fib[j-2][1]];
  }

  // 계산된 0과 1의 개수를 출력합니다.
  console.log(`${fib[number][0]} ${fib[number][1]}`);
}

 

 

 // 피보나치 수열의 세 번째 항부터는 이전 두 항의 0과 1의 개수를 더하여 계산합니다.
  for (let j = 2; j <= number; j++) {
  	console.log("fib : ",fib);
    console.log(fib[j-1][0] , "+" , fib[j-2][0]," , " ,fib[j-1][1] , "+" , fib[j-2][1] );
    fib[j] = [fib[j-1][0] + fib[j-2][0], fib[j-1][1] + fib[j-2][1]];
    console.log(`fib[${j}] : `,fib[j]);
    console.log();
  }

이 부분이 이해가 안되고 있어서 자세하게 찾아봤습니다.

1. 우리가 만들고 있는 것은 피보나치 수열입니다. 피보나치 수열은 이전 두 개의 숫자를 더해서 다음 숫자를 만드는 수열입니다. 예를 들어, 0, 1, 1, 2, 3, 5, 8, 13, ... 이런 식으로 진행됩니다. - OK 

 

2. 이 코드에서는 피보나치 수열의 각 숫자가 얼마나 많은 0과 1을 가지고 있는지를 계산하고 있습니다.

예를 들어, 피보나치 수열의 첫 번째 숫자는 0이므로 0이 1개, 1이 0개입니다. 두 번째 숫자는 1이므로 0이 0개, 1이 1개입니다. -OK

 

3. for (let j = 2; j <= number; j++) {

이 줄은 2부터 원하는 피보나치 수까지 반복하는 루프를 시작합니다.

왜냐하면 피보나치 수열의 첫 번째와 두 번째 숫자는 이미 알고 있기 때문입니다. 

첫 번째 = 0

두 번째는 = 1 -OK

 

4. fib[j] = [fib[j-1][0] + fib[j-2][0], fib[j-1][1] + fib[j-2][1]];

이 줄이 실제 계산을 하는 부분입니다. 

현재의 피보나치 수의 0의 개수는 이전 두 개의 피보나치 수의 0의 개수를 더한 것이고, 

1의 개수도 마찬가지로 이전 두 개의 피보나치 수의 1의 개수를 더한 것입니다.

 

그서 콘솔을 찍어봤습니다.

fib :  [
  [ 1, 0 ],       [ 0, 1 ],
  [ 1, 1 ],       [ 1, 2 ],
  [ 2, 3 ],       [ 3, 5 ],
  [ 5, 8 ],       [ 8, 13 ],
  [ 13, 21 ],     [ 21, 34 ],
  [ 34, 55 ],     [ 55, 89 ],
  [ 89, 144 ],    [ 144, 233 ],
  [ 233, 377 ],   [ 377, 610 ],
  [ 610, 987 ],   [ 987, 1597 ],
  [ 1597, 2584 ], [ 2584, 4181 ],
  [ 4181, 6765 ], [ 6765, 10946 ],
  [ 0, 0 ]
]
6765 + 4181  ,  10946 + 6765
fib[22] :  [ 10946, 17711 ]

 

 

오늘의 느낀 점

응용해서 하라고 하면 할 수 있을까?

겨우 이해를 했는데 가능 할지 모르겠다