[baekjoon] 12605๋ฒˆ : ๋‹จ์–ด์ˆœ์„œ ๋’ค์ง‘๊ธฐ (C++)

๋งŒ๋งŒํ•œ์ค„ ์•Œ์•˜๋Š”๋””.. ๊ทธ๋ƒฅ ๋ณด๊ณ  ์ฝ”์›ƒ์Œ ์ณค๋Š”๋””ใ…ฃ.... ์˜ค๋ž˜๊ฑธ๋ฆฐ๋“ฏ.. ์™œ๋ƒ๋ฉด reverse ํ•จ์ˆ˜์— ๋Œ€ํ•œ ์ดํ•ด ๋ถ€์กฑ + getline ์ž˜๋ชจ๋ฆ„ ๋“ฑ์œผ๋กœ ์ธํ•ด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ƒ๊ฐ์€ ํ–ˆ์œผ๋‚˜ ๊ตฌํ˜„์„ ๋ชปํ•˜๋Š”.. ์•„๋‹ˆ ํ•ด๋„ ๋Œ์•„๊ฐ€์ง€ ์•Š๋Š” ์ƒํ™ฉ์— ๋งˆ์ฃผํ–ˆ๋˜ ๊ฒƒ..! ์ผ๋‹จ ๋‚ด๊ฐ€ ์ƒ๊ฐํ•œ ๊ฒƒ์€? ๋ฌธ์žฅ ์ „์ฒด๊ฐ€ ๋’ค์ง‘ํ˜”์ง€๋งŒ.. ๋‹จ์–ด๋Š” ์•ˆ๋’ค์ง‘ํžŒ.. ๊ณ ๋Ÿฐ ๋А๋‚Œ์ด๋‹ˆ๊นŒ ์ผ๋‹จ reverse ํ•จ์ˆ˜๋กœ ์ „์ฒด๋ฅผ ๋’ค์ง‘๊ณ  ํ† ํฐ ๋‹จ์œ„๋กœ ๋’ค์ง‘์œผ๋ฉด ๋˜๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐ ํ† ํฐ ํ•˜๋‹ˆ๊นŒ ์ž๋ฐ” ์ƒ๊ฐ๋‚˜๋„ค ์ž๋ฐ”๋กœ ํ’€์—ˆ์œผ๋ฉด ๋” ๋นจ๋ฆฌ ํ’€๋ ธ์„๋ผ๋‚˜ ์–ด์จŒ๋“  ๋ฌธ์žฅ์„ ์ž…๋ ฅ๋ฐ›์•„์•ผ ํ–ˆ๊ธฐ์— ๋‚˜๋Š” cin์œผ๋กœ n์„ ์ž…๋ ฅ๋ฐ›๊ณ  getline์œผ๋กœ ๋ฌธ์ž์—ด์„ ์ž…๋ ฅ๋ฐ›์Œ ๊ทผ๋ฐ ์ œ๋Œ€๋กœ ์•ˆ๋Œ์•„๊ฐ.. ๋งŒ์•ฝ ์ € ์˜ˆ์ œ๋ฅผ ์ž…๋ ฅํ–ˆ๋‹ค๊ณ  ์น˜๋ฉด footbar๊นŒ์ง€๋Š” ์ž˜ ๋“ค์–ด๊ฐ€๋Š”๋ฐ all your base ๋ฌธ์žฅ์ด ์•ˆ๋“ค์–ด๊ฐ€๋Š”๊ฒƒ..! ์ด..

[baekjoon] 1158๋ฒˆ : ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ (C++)

์ฒ˜์Œ ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  ์ƒ๊ฐ๋‚œ ๊ฒƒ์€ .. ์›ํ˜• ํ์˜€๋‹ค ๊ทธ๋ž˜์„œ ๊ตฌํ˜„ํ•˜๋ ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์•˜์œผ๋‚˜.. ์‚ฌ๋žŒ๋“ค์ด ์ œ๊ฑฐ๋ ๋•Œ๋งˆ๋‹ค ๋นˆ ๊ณต๊ฐ„์„ ๋•ก๊ฒจ์„œ ๋‚ด๋ ค์™€์•ผ ํ•˜๊ณ ?... ์ข€ ๊นŒ๋‹ค๋กœ์› ๋‹ค๋Š” ๊ฒƒ์„ ๊นจ๋‹ฌ์•„์„œ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ฐพ์•˜๋‹ค ๋ฐ”๋กœ C++์˜ SLT์ค‘ ํ•˜๋‚˜์ธ Queue๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ k๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋  ๋•Œ๋Š” pop์„ ํ•˜๋ฉด ๋˜์ง€๋งŒ ๊ทธ๋ ‡์ง€ ์•Š์„ ๊ฒฝ์šฐ์—๋Š” ๋งจ ์•ž ์›์†Œ(front)๋ฅผ ํ์— pushํ•œ ๋’ค pop์„ ํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ํ๊ฐ€ empty๊ฐ€ ๋  ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค // BOJ 1158๋ฒˆ : ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ #include #include using namespace std; int main() { int n, k; // n: ์‚ฌ๋žŒ ์ˆ˜ / k: k๋ฒˆ์งธ ์‚ฌ๋žŒ ์ œ๊ฑฐ cin >> n >> k; queue q; // q ์ƒ์„ฑ int count..

