[백준/boj.kr] 2748번 피보나치 수 2 (C/C++, JAVA)

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

1. 문제 정의

 

피보나치 수열은 학창시절에 많이 봐왔던 일종의 '점화식'으로 정의되는 수열입니다.

F(n) = F(n - 1) + F(n - 2) (단, n >= 2)

 

이 문제에 나와 있듯이, n=2 부터 점화식이 성립하고 n=0일 때 F(0) = 0, n = 1일 때 F(1) = 1 입니다.

 

 

2. 풀이 방법 탐색

예를 들어, n = 5라고 가정하고 점화식에 대입해 봅시다.

F(5) = F(4) + F(3) 라는 점화식을 구하기 위해 F(4), F(3)이 무엇인지 알아야 하고,

F(4) = F(3) + F(2) 라는 점화식을 구하기 위해 F(3), F(2)이 무엇인지 알아야 하고,

F(3) = F(2) + F(1) 라는 점화식을 구하기 위해 F(2), F(1)이 무엇인지 알야아 하고,

F(2) = F(1) + F(0) 라는 점화식을 구하기 위해 F(1), F(0)이 무엇인지 알아야 합니다.

 

 

이 때, F(5)를 구하기 위해 컴퓨터한테 계산을 하도록 시켰지만 컴퓨터는 위 그래프처럼 순서대로 여러개의 점화식을 계산하도록 순서를 구성합니다. 여기서 같은 색깔로 칠해져 있는 피보나치 원소가 중복되어 있음을 확인할 수 있습니다. F(3)은 2번 호출해야 하고, F(2)는 3번 호출해야 하고, F(1)은 4번 호출해야 하고, F(0)은 3번 호출해야 합니다.

 

이처럼 호출하는 횟수가 중복하게 되면, 속도와 메모리에 부담을 가지기 마련입니다.

이를 보완하기 위해 DP(Dynamic Programming) 방법론으로 풀어보겠습니다.

 

3. 풀이 순서 설계

DP(Dynamic Programming) 풀이는 다음의 순서로 설계할 수 있습니다.

 

1) DP로 풀 수 있는 문제인지 확인
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(점화식)
4) 메모하기(memoization or tabulation)
5) 기저 상태 파악하기
6) 구현하기

 

 

1) DP로 풀 수 있는 문제인지 확인

DP가 적용되기 위해서는 2가지의 조건을 만족해야 합니다.

 

① Overlapping Subproblems(겹치는 부분 문제)

위 그래프에서 확인한 것처럼, 중복되는 문제들이 여럿 등장합니다. 따라서 피보나치 수열은 겹치는 부분 문제로 구성되어 있습니다.

② Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 활용해 전체 문제의 최적 결과임을 보장해야 합니다. 피보나치 수열에서는 한 원소의 값이 정해져 있는 '해' 이므로, 고민의 여지 없이 최적 결과 값이며 이를 조합해 전체 문제의 최적 결과임이 보장 됩니다.

 

2) 문제의 변수 파악

F(n) = F(n - 1) + F(n - 2) (단, n >= 2)

위 점화식에서 존재하는 유일한 변수는 'n' 하나 입니다.

 

3) 변수 간 관계식 만들기(점화식)

피보나치 수열이고, 문제에서 제공되어 있는 것처럼 점화식은 다음과 같습니다.

F(n) = F(n - 1) + F(n - 2) (단, n >= 2)

 

4) 메모하기(memoization or tabulation)

DP 풀이의 핵심 중 하나는, '중복 계산하지 않기 위해 이전에 계산한 결과 값을 메모리에 저장한다!' 입니다.

F(1), F(2), F(3), F(4) ... 이 결과 값들을 저장하기 위해 dp[n] 메모리를 할당합니다.

 

5) 기저 상태 파악하기

재귀 방식으로 풀이를 작성할 경우, 재귀의 종료 조건인 '기저 조건'을 설정해야 합니다. 이 '기저 조건'이 설정되어 있지 않으면, 재귀 함수는 무한 루프에 빠지게 되므로 이를 방지해야 합니다.

이 피보나치 수열에서 기저 조건은 2가지 입니다.

① n < 2인 경우

② 이미 구한 적이 있는 F(n)인 경우

 

