[백준] 2748번 : 피보나치 수 2 - JAVA [자바]

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

 

---

• 문제

 

 

 

동적 계획법 1의 첫 문제다.

확인한바 동적계획법에서 사라졌다. (2021.01.02)

 

 

이 전 재귀 문제에서도 피보나치 수 문제를 올려둔 것이 있으니 한 번 아래 포스팅을 참고해보시는 것도 좋을 것 같다.

st-lab.tistory.com/94 

[백준] 10870번 : 피보나치 수 5 - JAVA [자바]

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

피보나치 수의 경우 문제 자체는 어렵지 않게 풀 수 있을 것이다.사실 이 문제는 어렵지 않다. 다만, 이번 동적 계획법의 첫 문제인만큼 동적계획법이 무엇인지, 그리고 어떻게 접근해야하는지를 알려줄 것이다.

 

 

위 참고링크의 포스팅을 보면 피보나치 수 5 문제의 경우 재귀로 풀었다. 그 외에도 반복문, 배열 등 여러 접근 방법이 있는데, 이 문제에서는 배열을 이용하여 풀이해볼 것이다.

 

그 전에 먼저 동적 계획법이 무엇인이 알아보도록 하자.

 

 

먼저 동적 계획법은 영어로는 Dynamic Programming 이라고 하고 흔히 줄여서 DP 라고 부른다.

그럼 동적 계획법은 무엇이냐라고 한다면 가장 쉽게 말해서 '어떤 주어진 문제를 작은문제로 쪼개서 풀어나감에 있어 반복되는 호출을 줄이는 방법'이다.

 

눈치 빠른 분들은 이렇게 느꼈을 수도 있다. "분할 정복이랑 비슷하네!"

만약 백준 문제를 카테고리 별로 쭉 풀어오신 분이라면 한 번쯤은 접해보셨을 것이다. 필자의 포스팅에서도 있는데, 대표적인 분할 정복 문제가 바로 별찍기-10 이었다.

st-lab.tistory.com/95

[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]

 

그렇다. 분할 정복이랑 접근 방법 자체는 유사하다. 흔히 동적계획법은 재귀로 많이 설명된다.

 

크게 동적계획법은 두 가지 방식으로 나뉘는데 재귀(Top-Down) 방식, 반복문(Bottom-Up) 방식이 있다.

 

먼저 재귀 방식은 큰 문제를 하위 문제로 쪼개어 가장 하위의 문제부터 풀어나가는 방법이다. 다만 다른점이 있다. 동적계획법은 "반복되는 문제는 한 번만 푼다"는 것이 추가된다. 즉, 쉽게 말하면 이미 풀렸던 값을 재활용한다고 생각하면 쉽다.

 

그리고 이러한 재활용, 즉 이미 풀린 하위 문제를 다시 풀지 않고 재활용 하는 것을 메모이제이션(Memoization) 이라고 한다.

 

무슨 말인가 싶을 것 같은 분들을 위해 이해하기 쉽게 위의 피보나치 수를 이용하여 비교해보도록 하겠다.

 

일반적으로 피보나치 수를 재귀를 이용하여 푼다고 하면 코드는 다음과 같다.

int Fib(int N) {
	if(N == 0) return 0;
	if(N == 1) return 1;
 
	return Fib(N - 1) + Fib(N - 2);
}

 

그럼 만약 Fibonacci(5)을 구한다고 한다면, 다음과 같이 수행한다.

 

1.  Fib(5)

2. Fib(4) + Fib(3)

3. ( Fib(3) + Fib(2) ) + ( Fib(2) + Fib(1) )

4. ( ( Fib(2) + Fib(1) ) + ( Fib(1) + Fib(0) ) ) + ( ( Fib(1) + Fib(0) ) + Fib(1) )

5. ( ( ( Fib(1) + Fib(0) )+ Fib(1) ) + ( Fib(1) + Fib(0) ) ) + ( ( Fib(1) + Fib(0) ) + Fib(1) )

 

위 과정에서 보면 Fib(2)이 두 번 호출되는 것을 볼 수 있다. Fib(2) 때문에 이미 계산한 과정이 있음에도 다른 부분에서 Fib(2)를 호출하면 또 다시 Fib(0) 또는 Fib(1) 이 될 떄 까지 또 재귀호출이 되기에 매우 시간이 낭비된다.

 

 

 