[baekjoon] 1655๋ฒˆ : ๊ฐ€์šด๋ฐ๋ฅผ ๋งํ•ด์š” (C++)

์ตœ๋Œ€ํž™๊ณผ ์ตœ์†Œํž™์„ ์ด์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€๋‹น.. ๊ฐ’์ด ๋“ค์–ด์˜ฌ ๋•Œ๋งˆ๋‹ค ์ค‘๊ฐ„๊ฐ’์„ ์ถœ๋ ฅํ•˜๊ฒŒ ๋˜๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ์ฆ๊ฐ€ํ•˜๊ณ  ์ด ๋ฌธ์ œ๋Š” ์‹œ๊ฐ„ ์ œํ•œ์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์—... ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์ด ํ•„์š”ํ–ˆ๋‹ค ์—ฌ๊ธฐ์„œ ์กฐ๊ฑด์€ 1. ์ตœ์†Œ ํž™์˜ ๊ฐ’๋“ค์€ ๋ชจ๋‘ ์ตœ๋Œ€ ํž™๋ณด๋‹ค ํผ 2. ์ตœ๋Œ€ ํž™์˜ ํฌ๊ธฐ๊ฐ€ ์ตœ์†Œ ํž™์˜ ํฌ๊ธฐ๋ณด๋‹ค 1 ํฌ๊ฑฐ๋‚˜ ๊ฐ™๋„๋ก ์œ ์ง€ํ•˜๋ฉด์„œ ๊ฐ’์„ ๋„ฃ์–ด์•ผ ํ•จ 3. ๊ฐ’์„ ๋„ฃ์–ด์ค€ ํ›„์— ์ตœ๋Œ€ ํž™๊ณผ ์ตœ์†Œ ํž™์˜ top ๊ฐ’์„ ๋น„๊ตํ•ด ์ตœ์†Œ ํž™์˜ top๋ณด๋‹ค ์ตœ๋Œ€ ํž™์˜ top์ด ๋” ํฌ๋‹ค๋ฉด swapํ•จ arr[] = { 1, 5, 2, 10, -99, 7, 5 } ← ๋ฐฐ์—ด์ด ์ด๋ ‡๋‹ค๋ฉด [1 ์‚ฝ์ž…] - maxH = 1 - minH → ์ถœ๋ ฅ : 1 [5 ์‚ฝ์ž…] - maxH = 1 - minH = 5 → ์ถœ๋ ฅ : 1 [2 ์‚ฝ์ž…] - maxH = 1 2 - m..

[baekjoon] 12865๋ฒˆ : ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ (C++)

๋ฌธ์ œ๊ฐ€ ์ดํ•ด๊ฐ€ ์•ˆ๋ผ์„œ ํ•œ 5๋ฒˆ์ •๋„ ์ฝ์Œ ๊ทธ๋‹ˆ๊นŒ ๋Œ€์ถฉ... ์ดํ•ด๊ฐ€ ๋์Œ!! ์ผ๋‹จ ๋ฌผ๊ฑด์—๋Š” ๊ฐ๊ฐ์˜ ๊ฐ€์น˜๊ฐ€ ๋ถ€์—ฌ๊ฐ€ ๋˜๊ณ  ๊ทธ ๊ฐ€์น˜๋ฅผ ์ตœ๋Œ€ํ•œ์œผ๋กœ ํ•˜๋ฉด์„œ ๋ฐฐ๋‚ญ์— ๋ฌผ๊ฑด์„ ์ง‘์–ด๋„ฃ์–ด์•ผ ํ•จ ๊ทธ๋ ‡์ง€๋งŒ ๋ฐฐ๋‚ญ์—๋Š” ๋ฌด๊ฒŒ ์ œํ•œ์ด ์žˆ์Œ... ๋ฌผ๋ก  ๊ฐ๊ฐ ๋ฌผ๊ฑด์—๋„ ๋ฌด๊ฒŒ๊ฐ€ ์ฃผ์–ด์ง [ํ’€์ด] ๊ทธ๋Ÿฌ๋‹ˆ๊นŒ 1 ~ n ๊ฐœ์˜ ๋ฌผ๊ฑด์„ ํƒ์ƒ‰ ํ•˜๋ฉด์„œ ์ตœ๋Œ€ํ•œ ๊ฐ€์น˜๊ฐ€ ๋†’์•„์•ผ ํ•จ ๊ทผ๋ฐ ๋˜ ๋ฌด๊ฒŒ๊ฐ€ ์ดˆ๊ณผ๊ฐ€ ๋˜๋ฉด ์•ˆ๋จ Knapsack ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋ฉด ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ž„ ๋จผ์ € ์ฃผ์–ด์ง„ ๋ฌผ๊ฑด๋“ค์„ ์ฐจ๋ก€๋กœ w[i], v[i] ๋ฐฐ์—ด์— ์ง‘์–ด๋„ฃ์Œ w[i] : i๋ฒˆ์งธ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ v[i] : i๋ฒˆ์งธ ๋ฌผ๊ฑด์˜ ๊ฐ€์น˜ ๊ทธ๋ฆฌ๊ณ  2์ฐจ์› ๋ฐฐ์—ด ์ƒ์„ฑ arr[i][j] : ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜๋งŒํผ i ์กด์žฌ, ๋ฐฐ๋‚ญ์— ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋งŒํผ j ์กด์žฌ arr[i][j] = max(arr[i - 1][j..