DP๋?
GeeksforGeeks์ ์ํ๋ฉด DP๋ Sub-Problem๋ค๋ก ๋๋์ด ๊ฒฐ๊ณผ ๊ฐ์ ์ ์ฅํจ์ผ๋ก์จ ๊ณ์ฐ ์๋ฅผ ์ค์ด๋ ๊ฒ์ ๋งํ๋ค.
๊ทธ๋ฌ๋ ์๋ ๊ทธ์ ์ ์์ด๊ณ ์ค์ ๋ก ํ ๋๋ ๋ค์๊ณผ ๊ฐ์ ์ ๊ทผ ๋ฐฉ๋ฒ์ด ํธํ ๊ฒ์ด๋ค. DP๋ ๋ฌธ์ ๋ค์ ์์ Sub-Problem์ผ๋ก ์ชผ๊ฐ์ด Sub-Problem ๊ฐ์ ์๊ด ๊ด๊ณ์ ์ง์คํ์ฌ ๊ฒฐ๊ณผ์ ์ผ๋ก ์ ์ฒด Problem์ ํธ๋ ๋ฐฉ๋ฒ์ด๋ค.
์กฐ๊ธ ๋ ์น๊ทผํ๊ฒ ๋งํ๊ธฐ ์ํด ๊ณ๋จ์ ๋น์ ํด ๋ณด๊ฒ ๋ค. ์ฐ๋ฆฌ๊ฐย ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ธฐ ์ํด์๋ย ๋ฒ์งธ ๊ณ๋จ๋ค์ ๋ฐ์์ผ ํ๋ค. ์์๋๋ก ๊ณ๋จ์ ๋ฐ๋๋ค๋ฉด ๋์ ๋๋ฌํ ์ ์๋ค. ๋ฌธ์ ๊ฐ ์ฃผ์ด์ก์ ๋ ๊ณ๋จ์ผ๋ก ๋ฐ๊พธ์ด ์๊ฐํด ๋ณด๋๋ก ํ๋ค. ์ด๋ ํ ์ํ์์ ๋ค์ ์ํ๋ก ๋์๊ฐ๊ธฐ ์ํด ๋ฌด์จ ์ผ์ ํด์ผํ๋์ง ๊ณ ๋ฏผํ๊ณ ์ฒ์ ์ํ์ ๋ ์ํ๋ฅผ ๊ณ ๋ คํ๋ฉด ๋ฌธ์ ๋ ํ๋ฆฐ๋ค.
ํผ๋ณด๋์น ์์ด์ ์๋ก ๋ค์ด๋ณด์.
์ ๊ณ์ฐํ๊ธฐ ์ํด์ ์ฌ๊ท ํจ์๋ฅผ ์ด์ฉํ๋ค๋ฉด ์ ๊ณ์ฐํ ๋ ๊ฐ ํ์ํ ๋๋ง๋ค, ์ ๊ณ์ฐํด์ผ ํ๋ค. ์ด๋ ๊ฒ ํผ๋ค๋ฉด ๊ต์ฅํ ๋นํจ์จ์ ์ด์ง ์์๊ฐ? ์ด ๋ฐฉ๋ฒ ๋์ ์, ์ด์ ๋ ๊ฐ์ ์ ๋ ๋ค์ ๊ฐ์ ์ ์ ์๋ค๋ ์ ์ ๊ณ ๋ คํ์ฌ ์์๋ก ๊ณ์ฐํด ๋๊ฐ๋ค๋ฉด ์ฝ๊ฒ ํ ์ ์๋ค๋ ๊ฒ์ ์ ์ถํ ์ ์๋ค.
์ด์ฒ๋ผ ์์์ ๋ฒ์งธ Sub-Problem์ ๋ํ์ฌ, ๋ฒ์งธ Sub-Problem์ ๊ตฌํ ์ ์๋ค๋ฉด DP๋ก ํ ์ ์๋ค. ๋ํ ์ด ๋ ๋ฐ๋์ ์ฒ์ Sub-Problem๊ณผ ๋ง์ง๋ง Sub-Problem์ ๊ณ ๋ คํด์ผ ํ๋ค. ๊ฒฝ๊ณ ๊ฐ์์ ํ๋ก๊ทธ๋จ์ด ๋ฒ๊ทธ๋ฅผ ์ผ์ผํฌ ๊ฐ๋ฅ์ฑ์ด ๋๊ธฐ ๋๋ฌธ์ด๋ค. ๋์ค์ ๋ฌธ์ ์ ๋์ด๋๊ฐ ์กฐ๊ธ ๋ ์์นํ๋ค๋ฉด, ์์์ Sub-Problem์ ๋ํ์ฌ ๊ณผ ๋ฒ์งธ Sub-Problem์ ๊ตฌํ ์ ์์ ๋ 2์ฐจ์ DP๋ ํ ์ ์๋ค. DP์ ์๋ฆฌ๋ฅผ ์ ํ์
ํ๋ค๋ฉด ๋ณด๋ค ์ด๋ ค์ด 3, 4์ DP ๋ฌธ์ ๋ค๋ ํ ์ ์์ ๊ฒ์ด๋ค. (ใ
ใ
ใ
ใ
ใ
ใ
..)
๋๋ถ๋ถ ๋์น๋ฅผ ์ฑ๊ฒ ์ง๋ง, ์ ํ์์ผ๋ก ๋ํ๋ผ ์ ์๋ ๋ชจ๋ ์์ด์ DP๋ก ํ ์ ์๋ค. ํ์ง๋ง ์ด ๋ง์ด ๊ณง ์ ํ์์ผ๋ก ๋ํ๋ผ ์ ์๋ค๋ฉด ๋ฌด์กฐ๊ฑด DP๋ก ํ์ด์ผ ํ๋ค๋ ๊ฒ์ ์๋๋ค. ๋ฐ๋ก๋ก ํผ๋ณด๋์น ์์ด์ ๊ตฌํ๋ O(logn)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ DP๊ฐ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ค.
์ฃผ๋ก ๋์ค๋ ๋ฌธ์ ?
์ฝ๋ฉ ํ
์คํธ์ ์์ฃผ ๋์ค๋ DP ๋ฌธ์ ๋ค์ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์
ํ๋ ๋ฌธ์ , ์กฐํฉ์ ๊ตฌํ๋ ๋ฌธ์ , LIS (Longest Increasing Subsequence) ์ ๋๋ก ์์ฝํ ์ ์๋ค.
โข
๊ฒฝ์ฐ์ ์๋ฅผ ํ์
ํ๋ ๋ฌธ์
๋ณดํต ๊ธฐ์ด์ ์ธ ๋ฌธ์ ๋ค์ด ๋ง๊ณ Sub-Problem์ผ๋ก ๋๋๋ ๊ฒ๋ง ์๊ฐํ๋ฉด ์ฝ๊ฒ ํ ์ ์๋ค.
โข
์กฐํฉ์ ๊ตฌํ๋ ๋ฌธ์
์กฐํฉ์ ๊ณต์์ ๋ค์๊ณผ ๊ฐ๋ค.
์ด๋ฅผ ๊ณต์๋๋ก ํฉํ ๋ฆฌ์ผ์ ์ด์ฉํด์ ํ๋ฉด ๋งค์ฐ ๋น ๋ฅด๊ฒ Overflow๊ฐ ๋์์ ์๋ชป๋ ๊ฐ์ ์ป๊ฒ ๋๋ค. ์กฐํฉ์ ๋ํ ๊ณต์์ ์์ ๊ฒ ๋ง๊ณ ํ ๊ฐ์ง๊ฐ ๋ ์๋ค. ์ด ๊ณต์์ ํ์ฉํ๋ฉด, ์ค๊ฐ ๊ณ์ฐ ๊ณผ์ ์์ ๋ ํฐ ๊ฐ์ด ๋ฑ์ฅํ์ง ์๊ธฐ ๋๋ฌธ์ Overflow๋ฅผ ํผํ ์ ์๋ค.
ํ์ค์นผ์ ์ผ๊ฐํ์ ์ ๊ณต์์ ์๊ฐ์ ์ผ๋ก ๋ณผ ์ ์๋ ์ผ๊ฐํ์ด๋ค. ํ์ค์นผ์ ์ผ๊ฐํ์ ์๋์ ๊ฐ๋ค.
ํ์ค์นผ์ ์ผ๊ฐํ์ ์ ์๊ฐํด๋ณด๋ฉด, ๋ฒ์งธ ์ค์ ์๋ฉด ๋ฒ์งธ ์ค์ ์ ์ ์๊ณ ์ค๊ฐ ๊ณ์ฐ ๊ณผ์ ์์ ์ต์ข
๊ฒฐ๊ณผ๋ณด๋ค ํฐ ๊ฐ์ด ๋์ค์ง ์๋ ๊ฒ์ ์ ์ ์๋ค. ๋ฐ๋ผ์ ์ต์ข
๊ฒฐ๊ณผ ๊ฐ์ด Overflow๊ฐ ๋ฐ์ํ์ง ์๋ ๊ฐ์ด๋ผ๋ฉด, ์ด ๋ฐฉ๋ฒ์ ํตํด์ ๋ฌธ์ ์์ด ์ ๋ต์ ๊ตฌํ ์ ์๋ ๊ฒ์ ์ ์ ์๋ค. ๋๋ถ๋ถ์ ์กฐํฉ ๋ฌธ์ ๋ ์ฃผ์ด์ง ๋ฌธ์ ๊ฐ ์กฐํฉ์ ๊ตฌํด์ผํ๋ ๋ฌธ์ ์ธ์ง ํ์
๋ง ํ๋ฉด ์ฝ๊ฒ ํ ์ ์๋ค.
โข
LIS (Longest Increasing Subsequence)
LIS๋ Longest Increasing Subsequence์ ์ฝ์๋ก ์ฃผ์ด์ง ์์ด์ ์ต์ฅ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. LIS๋ฅผ ๊ตฌํ๋ ์ ๋ช
ํ ๋ฐฉ๋ฒ์ผ๋ก๋ ์ด๋ถ ํ์์ผ๋ก O(nlogn)๋ง์ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ๋ ์์ง๋ง, DP๋ฅผ ํตํด์๋ ํ ์ ์๋ค.
DP๋ฅผ ํตํด์ LIS๋ฅผ ํธ๋ ๋ฐฉ๋ฒ์ ์์ด์ ์์๋ฅผ ํ๋์ฉ ๋ณด๋ฉด์ ํด๋น ์์๋ก ๋๋๋ LIS์ ๊ธธ์ด๋ฅผ ์ถ์ ํ๋ฉด LIS๋ฅผ ๊ตฌํ ์ ์๋ค. ์์์ ์์๋ก ๋๋๋ LIS๋ฅผ ๊ตฌํ๊ธฐ ์ํด์ ์๊ธฐ๋ณด๋ค ์์๋ฉด์ ์๊ธฐ๋ณด๋ค ์์ ์์๋ก ๋๋๋ LIS ์ค ๊ฐ์ฅ ๊ธด LIS๋ฅผ ์ฐพ์์ผ ํ๋ค. ๊ทธ ๋ ์ฐพ์ LIS ๋ค์ ํด๋น ์์๋ฅผ ๋ํ๋ฉด ๊ทธ๊ฒ ํด๋น ์์๋ก ๋๋๋ LIS ์ด๊ธฐ ๋๋ฌธ์ด๋ค.
์๋ฅผ ๋ค์ด๋ณด์.
์ ์ผ ์์ ์๋ ์ ๊ฒฝ์ฐ ์์ ๋ณด๋ค ์์ ์์๊ฐ ์๊ธฐ ๋๋ฌธ์ ์ฒซ ๋ฒ์งธ ์์๋ก ๋๋๋ LIS๋ ์ด๋ค.
๊ทธ ๋ค์ ์์์ธ ์ ๋ณด๋ฉด ์์ ๋ณด๋ค ์์๋ฉด์ ์์ ๋ณด๋ค ์์ ์์๋ ๋ก 1๊ฐ๊ฐ ์๋ค. ๋ฐ๋ผ์ ์ผ๋ก ๋๋๋ LIS๋ ์ด ๋๋ค.
๊ทธ ๋ค์ ์์์ธ ๋ฅผ ๋ณด๋ฉด ์์ ๋ณด๋ค ์์๋ฉด์ ์์ ๋ณด๋ค ์์ ์์๋ ๋ก 1๊ฐ๊ฐ ์๋ค. ๋ฐ๋ผ์ ๋ก ๋๋๋ LIS๋ ๊ฐ ๋๋ค.
๊ทธ ๋ค์ ์์์ธ ๋ฅผ ๋ณด๋ฉด ์์ ๋ณด๋ค ์์๋ฉด์ ์์ ๋ณด๋ค ์์ ์์๋ ๊ณผ ๊ฐ ์๋ค. ์ด ๋, ๋ก ๋๋๋ LIS๋ ์ด๊ณ , ๋ก ๋๋๋ LIS๋ ์ด๋ค. ๋ฐ๋ผ์ ๋ณด๋ค ๊ธด ๋ฅผ ๋ถ์ฌ์ ๋ก ๋๋๋ LIS๋ ๊ฐ ๋๋ค.
์ด์ฒ๋ผ ๊ฐ ์์๋ง๋ค ํด๋น ์์๋ก ๋๋๋ LIS๋ฅผ ์ถ์ ํ ํ์ ๊ทธ ์ค์์ ๊ฐ์ฅ ๊ธด LIS๋ฅผ ์ฐพ์ผ๋ฉด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
๋ฉ๋ชจ์ด์ ์ด์ (Memoization)
๋ฉ๋ชจ์ด์ ์ด์
์ ์ค๋ณต ๊ณ์ฐ์ ํผํ๋ ๊ณ์ฐ ์ต์ ํ ๊ธฐ๋ฒ์ ๋งํ๋ค. DP ๋ฌธ์ ๋ฅผ ํ๋ค๋ณด๋ฉด ๊ฐ์ ๊ฐ์ ๊ณ์ ํธ์ถํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง๋ค. ์ง๊ธ์ ํผ๋ณด๋์น ์์ด์ ๊ณ์ํด์ ๊ณ์ฐํด์ผ ํ๋ค๊ณ ๊ฐ์ ํด๋ณด์. ์ฒ์์ ์ ๊ฐ์ด ํ์ํ๊ณ , ๊ทธ ์งํ์ ๊ฐ์ด ํ์ํ๋ค๋ฉด ์ด ๋ ๊ฐ์ ๊ณ์ฐํ๊ธฐ ์ํด์ ํผ๋ณด๋์น ์์ด ๊ณ์ฐ์ ๋ฐ๋ก ๋ฐ๋ก ํ ํ์๊ฐ ์๋ค๋ ๊ฒ์ด๋ค. ํผ๋ณด๋์น ์์ด์ DP ๋ฐฉ์์ผ๋ก ๊ณ์ฐํ๋ค๊ณ ๊ฐ์ ํ ๋, ์ ๊ณ์ฐํ๋ ๊ณผ์ ์์ ๋ถํฐ ๊น์ง ๊ณ์ฐํ๊ฒ ๋๋ค. ์ ๊ณ์ฐํ๋ ๋์ ๊ทธ ์ ๊ฐ๋ค์ ๋ฐฐ์ด์ ์ ์ฅํ๋ค๋ฉด, ์ ๋ค์ ๊ณ์ฐํ ํ์ ์์ด ๋ฐ๋ก ๊ฐ์ ๊ตฌํ ์ ์๋ค. ๋ฉ๋ชจ์ด์ ์ด์
์ ํน๋ณํ ์ด๋ ต์ง๋ ์๊ณ DP ์ธ์๋ ๋ง์ด ์ฌ์ฉ๋๋ ์ด ๊ฐ๋
์ ์ตํ๋๋ฉด ์ข๋ค.