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

์•Œ๊ณ ๋ฆฌ์ฆ˜8

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์ •๋ ฌ (์„ ํƒ, ์‚ฝ์ž…, ํ€ต์ •๋ ฌ..) ์ •๋ ฌ(sorting)์ด๋ž€ ๋ฐ์ดํ„ฐ๋ฅผ ํŠน์ •ํ•œ ๊ธฐ์ค€์— ๋”ฐ๋ผ์„œ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•˜๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค.(ex. ์˜ค๋ฆ„์ฐจ์ˆœ, ๋‚ด๋ฆผ์ฐจ์ˆœ) ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ •๋ ฌํ•˜๋ฉด ๋‹ค์Œ์žฅ์—์„œ ๋ฐฐ์šธ ์ด์ง„ํƒ์ƒ‰(binary search)๊ฐ€ ๊ฐ€๋Šฅํ•ด์ง„๋‹ค. ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ด์ง„ํƒ์ƒ‰์˜ ์ „์ฒ˜๋ฆฌ ๊ณผ์ •์ด๋ผ๊ณ ๋„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ์ฝ”๋”ฉํ…Œ์ŠคํŠธ๋ฅผ ๋Œ€๋น„ํ•˜๊ธฐ ์œ„ํ•ด์„  ํฌ๊ฒŒ 5๊ฐ€์ง€ ์ •๋ ฌ ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ ์•Œ๊ณ  ์žˆ์œผ๋ฉด ์ข‹๋‹ค! ์„ ํƒ์ •๋ ฌ / ์‚ฝ์ž…์ •๋ ฌ / ํ€ต์ •๋ ฌ / ๊ณ„์ˆ˜์ •๋ ฌ / ํŒŒ์ด์ฌ ๊ธฐ๋ณธ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์ •๋ ฌ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ „๊ณต ์‹œ๊ฐ„๋•Œ ๋ฐฐ์šด๋ฐ” ์žˆ๋Š”๋ฐ, ๊ทธ๋•Œ๋Š” c++ ์œ„์ฃผ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์˜์‚ฌ์ฝ”๋“œ๋ฅผ ํ†ตํ•ด ๊ณต๋ถ€๋ฅผ ํ–ˆ์—ˆ๋‹ค.(์ค‘๊ฐ„๊ณ ์‚ฌ ๋Œ€๋น„๋ฅผ ์œ„ํ•ด pseudocode ์ „์ฒด๋ฅผ ์™ธ์› ๋˜ ์•…๋ชฝ์ด...) ๊ทธ ๊ธฐ์–ต์„ ๋– ์˜ฌ๋ ค๋ณด๋ฉด์„œ python์—์„œ์˜ ์ฝ”๋“œ ๊ตฌํ˜„์—๋Š” ์–ด๋–ค ์ด์ ์ด ์žˆ๋Š”์ง€ ์•Œ์•„๋ณด๊ณ  ์‹ถ์€ .. 2023. 11. 13.
[์•Œ๊ณ ๋ฆฌ์ฆ˜] BFS/DFS (feat. stack, queue) ๊ผญ ํ•„์š”ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ๊ธฐ์ดˆ BFS/DFS๋ฅผ ๋“ค์–ด๊ฐ€๊ธฐ์— ์•ž์„œ, ๋ฐ์ดํ„ฐ๋ฅผ ํ‘œํ˜„ํ•˜๊ณ  ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•œ ๊ตฌ์กฐ์— ๋Œ€ํ•ด์„œ ๊ฐ„๋‹จํžˆ ์–˜๊ธฐํ•ด๋ณด๊ณ  ๋„˜์–ด๊ฐ€์ž. Stack ๋ฐ•์Šค ์Œ“๊ธฐ์— ๋น„์œ ํ•  ์ˆ˜ ์žˆ๋‹ค ์„ ์ž…ํ›„์ถœ, ํ›„์ž…์„ ์ถœ ํŒŒ์ด์ฌ์—์„œ ์Šคํƒ์„ ์ด์šฉํ•  ๋•Œ์—๋Š” ๋ณ„๋„์˜ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค. ๊ธฐ๋ณธ ๋ฆฌ์ŠคํŠธ์—์„œ append()์™€ pop() ๋ฉ”์„œ๋“œ๋ฅผ ์ด์šฉํ•˜๋ฉด ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ๋™์ผํ•˜๊ธฐ ๋™์ž‘ํ•œ๋‹ค. Queue ๋Œ€๊ธฐ์ค„์— ๋น„์œ ํ•  ์ˆ˜ ์žˆ๋‹ค. ์„ ์ž…์„ ์ถœ ๊ตฌ์กฐ ํŒŒ์ด์ฌ์œผ๋กœ ํ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ๋Š” collections ๋ชจ๋“ˆ์—์„œ ์ œ๊ณตํ•˜๋Š” deque ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•˜์ž. deque๋Š” ์Šคํƒ๊ณผ ํ์˜ ์žฅ์ ์„ ๋ชจ๋‘ ์ฑ„ํƒํ•œ ๊ฒƒ์ธ๋ฐ ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ  ๋นผ๋Š” ์†๋„๊ฐ€ ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒํ˜•์— ๋น„ํ•ด ํšจ์œจ์ ์ด๋ฉฐ queue ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋” ๊ฐ„๋‹จํ•˜๋‹ค. ํ์™€ ๊ฐ™์€ ๊ฒฝ์šฐ push_bac.. 2023. 10. 11.
[C++] ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ (feat.๋ฐ”ํ‚น๋…) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ์ •์˜ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ž€, ์›์†Œ๋“ค์„ ์ €์žฅํ•  ๋•Œ ๊ทธ ๋‹ค์Œ ์›์†Œ๊ฐ€ ์žˆ๋Š” ์œ„์น˜๋ฅผ ํฌํ•จ์‹œํ‚ค๋Š” ๋ฐฉ์‹์œผ๋กœ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ์„ฑ์งˆ k ๋ฒˆ์งธ ์›์†Œ๋ฅผ ํ™•์ธ/๋ณ€๊ฒฝํ•˜๊ธฐ ์œ„ํ•ด O(k)๊ฐ€ ํ•„์š” (๋ฐฐ์—ด๊ณผ ๋‹ค๋ฅด๊ฒŒ ๊ณต๊ฐ„์— ์›์†Œ๋“ค์ด ์—ฐ์†ํ•ด์„œ ์œ„์น˜ํ•˜๊ณ  ์žˆ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ) ์ž„์˜์˜ ์œ„์น˜์— ์›์†Œ๋ฅผ ์ถ”๊ฐ€/์ž„์˜ ์œ„์น˜์˜ ์›์†Œ ์ œ๊ฑฐ๋Š” O(1) โญ๏ธ ์›์†Œ๋“ค์ด ๋ฉ”๋ชจ๋ฆฌ ์ƒ์— ์—ฐ์†ํ•ด์žˆ์ง€ ์•Š์•„ Cache hit rate๊ฐ€ ๋‚ฎ์ง€๋งŒ ํ• ๋‹น์ด ๋‹ค์†Œ ์‰ฌ์›€ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ์ข…๋ฅ˜ ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ: ๊ฐ ์›์†Œ๊ฐ€ ์ž์‹ ์˜ ๋‹ค์Œ ์›์†Œ์˜ ์ฃผ์†Œ๋ฅผ ๋“ค๊ณ  ์žˆ๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ: ๊ฐ ์›์†Œ๊ฐ€ ์ž์‹ ์˜ ์ด์ „ ์›์†Œ์™€ ๋‹ค์Œ ์›์†Œ์˜ ์ฃผ์†Œ๋ฅผ ๋‘˜๋‹ค ๋“ค๊ณ  ์žˆ๋‹ค. ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ๋Š” ์ฃผ์–ด์ง„ ์›์†Œ์˜ ์ด์ „ ์›์†Œ๊ฐ€ ๋ฌด์—‡์ธ์ง€๋ฅผ ์•Œ ์ˆ˜ ์—†๋Š”๋ฐ, ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ๋Š” .. 2023. 9. 19.
[์•Œ๊ณ ๋ฆฌ์ฆ˜]๊ตฌํ˜„ ๋จธ๋ฆฟ์†์— ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ •ํ™•ํ•˜๊ณ  ๋น ๋ฅด๊ฒŒ ํ”„๋กœ๊ทธ๋žจ์œผ๋กœ ์ž‘์„ฑํ•˜๊ธฐ ๊ตฌํ˜„ ํ•˜๊ธฐ ๊นŒ๋‹ค๋กœ์šด ๋ฌธ์ œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ„๋‹จํ•œ๋ฐ ์ฝ”๋“œ๊ฐ€ ์ง€๋‚˜์น  ๋งŒํผ ๊ธธ์–ด์ง€๋Š” ๋ฌธ์ œ ํŠน์ • ์†Œ์ˆ˜์  ์ž๋ฆฌ๊นŒ์ง€ ์ถœ๋ ฅํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ ๋ฌธ์ž์—ด์ด ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ ํ•œ ๋ฌธ์ž ๋‹จ์œ„๋กœ ๋Š์–ด์„œ ๋ฆฌ์ŠคํŠธ์— ๋„ฃ์–ด์•ผํ•˜๋Š”(ํŒŒ์‹ฑ์„ ํ•ด์•ผ ํ•˜๋Š”) ๋ฌธ์ œ ๋“ฑ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ "๊ตฌํ˜„"์€ ์–ด๋–ป๊ฒŒ ํ’€๋ฉด ๋ ์ง€ ๋Œ€๋žต ๊ฐ์€ ์˜ค๋Š”๋ฐ, ๋ง‰์ƒ ์ฝ”๋“œ๋กœ ์˜ฎ๊ธฐ๋ ค๋‹ˆ ๋ฌด์—‡๋ถ€ํ„ฐ ์ž‘์„ฑํ•ด์•ผ ํ• ์ง€ ๋ชจ๋ฅผ ์ˆ˜ ์žˆ๋‹ค.. ๋˜ํ•œ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋ฌธ๋ฒ•์„ ์ •ํ™•ํ•˜๊ฒŒ ์ˆ™์ง€ํ•˜์ง€ ๋ชปํ–ˆ๊ฑฐ๋‚˜, ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์‚ฌ์šฉ ๊ฒฝํ—˜์ด ๋ถ€์กฑํ•˜๋ฉด ๊ตฌํ˜„ ์œ ํ˜•์˜ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ๋ถˆ๋ฆฌํ•˜๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํŒŒ์ด์ฌ์œผ๋กœ ์ฝ”ํ…Œ๋ฅผ ๋ณด๋Š”๋ฐ N๊ฐœ์˜ ์›์†Œ๊ฐ€ ๋“ค์–ด ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ์—์„œ R๊ฐœ์˜ ์›์†Œ๋ฅผ ๋ฝ‘์•„ ํ•œ์ค„๋กœ ์„ธ์šฐ๋Š” ๊ฒฝ์šฐ(์ˆœ์—ด)์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ๋งŒ๋‚˜๋ฉด ์–ด๋–ป๊ฒŒ ํ• ๊ฒƒ์ธ๊ฐ€?? ๋ฌด์ž‘์ • ๊ธฐ๋Šฅ์„ ์ „.. 2023. 9. 13.
[์•Œ๊ณ ๋ฆฌ์ฆ˜]๊ทธ๋ฆฌ๋”” ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ๊ฐ€์žฅ ์ข‹์•„ ๋ณด์ด๋Š” ๊ฒƒ๋งŒ์„ ์„ ํƒํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๐Ÿงค ๊ทธ๋ฆฌ๋””(ํƒ์š•๋ฒ•)์ด๋ž€? ⇒ ๋‚˜๋จธ์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋‹ค ์ œ์ณ๋‘๊ณ  ๊ฐ€์žฅ ์ตœ์„ ์˜ ๋ฐฉ๋ฒ• ํ•œ๊ฐœ๋งŒ ํŒŒ๊ณ  ๋“ค์–ด์„œ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด ์ตœ์†Œ๋™์ „ ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค. (ex. ๋™์ „์œผ๋กœ 1400์„ ๋งŒ๋“ค๋•Œ ๋™์ „์„ ๊ฐ€์žฅ ์ ๊ฒŒ ์“ฐ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜ ์ฐพ๊ธฐ) ⇒ ๋งค ์ˆœ๊ฐ„ ๊ฐ€์žฅ ์ข‹์•„๋ณด์ด๋Š” ๋ฐฉ๋ฒ•์„ ์„ ํƒํ•˜๋ฉฐ, ํ˜„์žฌ์˜ ์„ ํƒ์ด ๋‚˜์ค‘์— ๋ฏธ์น  ์˜ํ–ฅ์— ๋Œ€ํ•ด์„œ๋Š” ๊ณ ๋ คํ•˜์ง€ ์•Š๋Š”๋‹ค. ๐Ÿ’ก ๊ทธ๋ฆฌ๋””๋ฌธ์ œ๋Š” ์ด ๋ฌธ์ œ๊ฐ€ ๊ทธ๋ฆฌ๋””์ธ๊ฐ€? ๋ฐ˜๋ก€๊ฐ€ ์žˆ๋Š”๊ฒƒ์€ ์•„๋‹๊นŒ? ๋ผ๋Š” ๊ณ ๋ฏผํ•˜๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ์–ด๋ ต๋‹ค๊ณ  ํ•œ๋‹ค. ๊ทธ๋ž˜์„œ ๋Š์ž„์—†์ด ์ด ๋ฌธ์ œ๋ฅผ ๊ทธ๋ฆฌ๋””๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š”์ง€, ๋ฐ˜๋ก€๊ฐ€ ์žˆ์„์ง€ ์—†์„์ง€ ๊ณ ๋ฏผํ•˜๋Š”๊ฒƒ์ด ์ •์ƒ์ด๋ผ๊ณ  ํ•œ๋‹ค. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋Š” ์ž์ฃผ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ง์„ ์ด๋ค„ ์ถœ์ œ๋œ๋‹ค. ๋Œ€ํ‘œ์ ์ธ ๋ฌธ์ œ ์œ ํ˜•์ด "๊ฑฐ์Šค๋ฆ„๋ˆ์„ ๋™์ „์œผ.. 2023. 9. 11.
[๋ธŒ๋ฃจํŠธํฌ์Šค][๋ฐฑ์ค€]1018-์ฒด์ŠคํŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ ์ฒด์ŠคํŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ ์‹œ๊ฐ„ ์ œํ•œ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ์ œ์ถœ์ •๋‹ต๋งžํžŒ ์‚ฌ๋žŒ์ •๋‹ต ๋น„์œจ 2 ์ดˆ 128 MB 103387 51258 41039 49.647% ๋ฌธ์ œ ์ง€๋ฏผ์ด๋Š” ์ž์‹ ์˜ ์ €ํƒ์—์„œ MN๊ฐœ์˜ ๋‹จ์œ„ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋Š” M×N ํฌ๊ธฐ์˜ ๋ณด๋“œ๋ฅผ ์ฐพ์•˜๋‹ค. ์–ด๋–ค ์ •์‚ฌ๊ฐํ˜•์€ ๊ฒ€์€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๊ณ , ๋‚˜๋จธ์ง€๋Š” ํฐ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๋‹ค. ์ง€๋ฏผ์ด๋Š” ์ด ๋ณด๋“œ๋ฅผ ์ž˜๋ผ์„œ 8×8 ํฌ๊ธฐ์˜ ์ฒด์ŠคํŒ์œผ๋กœ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์ฒด์ŠคํŒ์€ ๊ฒ€์€์ƒ‰๊ณผ ํฐ์ƒ‰์ด ๋ฒˆ๊ฐˆ์•„์„œ ์น ํ•ด์ ธ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ, ๊ฐ ์นธ์ด ๊ฒ€์€์ƒ‰๊ณผ ํฐ์ƒ‰ ์ค‘ ํ•˜๋‚˜๋กœ ์ƒ‰์น ๋˜์–ด ์žˆ๊ณ , ๋ณ€์„ ๊ณต์œ ํ•˜๋Š” ๋‘ ๊ฐœ์˜ ์‚ฌ๊ฐํ˜•์€ ๋‹ค๋ฅธ ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ์ด ์ •์˜๋ฅผ ๋”ฐ๋ฅด๋ฉด ์ฒด์ŠคํŒ์„ ์ƒ‰์น ํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ๋‘ ๊ฐ€์ง€๋ฟ์ด๋‹ค. ํ•˜๋‚˜๋Š” ๋งจ ์™ผ์ชฝ ์œ„ ์นธ์ด ํฐ์ƒ‰์ธ ๊ฒฝ์šฐ, ํ•˜๋‚˜๋Š” ๊ฒ€์€์ƒ‰์ธ ๊ฒฝ์šฐ์ด๋‹ค. ๋ณด๋“œ๊ฐ€ ์ฒด์ŠคํŒ์ฒ˜๋Ÿผ .. 2023. 9. 10.