์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด (LIS,Longest Increasing Subsequence) ์ด๋? ์ด๋ค ์์์ ์์ด์ด ์ฃผ์ด์ง ๋, ์ด ์์ด์์ ๋ช ๊ฐ์ ์๋ค์ ์ ๊ฑฐํด์ ๋ถ๋ถ ์์ด์ ๋ง๋ค ์ ์๋ค. ์ด๋ ๋ง๋ค์ด์ง ๋ถ๋ถ ์์ด ์ค ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ๊ฐ์ฅ ๊ธด ์์ด์ "์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด"์ด๋ผ๊ณ ํ๋ค. - ๋๋ฌด์ํค ๐ณ โท ์์๋ฅผ ๋ค์ด๋ณด์. [ 3, 5, 7, 9, 2, 1, 4, 8] ๋ค์๊ณผ ๊ฐ์ ์์ด์ด ์๋ค๊ณ ํ์. ์ด ์์ด์์ ๋ช ๊ฐ์ ์๋ฅผ ์ ๊ฑฐํด์ ๋ถ๋ถ์์ด์ ๋ง๋ค ์ ์๋ค. ๋ช ๊ฐ์ ์๋ฅผ ์ ๊ฑฐํด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ด๋ฃจ์ด์ง ์์ด์ ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด์ด๋ผ๊ณ ํ์๋๋ฐ, ์ฆ, '๊ณต์ฐจ'๊ฐ ์กด์ฌํ์ง ์์๋ ๋ถ๋ถ์์ด์ด๋ผ๊ณ ๋ณธ๋ค๋ ๊ฒ์ด๋ค. (๊ท์น์ ์ด์ง ์๊ณ ์ค๋ฆ์ฐจ์์ด๋ฉด ๋๋ค๋ ๋ป) ๋ฐ๋ผ์ ์ ์์ด์์ ๋์ถ๋ ์ ์๋ ๋ถ๋ถ์..
