Algorithm - No.2

작성일 | In | 0 comments
| Words count in article 921

알고리즘 문제 풀기 2

No.2 - Fibonacci

백준 사이트의 피보나치 수열 문제를 리뷰해보자.

피보나치란?

위키문서 참조

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

IoC 1

\[ \mathbf{F}_{1} = \mathbf{F}_{2} \ = 1 \] \[ \mathbf{F}_{n} = \mathbf{F}_{n-1} \ + \mathbf{F}_{n-2} \]

피보나치를 로직적으로 표현했을 경우 이렇다고 한다.

1
2
3
4
5
6
7
8
9
10
11
int fibonacci(int n) {
    if (n == 0) {
        out.write("0");
        return 0;
    } else if (n == 1) {
        out.write("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

문제는 N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램

풀어보면서…

물론 위의 예제 함수를 사용하면 0과 1의 개수를 표현 하는데 문제는 없을 것이다 다만, n이 2 이상 일 경우에는 다시 함수를 타게 된다.
n이 10이라면.. fibo(10) = fibo(9) + fibo(8), 여기서 fibo(9) = fibo(8) + fibo(7)… 계속 이런식으로 함수를 타게 되어 많은 연산을 거치게 될 것 이다.

피보나치 로직자체를 보면 결국 0과 1의 개수의 합이 N번쨰의 피보나치가 되며, 그렇다면 많은 연산을 거치지 않도록 n번째마다 0과 1의 개수를 피보나치 방식으로 더해주면 된다.

1
2
int zero[n] = new int[41];
int one[n] = new int[41];
  1. 위의 형태로 먼저 0의 개수와 1의 개수를 저장할 배열 두개를 먼저 선언하고,
  2. 0일떈 zero배열의 개수를 하나 증가, 1일떈 one배열의 개수를 하나 증가 하고,
  3. 2일떄는 (n-1) + (n-2)이니까 두번째 전까지 더하면 되는거니, n-1이 1일때는 1의 개수만 1이므로 one배열의 개수에 1을 더하고 n-2가 0일때는 0의 개수만 0이므로 zero배열의 개수에 0을 더한다.
  4. 그리고 3일때는 (2) + (1)로 (2)일 경우에는 앞에서 구한 zero[2]의 개수 값과 one[2] 개수 값에, (1)일땐 1의 개수 값을 1 증가해주면 된다.
  5. 이렇게 구한 값이 3일때의 각각 0과 1의 개수 값이 되는 것이다.

이렇게 하여 자연수 40까지의 0과 1의 갯수를 반복문 40번만에 구할 수 있게되는 것이다.

작성자, DevInSpace