그러면 DP 방식으로 풀라면 어떻게 할까?

앞서 말했듯이 작은 부분부터 풀되 이미 계산한 적이 있는 경우 또다시 계산하는 것이 아닌 해당 값을 재활용하면 된다. 즉, 메모이제이션을 하라는 말이다.

 

즉, 배열을 이용하여 해당 배열에 값이 없는 경우는 재귀호출을 하고, 있을 경우는 그 값을 그대로 쓰면 된다. 코드로 보면 다음과 같다.

static int[] arr = new int[size];	// 배열 비어있는 표시는 -1 이라고 가정

arr[0] = 0;
arr[1] = 1;

int Fib(int N) {
	if(arr[N] == -1) {	// 해당 배열에 값이 없을경우 재귀호출
		arr[N] = Fib(N - 1) + Fib(N - 2);
 	}
	return arr[N];
}

 

이 방법이 정석인 방법이다.

일단 자바의 경우 int 배열을 생성할 경우 0이 디폴트 값으로 설정되어있기 때문에 비어있는 수를 체크할 때 0으로 하면 Fib(0) 의 경우 중복되기 때문에 이러한 것을 방지하기 위해 -1 으로 초기화해주고나서 풀어야한다. (또는 Integer 배열로 하여 null 체크를 해주어도 된다.)

 

(null 체크를 위해 다음과 같이 해도 된다.)

static Integer[] arr = new Integer[size];

arr[0] = 0;
arr[1] = 1;

int Fib(int N) {
	if(arr[N] == null) {	// 해당 배열에 값이 없을경우 재귀호출
		arr[N] = Fib(N - 1) + Fib(N - 2);
 	}
	return arr[N];
}

 

 

그리고 해당 배열 index에는 각 계산한 값이 들어가고, 만약 중복호출일 경우 굳이 재귀호출 할 필요 없이 해당 index의 값을 사용하면 된다.

 

특이 위와같은 방법은 중복되는 재귀호출이 많으면 많을수록, 재귀가 깊으면 깊을수록 효율이 극대화 된다.

 

단 주의할 점은 문제에서는 N=90 까지 주어지기 때문에 long 타입으로 해주어야 한다.

(참고로 N=90 일 때의 수는 2880067194370816120 이다.)

 

 

 

반대로 재귀 방식이 아닌 반복문으로도 풀 수 있다.

흔히 반복문으로 접근하는 방식을 Bottom-Up(상향식)이라고 하는데, 이 또한 동적계획법이 가능하다. 대신 재귀에 비해 조금은 까다롭다. 먼저 재귀는 큰 문제에서 작은문제로 쪼개들어가기 때문에 별다른 초기값이 없고 재귀 탈출 조건만 잘 설정해주면 된다.

반면에 반복문은 반대로 작은문제들을 풀어서 하나의 큰 문제로 합쳐나가는 방식이기 때문에 초기 조건이 약간 필요하다.

 

 

long sum = 1;
long f1 = 0;
long f2 = 1;
		
for(int i = 1 ; i < N ; i++) {
	sum = f1 + f2;
	f1 = f2;
	f2 = sum;
}

 

물론 여기서 메모이제이션이 뭐가 되었냐고 하겠다만, 사실 피보나치 수 같은 경우 변수 자체가 메모이제이션이 된 것이기 때문에... 나중에 문제를 더 풀다보면 반복문으로도 메모이제이션을 하기위한 배열이 필요하다는 것을 볼 수 있을 것이다.

 

여튼 위 코드에서 보면 알겠지만, 재귀는 함수 호출을 재귀적으로 하면서 변수를 줄여가 작은 단위를 푸는 방식이라면, 반복문은 작은 문제들을 해결해가면서 큰 문제로 합쳐나가는 방식이라는 것이다.,

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

메모이제이션을 명확하게 볼 수 있는 재귀(Top-Down)방식 코드와 반복문(Bottom-Up)방식 코드 풀이 하는 것은 입력 방법을 Scanner 와 BufferedReader을 각각 사용하여 성능을 비교해보고자 한다. 단순 반복문의 경우는 한 가지 입력방식으로 BufferedReader만 쓸 것이다.

 

또한 기본적으로 DP의 경우 long[] 배열이 여러분들에게 익숙하기 때문에 int형 배열로 풀 것이나, null체크를 쉽게하기 위해 Long[] 배열도 같이 첨부하겠다.

 