이외에도, 피보나치 수열은 n이 커질수록 기하급수적으로 그 값이 증가합니다. int 범위로 담을 수 있는 피보나치의 최대 값은 354224848179261915075(n = 46) 으로 64비트 이상을 사용합니다. 이 문제에서 n은 90이하의 자연수 이므로, int가 아닌 long long 자료형으로 연산을 진행해야 합니다.

(참고)

 

6) 구현하기

DP는 2가지 방식으로 구현할 수 있다.

1) Bottom-Up (Tabulation 방식) - 반복문 사용
2) Top-Down (Memoization 방식) - 재귀 사용

 

① Bottom-Up 방식

이름에서 느껴지듯이, 아래부터 점차 위로 계산을 수행하며 전체 큰 문제를 해결하는 방식 입니다.

피보나치 수열에서 '아래'라 함은 n=0이 될 것이며 n이 커질수록 점차 위로 계산하는 순서일 것입니다.

long long dp[100];

long long fibbo(int n) {
	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return dp[n];
}

-. for문을 이용해 아래부터 점차 계산한다.

-. 이전에 계산했던 값을 dp에 저장한다. -> Memoization

-. for문이 한번 돌 때마다의 결과 값이 최적의 해이고, 전체 큰 문제의 최적 결과로 이어질 수 있다.

 

여기서, Bottom-Up 방식같은 경우 Memoization 또는 'Tabulation' 이라고 부릅니다.

Tabulation? 

: 반복문을 통해 dp[0]부터 하나씩 채우는 과정을 "table-filling"이라 하고, 이 Table에 저장된 값을 직접 활용하므로 "Tabulation" 이라고 호칭하기도 한다.

 

② Top-Down 방식

위에서부터 바로 호출을 시작하여 dp[0]까지 내려간 다음, 재귀를 통해 차근차근 결과 값을 계산하는 방식 입니다.

피보나치 수열에서 '위'라 함은 F(n)을 뜻합니다.

 

long long dp[100];

long long fibbo(int n) {
	// 기저 조건
	if (n <= 1) return n;
	else if (dp[n] != 0) return dp[n];

	dp[n] = fibbo(n - 1) + fibbo(n - 2);

	return dp[n];
}

-. 재귀함수의 기저조건을 세운다.

   : n <= 1 이거나, 이미 구한 값일 때 바로 return!

-. 피보나치 수열의 점화식을 활용해, 재귀로 dp[0]까지 내려간다.

   : Stack에 현재까지 수행했던 부분이 기록되어 쌓이게 된다.

-. n <= 1일 때, 0과 1을 리턴하게 되면서, 쌓았던 Stack이 하나씩 pop하게 된다.

-. 결국 n=0부터 차근차근 계산하여 dp[n] 값을 가져온다.

 

 

4-1. 최종 제출 소스(C++)

①  Bottom-Up 방식

#include <cstdio>

long long dp[100];

long long fibbo(int n) {
	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return dp[n];
}


int main(void) {
	int n;
	scanf("%d", &n);

	printf("%lld\n", fibbo(n));
}

 

 

② Top-Down 방식

#include <cstdio>

long long dp[100];

long long fibbo(int n) {
	if (n <= 1) return n;
	else if (dp[n] != 0) return dp[n];

	dp[n] = fibbo(n - 1) + fibbo(n - 2);

	return dp[n];	
}

int main(void) {
	int n;
	scanf("%d", &n);

	printf("%lld\n", fibbo(n));
}

 

4-2. 최종 소스(JAVA)

JAVA의 자료형은 C/C++와 상이한 부분이 있다.

(참고)

C/C++에서는 long long 자료형으로 할당한 반면, JAVA에서는 long으로 할당한다.

 

 

① Bottom-Up 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static long dp[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		dp = new long[N + 1];
		
		System.out.println(fibbo(N));
	}

	public static long fibbo(int n) {
		dp[0] = 0;
		dp[1] = 1;
		
		for(int i=2; i<=n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		
		return dp[n];
	}
}

 

② Top-Down 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static long dp[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		dp = new long[N + 1];
		
		
		System.out.println(fibbo(N));
	}

	public static long fibbo(int n) {
		if(n <= 1) return n;
		else if(dp[n] != 0) return dp[n];
		
		dp[n] = fibbo(n - 1) + fibbo(n - 2);
		
		return dp[n];
	}
}