๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/Linear Data Structure 7

[BOJ][C++] ๋ฐฑ์ค€ 1966๋ฒˆ: ํ”„๋ฆฐํ„ฐ ํ

https://www.acmicpc.net/problem/1966 1966๋ฒˆ: ํ”„๋ฆฐํ„ฐ ํ ์—ฌ๋Ÿฌ๋ถ„๋„ ์•Œ๋‹ค์‹œํ”ผ ์—ฌ๋Ÿฌ๋ถ„์˜ ํ”„๋ฆฐํ„ฐ ๊ธฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ๋ถ„์ด ์ธ์‡„ํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฌธ์„œ๋ฅผ ์ธ์‡„ ๋ช…๋ น์„ ๋ฐ›์€ ‘์ˆœ์„œ๋Œ€๋กœ’, ์ฆ‰ ๋จผ์ € ์š”์ฒญ๋œ ๊ฒƒ์„ ๋จผ์ € ์ธ์‡„ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์„œ๊ฐ€ ์Œ“์ธ๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ์— www.acmicpc.net ๋ฌธ์ œ ์—ฌ๋Ÿฌ๋ถ„๋„ ์•Œ๋‹ค์‹œํ”ผ ์—ฌ๋Ÿฌ๋ถ„์˜ ํ”„๋ฆฐํ„ฐ ๊ธฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ๋ถ„์ด ์ธ์‡„ํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฌธ์„œ๋ฅผ ์ธ์‡„ ๋ช…๋ น์„ ๋ฐ›์€ ‘์ˆœ์„œ๋Œ€๋กœ’, ์ฆ‰ ๋จผ์ € ์š”์ฒญ๋œ ๊ฒƒ์„ ๋จผ์ € ์ธ์‡„ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์„œ๊ฐ€ ์Œ“์ธ๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ์— ์Œ“์—ฌ์„œ FIFO - First In First Out - ์— ๋”ฐ๋ผ ์ธ์‡„๊ฐ€ ๋˜๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ์šด ํ”„๋ฆฐํ„ฐ๊ธฐ ๋‚ด๋ถ€ ์†Œํ”„ํŠธ์›จ์–ด๋ฅผ ๊ฐœ๋ฐœํ•˜์˜€๋Š”๋ฐ, ์ด ํ”„๋ฆฐํ„ฐ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์— ๋”ฐ๋ผ ์ธ์‡„๋ฅผ ํ•˜๊ฒŒ ๋œ๋‹ค..

[BOJ][C++] ๋ฐฑ์ค€ 17299๋ฒˆ: ์˜ค๋“ฑํฐ์ˆ˜

https://www.acmicpc.net/problem/17299 17299๋ฒˆ: ์˜ค๋“ฑํฐ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N (1 ≤ N ≤ 1,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ์— ์ˆ˜์—ด A์˜ ์›์†Œ A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ํ’€์ด ๊ฐ ์ˆซ์ž๋“ค์˜ ๊ฐฏ์ˆ˜๋Š” ์ž…๋ ฅ์„ ๋ฐ›๋Š” ์ค‘์— cnt ๋ฒกํ„ฐ๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋ฉฐ ๊ตฌํ–ˆ๋‹ค ์ž…๋ ฅ์„ ๋‹ค ๋ฐ›์€ ํ›„์—๋Š” ์ž…๋ ฅ์— ํ•ด๋‹นํ•˜๋Š” ๊ฐ ์ˆซ์ž์™€ ํ•ด๋‹น ์ˆซ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ pair๋กœ ๋งŒ๋“ค์–ด์„œ f ๋ฒกํ„ฐ์— ์ €์žฅํ•ด์ค€๋‹ค ์ด์ œ f๋ฒกํ„ฐ๋ฅผ ๊ฑฐ๊พธ๋กœ ๋Œ๋ฉด์„œ ์Šคํƒ์„ ์ด์šฉํ•ด ์˜ค๋“ฑํฐ์ˆ˜๋ฅผ ๊ตฌํ•ด์ค€๋‹ค ์Šคํƒ์•ˆ์— ์žˆ๋Š” ์ˆซ์ž๋“ค์€ ๋ณธ์ธ๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ์ˆซ์ž์ด๋ฏ€๋กœ ํ•ด๋‹น ์Šคํƒ ๋‚ด์—์„œ ๋ณธ์ธ์˜ ๋นˆ๋„๋ณด๋‹ค ๋” ํฐ ๋นˆ๋„๋ฅผ ๊ฐ€์ง„ ์ˆ˜๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ popํ•œ๋‹ค. ๊ทธ๋ ‡๊ฒŒ ๊ตฌํ•œ ์˜ค๋“ฑํฐ์ˆ˜..

