[알고리즘] 동적계획법(2021.02.03수정) + 그리디 알고리즘 정리 1차 + (분할 vs 동적 )

 

동적계획법

 

- 동적 계획법은 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다 ( 동적계획법의 사용 조건 : 최적 부분 구조 && 중복된 하위 문제들 )

 

- 쪼개지는 부분 문제가 중복될 때 메모이제이션을 사용하여 속도를 향상시키는 방법이다.

즉 하나의 문제가 부분 문제로 쪼개져서 푸는 문제에서, 같은 부분 문제들이 있다면 이들을 한 번만 실행하게끔만 구현해주는 것. (중복되는 문제에 대한 답을 여러 번 구할 필요가 없도록, 한 번 실행할 때 결과값을 캐시해놨다가 다음에 실행될 때는 캐시해놓은 값을 꺼내 쓰는것)

 

- 부분 문제로 쪼개서 원래의 답을 구한다는 점, 최적 부분 구조에서 사용된다는 점에서 분할정복과 비슷하나, 부분문제의 중복여부와 그로인한 메모이제이션 사용여부에 대한 차이가 있다.(즉, 동적계획법과 분할정복법의 차이점은 계산결과의 재활용 여부 )

 

- 대표적으로 피보나치 수열을 동적계획법으로 구현할 수 있다.

 

+ 동적계획법과 부분정복법 정리

공통점 : 모두 부분 문제로 쪼개서 원래의 답을 구하는 방식이며, 최적 부분 구조 기반에서 사용되나

차이점 : 부분 문제가 중복적이냐와 그로인해 메모이제이션을 사용하냐가 차이점이다.

 

+ 분할 정복 알고리즘은 문제를 나눌 수 없을 때 까지 나눠서 각각 문제를 풀면서 다시 합병하여 문제를 해결해가는 알고리즘

분할 정복의 대표적인 예시 : Quick Sort, Merge Sort
(2021.11.16)

 

 

+ 동적계획법에는 엄밀히 두 가지가 있다. (2021.01.01 수정)

 

[ Top - down ]

Top - down은 최종 함수에서 시작해서 재귀를 통해 끝까지 내려갔다가 다시 올라오는 resolve 방식이다.

재귀함수를 통한 구현. 반복되는 부분문제에 대한 재귀함수를 호출하는 수고를 덜기 위해서 메모이제이션을 사용한다.

[ Bottom - up ]

반복문을 통한 구현. 앞에서부터 차례차례 구해나가면서 최종값에 다다르는 방식. 그 자체로 메모이제이션이 내장된다고 생각하면 된다.

 

 

'재귀를 이용한 동적계획법'인 Top - bottom 방식에서 주로 '메모이제이션'이라는 표현을 쓰고, '반복문을 이용한 동적계획법'인 Bottom - up 에서는 메모이제이션이라는 표현을 쓰지 않는 것 같다.

 

하지만 Top - down에는 중복되는 부분문제들이 존재해서 메모이제이션을 사용하고, Bottom - up 에서는 중복되는 부분문제들이 존재하지 않아서 메모이제이션을 사용하지 않는다고 표현하는 게 아니다.

Top - down 방식으로 구현하나, Bottom - up 방식으로 구현하나 결국 과정에서 동일하게 반복되는 부분문제들이 존재한다.

(그러니 동적계획법 문제이기도 한 것)

 

차이점은 Top - down 방식에서 일반적인 재귀방식으로 이런 동일한 부분문제를 반복적으로 호출해야 하는 대신에 메모이제이션을 도입하여 중복부분문제(함수)를 캐싱하는 것이고, Bottom - up 방식은 아예 처음부터 메모이제이션이 내장되어 있다고 생각하면 된다.

 

Top - bottom ( 재귀 함수 흐름 )

fibo(4) = fibo(3) + fibo(2)

fibo(3) = fibo(2) + fibo(1)

fibo(2) = fibo(1) + fibo(0)

 

fibo(2) = fibo(1) + fibo(0) -> 메모이제이션 도입 시엔 이렇게 호출하지 않아도 됨

 

 

Bottom - up

fibo[2] = fibo[1] + fibo[0]

fibo[3] = fibo[2] + fibo[1]

fibo[4] = fibo[3] + fibo[2]

 

 

핵심은

메모이제이션 기반의 Top - Bottom = Bottom - up 이란 느낌이라는 것.

즉, Top - bottom 이나 Bottom - up이나 똑같은 문제에서는 중복되는 부분문제가 동일하게 존재하는건 변하지 않는 사실인데,

Top - Bottom 방식에서 메모이제이션을 구현함으로써 이런 중복되는 부분문제 '함수' 계산을 시행하지 않는 것이고

Bottom - Up은 아래에서 위로 올라가면서, 이미 그 자체만으로도 반복되는 부분문제들에 대한 메모이제이션을 진행하며 풀어나가게 된다. (이런 말을 응축하여 메모이제이션이라는 표현 대신 '타뷸레이션' 이라는 표현을 쓰는 것 같다)

 

