๋ฐฑ์ค 11053 ํ์ด์ฌ - ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด - ๋์ ๊ณํ๋ฒ, LIS
๋ฐฑ์ค 11053 ํ์ด์ฌ https://www.acmicpc.net/problem/11053 11053๋ฒ: ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net ์ด๋ฒ ๋ฌธ์ ๋ ์์ด์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. LIS(Longest Increasing Subsequence)๋ผ๊ณ ํ๋ค. A๋ผ๋ ์์ด {10, 20, 10, 30, 20, 50}์ด ์๋ค๋ฉด {10, 20, 10, 30, 20, 50}์ด ๊ฐ์ฅ ๊ธด ๋ถ๋ถ ์์ด์ด๋ค. ์ด๋ฒ ๋ฌธ์ ..
2021. 10. 13.