Search
Duplicate
๐Ÿ“—

Dynamic Programming

DP๋ž€?

GeeksforGeeks์— ์˜ํ•˜๋ฉด DP๋Š” Sub-Problem๋“ค๋กœ ๋‚˜๋ˆ„์–ด ๊ฒฐ๊ณผ ๊ฐ’์„ ์ €์žฅํ•จ์œผ๋กœ์จ ๊ณ„์‚ฐ ์ˆ˜๋ฅผ ์ค„์ด๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค.
๊ทธ๋Ÿฌ๋‚˜ ์œ„๋Š” ๊ทธ์ € ์ •์˜์ด๊ณ  ์‹ค์ œ๋กœ ํ’€ ๋•Œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ ‘๊ทผ ๋ฐฉ๋ฒ•์ด ํŽธํ•  ๊ฒƒ์ด๋‹ค. DP๋Š” ๋ฌธ์ œ๋“ค์„ ์ž‘์€ Sub-Problem์œผ๋กœ ์ชผ๊ฐœ์–ด Sub-Problem ๊ฐ„์˜ ์ƒ๊ด€ ๊ด€๊ณ„์— ์ง‘์ค‘ํ•˜์—ฌ ๊ฒฐ๊ณผ์ ์œผ๋กœ ์ „์ฒด Problem์„ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
์กฐ๊ธˆ ๋” ์นœ๊ทผํ•˜๊ฒŒ ๋งํ•˜๊ธฐ ์œ„ํ•ด ๊ณ„๋‹จ์— ๋น„์œ ํ•ด ๋ณด๊ฒ ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ย nn๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ๊ธฐ ์œ„ํ•ด์„œ๋Š”ย nโˆ’1,nโˆ’2,nโˆ’3,...,1n-1, n-2, n-3, ..., 1๋ฒˆ์งธ ๊ณ„๋‹จ๋“ค์„ ๋ฐŸ์•„์•ผ ํ•œ๋‹ค. ์ˆœ์„œ๋Œ€๋กœ ๊ณ„๋‹จ์„ ๋ฐŸ๋Š”๋‹ค๋ฉด ๋์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฌธ์ œ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ๊ณ„๋‹จ์œผ๋กœ ๋ฐ”๊พธ์–ด ์ƒ๊ฐํ•ด ๋ณด๋„๋ก ํ•œ๋‹ค. ์–ด๋– ํ•œ ์ƒํƒœ์—์„œ ๋‹ค์Œ ์ƒํƒœ๋กœ ๋‚˜์•„๊ฐ€๊ธฐ ์œ„ํ•ด ๋ฌด์Šจ ์ผ์„ ํ•ด์•ผํ•˜๋Š”์ง€ ๊ณ ๋ฏผํ•˜๊ณ  ์ฒ˜์Œ ์ƒํƒœ์™€ ๋ ์ƒํƒœ๋ฅผ ๊ณ ๋ คํ•˜๋ฉด ๋ฌธ์ œ๋Š” ํ’€๋ฆฐ๋‹ค.
ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ์˜ˆ๋กœ ๋“ค์–ด๋ณด์ž.
fn=fnโˆ’1+fnโˆ’1f_n = f_{n-1} + f_{n-1}
f10f_{10}์„ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•œ๋‹ค๋ฉด f10f_{10}์„ ๊ณ„์‚ฐํ•  ๋•Œ f5f_5๊ฐ€ ํ•„์š”ํ•  ๋•Œ๋งˆ๋‹ค, f4,f3,f2,f1,f0f_4, f_3, f_2, f_1, f_0์„ ๊ณ„์‚ฐํ•ด์•ผ ํ•œ๋‹ค. ์ด๋ ‡๊ฒŒ ํ‘ผ๋‹ค๋ฉด ๊ต‰์žฅํžˆ ๋น„ํšจ์œจ์ ์ด์ง€ ์•Š์€๊ฐ€? ์ด ๋ฐฉ๋ฒ• ๋Œ€์‹ ์—, ์ด์ „ ๋‘ ๊ฐ’์„ ์•Œ ๋•Œ ๋‹ค์Œ ๊ฐ’์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์„ ๊ณ ๋ คํ•˜์—ฌ f2,f3,f4...f_2, f_3, f_4 ... ์ˆœ์„œ๋กœ ๊ณ„์‚ฐํ•ด ๋‚˜๊ฐ„๋‹ค๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์œ ์ถ”ํ•  ์ˆ˜ ์žˆ๋‹ค.
์ด์ฒ˜๋Ÿผ ์ž„์˜์˜ nn๋ฒˆ์งธ Sub-Problem์— ๋Œ€ํ•˜์—ฌ, n+1n+1 ๋ฒˆ์งธ Sub-Problem์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด DP๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ๋˜ํ•œ ์ด ๋•Œ ๋ฐ˜๋“œ์‹œ ์ฒ˜์Œ Sub-Problem๊ณผ ๋งˆ์ง€๋ง‰ Sub-Problem์„ ๊ณ ๋ คํ•ด์•ผ ํ•œ๋‹ค. ๊ฒฝ๊ณ„ ๊ฐ’์—์„œ ํ”„๋กœ๊ทธ๋žจ์ด ๋ฒ„๊ทธ๋ฅผ ์ผ์œผํ‚ฌ ๊ฐ€๋Šฅ์„ฑ์ด ๋†’๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๋‚˜์ค‘์— ๋ฌธ์ œ์˜ ๋‚œ์ด๋„๊ฐ€ ์กฐ๊ธˆ ๋” ์ƒ์Šนํ•œ๋‹ค๋ฉด, ์ž„์˜์˜ (n,m)(n,m) Sub-Problem์— ๋Œ€ํ•˜์—ฌ (n+1,m)(n+1, m)๊ณผ (n,m+1)(n, m+1) ๋ฒˆ์งธ Sub-Problem์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์„ ๋•Œ 2์ฐจ์› DP๋„ ํ’€ ์ˆ˜ ์žˆ๋‹ค. DP์˜ ์›๋ฆฌ๋ฅผ ์ž˜ ํŒŒ์•…ํ•œ๋‹ค๋ฉด ๋ณด๋‹ค ์–ด๋ ค์šด 3, 4์› DP ๋ฌธ์ œ๋“ค๋„ ํ’€ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. (ใ…‹ใ…‹ใ…‹ใ…‹ใ…‹ใ…‹..)
๋Œ€๋ถ€๋ถ„ ๋ˆˆ์น˜๋ฅผ ์ฑ˜๊ฒ ์ง€๋งŒ, ์ ํ™”์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์ˆ˜์—ด์€ DP๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด ๋ง์ด ๊ณง ์ ํ™”์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค๋ฉด ๋ฌด์กฐ๊ฑด DP๋กœ ํ’€์–ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค. ๋ฐ˜๋ก€๋กœ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” O(logn)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๋Š” DP๊ฐ€ ์•„๋‹Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์žˆ๋‹ค.