Top - down은 resovle 방식인 탓에 큰 문제에서 내려갔다가 다시 올라오는 과정이므로 메모이제이션은 해당 결과 값이 필요해질 때 계산을 해서 저장을 하지만, Bottom - up은 아래에서 시작되므로 타뷸레이션은 필요하지 않은 값도 미리 계산해서 메모리에 저장해두는 차이점이 있다;

 

어쨌든 Top - down / Bottom - up을 이렇게 구분지어서 생각할 필요없이 동적계획법 적용 문제에선 중복되는 부분 문제 자체들이 존재하고, 이미 계산했던 결과를 이미 저장해놨어서 다시 계산하지 않는다는 개념에서 메모이제이션/타뷸레이션이라고 부른다.

 

Top - down이나 Bottom - up 이나 '반복되는 부분문제의 중복 실행 방지'라는 흐름에서, 메모이제이션/타뷸레이션 굳이 구분지을 필요 없이 개념적으로 메모이제이션이라고 이해해도 무방할 것 같다. (둘은 Bottom - up 식이냐 Top - down 식이냐의 차이지, 중복되는 문제를 저장한다는 개념의 의도는 동일하고, 그건 메모이제이션이다. 타뷸레이션은 거기서 bottom - up의 흐름이 응축된 단어)

 

이 내용 관련 참고

umbum.dev/770

Dynamic programming, 동적 계획법

infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

arincblossom.wordpress.com/2019/08/17/dynamic-programming-동적계획법/comment-page-1/

Dynamic Programming (동적계획법)

kamang-it.tistory.com/entry/AlgorithmDynamic-Programming동적계획법다이나믹-프로그래밍과-메모이제이션memoization-타뷸레이션tabulation

[Algorithm][Dynamic Programming]동적계획법(다이나믹 프로그래밍)과 메모이제이션(memoization), 타뷸레이

namu.wiki/w/메모이제이션

메모이제이션 - 나무위키

 

 

 

 

 

전체 글 내용 관련 참고

galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

velog.io/@polynomeer/동적-계획법Dynamic-Programming

동적 계획법(Dynamic Programming)

chickenpaella.tistory.com/37

다이나믹 프로그래밍

nsgg.tistory.com/33

(최적 부분 구조 설명)

[동적 계획법] Dynamic programming

doorbw.tistory.com/53

(최적 부분 구조 설명)

알고리즘 #7_ 동적 프로그래밍: 동적 프로그래밍의 요소

museop.github.io/computer%20algorithm/2017/08/13/Dynamic-Programming.html

(최적 부분 구조 설명)

동적 계획법(Dynamic Programming) · Pleasure of Learning

hroad.tistory.com/46

(최적 부분 구조 설명)

[알고리즘] 동적 계획법 (Dynamic Programming)

codingsmu.tistory.com/15

[SW Expert Academy] 동적 계획법(Dynamic Programming)

 

 

동적계획 vs 분할정복 비교 참고

euju-wouldyou.tistory.com/m/104?category=766590

다이나믹 프로그래밍(dynamic Programming)

freedeveloper.tistory.com/m/276

[이것이 코딩 테스트다] 6. 다이나믹 프로그래밍

 

그리디 알고리즘

(최적 부분 구조를 가져야 그리디 알고리즘도 효과가 있다는 것)

velog.io/@cyranocoding/동적-계획법Dynamic-Programming과-탐욕법Greedy-Algorithm-3yjyoohia5

동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm)

namu.wiki/w/그리디%20알고리즘

(그리디 알고리즘 & 최적 부분 구조 설명)

그리디 알고리즘 - 나무위키

 

동적 계획법과 그리디 알고리즘의 차이

- 동적 계획법은 모든 경우를 따져본다(일반 재귀와 다른 점은 메모이제이션을 사용하여 시간을 줄이는 것)

- 그리디 알고리즘은 일단 지금 최적을 계속 쫓는다.

skmouse.tistory.com/entry/탐욕Greedy알고리즘동적Dynamic계획법

탐욕(Greedy)그리디알고리즘/동적(Dynamic)계획법 비교

medium.com/@lunay0ung/동적-프로그래밍-dynamic-programming-5f5131380c22

동적 프로그래밍 / Dynamic Programming

rain-bow.tistory.com/entry/DP와-Greedy-Algorithm

 

 

+ <동적계획법 vs 그리디알고리즘>에 대한 정리는 이 게시글에 이어 다른 게시글에 더 자세히 담아놨다.

(탐욕스러운 선택 조건과 최적 부분 구조 조건에 대해, 그리고 이 두 조건에서의 독립적이라는 표현의 정의의 시시비비는 피하는 것이 좋겠다. 관점에 따라서도 다를 수 있고, 그리고 추상적일 수 있는 것 같다.)

hevton.tistory.com/364