ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํ’์„  ํ„ฐํŠธ๋ฆฌ๊ธฐ c++ 1

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํ’์„  ํ„ฐํŠธ๋ฆฌ๊ธฐ C++ (Lv.3)

https://school.programmers.co.kr/learn/courses/30/lessons/68646?language=cpp ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”. programmers.co.kr ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ(DP) ๋˜๋Š” ์Šคํƒ(stack) ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. 1. ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ DP ๐Ÿ“ ๋ฌธ์ œ ํ’€์ด 1. ๊ฐ ํ’์„ ์˜ ์™ผ์ชฝ ์ตœ์†Ÿ๊ฐ’(leftMin)๊ณผ ์˜ค๋ฅธ์ชฝ ์ตœ์†Ÿ๊ฐ’(rightMin)์„ ์ €์žฅํ•  ๋ฐฐ์—ด ์„ ์–ธ leftMin[0]์€ a ๋ฒกํ„ฐ์˜ ์ฒซ๋ฒˆ์งธ ๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™” rightMin[n-1]์€ a ๋ฒกํ„ฐ์˜ ๋งˆ์ง€๋ง‰ ๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™” 2. for ๋ฌธ์„ ๋Œ๋ฉฐ ๊ฐ ํ’์„ ์˜ ์™ผ์ชฝ ์ตœ์†Ÿ..

๋ฐ˜์‘ํ˜•