[BOJ][C++] ๋ฐฑ์ค€ 1918๋ฒˆ: ํ›„์œ„ ํ‘œ๊ธฐ์‹

https://www.acmicpc.net/problem/1918 1918๋ฒˆ: ํ›„์œ„ ํ‘œ๊ธฐ์‹ ์ฒซ์งธ ์ค„์— ์ค‘์œ„ ํ‘œ๊ธฐ์‹์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹จ ์ด ์ˆ˜์‹์˜ ํ”ผ์—ฐ์‚ฐ์ž๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง€๋ฉฐ ์ˆ˜์‹์—์„œ ํ•œ ๋ฒˆ์”ฉ๋งŒ ๋“ฑ์žฅํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  -A+B์™€ ๊ฐ™์ด -๊ฐ€ ๊ฐ€์žฅ ์•ž์— ์˜ค๊ฑฐ๋‚˜ AB์™€ ๊ฐ™์ด *๊ฐ€ ์ƒ๋žต๋˜๋Š” ๋“ฑ์˜ www.acmicpc.net ํ’€์ด ํ”ผ์—ฐ์‚ฐ์ž๋Š” ๋ฐ”๋กœ ๋‹ต ๋ฌธ์ž์—ด์— ๋„ฃ๋Š”๋‹ค. ์—ฐ์‚ฐ์ž๋Š” ์Šคํƒ์— ๋„ฃ์–ด์„œ ๊ด€๋ฆฌํ•œ๋‹ค. ๋‹ซํžŒ ๊ด„ํ˜ธ๊ฐ€ ๋‚˜์˜ค๋ฉด ์Šคํƒ ๋‚ด์— ์—ด๋ฆฐ ๊ด„ํ˜ธ๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์Šคํƒ์— ์žˆ๋Š” ์—ฐ์‚ฌ์ž๋“ค์„ ๋ฝ‘์•„์„œ ๋‹ต ๋ฌธ์ž์—ด์— ๋„ฃ๋Š”๋‹ค. ์—ฐ์‚ฐ์ž๋ฅผ ์Šคํƒ์— ๋„ฃ์„ ๋•Œ ์Šคํƒ ๋‚ด ์—ฐ์‚ฐ์ž๊ฐ€ ํ˜„์žฌ ์—ฐ์‚ฐ์ž๋ณด๋‹ค ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’๊ฑฐ๋‚˜ ๊ฐ™๋‹ค๋ฉด ์Šคํƒ์— ์žˆ๋Š” ์—ฐ์‚ฐ์ž๋ฅผ ๋‹ค ๋ฝ‘์•„์„œ ๋‹ต ๋ฌธ์ž์—ด์— ๋„ฃ๋Š”๋‹ค #include #include using namespace std; int..

[BOJ][C++] ๋ฐฑ์ค€ 20301๋ฒˆ: ๋ฐ˜์ „ ์š”์„ธํ‘ธ์Šค

