피보나치 함수

---

🔗 🔗 전체 1003번 문제

조건

---

문제

---

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

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

출력

---

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

케이스

---

• 입력

TC
1
2
3
4
3
0
1
3

• 출력

TC
1
2
3
1 0
0 1
1 2

풀이

---

알고리즘 풀면서 느끼는 거지만, 문제가 뭘 말하는 지 이해가 안 되는 경우가 많은 것 같다. 내가 멍청해서 그런건가.

이 문제를 풀기 위해선, 피보나치 수열에 대한 식을 이해하고 있어야 한다.
피보나치 수열이 $f()$일 때, $n$번째 피보나치 수열의 식은 $f(n) = f(n - 1) + f(n - 2)$로 정의할 수 있다.

$n = 0, 1$일 때의 초기값이 정해져있다. (식의 특성 상 초기값이 없으면 계산할 수가 없다.)
$f(0) = 0$
$f(1) = 1$
초기값은 위와 같으며, 실질적으로 $n >= 2$ 부터 의미있는 연산이 수행된다.

다시 문제로 돌아가서, 임의의 수 N이 주어질 경우 $f(N)$을 수행하면서 $f(0)$, $f(1)$이 몇 번 호출되는지를 구하면 된다.
예를 들어, $N = 4$라고 가정하고 식을 전개하면 아래와 같다.
$f(4) = f(3) + f(2)$
위 식에서 $f(3)$은 $f(2) + f(1)$로 치환할 수 있으며, 같은 이유로 $f(2)$ 역시 $f(1) + f(0)$으로 치환 가능하다.
$f(4) = f(2) + f(1) + f(1) + f(0)$
$= f(1) + f(0) + f(1) + f(1) + f(0)$

결과적으로 $f(4) = 2(f0) + 3f(1)$로 정리할 수 있다.
따라서 이 문제의 알고리즘은 $N = 4$일 경우 2 3이 출력되어야 한다.

우선 식을 정리하여 한 눈에 보면 문제 해결에 도움이 될 것 같다.
피보나치 수열을 쭉 정리하면 아래와 같다.

표로 정리하니 어느정도 규칙성이 눈에 보이기 시작한다.

• N의 $f(1)$ 출력 갯수는 $f(N)$과 동일하다.
• N의 $f(0)$ 출력 갯수는 $f(N - 1)$과 동일하다.

즉, $N = 4$일 경우 알고리즘은 $f(3)$ $f(4)$가 출력되면 된다.

여기서 단순하게 생각하면 아래와 같이 코드를 짤 수 있다.

완성....?

---

JAVA
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Scanner;

/**
 * 백준 전체 1003 문제 알고리즘 클래스
 *
 * @author RWB
 * @since 2021.04.21 Wed 23:29:03
 */
public class Main
{
	static Integer[][] arr = new Integer[41][2];

	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);

		// N = 0일 때, 0이 호출되는 횟수
		arr[0][0] = 1;

		// N = 0일 때, 1이 호출되는 횟수
		arr[0][1] = 0;

		// N = 1일 때, 0이 호출되는 횟수
		arr[1][0] = 0;

		// N = 1일 때, 1이 호출되는 횟수
		arr[1][1] = 1;

		int length = scanner.nextInt();

		for (int i = 0; i < length; i++)
		{
			int n = scanner.nextInt();

			int f0 = fibonacci(n - 1);
			int f1 = fibonacci(n);

			System.out.println(f0 + " " + f1);
		}
	}

	/**
	 * 피보나치 값 반환 함수
	 *
	 * @param n: [int] 인덱스
	 *
	 * @return [int] 피보나치 값
	 */
	private static int fibonacci(int n)
	{
		// 인덱스가 0일 경우
		if (n == 0)
		{
			return 0;
		}

		// 인덱스가 1일 경우
		else if (n == 1)
		{
			return 1;
		}

		// 인덱스가 2 이상일 경우 (연산 가능)
		else
		{
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
}

위 코드는 크게 두 가지 문제가 있는데, 우선 $n = 0, 1$일 때의 처리가 정상적으로 이루어지지 않고 있다.
$f(1) = f(0) + f(-1)$
N이 문제되기 이전에 이 코드는 런타임 시간 초과로 실패한다. 왜일까?

위 코드는 불필요한 연산을 너무 많이 수행한다. 피보나치 수열의 특성 상 $f(N)$을 계산할 경우, $f(N - 1)$, $f(N - 2)$ ... 등과 같이 N 이하의 피보나치 값까지 전부 계산하게 된다.
다시 말하면, $f(6)$을 연산할 경우 계산 과정에서 자연스레 $f(4)$, $f(2)$ 등의 피보나치 값을 구할 수 있다.

위 이론을 알고리즘에 적용하면 아래와 같이 응용할 수 있다.
N을 총 3번 입력한다고 가정하면 $N_1$, $N_2$, $N_3$으로 구분할 수 있다.

$N_2 = 8$ -> $f(8)$ 부터 $f(0)$까지의 값을 구할 수 있음.
$N_3 = 4$ -> $f(4)$ 부터 $f(0)$까지의 값을 구할 수 있음.

피보나치 연산값을 저장하면 $N_n > N_n+1$일 경우 굳이 추가적인 연산을 진행하지 않고 이미 저장된 값을 출력만 함으로써, 런타임 리소스를 줄일 수 있다.

클래스의 멤버변수로 Integer 배열을 선언하여 피보나치 수열값을 저장하고, 알고리즘 연산에 이를 활용하면 될 것 같다.

다행히 문제에서 주어진 $N$의 조건은 $0 <= N <= 40$이므로, 배열의 인덱스는 최대 41을 넘지 않음을 알 수 있다.
(배열은 0부터 시작하므로 40개가 아닌 0을 포함한 41개임에 유의하자)

이후 피보나치 연산에서 각 과정의 값을 배열에 저장하는 로직을 추가한다.
배열의 값이 null일 경우, 아직 연산이 진행되지 않았으므로 피보나치 연산을 수행하고 배열에 저장한다.
반대로, 배열이 특정 숫자값을 가질 경우, 이미 연산이 진행된 인덱스이므로 별도의 연산을 거치지 않고 해당 값을 바로 출력한다.

전체 소스

---

JAVA
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.Scanner;

/**
 * 백준 전체 1003 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/05/21/a1003">1003 풀이</a>
 * @since 2021.04.21 Wed 23:29:03
 */
public class Main
{
	static Integer[] arr = new Integer[41];
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		// 피보나치 수열 초기값 (N = 0)
		arr[0] = 0;
		
		// 피보나치 수열 초기값 (N = 1)
		arr[1] = 1;
		
		int length = scanner.nextInt();
		
		for (int i = 0; i < length; i++)
		{
			int n = scanner.nextInt();
			
			fibonacci(n);
			
			// n이 0일 경우
			if (n == 0)
			{
				System.out.println("1 0");
			}
			
			// n이 1일 경우
			else if (n == 1)
			{
				System.out.println("0 1");
			}
			
			// 초기값이 아닐 경우
			else
			{
				System.out.println(new StringBuffer().append(arr[n - 1]).append(" ").append(arr[n]).toString());
			}
		}
		
		scanner.close();
	}
	
	/**
	 * 피보나치 값 반환 함수
	 *
	 * @param n: [int] 인덱스
	 *
	 * @return [int] 피보나치 값
	 */
	private static int fibonacci(int n)
	{
		// 해당 인덱스의 피보나치가 아직 연산되지 않았을 경우
		if (arr[n] == null)
		{
			arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}
		
		return arr[n];
	}
}

분류

---

• 다이나믹 프로그래밍