[SWEA_3307] ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด(LIS, Longest Increasing Subsequence)

[๋ฌธ์ œ] ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์—ด์˜ ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด(Longest Increasing Subsequence)์˜ ๊ธธ์ด๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ˆ˜์—ด { A1, A2, ... , AN }์˜ ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด B๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค. { B1, B2, ... , BK }์—์„œ 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK์ด๊ณ , AB1 ≤ AB2 ≤ ... ≤ ABK์ธ ์ตœ๋Œ€ K๋กœ ๊ตฌ์„ฑ๋œ ์ˆ˜์—ด์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด์ด { 1, 3, 2, 5, 4, 7 } ์ด๋ผ๋ฉด, ์ตœ์žฅ ๋ถ€๋ถ„ ์ฆ๊ฐ€ ์ˆ˜์—ด์˜ ๊ธธ์ด๋Š” 4๊ฐ€ ๋œ๋‹ค. [์ž…๋ ฅ] ์ฒซ ๋ฒˆ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ์ˆ˜์—ด์˜ ๊ธธ์ด N(1≤N≤1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด์˜ ์›์†Œ N๊ฐœ๊ฐ€ ๊ณต๋ฐฑ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋ณดํ˜ธ์†Œ์—์„œ ์ค‘์„ฑํ™”ํ•œ ๋™๋ฌผ

https://school.programmers.co.kr/learn/courses/30/lessons/59045 ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”. programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ANIMAL_INS ํ…Œ์ด๋ธ”์€ ๋™๋ฌผ ๋ณดํ˜ธ์†Œ์— ๋“ค์–ด์˜จ ๋™๋ฌผ์˜ ์ •๋ณด๋ฅผ ๋‹ด์€ ํ…Œ์ด๋ธ”์ž…๋‹ˆ๋‹ค. ANIMAL_INS ํ…Œ์ด๋ธ” ๊ตฌ์กฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์œผ๋ฉฐ, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE๋Š” ๊ฐ๊ฐ ๋™๋ฌผ์˜ ์•„์ด๋””, ์ƒ๋ฌผ ์ข…, ๋ณดํ˜ธ ์‹œ์ž‘์ผ, ๋ณดํ˜ธ ์‹œ์ž‘ ์‹œ ์ƒํƒœ, ์ด๋ฆ„, ์„ฑ๋ณ„ ๋ฐ ์ค‘์„ฑํ™” ์—ฌ๋ถ€๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. NAMET..

๋ฐ˜์‘ํ˜•
ยซ   2024/11   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30