약점보완: Dynamic Programming

 

 

" 계속 쓰일 값은 저장해놓고 가져다 쓰자"

메모리를 조금 더 쓰지만,

수행 시간을 단축시킬 수 있다.

 

 

큰 문제를 작은 문제들로 분할하여

작은 문제들을 푼 결과를 이용해서 큰 문제를 해결하는 방법

---

 

DP를 사용하려면?

1. 큰 문제를 작은 부분 문제로 나눌 수 있을 때
2. 작은 문제에서 구한 정답을 큰 문제에서 사용할 때에도 동일할 때

 

 

---

DP으로 문제를 어떻게 해결할까?

1. 메모이제이션 (Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다
  • 같은 정보를 다시 호출하면 메모했던 결과를 그대로 가져옵니다
  • 값을 기억해둔다는 점에서 캐싱(caching)라고 합니다

'한 번 계산한 결과를 메모리 공간에 기록했다가 필요할 때 가져오자'

---

2. Top-Down vs Bottom-Up

• 이처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 탑다운(Top-Down)방식이라고 한다.
• 반면에 작은 문제부터 차근차근 답을 도출하는 방식을 보텀업(Bottom-Up)방식이라고 말한다

작은 문제부터 해결해서 큰 문제를 해결할 것인가.
큰 문제부터 해결해서 작은 문제를 해결해 나갈 것인가

• 탑다운 방식(Memoization)은 하향식이라고 하며 Bottom-Up 방식은 상향식이라고 한다
• 다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식이다
  • 결과 저장용 리스트는 DP 테이블이라고 부른다
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미한다

 

탑다운Top-Down 방식 예시

재귀 함수를 이용하여 다이나믹 프로그래밍 알고리즘을 사용하는 방법은 큰 문제를 해결하기 위해 작은 문제를 호출

"f(6)을 구하려고 보니 f(5)가 필요하고 f(5)를 구하려고 보니 f(4)가 필요하고.."의 과정이 반복되어 결국 맨 밑의 값까지 구하는 연산까지 갔다가 값을 저장하면서 차레대로 다시 올라온다.

# 한 번 계산된 결과를 memoization하기 위한 리스트 초기화
d = [0] * 100

# Fibonacci Function을 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    #종료 조건 (1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    #이미 계산한 적 있는 문제라면 그대로 반환 (memoization)
    if d[x] != 0:
        return d[x]
    #아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] =  fibo(x-1) + fibo(x-2)
    return d[x]

이렇게 피보나치 수열을 구하는 함수를 구현한 코드의 시간복잡도는 O(N)이다. 왜나햐면 한번 구한 피보나치수는 리스트에 저장되므로 다시 필요할 때 찾아서 꺼내오기만 하면 되기 때문에 N번째 피보나치 수열을 구할 때 N번의 연산만 필요하다. (f(6)을 구할 때 f(5), f(4), f(3)을 각각 한번씩만 연산하면 된다)

실선으로 표현된 노드만 연산하면 된다. (source : 이것이 코딩 테스트다 (나동빈, 한빛미디어))

 

 

보텀업Bottom-Up 방식 예시

단순히 반복문을 이용해서 다이나믹 프로그래밍 알고리즘을 사용하는 방법은 작은 문제부터 답을 도출

 소스코드는 아래와 같다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

#Fibonacci Function 방복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
    
print(d[n])

6번째 피보나치수을 구하기 위해서 3번째 피보나치수부터 차례대로 수를 구해서 최종적으로 6번째 피보나치수에 다다른다. (다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.)

보텀업 방식에서 사용되는 작은 부분 문제들의 결과를 저장해놓는 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에서 국한되어 사용되는 방식이다.

(단, 메모이제이션이 탑다운 방식에 포함되는 개념은 아니며 맥락이 다른 용어이다. (이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 의미로 쓰인다.))

---

문제를 대하는 방법

1. 주어진 문제가 다이나믹 프로그래밍 유형인지 파악합니다
2. 특정한 문제를 완전탐색으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 확인합니다
   • 중복되는 부분문제들이 있는지 확인하는게 중요합니다
3. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어가 됩니다
4. 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장

---

막혔던 백준 문제

문제1: 계단 오르기 문제
https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 1. 한 칸 또는 두 칸 씩 점프

2. 연속된 세 계단 안됨, 마지막 도착 계단 반드시 밟아야함

3. 계단 수, 각 계단의 점수 입력됨

4. 계단의 갯수는 300개 이하의 자연수

5. 계단에 쓰여 있는 점수는 10,000 이하의 자연수

 

# 입력
n = int(input())
scores = [0 for i in range(301)]
dp_table = [0 for i in range(301)]
for i in range(n):
    scores[i] = int(input())


dp_table[0] = scores[0]
dp_table[1] = scores[0] + scores[1]
dp_table[2] = max(scores[1] + scores[2], scores[0] + scores[2])
for i in range(3, n):
    dp_table[i] = max(dp_table[i - 3] + scores[i - 1] + scores[i], dp_table[i - 2] + scores[i])
print(dp_table[n - 1])

scores로 점수 리스트를 받아주고, dp_table리스트는 점수의 합을 저장하는 리스트이다.

 

dp_table 리스트의 첫번째에는 당연히 s리스트 첫번째 점수가 들어가고,

 

dp_table[1]에는 scores[0] + scores[1] 즉, 첫번째 점수와 두번째 점수를 합한 값을 넣어준다.

 

dp_table[2]에는 첫번째 계단을 밟고 두 계단을 올랐을때 합과 두번째계단을 밟고 한 계단을 올랐을때 합 중에 큰 값을 넣어준다.

 

마지막 계단은 꼭 밟아야 하므로

 

1. 마지막 계단의 전 계단을 밟은 경우와

 

2. 마지막 계단의 전 계단을 밟지 않은 경우가 있다.

 

그러므로 dp_table[i]에는 dp_table[i - 3] + scores[i] + scores[i - 1]와 dp_table[i - 2] + scores[i] 이 들어갈 수 있다.

 

이 두 값 중에서 점수가 큰 값을 넣어준다.

 

 

---

문제2: 1이 될 때까지

참고 문제: https://www.acmicpc.net/problem/1463

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1. X가 5로 나누어 떨어지면 5로 나눈다.
2. X가 3으로 나누어 떨어지면 3으로 나눈다.
3. X가 2로 나누어 떨어지면 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

이 문제를 다이나믹 프로그래밍으로 풀기 위한 조건은 만족한다.

• 각 X의 최소 연산 횟수는 항상 같다.
• 각 X의 최소 연산 횟수의 값이 더 큰 X의 최소 연산 횟수를 구하는데에 반복적으로 필요하다.

문제풀이 소스코드는 다음과 같다.

x = int(input())
d = [0] * (x+1)

for i in range(2, x+1):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)
        