풀이방법 3가지는 다음과 같다.

 

1 . 재귀 + Scanner

2. 재귀 + BufferedReader 

3. 반복문 + BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [재귀 + Scanner]

 

import java.util.Scanner;

public class Main {

	static long[] arr;
    
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		arr = new long[N + 1];

		for(int i = 0; i < N + 1; i++) {
			arr[i] = -1;
		}
        
		arr[0] = 0;
		arr[1] = 1;
		System.out.println(Fib(N));
	}
	
	public static long Fib(int N) {
		if(arr[N] == -1) {
			arr[N] = Fib(N - 1) + Fib(N - 2);
		}
		return arr[N];
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

물론 기본 타입인 long을 사용하여 배열을 선언하면 0값이 디폴트로 되어있기 때문에 -1로 초기화 해주어야 한다.

이러한 번거로움을 덜기 위해 객체로 변경하여 Long 타입인 래퍼(Wrapper)클래스를 이용하는 것도 하나의 방법이다. 해당 방법은 더보기를 누르면 된다.

 

static Integer[] arr = new Integer[size];

arr[0] = 0;
arr[1] = 1;

int Fib(int N) {
	if(arr[N] == null) {	// 해당 배열에 값이 없을경우 재귀호출
		arr[N] = Fib(N - 1) + Fib(N - 2);
 	}
	return arr[N];
}

 

 

 

---

- 방법 2 : [재귀 + BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

 

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

public class Main {

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

		for(int i = 0; i < N + 1; i++) {
			arr[i] = -1;
		}
        
		arr[0] = 0;
		arr[1] = 1;
		System.out.println(Fib(N));
	}
	
	public static long Fib(int N) {
		if(arr[N] == -1) {
			arr[N] = Fib(N - 1) + Fib(N - 2);
		}
		return arr[N];
	}

}

 

 

 

Long 타입은 아래 더보기를 눌러 확인하면 된다.

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

public class Main {

	static Long[] arr;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		arr = new Long[N + 1];
		arr[0] = 0L;
		arr[1] = 1L;
		System.out.println(Fib(N));
	}
	
	public static long Fib(int N) {
		if(arr[N] == null) {
			arr[N] = Fib(N - 1) + Fib(N - 2);
		}
		return arr[N];
	}

}

 

 

---

- 방법 3 : [반복문 + BufferedReader]

 

 

 

가장 단순한 방식이다. 굳이 재귀호출할 필요 없이 0부터 N까지 반복하며 이전 값의 연산을 통해 N번째 피보나치 수를 찾는 방식이다. 

 

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		
		long sum = 1;
		long f1 = 0;
		long f2 = 1;
		
		for(int i = 1 ; i < N ; i++) {
			sum = f1 + f2;
			f1 = f2;
			f2 = sum;
		}
		
		System.out.println(sum);
	}
}

 

 

sum이 1부터 시작하는 이유는 입력이 자연수로 주어지는데, 1이 주어질 경우 밑의 반복문은 실행하지 않기 때문에 1을 출력할 수 있도록 1로 초기화한 것이다.

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 21119379  -  방법 3 : 반복문 + BufferedReader

채점 번호 : 21119374  -  방법 2 : 재귀 + BufferedReader

채점 번호 : 21119367  -  방법 1 : 재귀 + Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

오늘은 동적 계획법의 기초적인 지식과 어떻게 접근해야하는지를 알아보았다.

우리가 그동안 재귀, 브루트포스, 백트래킹 문제를 풀어보면 알겠지만, 이번 DP 카테고리의 경우 해당 문제들을 좀 더 효율적으로 풀 수 있게 해주는 방법 중 하나라는 것을 알게 될 것이다. 그만큼 중요한 알고리즘 중 하나이므로 이번 기초 방법을 잘 익혀두면 좋을 것이다.

 

특히 동적계획법의 가장 중요한 것은 '메모이제이션(memoization)'을 어떻게 잘 활용하냐의 문제다.

 

물론 이번 문제의 경우 굳이 재귀방법을 사용할 필요가 없는 문제지만 DP 카테고리인 만큼 메모이제이션을 보여주기 위한 취지에 맞게 정석적인 방법을 보여주었다.

 

만약 모르는 부분이 있다면 댓글 남겨주시면 최대한 빠른 시일내로 답변드리도록 하겠다.