user-img
์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋ก  5
thumbnail
ํˆฌ ํฌ์ธํ„ฐ ๊ฐœ๋… ๊ทธ๋ฆผ์œผ๋กœ ์‰ฝ๊ฒŒ ์„ค๋ช…^^
0. ๊ธ€์ด ํ˜๋Ÿฌ๊ฐ€๋Š” ๋ฐฉํ–ฅ๋จผ์ € ๊ฐœ๋… ์„ค๋ช…์„ ํ•˜๊ณ , ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ํ™œ์šฉํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ ๋ฌธ์ œ 2๊ฐœ๋ฅผ ์ง์ ‘ ํ’€์–ด๋ณด๋ฉฐ, ๊ฐœ๋…์— ๋Œ€ํ•œ ๋ณด์ถฉ์„ ํ•˜๊ฒ ๋‹ค.1. ๊ฐœ๋…1์ฐจ์› ๋ฐฐ์—ด์— ๋‘ ๊ฐœ์˜ ํฌ์ธํ„ฐ๋ฅผ ๋‘๊ณ , ๋‘ ํฌ์ธํ„ฐ์— ์˜๋ฏธ๋ฅผ ๋ถ€์—ฌํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ธฐ์ˆ ๋ฐฐ์—ด ์•ˆ์—์„œ ํŠน์ • ์กฐ๊ฑด์˜ ๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์—์„œ, ์ผ๋ฐ˜์ ์œผ๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O((N^{2}))๊ฐ€ ๋“ ๋‹ค๋ฉด, ํˆฌ ํฌ์ธํ„ฐ ๊ธฐ๋ฒ•์„ ํ™œ์šฉํ•˜๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ O(N)์œผ๋กœ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค. (์ด์œ ๋Š” ํ™œ์šฉ์„ ์‚ดํŽด๋ณด๋ฉฐ ์„ค๋ช…ํ•˜๊ฒ ๋‹ค.)(1) ์œ ํ˜•ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์šด์šฉํ•˜๋Š” ์œ ํ˜•์—๋Š” ํฌ๊ฒŒ 2๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.a.๋‹จ๋ฐฉํ–ฅ ์šด์šฉL ํฌ์ธํ„ฐ์™€ R ํฌ์ธํ„ฐ๊ฐ€ ํ•œ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ์›€์ง์ด๋Š” ๊ฒƒ์ด๋‹ค. ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ์˜ ์–‘๋์„ ์˜๋ฏธํ•œ๋‹ค๊ณ  ๋ณด๋ฉด ๋œ๋‹ค. ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ์™€ ๋‹ค๋ฅธ ์ ์€ ํฌ์ธํ„ฐ์— ๋”ฐ๋ผ ๊ตฌ๊ฐ„์˜ ๊ธธ์ด๊ฐ€ ๊ฐ€๋ณ€์ ์ด๋ผ๋Š” ๊ฒƒ์ด๋‹ค.b. ์–‘๋ฐฉํ–ฅ ์šด..
2024.12.23
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก 
thumbnail
์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ์— ๋Œ€ํ•˜์—ฌ
0. ์•Œ์•„๋ณผ ๊ฒƒ1. ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ๋ž€?๊ธธ์ด๊ฐ€ N์ธ 1์ฐจ์› ๋ฐฐ์—ด์•ˆ์— ๊ธธ์ด๊ฐ€ W์ธ ์›€์ง์ด๋Š” ๊ตฌ๊ฐ„์„ ์ƒ์„ฑํ•˜์—ฌ, ํ•ด๋‹น ๊ตฌ๊ฐ„์„ ํ•œ ์นธ์”ฉ ์›€์ง์ด๋ฉด์„œ ๊ตฌ๊ฐ„ ๋‚ด ์ •๋ณด๋ฅผ ์ถ”์ถœํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ์ˆ (N๊ณผ W๋Š” ์ƒ์ˆ˜)W์ธ ๊ตฌ๊ฐ„์„ ์›€์ง์ด๋Š” ๊ฒƒ์ด ๋งˆ์น˜ ์ฐฝ๋ฌธ์„ ๋ฐ€๊ณ  ๋‹น๊ธฐ๋Š” ๊ฒƒ๊ณผ ๊ฐ™๋‹ค๊ณ  ํ•˜์—ฌ, ์›€์ง์ด๋Š” ๊ตฌ๊ฐ„์„ ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ๋ผ๊ณ  ๋ช…๋ช…ํ•จ.2. ํ™œ์šฉ(1) ๊ตฌ๊ฐ„ํ•ฉ1์ฐจ์› ๋ฐฐ์—ด์—์„œ ํŠน์ • ๊ตฌ๊ฐ„ ๋‚ด์˜ ํ•ฉ์„ ์›ํ•˜๋Š” ๋ฌธ์ œ์—์„œ ํ™œ์šฉ.a. ์–ด๋–ป๊ฒŒ ํ™œ์šฉ?๋ฐฐ์—ด์˜ ๊ธธ์ด๊ฐ€ N, ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ์˜ ๊ธธ์ด๊ฐ€ W์ด๊ณ  ํ•ด๋‹น ์ฐฝ๋ฌธ์„ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ•œ ์นธ์”ฉ ์›€์ง์ธ๋‹ค๋ฉด, ๋งค ์›€์ง์ž„ ๋งˆ๋‹ค, ์ด์ „ ์œ„์น˜์—์„œ์˜ W-1์˜ ์›์†Œ๋Š” ๋ณ€ํ•˜์ง€ ์•Š๊ณ  ๊ตฌ๊ฐ„ ๋‚ด์— ์œ ์ง€๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด N = 10, W = 3์ด๋ผ ๊ฐ€์ •ํ•˜๋ฉด,๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด W-1์ธ 2๊ฐœ์˜ ์›์†Œ๋Š” ๋ณ€ํ•˜์ง€ ์•Š์•˜๋‹ค.์ด๋ฅผ ํ™œ์šฉํ•ด, ๋งจ ์ฒ˜..
2024.12.20
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก 
thumbnail
๐Ÿ–ค๊ตฌ๊ฐ„ํ•ฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜
1. ๊ตฌ๊ฐ„ํ•ฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?1์ฐจ์› ๋ฐฐ์—ด์—์„œ ํŠน์ • ๊ตฌ๊ฐ„ ๋‚ด์˜ ์›์†Œ๋“ค์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.2. ์™œ ์จ์•ผ ํ•˜๋Š”๊ฐ€?์œ„์˜ ์˜ˆ์‹œ์—์„œ A์—์„œ B๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ•œ๋‹ค๋ฉด, ์–ด๋–ป๊ฒŒ ๊ตฌํ•  ๊ฒƒ์ธ๊ฐ€? ํ˜น์ž๋Š” 2๋ฒˆ index๋ถ€ํ„ฐ 7๋ฒˆ index๊นŒ์ง€ for ๋ฐ˜๋ณต๋ฌธ์„ ํ™œ์šฉํ•ด ์ฐจ๋ก€๋Œ€๋กœ ๋”ํ•  ๊ฒƒ์ด๋‹ค. ํ˜น์ž๋Š” 0์—์„œ A๋ฒˆ๊นŒ์ง€์˜ ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•˜๊ณ , 0~B๋ฒˆ๊นŒ์ง€์˜ ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•ด, ๋‘˜์„ ๋นผ์„œ ๊ตฌํ•  ๊ฒƒ์ด๋‹ค. ๋งŒ์•ฝ ๋‹จ์ผ ๊ณ„์‚ฐ์ด๋ผ๋ฉด, ์ด๋Ÿฐ ์‹์˜ ํ’€์ด๋Š” n๋ฒˆ์˜ ๋ฐ˜๋ณต์ผ ๋ฟ์ด๋‹ˆ ๊ดœ์ฐฎ์„ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, ๋ฌธ์ œ์—์„œ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ตฌ๊ฐ„ํ•ฉ์„ ๋ฐ˜ํ™˜ํ•˜๊ธธ ๋ฐ”๋ž€๋‹ค๋ฉด? ๋งค๋ฒˆ ์ด๋Ÿฌํ•œ ๋ฐ˜๋ณต๋ฌธ์„ ๋ฐ˜๋ณตํ•˜๋Š” ๊ฒƒ์€ ๋น„ํšจ์œจ์ ์ด๋‹ค. ์ด๋Š” ์‹œ๊ฐ„ ์ดˆ๊ณผ๋กœ ์ด์–ด์งˆ ์ˆ˜ ์žˆ๋‹ค.์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ๊ณ„์‚ฐํ•ด ๋ณด๊ฒ ๋‹ค. ์ตœ์•…์„ ์ƒ์ •ํ•ด์•ผํ•˜๋‹ˆ, N๊ฐœ์˜ ์›์†Œ๋ฅผ ๊ฐ€์ง„ ๋ฐฐ์—ด์—์„œ 0~ N~1๊นŒ์ง€์˜ ๊ณ„์‚ฐ์„ K๋ฒˆ ๋ฐ˜..
2024.12.07
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก 
thumbnail
๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋…
1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌด์—‡์ธ๊ฐ€์š”? ๐Ÿ’กGreedy Algorithm์€ ๋งค ์„ ํƒ์˜ ์ˆœ๊ฐ„๋งˆ๋‹ค ๋‹น์‹œ์— ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์˜ ์„ ํƒ์ง€๋ฅผ ๊ณจ๋ผ๊ฐ€๋Š” ๊ฒƒ์ด ์ „์ฒด์—์„œ ๋ดค์„ ๋•Œ ์ตœ์„ ์˜ ์„ ํƒ์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•ด๋ณด์ž.ํ˜„์žฌ A์˜ ์‹œ์ ์—์„œ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์„ ํƒ์ง€ ์ค‘ C๊ฐ€ ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ด๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ C๋ฅผ ์„ ํƒํ•œ๋‹ค.C ์‹œ์ ์—์„œ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์„ ํƒ์ง€ ์ค‘ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋…ธ๋“œ๋Š” G์ด๋‹ค. ๋”ฐ๋ผ์„œ G๋ฅผ ์„ ํƒํ•œ๋‹ค. ๋‘๋ฒˆ์˜ ์„ ํƒ ํ›„ ๋ฌด์กฐ๊ฑด F๋ฅผ ๋น„์šฉ 0์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, ์ „์ฒด ๋…ธ๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.๋งค ์ˆœ๊ฐ„ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์˜ ์„ ํƒ์ง€๋ฅผ ๊ณจ๋ž๋”๋‹ˆ ์ „์ฒด์—์„œ ๋ดค์„ ๋•Œ๋„ ์ตœ์„ ์˜ ์„ ํƒ์ด์—ˆ๋‹ค. ์ด์™€ ๊ฐ™์ด ๋งค ์ˆœ๊ฐ„์˜ ์ตœ์„  = ์ „์ฒด์˜ ์ตœ์„  ์ด ์„ฑ๋ฆฝํ•  ๋•Œ, ์ด๋Ÿฌํ•œ ๋…ผ๋ฆฌ๋ฅผ Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ ํ•œ๋‹ค..
2024.11.07
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก 
thumbnail
๐Ÿ–ค ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ๊ฐœ๋…๊ณผ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ์˜ ํ™œ์šฉ๋ฒ•
1. ์‹œ๊ฐ„ ๋ณต์žก๋„ ๋ž€?(1) ๊ฐœ๋…์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ๋งํ•œ๋‹ค.(2) ํ‘œ๊ธฐ ๋ฐฉ๋ฒ•์˜ ์ข…๋ฅ˜์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œ๊ธฐํ•˜๋Š” ๋ฐฉ๋ฒ•์—๋Š” ๋‹ค์Œ์˜ 3 ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.์ด๋ฆ„์„ค๋ช…๋น…-์˜ค๋ฉ”๊ฐ€ ํ‘œ๊ธฐ๋ฒ•๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด ์ฃผ์–ด์ง„ ์ƒํ™ฉ์ด ์ตœ์„ ์˜ ์ƒํ™ฉ์ผ ๋•Œ ํ•„์š”ํ•œ ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ๊ธฐ๋ฒ•๋น…-์„ธํƒ€ ํ‘œ๊ธฐ๋ฒ•๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด ์ฃผ์–ด์ง„ ์ƒํ™ฉ์ด ๋ณดํ†ต์˜ ์ƒํ™ฉ์ผ ๋•Œ ํ•„์š”ํ•œ ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ๊ธฐ๋ฒ•๋น…-์˜ค ํ‘œ๊ธฐ๋ฒ•๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด ์ฃผ์–ด์ง„ ์ƒํ™ฉ์ด ์ตœ์•…์˜ ์ƒํ™ฉ์ผ ๋•Œ ํ•„์š”ํ•œ ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ๊ธฐ๋ฒ•์˜ˆ๋ฅผ ๋“ค์–ด ์„ค๋ช…1~100์˜ ์ˆซ์ž๊ฐ€ ๋žœ๋คํ•œ ์ˆœ์„œ๋กœ ์ €์žฅ๋œ ๋ฐฐ์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ•ด๋‹น ๋ฐฐ์—ด์—์„œ 56์˜ INDEX๋ฅผ ์ฐพ์•„์„œ ์ถœ๋ ฅํ•˜๋ผ ๋ผ๋Š” ๋ฌธ์ œ๋ฅผ ํ’€์–ด์•ผ ํ•œ๋‹ค๊ณ  ํ•˜์ž.์ด๋•Œ ๋‚ด๊ฐ€ ์„ ํƒํ•œ ๋ฐฉ๋ฒ•์€ ๋ฐฐ์—ด์˜ ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ถ€ํ„ฐ ์ผ์ผํžˆ ์กฐํšŒ์ด๋‹ค.๋น…-์˜ค..
2024.06.13
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก