๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Lis3

๋ฐฑ์ค€ 2565 ํŒŒ์ด์ฌ - ์ „๊นƒ์ค„ - ๋™์  ๊ณ„ํš๋ฒ•, LIS ๋ฐฑ์ค€ 2565 ํŒŒ์ด์ฌ https://www.acmicpc.net/problem/2565 2565๋ฒˆ: ์ „๊นƒ์ค„ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ „๊นƒ์ค„์ด A์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ์™€ B์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” www.acmicpc.net ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜์ง€ ์•Š๊ฒŒ ์—†์• ์•ผํ•˜๋Š” ์ „๊นƒ์ค„์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ฒ˜์Œ์— ๋ฌธ์ œ๋ฅผ ์–ด๋–ป๊ฒŒ ์ ‘๊ทผํ•ด์•ผํ• ์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋Š”๋ฐ... ์—ญ์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ข…์ด์— ์ ์–ด๊ฐ€๋ฉด์„œ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฐพ๋‹ค๋ณด๋‹ˆ ๊ทœ์น™์„ ์ฐพ์•˜์Šต๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋„ ์ด์ „์— ํ’€์—ˆ๋˜ LIS ๋ฌธ์ œ : [CS/์•Œ๊ณ ๋ฆฌ์ฆ˜] - ๋ฐฑ์ค€ 11053 ํŒŒ์ด์ฌ - ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด - ๋™์  ๊ณ„ํš๋ฒ•, LIS ์˜ ์—ฐ์žฅ์„  ์‘์šฉ.. 2021. 10. 15.
๋ฐฑ์ค€ 11054 ํŒŒ์ด์ฌ - ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด - ๋™์  ๊ณ„ํš๋ฒ•, LIS ๋ฐฑ์ค€ 11054 ํŒŒ์ด์ฌ https://www.acmicpc.net/problem/11054 11054๋ฒˆ: ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000, 1 โ‰ค Ai โ‰ค 1,000) www.acmicpc.net ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ์ด์ „์— ํ’€์—ˆ๋˜ [CS/์•Œ๊ณ ๋ฆฌ์ฆ˜] - ๋ฐฑ์ค€ 11053 ํŒŒ์ด์ฌ - ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด - ๋™์  ๊ณ„ํš๋ฒ•, LIS ๋ฌธ์ œ์˜ ์‘์šฉ์ด๋‹ค. ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๊ณ  ๊ฐ์†Œํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์ด๋‹ค. ์ฆ‰ ์ด์ „์— ํ’€์—ˆ๋˜ LIS ๋ฌธ์ œ์—์„œ ๋ฐฐ์—ด์˜ ๊ฐ ์œ„์น˜์—์„œ์˜ ์ตœ๋Œ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์ฃผ์–ด์ง„ ๋ฐฐ์—ด๊ณผ ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ ๋’ค์ง‘์€ ๋ฐฐ์—ด 2๊ฐ€์ง€๋ฅผ ๊ตฌํ•ด์„œ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. Python ํ’€์ด impor.. 2021. 10. 15.
๋ฐฑ์ค€ 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.