https://www.acmicpc.net/problem/20301 20301๋ฒˆ: ๋ฐ˜์ „ ์š”์„ธํ‘ธ์Šค ์ฒซ์งธ ์ค„์— ์ •์ˆ˜ $N$, $K$, $M$์ด ์ฃผ์–ด์ง„๋‹ค. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net ๋ฌธ์ œ ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1$1$๋ฒˆ ์‚ฌ๋žŒ ์˜ค๋ฅธ์ชฝ์—๋Š” 2$2$๋ฒˆ ์‚ฌ๋žŒ์ด ์•‰์•„ ์žˆ๊ณ , 2$2$๋ฒˆ ์‚ฌ๋žŒ ์˜ค๋ฅธ์ชฝ์—๋Š” 3$3$๋ฒˆ ์‚ฌ๋žŒ์ด ์•‰์•„ ์žˆ๊ณ , ๊ณ„์†ํ•˜์—ฌ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ N$N$๋ช…์˜ ์‚ฌ๋žŒ๋“ค์ด ์›์„ ์ด๋ฃจ๋ฉฐ ์•‰์•„ ์žˆ๋‹ค. N$N$๋ฒˆ ์‚ฌ๋žŒ ์˜ค๋ฅธ์ชฝ์—๋Š” 1$1$๋ฒˆ ์‚ฌ๋žŒ์ด ์•‰์•„ ์žˆ๋‹ค. ์ด์ œ K$K$(≤N$\leq N$)๋ฒˆ ์‚ฌ๋žŒ์„ ์šฐ์„  ์ œ๊ฑฐํ•˜๊ณ , ์ดํ›„ ์ง์ „ ์ œ๊ฑฐ๋œ ์‚ฌ๋žŒ์˜ ์˜ค๋ฅธ์ชฝ์˜ K$K$๋ฒˆ์งธ ์‚ฌ๋žŒ์„ ๊ณ„์† ์ œ๊ฑฐํ•ด ๋‚˜๊ฐ„๋‹ค. ๋ชจ๋“  ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋˜์—ˆ์„ ๋•Œ, ์ œ๊ฑฐ๋œ ..

[BOJ S1][C++] ๋ฐฑ์ค€ 4889๋ฒˆ : ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด

https://www.acmicpc.net/problem/4889 4889๋ฒˆ: ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฐ์ดํ„ฐ ์„ธํŠธ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ๋ฐ์ดํ„ฐ ์„ธํŠธ๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ค„์—๋Š” ์—ฌ๋Š” ๊ด„ํ˜ธ์™€ ๋‹ซ๋Š” ๊ด„ํ˜ธ๋งŒ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๊ฐ€ 2000์„ ๋„˜๋Š” ๊ฒฝ์šฐ www.acmicpc.net ๋ฌธ์ œ ์—ฌ๋Š” ๊ด„ํ˜ธ์™€ ๋‹ซ๋Š” ๊ด„ํ˜ธ๋งŒ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์—ฌ๊ธฐ์„œ ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด์„ ๋งŒ๋“ค๊ธฐ ์œ„ํ•œ ์ตœ์†Œ ์—ฐ์‚ฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด์˜ ์ •์˜๋ž€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ๋นˆ ๋ฌธ์ž์—ด์€ ์•ˆ์ •์ ์ด๋‹ค. S๊ฐ€ ์•ˆ์ •์ ์ด๋ผ๋ฉด, {S}๋„ ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด์ด๋‹ค. S์™€ T๊ฐ€ ์•ˆ์ •์ ์ด๋ผ๋ฉด, ST(๋‘ ๋ฌธ์ž์—ด์˜ ์—ฐ๊ฒฐ)๋„ ์•ˆ์ •์ ์ด๋‹ค. {}, {}{}, {{}{}}๋Š” ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด์ด์ง€๋งŒ, }{, {{}{, {}{๋Š” ..

[BOJ S3][C++] ๋ฐฑ์ค€ 18115๋ฒˆ : ์นด๋“œ ๋†“๊ธฐ

