DP(Dynamic Programming) 동적 프로그래밍

1. DP(Dynamic Programming) 이란?

 

• 각각의 작은 문제들을 해결한 값들을 저장하여 나중의 큰 문제를 해결할 때 결과들을 합산하여 구하는 것
• 메모리를 많이 사용하는 대신 연산 속도를 높여준다.

 

2. DP(Dynamic Programming) 조건

 

DP(Dynamic Programming)은 작은 값들을 기억했다가 큰 문제를 해결할 때 그 값들을 활용하여 푸는 구조를 가지고 있다. 조건으로는 아래 두 조건을 만족해야 적용할 수 있다.

• 부분 최적 구조 : 작은 문제의 결과를 모아서 큰 문제를 해결할 수 있는 구조
• 중복되는 부분 문제 : 동일한 작은 문제들을 반복적으로 해결할 수 있어야 한다.

 

3. DP(Dynamic Programming) 특징

 

  DP는 메모리를 많이 사용한다고 말을 했는데 이는 메모제이션을 이용하여 문제의 값들을 저장해둔 후 그 값들을 불러오는 구조를 취하기 때문에 메모리를 많이 사용하는 대신 연산 속도를 높여준다고 말을 할 수 있다.

 

  예를 들어 매번 값들을 반복문을 통해서 계산을 하는 것과 리스트를 통해서 계산된 값들을 저장해둔 후 거기서 들어오는 변수에 따라서 값을 내주는 것 중 어느 것이 연산의 속도가 빠를 것인지를 생각해보면 간단하다. 들어오는 수의 값이 작은 경우는 별반 다를게 없을지라도 들어오는 숫자의 양이 많아질 수록 연산속도 에서는 DP가 매우 빠르다.

 

  DP의 대표적인 예시인 "피보나치 수열"을 통해서 살펴보자.

"피보나치 수열"이란? => 첫째 항, 둘째 항 의 값은 1이고 그 이후 항들의 값은 그 이전의 값들의 합으로 나타낼 수 있다 라는 것이다.

1.  1 + 1 = 2 => 3번째 항 [ 1, 1, 2 ]
2.  1 + 2 = 3 => 4번째 항 [ 1, 1, 2, 3 ]
3. 2 + 3 = 5 => 5번째 항 [ 1, 1, 2, 3, 5 ]

이런 식으로 값들을 더해나가는 것이다.

 

  피보나치 수열을 해결하는데 있어서 보통은 재귀로 풀지만 알고리즘 에서는 재귀를 사용할 경우 시간초과가 날 확률이 높다.

def fibonacci(num):
    if num == 1 or num == 2:
    	return 1
    else:
    	return fibonacci(num-1) + fibonacci(num-2)

 

  이런 식으로 재귀함수를 써버릴 경우 'num' 값이 커질 수록 return 되는 함수의 갯수가 많아지고 그 중 동일한 함수들도 호출이 되기 때문에 많은 시간이 소요된다. 

 

  이런 문제점을 해결하기 위해서 N 값까지의 리스트를 미리 생성한 후 그 이전의 값들을 더해나가는 방식으로 재귀에서 해야할 일을 DP로 해결할 수 있다.

def fibonacci(num):
    fibo_list = [0,1,1] + [0]*(num-2) # 0 ~ num 까지 생성
    
    if num < 2:
    	return fibo_list[num]
    
    for i in range(2, num+1):
    	fibo_list[i] = fibo_list[i-1] + fibo_list[i-2]
    
    return fibo_list[num]

  위와 같이 num 의 크기만큼 리스트를 생성해준 후 함수를 통해 연산된 값을 가져와서 출력해주기만 하면 들어온 input 값에 따라서 계속해서 연산을 해나가거나 더해나갈 필요가 없다. 이미 함수로 연산을 끝내뒀기 때문에 함수를 한번 실행한 후 값만 넣어주면 바로 출력이 되기 때문이다. 이러한 방식을 메모제이션이라 부르고 메모리를 많이 차지하는 대신 연산속도는 훨씬 빨라지게 된다.

 

4. DP(Dynamic Programming) 구현 방법

 

1. Bottom-up 방식

def fibonacci(num):
    num_list = [0, 1]
    for i in range(2,num+1):
    	num_list.append(num_list[i-1] + num_list[i-2])
    return num_list

 

•   "상향식" 방식이라고도 얘기할 수 있으며 작은 값들부터 차례로 쌓아가며 답을 찾는 방식이다.
• 보통 반복문을 이용해서 구현을 한다.

 

2. Top-down

def fibonacci(num):
    if (num == 1 or num == 2):
    	return num
    elif num > 1:
    	return (fibonacci(num-1) + fibonacci(num-2))

 

• "하향식" 방식이라고도 얘기하며 재귀함수를 이용하여 구현 하며 큰 문제를 해결할때 작은 문제가 해결되지 않았을 때 사용한다.

 

• 문제를 풀기 위해서 어느 방식만을 익혀두기 보다는 두 방식모두 익혀두고 문제를 접하는 것이 좋다.
• DP(Dynamic Programming)은 개인적인 생각으로는 많은 문제를 풀어보면서 익히는 것이 좋은 것 같다.
• 문제를 읽고 문제의 규칙을 찾는 것이 매우 중요한 부분인 것 같고, 모르는 점이 생기면 직접 손으로 경우의 수를 적어보면 규칙을 찾을 수 있는 경우가 많이 있는 것 같다. 알고리즘을 풀기 위해서는 눈으로만 푸는 것이 아니라 손으로 직접 써가며 풀이를 해봐야 동작이 어떻게 작동되는지 눈으로 볼 수 있는 경우가 있으니 꼭 모르면 손으로 풀어본 후 검색을 해보자!!