[코드잇-알고리즘2 : 알고리즘 패러다임] 3. Dynamic Programming

본 게시물은 코드잇의(codeit) 알고리즘 시리즈 강의 세번째 주제인 'Dynamic Programming'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz

트리의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇

---

1. 최적 부분 구조 (Optimal Substructure)

Dynamic Programming을 사용하기 위해서 필요한 조건 두 가지

조건 1 : 최적 부분 구조

- 최적 부분 구조가 있다는 건 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 뜻

 

예시1 : 피보나치 수

 

- 다섯 번째 피보나치 수를 구하기 위해서는 네번째/세번째 피보나치 수를 구하는 부분 문제를 먼저 해결해야한다.

- 이 두 부분 문제의 최적의 답을 구하면 그걸 이용해서 기존 문제의 최적의 답을 구할 수 있음

- 그렇기 때문에 피보나치 문제는 최적 부분 구조를 갖고 있는 것

 

예시2: 최단 거리 구하기

- 서울에서 부산까지 최단 경로를 찾곡 싶음

- 그런데 부산으로 가기 위해서는 빨간색의 세 지점중에 하나를 무조건 거쳐가야 함

- 이에, 서울 -> 부산 최단경로 문제를 풀기 위해서는 서울에서 H로 가는 최단 경로 문제와 서울에서 I로 가는 최단 경로 문제, 서울에서 J로 가는 최단 경로 문제를 풀어야 하는 것.

- 즉, H까지의 최단 거리에 4를 더한것과 ,I/J에 마찬가지로 6/8을 더한거랑 비교해보면 최단거리를 알 수 있음

- 예시 1처럼 최적의 답을 전부 더한 것은 아니지만, 기존 문제의 최적의 답을 구했기 때문에 이 문제도 최적 부분 구조가 있음

2. 중복되는 부분 문제 (Overlapping Subproblems) 

Overlapping Subproblem (중복되는 부분 문제)

- fib(4)를 해결하기 위해서는 fib(3)과 fib(2)를 해결해야 한다.

- fib(3)을 해결하기 위해서는 fib(2)와 fib(1)을 해결해야 한다.

- fib (1), fib(2)는 base case

- 그런데 자세히 보면 중복되는 부분문제가 있음. 예를들어 fib(3)은 5번 계산함

- 이렇게 중복되는 부분 문제들을 해결하는 게 이번 챕터에서 배울 '다이나믹 프로그래밍'

Non-overlapping Subproblem (중복되지 않는 부분 문제)

- 부분 문제 중에 항상 중복되는 부분 문제만 있는 것은 아님

 

예를들어 'Divide & Conquer'를 사용하는 합병 정렬을 예시로 들어보자.

- 여덟 개짜리 리스트를 합병 정렬을 하려면 우선 네 개짜리 리스트를 두 개로 나눈다.

- 그리고 이 둘을 각각 합병정렬 한다.

- 그런데 왼쪽 반을 해결하는 과정과 오른쪽 반을 해결하는 과정은 완전히 독립적임. 서로 겹치는 게 없음

- 그렇기 때문에 합병 정렬의 이 두 부분 문제는 '중복되지 않는 부분 문제' 즉, Non-overlapping Subproblem이다.

3. Dynamic Programming 

- 어떤 문제에 최적 부분 구조가 있다는 건 부분 문제들의 최적의 답을 이용해서 기존 문제를 풀 수 있다는 뜻.

- 즉, 기존 문제를 부분 문제로 나눠서 풀 수 있음. 그런데 부분 문제로 나눠서 풀다보면 중복되는 부분 문제들이 있을 수 있음. 그러면 똑같은 문제를 여러 번 풀어야 한다는 비효율이 발생함.

- 이런 비효율을 해결하는 알고리즘 패러다임이 'Dynamic Programming'

 

- 예를 들어 피보나치 문제에서 fib(7)을 풀기 위해서 중복되는 부분 문제가 많은데, 이 중복되는 부분 문제들을 각각 딱 한 번씩만 풀자는 게 다이나믹 프로그래밍의 취지

 

Dynamic Programming을 구현하는 방법은 두 가지로 나뉨. 

- Memoization과 Tabulation

4. Memoization

Memoization

- 예를들어 카페에서 아메리카노+치즈케이크를 너무 많이 시키는데, 이를 그때마다 계산하지않고, '아메리카노 + 치즈케이크 = 9500원'이라는 메모를 계산대에 붙여놓음. 다음 계산부터는 이 메모를 참고하면 되는데, 이런 방식을 'Memoization'이라고 부름

 

프로그래밍에서의 Memoization (예시 : 피보나치 문제)

우선 시작 전에 옆에 파이썬 사전을 만들어 놓자. 우리가 한 번 계산한 문제는 모두 여기에 저장해 높을 건데, 보통 이렇게 다시 쓸 값들을 저장해 놓는 공간을 '캐시(Cache)'라고 부른다.

- 예를들어, 여섯 번째 피보나치 수를 찾는다고 가정하자. 베이스케이스들인 fib(1), fib(2)는 우선 캐시에 적어두고, fib(3)부터는 한 번 계산 될 때마다 Cache에 적어두고, 다음부터는 이 값들을 활용한다. 

- 결과적으로 fib(6)을 계산할 때까지 각 부분 문제를 딱 한 번씩만 풀었음.

- Memoization을 이용한 다이나믹 프로그래밍으로 중복되는 부분 문제에 대한 비효율성을 해결한 것

5. (실습) 피보나치 수열 Memoization

6. Tabulation

 

Top-Down Approach(Memoization) vs Bottom-up Approach(Tabulation)

중복되는 부분문제를 해결하기 위해서 부분문제를 메모하면서 푸는 'Memoization'이라는 방법을 봤음

- Memoization에서는 fib(6)을 구하기 위해서 fib(5)와 fib(4)를 구해야 하고, 이런식으로 맨 위에서 시작해서 하나씩 내려가는 사고방식인데, 이건 '하향식 접근' 즉, 'Top-down Approach'라고 부름

 

Tabulation

- Memoization과는 반대로, fib(6)을 구하기 위해서 fib(1)을 먼저 구하고, 그 다음에 fib(2)를 구하고, .. fib(6)까지 구하는 방식으로 해결. 즉, 이런 방식은 '상향식 접근' 이라고 부름. 이렇게 하면 중복되는 계산이 없음

- 실제로 상향식 접근으로 문제를 푼다면 위처럼 표를 채우는 것처럼 해결하는데, 그래서 Table 방식으로 정리한다는 뜻의 Tabulation

 

Memoization과 Tabulation의 구현 방식 차이

- 접근 방식이 다르기 때문에 Memoization에서는 재귀를 기반으로 코드를 작성했지만, Tabulation은 반복문을 사용해서 리스트를 채워나가는 식으로 구현함