์ฃผ๋กœ ๋‚˜์˜ค๋Š” ๋ฌธ์ œ?

์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์— ์ž์ฃผ ๋‚˜์˜ค๋Š” DP ๋ฌธ์ œ๋“ค์€ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํŒŒ์•…ํ•˜๋Š” ๋ฌธ์ œ, ์กฐํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ, LIS (Longest Increasing Subsequence) ์ •๋„๋กœ ์š”์•ฝํ•  ์ˆ˜ ์žˆ๋‹ค.
โ€ข
๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํŒŒ์•…ํ•˜๋Š” ๋ฌธ์ œ
๋ณดํ†ต ๊ธฐ์ดˆ์ ์ธ ๋ฌธ์ œ๋“ค์ด ๋งŽ๊ณ  Sub-Problem์œผ๋กœ ๋‚˜๋ˆ„๋Š” ๊ฒƒ๋งŒ ์ƒ๊ฐํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋‹ค.
โ€ข
์กฐํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ
์กฐํ•ฉ์˜ ๊ณต์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
nCr=n!r!(nโˆ’r)!nCr = \frac{n!}{r!(n-r)!}
์ด๋ฅผ ๊ณต์‹๋Œ€๋กœ ํŒฉํ† ๋ฆฌ์–ผ์„ ์ด์šฉํ•ด์„œ ํ’€๋ฉด ๋งค์šฐ ๋น ๋ฅด๊ฒŒ Overflow๊ฐ€ ๋‚˜์™€์„œ ์ž˜๋ชป๋œ ๊ฐ’์„ ์–ป๊ฒŒ ๋œ๋‹ค. ์กฐํ•ฉ์— ๋Œ€ํ•œ ๊ณต์‹์€ ์œ„์˜ ๊ฒƒ ๋ง๊ณ  ํ•œ ๊ฐ€์ง€๊ฐ€ ๋” ์žˆ๋‹ค. ์ด ๊ณต์‹์„ ํ™œ์šฉํ•˜๋ฉด, ์ค‘๊ฐ„ ๊ณ„์‚ฐ ๊ณผ์ •์—์„œ ๋” ํฐ ๊ฐ’์ด ๋“ฑ์žฅํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— Overflow๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋‹ค.
nCr=nโˆ’1Crโˆ’1+nโˆ’1Cr_nC_r = _{n-1}C_{r-1} + _{n-1}C_r
ํŒŒ์Šค์นผ์˜ ์‚ผ๊ฐํ˜•์€ ์œ„ ๊ณต์‹์„ ์‹œ๊ฐ์ ์œผ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋Š” ์‚ผ๊ฐํ˜•์ด๋‹ค. ํŒŒ์Šค์นผ์˜ ์‚ผ๊ฐํ˜•์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.
ํŒŒ์Šค์นผ์˜ ์‚ผ๊ฐํ˜•์„ ์ž˜ ์ƒ๊ฐํ•ด๋ณด๋ฉด, nn๋ฒˆ์งธ ์ค„์„ ์•Œ๋ฉด n+1n+1๋ฒˆ์งธ ์ค„์„ ์•Œ ์ˆ˜ ์žˆ๊ณ  ์ค‘๊ฐ„ ๊ณ„์‚ฐ ๊ณผ์ •์—์„œ ์ตœ์ข… ๊ฒฐ๊ณผ๋ณด๋‹ค ํฐ ๊ฐ’์ด ๋‚˜์˜ค์ง€ ์•Š๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ตœ์ข… ๊ฒฐ๊ณผ ๊ฐ’์ด Overflow๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š” ๊ฐ’์ด๋ผ๋ฉด, ์ด ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด์„œ ๋ฌธ์ œ ์—†์ด ์ •๋‹ต์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ๋Œ€๋ถ€๋ถ„์˜ ์กฐํ•ฉ ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ๋ฌธ์ œ๊ฐ€ ์กฐํ•ฉ์„ ๊ตฌํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ์ธ์ง€ ํŒŒ์•…๋งŒ ํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋‹ค.
โ€ข
LIS (Longest Increasing Subsequence)
LIS๋Š” Longest Increasing Subsequence์˜ ์•ฝ์ž๋กœ ์ฃผ์–ด์ง„ ์ˆ˜์—ด์˜ ์ตœ์žฅ ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. LIS๋ฅผ ๊ตฌํ•˜๋Š” ์œ ๋ช…ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ๋Š” ์ด๋ถ„ ํƒ์ƒ‰์œผ๋กœ O(nlogn)๋งŒ์— ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ์žˆ์ง€๋งŒ, DP๋ฅผ ํ†ตํ•ด์„œ๋„ ํ’€ ์ˆ˜ ์žˆ๋‹ค.
DP๋ฅผ ํ†ตํ•ด์„œ LIS๋ฅผ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์€ ์ˆ˜์—ด์˜ ์›์†Œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋ณด๋ฉด์„œ ํ•ด๋‹น ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS์˜ ๊ธธ์ด๋ฅผ ์ถ”์ ํ•˜๋ฉด LIS๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. ์ž„์˜์˜ ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด์„  ์ž๊ธฐ๋ณด๋‹ค ์•ž์„œ๋ฉด์„œ ์ž๊ธฐ๋ณด๋‹ค ์ž‘์€ ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS ์ค‘ ๊ฐ€์žฅ ๊ธด LIS๋ฅผ ์ฐพ์•„์•ผ ํ•œ๋‹ค. ๊ทธ ๋•Œ ์ฐพ์€ LIS ๋’ค์— ํ•ด๋‹น ์›์†Œ๋ฅผ ๋”ํ•˜๋ฉด ๊ทธ๊ฒŒ ํ•ด๋‹น ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS ์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด๋ณด์ž.
1,6,2,5,7,3,5,71, 6,2,5,7,3,5,7
์ œ์ผ ์•ž์— ์žˆ๋Š” 11์˜ ๊ฒฝ์šฐ ์ž์‹ ๋ณด๋‹ค ์•ž์„  ์›์†Œ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ฒซ ๋ฒˆ์งธ ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS๋Š” 11์ด๋‹ค.
๊ทธ ๋‹ค์Œ ์›์†Œ์ธ 66์„ ๋ณด๋ฉด ์ž์‹ ๋ณด๋‹ค ์•ž์„œ๋ฉด์„œ ์ž์‹ ๋ณด๋‹ค ์ž‘์€ ์›์†Œ๋Š” 11๋กœ 1๊ฐœ๊ฐ€ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ 66์œผ๋กœ ๋๋‚˜๋Š” LIS๋Š” 1,61,6์ด ๋œ๋‹ค.
๊ทธ ๋‹ค์Œ ์›์†Œ์ธ 22๋ฅผ ๋ณด๋ฉด ์ž์‹ ๋ณด๋‹ค ์•ž์„œ๋ฉด์„œ ์ž์‹ ๋ณด๋‹ค ์ž‘์€ ์›์†Œ๋Š” 11๋กœ 1๊ฐœ๊ฐ€ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ 22๋กœ ๋๋‚˜๋Š” LIS๋Š” 1,21, 2๊ฐ€ ๋œ๋‹ค.
๊ทธ ๋‹ค์Œ ์›์†Œ์ธ 55๋ฅผ ๋ณด๋ฉด ์ž์‹ ๋ณด๋‹ค ์•ž์„œ๋ฉด์„œ ์ž์‹ ๋ณด๋‹ค ์ž‘์€ ์›์†Œ๋Š” 11๊ณผ 22๊ฐ€ ์žˆ๋‹ค. ์ด ๋•Œ, 11๋กœ ๋๋‚˜๋Š” LIS๋Š” 11์ด๊ณ , 22๋กœ ๋๋‚˜๋Š” LIS๋Š” 1,21,2์ด๋‹ค. ๋”ฐ๋ผ์„œ ๋ณด๋‹ค ๊ธด 1,21, 2๋ฅผ ๋ถ™์—ฌ์„œ 55๋กœ ๋๋‚˜๋Š” LIS๋Š” 1,2,51,2,5๊ฐ€ ๋œ๋‹ค.
์ด์ฒ˜๋Ÿผ ๊ฐ ์›์†Œ๋งˆ๋‹ค ํ•ด๋‹น ์›์†Œ๋กœ ๋๋‚˜๋Š” LIS๋ฅผ ์ถ”์ ํ•œ ํ›„์— ๊ทธ ์ค‘์—์„œ ๊ฐ€์žฅ ๊ธด LIS๋ฅผ ์ฐพ์œผ๋ฉด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ฉ”๋ชจ์ด์ œ์ด์…˜ (Memoization)

