선택 트랙 알고리즘 [9일차]

1. DP의 탄생 배경

: DP는 완전탐색의 단점을 보안하기 위해서 생겼다. 그럼 여기서 완전탐색은 무엇일까?

완전 탐색이란 말 그대로 처음부터 끝까지 다 돌면서 조건에 부합하는 경우를 고르는 탐색 알고리즘이다.

따라서 완전 탐색을 쓰게 되면 데이터가 많아질 수록 시간이 오래 걸린다. 그래서 나온 알고리즘이 DP이다.

즉 DP는 완전 탐색 보다 빠르며 정확한 알고리즘이다. 하지만 DP는 구현하는데에서 굉장한 어려움이 발생한다.

우리가 완전탐색을 구현하는 것도 힘든데 완전탐색을 효율적으로 처리하기 위해서는 당연히 더 힘들 수 밖에 없다.

그래서 나는 백준의 피보나치 함수를 통해서 한번 DP를 구체적으로 살펴볼까 한다.

 

 

2. DP의 구현방법

문제

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

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이 출력되는 횟수를 공백으로 구분해서 출력한다.

<풀이 및 회고>

: 우리는 여기서 0과 1을 사용한 경우를 봐야한다. 그럼 한번 나열해보자. 나열을 해보시면 알 수 있듯이 0과 1이 나온 횟수사이에서 피보나치 수열이 만들어지는 것을 확인할 수 있다. 즉 피보나치 안에 피보나치인 셈이다. 그럼 이문제를 어떻게 풀 수 있을까?

방법 중 하나는 재귀함수를 사용하는 것이다. 즉 예를 들어서 내가 피보나치와 관련된 코드를 가져오겠다.(문제와는 상관이 없습니다.)

def fibo(n):
	if n < 2:
    	return n
    else:
    	return fibo(n-1) + fibo(n-2)
print(fibo(10)) #55가 출력됨

하지만 위 경우에서는 들어오는 수 예를 들어 10이 들어온다면 2**10이라는 시간복잡도가 발생한다는 것을 알 수 있다.

즉 완전탐색으로 문제를 푼것이기에 우리는 dp를 이용할 필요가 있다.

dp를 구현하는 방법은 자료구조를 통해서 이전에 계산한 값을 저장하고 그 값을 이용해서 문제를 푸는 방식이다.

이를 코드로 구현하면 다음과 같다.

def fibo(n):
	val = [0,1]
    if n >= 2:
    	for i in range(2,n+1):
        	val.append(val[i-2] + val[i-1])
    return val[n]
print(fibo(10)) #55가 출력됨

위 코드의 시간복잡도를 그림으로 그리면 다음과 같다.

즉 모든 경우를 돌지 않고 전에 있었던 값을 이용하기 때문에 결국엔 문제를 풀때 시간복잡도가 훨씬 줄어드는 것이다.

이처럼 DP를 이용한다면 시간이 휠씬 줄어든다는 것을 알 수 있다.