이코테 - 다이나믹 프로그래밍(dp)

이코테 - 다이나믹 프로그래밍

본 게시물은 이것이 코딩테스트다(저자 나동빈님)의 책을 구매하고 공부하는 과정에서 남기는 정보공유의 목적보다

개인적인 기록에 가까운 포스팅입니다.

 

항상 이런저런 이유로 알고리즘 풀이를 신경끄고 살다가 이제 졸업을 앞두게 되니 코딩테스트를 맞닥뜨리게 되었다.

한번도 제대로 준비해본적이 없어서 문제 대충 읽고 구현하는 연습만 했더니 난이도가 있는 문제는 하나도 못풀었다.

 

어떻게 푸는거지 하면서 찾아보니 내가 못 푼 문제는 대부분 DP 문제였다... 올 하반기동안은 알고리즘 실력을 늘리는데에 집중해보자 !!!

 

 

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 완전탐색을 했을때 매우 비효율적인 시간복잡도를 가지고 하는 문제라도 다이나믹 프로그래밍을 이용하면 시간 복잡도를 획기적으로 줄일 수 있는 경우가 많다.

 

이러한 다이나믹 프로그래밍은 일반적으로 탑다운과 보텀업 두가지 방식으로 구성된다.

 

 

다이나믹 프로그래밍의 조건

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눌 수 있으며, 동일한 작은 문제를 반복적으로 해결해야한다.

 

가장 대표적인 예시인 피보나치 수열을 살펴보자

일반적인 풀이 방법으로는 위의 점화식을 재귀로 푸는 방법이 일반적인데

위의 코드로 피보나치 수열을 계산할 수 있다.

하지만 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간의 복잡도를 가지게 된다.

위의 그림을 보면 f(6)을 구하는 과정에서 f(2)가 5번이나 호출되는 것을 볼 수 있다.

따라서 다이나믹 프로그래밍의 조건인 최적 부분 구조와 , 중복되는 부분 문제 두가지 조건을 만족한다.

 

먼저 하향식 DP를 알아보자.

탑다운(메모이제이션)

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.

같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다

 

탑다운 VS 보텀업

탑다운 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.

탑다운 방식은 구현 과정에서 재귀함수를 이용한다. 즉 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 작은 문제들이 모두해결되었을때 큰 문제가 해결되도록 코드를 작성한다.

 

호출해서 작은 

전형적인 DP의 형태는 상향식 방식이고, 결과 저장용 리스트는 DP 테이블이라고 부름

 

엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미한다

따라서 메모이제이션은 DP에 국한된 개념은 아니다

 

피보나치 수열을 탑다운 DP로 풀이한 소스코드

# memoization을 위한 리스트 초기화 d = [0] * 100 def fibo(x):     # base case      if x ==1 or x == 2:         return 1     # 이미 계산한 적 있는 문제라면 그대로 결과값 반환 ( DP TABLE )     if d[x] != 0:         return d[x]     # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환     d[x] = fibo(x-1) + fibo(x-2)     return d[x]

피보나치 수열을 보텀업 DP로 풀이한 소스코드

d = [0] * 100 d[1] = 1 d[2] = 1 n= 99 for i in range(3, n + 1):       d[i] = d[ i - 1 ] + d[ i - 2] print(d[n])

위와 같이 메모이제이션을 통해 피보나치 수열을 풀이하게 되면 부분 문제를 여러번 해결하는 과정이 없어집니다.

 

이렇게 메모이제이션을 이용하면 기존의 피보나치 수열 함수를 풀이할 때 걸렸던 지수시간의 시간복잡도를 O(N) 까지 줄일 수 있다.

다이나믹 프로그래밍 vs 분할정복

다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.

즉 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황에 적합하다

 

차이점은 부분 문제의 중복을 가지는가 이다

다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

분할정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

분할정복의 대표적인 예시인 퀵 정렬을 살펴보면, 피벗이 한번 처리되면 다시 호출되지 않는다.

즉 부분 문제의 중복을 가지지 않는 것

예를 들면 그림의 5가 피벗일때, 위치가 정해지면 피벗을 기준으로 좌측은 5보다 작고

우측은 5보다 크다. 따라서 정렬이 모두 이루어진 뒤에도 5의 위치는 변하지 않는다.

 

다이나믹 프로그래밍 문제에 접근하는 방법

1. 주어진 문제가 DP 유형임을 파악 하는 것이 중요하다

2. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고

다른 알고리즘으로 풀이 방법이 떠오르지 않으면 DP를 고려한다

3. 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수있으면

코드를 개선한다.

4. 일반적으로 코딩 테스트 수준에서는 기본 유형의 DP 문제가 출제되는 경우가 많다.

 

 

DP 문제1. 개미전사

예시처럼 N = 4, 식량 = [1,3,1,5]와 같다면

위 처럼 8가지 경우가 존재하게 되고 7번째 경우 3,5가 최적의 해가 된다.

N과 식량 리스트가 입력으로 주어질 때 어떻게 해야 최적의 해를 구할 수 있을까?

 

먼저 

i번째 식량창고까지의 최적의 해를 a{i}로 정의한다. 

 이렇게되면

a{0} 부터 a{3}까지 각 창고에서의 최적의 해를 계산할 수 있다. 

따라서 일반화하여 a{i}번째 창고에서 최적의 해를 계산한다는 것은 아래와 같다.

다음으로 다이나믹 프로그래밍 문제 조건을 만족하는지 생각해보자.

 

1. 최적 부분 구조를 만족하는가?

i번째 창고에서 최적의 해는 i-1번째 또는 i-2번째 최적의 해 가 필요하다

 

2. 중복되는 부분 문제가 있는가?

i번째 창고의 최적의 해를 위해 1~i-1 창고까지의 최적의 해를 구해야하는 과정이 중복된다.

 

문제해결 아이디어를 정리하면 아래와 같다.

 

n = int(input()) array = list(map,int input().split()) d = [0] * 100 d[0] = array[0] d[1] = max(array[0], array[1]) for i in range(2,n):     d[i] = max(d[i-1], d[i-2] + array[i]) print(d[n-1])

강의를 들으면서 느낀 것은 DP에서 가장 중요한 것은 재귀를 떠올리거나 점화식을 떠올리는 것이 핵심이라고 생각했다.