๋ฉ”๋ชจ์ด์ œ์ด์…˜์€ ์ค‘๋ณต ๊ณ„์‚ฐ์„ ํ”ผํ•˜๋Š” ๊ณ„์‚ฐ ์ตœ์ ํ™” ๊ธฐ๋ฒ•์„ ๋งํ•œ๋‹ค. DP ๋ฌธ์ œ๋ฅผ ํ’€๋‹ค๋ณด๋ฉด ๊ฐ™์€ ๊ฐ’์„ ๊ณ„์† ํ˜ธ์ถœํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๋‹ค. ์ง€๊ธˆ์€ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ณ„์†ํ•ด์„œ ๊ณ„์‚ฐํ•ด์•ผ ํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž. ์ฒ˜์Œ์— f100f_{100}์˜ ๊ฐ’์ด ํ•„์š”ํ•˜๊ณ , ๊ทธ ์งํ›„์— f50f_{50} ๊ฐ’์ด ํ•„์š”ํ•˜๋‹ค๋ฉด ์ด ๋‘ ๊ฐ’์„ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ๊ณ„์‚ฐ์„ ๋”ฐ๋กœ ๋”ฐ๋กœ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ DP ๋ฐฉ์‹์œผ๋กœ ๊ณ„์‚ฐํ–ˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•  ๋•Œ, f100f_{100}์„ ๊ณ„์‚ฐํ•˜๋Š” ๊ณผ์ •์—์„œ f0f_0๋ถ€ํ„ฐ f99f_{99}๊นŒ์ง€ ๊ณ„์‚ฐํ•˜๊ฒŒ ๋œ๋‹ค. f100f_{100}์„ ๊ณ„์‚ฐํ•˜๋Š” ๋™์•ˆ ๊ทธ ์ „ ๊ฐ’๋“ค์„ ๋ฐฐ์—ด์— ์ €์žฅํ•œ๋‹ค๋ฉด, f50f_{50}์„ ๋‹ค์‹œ ๊ณ„์‚ฐํ•  ํ•„์š” ์—†์ด ๋ฐ”๋กœ ๊ฐ’์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฉ”๋ชจ์ด์ œ์ด์…˜์€ ํŠน๋ณ„ํžˆ ์–ด๋ ต์ง€๋„ ์•Š๊ณ  DP ์™ธ์—๋„ ๋งŽ์ด ์‚ฌ์šฉ๋˜๋‹ˆ ์ด ๊ฐœ๋…์„ ์ตํ˜€๋‘๋ฉด ์ข‹๋‹ค.