반응형

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

해설

피보나치 수를 구하는 함수를 작성하기 위해서는

최소케이스를 먼저 작성을 해야한다.

 

이 문제에서의 최소 케이스는 fibonacci(0) 은 0, fibonacci(1)은 1 을 리턴하도록 작성을 한다.

이후 2 부터는 는 fibonacci(n-1) + fibonacci(n-1)를 재귀를 통해 구해서 더하도록 작성하면 된다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
 
const num = input[0]
 
console.log(fibonacci(num))
 
function fibonacci(n) {
  if(n == 0) {
    return 0
  } else if(n == 1) {
    return 1
  }
 
  return fibonacci(n-1) + fibonacci(n-2)
}
 cs
반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 11729 하노이의 탑 이동 순서 해설, node js 구현  (0) 2021.09.18
[알고리즘] 백준 - 2447 별 찍기 - 10 해설, node js 구현  (1) 2021.09.04
[알고리즘] 백준 - 1002 터렛 해설, node js 구현  (0) 2021.08.28
[알고리즘] 백준 - 3053 택시 기하학 해설, node js 구현  (0) 2021.08.28
[알고리즘] 백준 - 4153 직각삼각형 node js 구현  (0) 2021.08.27
반응형

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1
2
3
4
5
6
7
8
9
10
11		 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이다.

 

해설

문제는 재귀적으로 피보나치 수열 문제를 풀었을 때 f(n)은 f(1)과 f(0)을 각각 몇번씩 호출하게 되는가?로 해석이 가능하다.

f(2)는 f(1)을 1번, f(0)을 1번 호출한다.

f(3)은 f(2)를 1번, f(1)을 1번 호출한다. 따라서 f(2)각 f(1)과 f(0)을 각각 1번씩 호출하기 때문에 총 f(1) 2번 f(0) 1번 을 호출한다.

이러한 방식으로 f(1)을 호출하는 회수와  f(0)을 호출하는 회수를 위의 피보나치 코드와 매우 비슷한 형태로 풀 수 있다.

그림이 매우 별로이지만 zero라고 된 부분이 f(0)을 호출하는 회수이고 one 이 f(1)을 호출하는 회수이다.

이 각각은 zreo(n) = zero(n-1) + zero(n-2) 와 같이 풀면서 계속해서 더해간다면 f(n)에서의 f(0), f(1) 호출 회수를 구할 수 있다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cnt = input[0]
var inputlist = input.slice(1)
 
const countFibonacci = n => {
  const returnObj = {
    zeroCount: [1, 0],
    oneCount: [0,1]
  }
 
  if (n <= 1) {
    return returnObj  
  }
 
  for (let i = 2; i < n+1; i++) {
    returnObj.zeroCount.push(returnObj.zeroCount[i-1] + returnObj.zeroCount[i-2])
    returnObj.oneCount.push(returnObj.oneCount[i-1] + returnObj.oneCount[i-2])
  }
 
  return returnObj
}
 
// 미리 40까지의 list를 생성
const cache = countFibonacci(40)
 
for(let i = 0; i < cnt; i++) {
  num = inputlist[i]
  console.log(`${cache.zeroCount[num]} ${cache.oneCount[num]}`)
}
 cs

 

반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1149 RGB 거리 node js 구현  (0) 2021.08.22
[알고리즘] 백준 - 3009 네 번째 점 node js 구현  (0) 2021.08.22
[알고리즘] 백준 -1085 직사각형에서 탈출 node.js 구현  (0) 2021.08.17
[알고리즘] 백준 -11653 소인수분해 node.js 구현  (0) 2021.08.16
[알고리즘] 백준 -1463 1로 만들기 파이썬 구현  (0) 2019.02.12
반응형

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1
2
3
4
5
6
7
8
9
10
11
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이다.

 

반응형

해설

문제는 재귀적으로 피보나치 수열 문제를 풀었을 때 f(n)은 f(1)과 f(0)을 각각 몇번씩 호출하게 되는가?로 해석이 가능하다.

f(2)는 f(1)을 1번, f(0)을 1번 호출한다.

f(3)은 f(2)를 1번, f(1)을 1번 호출한다. 따라서 f(2)각 f(1)과 f(0)을 각각 1번씩 호출하기 때문에 총 f(1) 2번 f(0) 1번 을 호출한다.

이러한 방식으로 f(1)을 호출하는 회수와  f(0)을 호출하는 회수를 위의 피보나치 코드와 매우 비슷한 형태로 풀 수 있다.

그림이 매우 별로이지만 zero라고 된 부분이 f(0)을 호출하는 회수이고 one 이 f(1)을 호출하는 회수이다.

이 각각은 zreo(n) = zero(n-1) + zero(n-2) 와 같이 풀면서 계속해서 더해간다면 f(n)에서의 f(0), f(1) 호출 회수를 구할 수 있다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def count_fibonacci(n):
    zero_count = [1,0]
    one_count = [0,1]
    if n <= 1:
        return
 
    for i in range(2, n+1):
        zero_count.append(zero_count[i-1] + zero_count[i-2])
        one_count.append(one_count[i-1] + one_count[i-2])
 
    return zero_count, one_count
 
n = int(input())
zero_count, one_count = count_fibonacci(40)
 
for _ in range(n):
    m = int(input())
    print("%d %d" % (zero_count[m], one_count[m]))
 
 cs

 

반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1149 RGB 거리 파이썬 구현  (0) 2019.02.01
[알고리즘] 백준 - 11718 그대로 출력하기 파이썬 구현  (0) 2019.01.23
[알고리즘] 백준 - 5430 AC 파이썬 구현  (0) 2019.01.17
[알고리즘] 백준 - 1021 회전하는 큐 파이썬 구현  (0) 2019.01.16
[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13

+ Recent posts

티스토리툴바