https://www.acmicpc.net/problem/18115 18115๋ฒˆ: ์นด๋“œ ๋†“๊ธฐ ์ˆ˜ํ˜„์ด๋Š” ์นด๋“œ ๊ธฐ์ˆ ์„ ์—ฐ์Šตํ•˜๊ณ  ์žˆ๋‹ค. ์ˆ˜ํ˜„์ด์˜ ์†์— ๋“ค๋ฆฐ ์นด๋“œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋‚ด๋ ค๋†“์•„ ๋ฐ”๋‹ฅ์— ์Œ“์œผ๋ ค๊ณ  ํ•œ๋‹ค. ์ˆ˜ํ˜„์ด๊ฐ€ ์“ธ ์ˆ˜ ์žˆ๋Š” ๊ธฐ์ˆ ์€ ๋‹ค์Œ 3๊ฐ€์ง€๋‹ค. ์ œ์ผ ์œ„์˜ ์นด๋“œ 1์žฅ์„ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์ˆ˜ํ˜„์ด๋Š” ์นด๋“œ ๊ธฐ์ˆ ์„ ์—ฐ์Šตํ•˜๊ณ  ์žˆ๋‹ค. ์ˆ˜ํ˜„์ด์˜ ์†์— ๋“ค๋ฆฐ ์นด๋“œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋‚ด๋ ค๋†“์•„ ๋ฐ”๋‹ฅ์— ์Œ“์œผ๋ ค๊ณ  ํ•œ๋‹ค. ์ˆ˜ํ˜„์ด๊ฐ€ ์“ธ ์ˆ˜ ์žˆ๋Š” ๊ธฐ์ˆ ์€ ๋‹ค์Œ 3๊ฐ€์ง€๋‹ค. ์ œ์ผ ์œ„์˜ ์นด๋“œ 1์žฅ์„ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. ์œ„์—์„œ ๋‘ ๋ฒˆ์งธ ์นด๋“œ๋ฅผ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. ์นด๋“œ๊ฐ€ 2์žฅ ์ด์ƒ์ผ ๋•Œ๋งŒ ์“ธ ์ˆ˜ ์žˆ๋‹ค. ์ œ์ผ ๋ฐ‘์— ์žˆ๋Š” ์นด๋“œ๋ฅผ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. ์นด๋“œ๊ฐ€ 2์žฅ ์ด์ƒ์ผ ๋•Œ๋งŒ ์“ธ ์ˆ˜ ์žˆ๋‹ค. ์ˆ˜ํ˜„์ด๋Š” ์ฒ˜์Œ์— ์นด๋“œ N์žฅ์„ ๋“ค๊ณ  ์žˆ๋‹ค..

[BOJ S5][C++] ๋ฐฑ์ค€ 11866๋ฒˆ : ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ 0

https://www.acmicpc.net/problem/11866 11866๋ฒˆ: ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ 0 ์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net ๋ฌธ์ œ ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ์›์„ ์ด๋ฃจ๋ฉด์„œ ์•‰์•„์žˆ๊ณ , ์–‘์˜ ์ •์ˆ˜ K(≤ N)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์ œ ์ˆœ์„œ๋Œ€๋กœ K๋ฒˆ์งธ ์‚ฌ๋žŒ์„ ์ œ๊ฑฐํ•œ๋‹ค. ํ•œ ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋˜๋ฉด ๋‚จ์€ ์‚ฌ๋žŒ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์›์„ ๋”ฐ๋ผ ์ด ๊ณผ์ •์„ ๊ณ„์†ํ•ด ๋‚˜๊ฐ„๋‹ค. ์ด ๊ณผ์ •์€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ๋ชจ๋‘ ์ œ๊ฑฐ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†๋œ๋‹ค. ์›์—์„œ ์‚ฌ๋žŒ๋“ค์ด ์ œ๊ฑฐ๋˜๋Š” ์ˆœ์„œ๋ฅผ (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์ด๋ผ๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด (7, 3)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์€ ์ด๋‹ค. N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง€๋ฉด (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ..

๋ฐ˜์‘ํ˜•