answer = d[x]

• x의 최소 연산 횟수를 저장하기 위한 list (d)를 생성한다.
• 2의 최소 연산 횟수부터 저장하기 시작하여 마지막으로 26의 최소 연산 횟수까지 저장한다. → Bottom-Up 방법

문제 해결 아이디어는 점화식으로 표현하면

즉, 24의 최소 연산 횟수는 23(=24-1)의 연산횟수, 8(=24/3)의 최소연산횟수, 12(=24/2)의 최소연산횟수의 최솟값 + 1이다. (24는 5로 나누어떨어지지 않으므로 최솟값을 고르는 선택지에 포함될 수 없다.) 1을 더해주는 이유는 23, 8, 12로 가기위한 연산 횟수를 더해줘야하기 때문이다!

x가 15일 때까지의 최소연산횟수를 저장한 리스트를 표현하면 이와 같다.

 

---

참고:  분할 정복과 다이나믹 프로그래밍의 차이점

큰 문제를 작은 문제들로 분할하는 알고리즘 중에는 '분할 정복 알고리즘'도 있다. 다이나믹 프로그래밍이 분할 정복과 다른점은 '작은 부분 문제를 반복적으로 풀어야 한다는 것'이다.

# 분할 정복 알고리즘
: 큰 문제를 작은 문제로 쪼갠 후, 각각 작은 부분 문제들을 풀어서 큰 문제를 해결한다.

 # 다이나믹 프로그래밍
: 작은 부분 문제로 큰 문제를 쪼개는 것은 같지만, 다이나믹 프로그래밍은 작은 문제의 결과값이 다른 부분 문제를 푸는 데에 반복되어 사용된다. (예를 들면 위에서 이야기 한 것처럼  피보나치 수열에서 f(6)를 계산하기 위해서는 f(3)의 결과값이 3번 필요한 것처럼..!_!)

 

 

https://eunbin00.tistory.com/71 , https://pacific-ocean.tistory.com/149, https://deepinsight.tistory.com/162 참조