profile
๐Ÿง‘โ€๐Ÿ’ป ์ด์ œ ๋ง‰ ์‹œ์ž‘ํ•œ ๋นˆ ์ง‘ ๋ธ”๋กœ๊ทธ...
post-thumbnail

BOJ 1011. Fly me to the Alpha Centauri

๋ฌธ์ œ ๋งํฌ ์šฐ์ฃผ์„ ์ด $i$๋ฒˆ์งธ๋กœ ์ด๋™ํ•œ ๊ฑฐ๋ฆฌ๋ฅผ $k{i}$๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, ์ˆ˜์—ด์˜ ์ฒซ์งธ ํ•ญ๊ณผ ๋งˆ์ง€๋ง‰ ํ•ญ์ด 1์ด๊ณ  $k{i+1} = k{i} - 1$ ๋˜๋Š” $k{i}$ ๋˜๋Š” $k_{i} + 1$๊ฐ€ ๋˜๋Š” ์ƒํ™ฉ์—์„œ ์ตœ์†Œ ์ด๋™ ํšŸ์ˆ˜๋ฅผ ๋ฌป๋Š” ๋ฌธ์ œ์ด๋‹ค! ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ํ•ต์‹ฌ ์ฒซ ๋ฒˆ์งธ๋Š” ๋ฐ”๋กœ $k{i}$์˜ ์ตœ๋Œ“๊ฐ’์— ๋Œ€ํ•ด ์ƒ๊ฐํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ˆ˜์—ด $k{i}$๋Š” ์ด์›ƒํ•˜๋Š” ํ•ญ๊ณผ์˜ ์ฐจ์ด๊ฐ€ ํ•ญ์ƒ $0$ ๋˜๋Š” $1$์ด์–ด์•ผ ํ•˜๋ฏ€๋กœ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํŠน์ง•์ด ์„ฑ๋ฆฝํ•œ๋‹ค. > $k_{i}$์˜ ์ตœ๋Œ“๊ฐ’์ด $n$์ด๋ผ๋ฉด, ์šฐ์ฃผ์„ ์€ ์ ์–ด๋„ $1 + 2 + \cdots + n + (n-1) + (n-2) + \cdots + 1 = n^2$๋งŒํผ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ด๋™ํ–ˆ์–ด์•ผ ํ•œ๋‹ค! ๋”ฐ๋ผ์„œ, ๊ฐ€๋Šฅํ•œ $n$์˜ ์ตœ๋Œ“๊ฐ’์€ $\sqrt{y - x}$ ์˜ ์ •์ˆ˜ ๋ถ€๋ถ„์ด ๋  ๊ฒƒ์ด๋‹ค. ํ•œํŽธ, ์œ„์™€ ๊ฐ™์ด ์šฐ์ฃผ์„ ์ด $(2n - 1)$๋ฒˆ์˜ ์›€์ง์ž„์œผ๋กœ $n^2$๋งŒํผ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ด๋™ํ•˜

2022๋…„ 11์›” 5์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 2505. ๋‘ ๋ฒˆ ๋’ค์ง‘๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜์— ์• ๋“œ ํ˜น์ด๋ผ๋Š” ๋ถ„๋ฅ˜๊ฐ€ ์žˆ์–ด, ๊ถ๊ธˆํ•ด์„œ ํ’€์–ด ๋ณธ ๋ฌธ์ œ์˜€๋‹ค! ์ฒ˜์Œ์—๋Š” ์• ๋“œ ํ˜น๋„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ข…๋ฅ˜์ธ ์ค„ ์•Œ์•˜๋Š”๋ฐ, ๋‚ด๊ฐ€ ์•„๋Š” ์˜๋ฏธ๊ฐ€ ์•„๋‹ˆ๋ผ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์•Œ๋ ค์ง„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ์ •๋ง '์•Œ์•„์„œ ์ƒ๊ฐํ•ด์„œ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ'๋ฅผ ์ผ์ปซ๋Š” ๋ง์ด์—ˆ๋‹ค. ๋ฌธ์ œ๋Š” 1๋ถ€ํ„ฐ $n$๊นŒ์ง€์˜ ์ˆ˜์—ด์„ ๋‘ ๋ฒˆ ๋’ค์ง‘์—ˆ์„ ๋•Œ, ์ด๋ฅผ ์›์ƒ๋ณต๊ตฌ์‹œํ‚ค๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ๋’ค์ง‘์–ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋ฌป๋Š”๋‹ค. ์•Œ๋ ค์ง„ ๊ณต์‹์ด๋‚˜ ๋ฐฉ๋ฒ•์„ ์ ์šฉํ•  ์ˆ˜ ์—†์–ด์„œ, ์šฐ์„  ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์˜ˆ์‹œ๋ฅผ ์ƒ์„ฑํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค! ๊ทธ๋Ÿฌ๋‹ค ๋ณด๋‹ˆ, ์ˆ˜์—ด์„ ๋’ค์ง‘์œผ๋ฉด ๋’ค์ง‘ํžŒ ๊ตฌ๊ฐ„ ๋‚ด๋ถ€์— ์žˆ๋Š” ์ˆซ์ž๋“ค์€ ์ธ์ ‘ํ•œ ์ˆซ์ž์™€์˜ ์ฐจ์ด๊ฐ€ 1 ๋˜๋Š” -1์ด์ง€๋งŒ ๊ทธ ๊ฒฝ๊ณ„์— ์žˆ๋Š” ์ˆซ์ž๋Š” ์ธ์ ‘ํ•œ ์ˆซ์ž์™€์˜ ์ฐจ์ด๊ฐ€ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์—, ์ด ์ ๋“ค์„ ํ‘œ์‹œํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค! ๊ทธ๋Ÿฐ๋ฐ ์ฒ˜์Œ

2022๋…„ 10์›” 28์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 6549. ํžˆ์Šคํ† ๊ทธ๋žจ์—์„œ ๊ฐ€์žฅ ํฐ ์ง์‚ฌ๊ฐํ˜•

๋ฌธ์ œ ๋งํฌ ์˜ˆ์ „์— ์ฑ…์—์„œ ์–ผํ• ๋ณธ ๊ฒƒ ๊ฐ™์€ ๋ฌธ์ œ๋ผ ์ƒ๊ฐ๋ณด๋‹ค ๊ฐ„๋‹จํ•˜๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค! ์œ„ ์‚ฌ์ง„๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„ ํžˆ์Šคํ† ๊ทธ๋žจ์„ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆˆ ํ›„, ์•„๋ž˜์˜ 3๊ฐ€์ง€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ„์–ด์„œ ๋ถ„ํ•  ์ •๋ณต์„ ์ด์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋ฉด ๋œ๋‹ค. > 1. ์ •๋‹ต์ด ๋˜๋Š” ์ง์‚ฌ๊ฐํ˜•์ด ์™ผ์ชฝ ๋ถ€๋ถ„์—๋งŒ ์žˆ๋‹ค. > 2. ์ •๋‹ต์ด ๋˜๋Š” ์ง์‚ฌ๊ฐํ˜•์ด ์˜ค๋ฅธ์ชฝ ๋ถ€๋ถ„์—๋งŒ ์žˆ๋‹ค. > 3. ์ •๋‹ต์ด ๋˜๋Š” ์ง์‚ฌ๊ฐํ˜•์ด ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์— ๊ฑธ์ณ ์žˆ๋‹ค. $i$๋ฒˆ ์ง์‚ฌ๊ฐํ˜•๋ถ€ํ„ฐ $j$๋ฒˆ ์ง์‚ฌ๊ฐํ˜•๊นŒ์ง€ ๊ณ ๋ คํ•œ ๋‹ต์„ $solve(i, j)$๋ผ ํ•˜๋ฉด, $mid = \lfloor\frac{i + j}{2}\rfloor$๋ผ๊ณ  ํ•˜์˜€์„ ๋•Œ, 1๋ฒˆ๊ณผ 2๋ฒˆ์˜ ๊ฒฝ์šฐ๋Š” $solve(i, mid)$์™€ $s

2022๋…„ 10์›” 27์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 2152. ์—ฌํ–‰ ๊ณ„ํš ์„ธ์šฐ๊ธฐ

๋ฌธ์ œ ๋งํฌ ์•„์ด๋””์–ด ์ž์ฒด๋Š”, ๊ทธ๋ž˜ํ”„์˜ SCC(Strongly connected components)๋ฅผ ์ฐพ์•„์„œ ์ „์ฒด ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•˜๊ณ  ๊ฐ๊ฐ์˜ SCC๋ฅผ ์ •์ ์œผ๋กœ ๊ฐ–๋Š” ์ƒˆ๋กœ์šด ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ๋“ค์–ด์„œ ํ•ด๊ฒฐํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ผ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค! SCC ์ฐพ๊ธฐ ๊ทธ๋ž˜ํ”„์˜ SCC๋ฅผ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์€ ์ด ๋ธ”๋กœ๊ทธ๋ฅผ ์ฐธ๊ณ ํ–ˆ๋Š”๋ฐ, ๋‚˜์ค‘์— ํ…œํ”Œ๋ฆฟ์œผ๋กœ ๋งŒ๋“ค์–ด ๋‘๋ฉด ์ข‹์„ ๊ฒƒ ๊ฐ™๋‹ค! ์•„์ด๋””์–ด๋Š” ํ•˜๋‚˜์˜ ์ •์ ์— ๋Œ€ํ•ด DFS๋ฅผ ํ•˜๋˜, ๋ฐฉ๋ฌธํ•œ ์ˆœ์„œ๋ฅผ ์ €์žฅํ•˜๊ณ  ์Šคํƒ์— ๋„ฃ์œผ๋ฉด์„œ, ๋ฐฉ๋ฌธํ•œ ์ •์ ์ด ์ด๋ฏธ ๋ฐฉ๋ฌธํ–ˆ์œผ๋‚˜ SCC๋กœ ๋ถ„๋ฅ˜๋˜์ง€ ์•Š์€ ์ •์ ์ด๋ฉด cycle์„ ๋ฐœ๊ฒฌํ•œ ๊ฒƒ์ด๋ฏ€๋กœ cycle์—์„œ ์ตœ์ดˆ๋กœ ๋ฐฉ๋ฌธ

2022๋…„ 10์›” 18์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 14003. ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด 5

๋ฌธ์ œ ๋งํฌ LIS(Longest Increasing Subsequence) ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์œ ๋ช…ํ•œ ๋ฌธ์ œ๋“ค ์ค‘ ํ•˜๋‚˜๋กœ, ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์ด์šฉํ•œ๋‹ค๋ฉด $dp(i)$๋ฅผ $i$๋ฒˆ์งธ ์›์†Œ๋ฅผ ๋งˆ์ง€๋ง‰ ๊ฐ’์œผ๋กœ ๊ฐ–๋Š” LIS์˜ ๊ธธ์ด๋กœ ์ •์˜ํ•œ ๋’ค $dp(n)$์„ ๊ตฌํ•ด์ฃผ๋ฉด ๋˜๋Š”๋ฐ, ์ด๋•Œ $dp(i)$๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด $i$๋ฒˆ์งธ ์›์†Œ ์•ž์— ์žˆ๋Š” ๋ฐฐ์—ด์˜ ์›์†Œ์™€ $dp(j)$ ๊ฐ’์„ ์Šค์บ”ํ•ด์•ผ ํ•˜๋ฏ€๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(n^2)$๊ฐ€ ๋œ๋‹ค. ํ•˜์ง€๋งŒ ์ด ๋ฌธ์ œ๋Š” ์ˆ˜์—ด์˜ ์›์†Œ ๊ฐœ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 1,000,000๊ฐœ์ด๋ฏ€๋กœ ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜๋ฐ–์— ์—†๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ $O(n log n)$์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•˜๋Š”๋ฐ, ๋ฐ”๋กœ ์ˆ˜์—ด์— ์žˆ๋Š” ์ˆ˜๋“ค์„ ๊ฐ๊ฐ ๊ฒ€์‚ฌํ•˜๋ฉด์„œ, LIS๊ฐ€ ๋  ์ˆ˜ ์žˆ๋Š” ํ›„๋ณด ์ˆ˜์—ด์„ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด์„ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘ํ•œ๋‹ค. ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ $A$, LIS๊ฐ€ ๋ 

2022๋…„ 10์›” 16์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 14853. ๋™์ „ ๋˜์ง€๊ธฐ

๋ฌธ์ œ ๋งํฌ ๋™์ „ ๋˜์ง€๊ธฐ์˜ ๊ฒฐ๊ณผ๋ฅผ ์•Œ๋ ค์ฃผ๊ณ , ๋™์ „์ด ์•ž๋ฉด์ด ๋‚˜์˜ฌ ํ™•๋ฅ ์— ๋Œ€ํ•ด ๋ฌผ์–ด๋ณด๋Š” ๋ฌธ์ œ๋ผ์„œ ๋ฒ ์ด์ฆˆ ์ •๋ฆฌ๋ฅผ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•˜๋‹ค! ๊ฒฐ๊ณผ์ ์œผ๋กœ ๋ฒ ์ด์ฆˆ ์ •๋ฆฌ๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ™•๋ฅ ๋ถ„ํฌ๋ฅผ ๊ตฌํ•˜๊ณ  ์ ๋ถ„์„ ํ†ตํ•ด ๊ณ„์‚ฐํ•˜๋Š” ๊ฒƒ์€ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜์„œ ์‹คํŒจํ–ˆ์ง€๋งŒ, ๊ทธ๋ž˜๋„ ๊ณ„์‚ฐ ๊ณผ์ •์ด ๋งž๊ณ  ์˜ค๋žœ๋งŒ์— ๋ฒ ์ด์ฆˆ ์ •๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ดค์œผ๋‹ˆ๊นŒ ์ด๊ฒƒ๋„ ์จ ๋ด์•ผ๊ฒ ๋‹ค! ๋ฒ ์ด์ฆˆ ์ •๋ฆฌ๋ฅผ ์ด์šฉํ•ด์„œ ํ™•๋ฅ  ๋ถ„ํฌ ๊ตฌํ•˜๊ธฐ(์‹œ๊ฐ„ ์ดˆ๊ณผ) ๋ฒ ์ด์ฆˆ ์ •๋ฆฌ์˜ ๋ชจ์Šต์ธ๋ฐ, ์—ฌ๊ธฐ์„œ ๋™์ „์˜ ํ™•๋ฅ  $p$์™€ $q$๋Š” ์—ฐ์†ํ™•๋ฅ ๋ณ€์ˆ˜์ด๋ฏ€๋กœ ํ™•๋ฅ ๋ฐ€๋„ํ•จ์ˆ˜์— ๋Œ€ํ•ด์„œ ์“ฐ๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค! ๋จผ์ € ์‚ฌ๊ฑด $A$๋ฅผ ๋™์ „์„ $n1$๋ฒˆ ๋˜์งˆ ๋•Œ ์•ž๋ฉด์ด $m1$๋ฒˆ ๋‚˜์˜จ ์‚ฌ๊ฑด์œผ๋กœ ์ •์˜ํ•˜๊ณ , ๋™์ „ 1์˜ ์‚ฌ์ „ ํ™•๋ฅ  ๋ถ„ํฌ๋Š”

2022๋…„ 10์›” 15์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 10942. ํŒฐ๋ฆฐ๋“œ๋กฌ?

๋ฌธ์ œ ๋งํฌ ๊ฐ„๋‹จํ•œ DP ๋ฌธ์ œ๋กœ, ์–ด๋–ค ์ˆ˜์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ $i$๋ฒˆ์งธ๋ถ€ํ„ฐ $j$๋ฒˆ์งธ๊นŒ์ง€์˜ ๋ถ€๋ถ„ ์ˆ˜์—ด์ด ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€ ์ฐพ๋Š” ๊ฒƒ์ธ๋ฐ ๋ฌธ์ œ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ ์ฃผ์–ด์ง„๋‹ค! ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํฌ๊ธฐ๊ฐ€ 1 ์ดํ•˜์ผ ๋•Œ๋Š” ํ•ญ์ƒ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด ๋˜๊ณ , ํฐ ์ž…๋ ฅ์— ๋Œ€ํ•ด์„œ๋Š” $i$๋ฅผ ํ•˜๋‚˜ ๋Š˜๋ฆฌ๊ณ  $j$๋ฅผ ํ•˜๋‚˜ ์ค„์ด๋ฉด์„œ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด์— ์ €์žฅํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

2022๋…„ 10์›” 15์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 2618๋ฒˆ: ๊ฒฝ์ฐฐ์ฐจ

๋ฌธ์ œ ๋งํฌ DP๋งŒ ์“ฐ๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ธ๋ฐ, ๋‚œ์ด๋„๊ฐ€ ํ”Œ๋ž˜ํ‹ฐ๋„˜ V๋กœ ๋‚˜์—๊ฒŒ๋Š” ์–ด๋ ค์šด ํŽธ์ธ ๋ฌธ์ œ์˜€๋‹ค! ๋‹น์—ฐํžˆ ์•ˆ ๋˜๊ฒ ์ง€๋งŒ, ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ‘ผ๋‹ค๋ฉด ๊ฒฐ๊ตญ ๊ฐ๊ฐ์˜ ์‚ฌ๊ฑด์— ๋Œ€ํ•ด 1๋ฒˆ ๊ฒฝ์ฐฐ์ฐจ๊ฐ€ ์ถœ๋™ํ•˜๋ฉด ๋˜๋Š”์ง€, 2๋ฒˆ ๊ฒฝ์ฐฐ์ฐจ๊ฐ€ ์ถœ๋™ํ•˜๋ฉด ๋˜๋Š”์ง€๋ฅผ ํŒ๋‹จํ•˜๋ฉด ๋˜๋‹ˆ๊นŒ ์ตœ๋Œ€ $2^{1000}$๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•  ๊ฒƒ์ด๋‹ค. ์—ฌ๊ธฐ์„œ ์ค‘๋ณต๋œ ๊ณ„์‚ฐ์ด ์—ฌ๋Ÿฌ ๋ฒˆ ๋‚˜์˜ค๋ฉด DP๋ฅผ ์ ์šฉํ•˜๋ฉด ๋˜๋Š”๋ฐ, ์ฒ˜์Œ์—๋Š” ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ(optimal substructure)๊ฐ€ ์„ฑ๋ฆฝํ•˜๋Š”์ง€์— ๋Œ€ํ•œ ์˜์‹ฌ์„ ํ•ด ๋ณด์•˜๋‹ค! > $w$๊ฐœ์˜ ์‚ฌ๊ฑด์„ ํ•ด๊ฒฐํ•˜๋Š” ์ตœ์ ์˜ ์„ ํƒ์„ $A$๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, ์—ฌ๊ธฐ์„œ ์ƒˆ๋กœ์šด ์‚ฌ๊ฑด์ด ์ถ”๊ฐ€๋˜์—ˆ์„ ๋•Œ $(w+1)$๊ฐœ์˜ ์‚ฌ๊ฑด์„ ํ•ด๊ฒฐํ•˜๋Š” ์ตœ์ ์˜ ๊ฒฝ๋กœ๋Š” $A$๋ฅผ ํฌํ•จํ•˜๋Š”๊ฐ€? ์ด๊ฒƒ์ด ์‚ฌ์‹ค์ด๋ผ๋ฉด ์ƒˆ๋กœ์šด ์‚ฌ๊ฑด์ด ์ถ”๊ฐ€๋  ๋•Œ๋งˆ๋‹ค, 1๋ฒˆ ๊ฒฝ์ฐฐ์ฐจ ํ˜น์€ 2๋ฒˆ ๊ฒฝ์ฐฐ์ฐจ๊ฐ€ ์ถœ๋™ํ•˜๋Š” ๋‘ ๊ฐ€์ง€ ๊ฒฝ์šฐ๋งŒ ๊ณ ๋ คํ•˜๋ฉด ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋งค์šฐ ์‰ฝ๊ฒŒ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ ๊ทธ๋ ‡์ง€ ์•Š๋‹ค. !

2022๋…„ 10์›” 15์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

BOJ 2098๋ฒˆ: ์™ธํŒ์› ์ˆœํšŒ

๋ฌธ์ œ ๋งํฌ TSP(Traveling Salesman Problem)์ด๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” ์œ ๋ช…ํ•œ ๋ฌธ์ œ์ด๋‹ค. NP-Complete์˜ ๋Œ€ํ‘œ์  ๋ฌธ์ œ๋กœ ์•„์ง ๋‹คํ•ญ ์‹œ๊ฐ„ ๋‚ด์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์—†๋‹ค! ๋ชจ๋“  ๊ฒฝ๋กœ๋ฅผ ์ˆœ์—ด๋กœ ๋งŒ๋“ค์–ด ์ผ์ผ์ด ํƒ์ƒ‰ํ•œ๋‹ค๋ฉด $O(n!)$์˜ ์‹œ๊ฐ„์ด ์†Œ์š”๋˜๋Š”๋ฐ ์ด ๋ฌธ์ œ์—์„œ๋Š” ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์ด์šฉํ•˜๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค. ์ •์  ์ง‘ํ•ฉ $V$์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ $S$์™€ ์ •์  $j(j \neq 0)$์— ๋Œ€ํ•˜์—ฌ, $C(S, i)$๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•˜์ž. > $C(S, j)$ : ์ง‘ํ•ฉ $S$์˜ ์ •์ ์„ ํ•œ ๋ฒˆ์”ฉ ๋ชจ๋‘ ๋ฐฉ๋ฌธํ•˜๊ณ  ์ •์  $i$์—์„œ ์ข…๋ฃŒ๋˜๋Š” ๊ฒฝ๋กœ์˜ ์ตœ์†Œ ๋น„์šฉ ์ด๋•Œ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋‹ต์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. > $answer = \displaystyle\min_{i \in V, i \neq 0 }{[C(V, i) + dist(i, 0)]}$ ์ดˆ๊นƒ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ค์ •ํ•  ์ˆ˜ ์žˆ

2022๋…„ 10์›” 10์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ…œํ”Œ๋ฆฟ : DFS์™€ BFS

์•ž์œผ๋กœ ์—ฌ๊ธฐ์— ์˜ฌ๋ฆด ํ…œํ”Œ๋ฆฟ ์ฝ”๋“œ๋Š” Github์—์„œ๋„ ๋ณผ ์ˆ˜ ์žˆ๊ณ , ๋งค์šฐ ์ค‘์š”ํ•œ ๋‚ด์šฉ์ด ์•„๋‹ˆ๋ฉด ์ตœ์‹  ์ฝ”๋“œ๋Š” ์ด ๋ธ”๋กœ๊ทธ๊ฐ€ ์•„๋‹ˆ๋ผ Github์—์„œ๋งŒ ์œ ์ง€ํ•  ์˜ˆ์ •์ด๋‹ค! ๊ทธ๋ž˜ํ”„๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๊ฐ€์žฅ ๊ธฐ์ดˆ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ DFS์™€ BFS์ด๋‹ค! DFS๋Š” ๋ณดํ†ต ์žฌ๊ท€ ํ•จ์ˆ˜๋กœ ๊ตฌํ˜„๋˜๊ณ , BFS๋Š” ๋ณดํ†ต Queue ์ž๋ฃŒ ๊ตฌ์กฐ๋ฅผ ํ†ตํ•ด์„œ ๊ตฌํ˜„๋˜๊ณ , ์ด๋ฒˆ์—๋Š” DFS์™€ BFS๋ฅผ ํฌ๊ฒŒ 4๊ฐ€์ง€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ„์–ด์„œ ํ…œํ”Œ๋ฆฟ์„ ๋งŒ๋“ค์–ด ๋ณด์•˜๋‹ค. ๋‚ด๊ฐ€ ์ฃผ๋กœ ์ง€ํ‚ค๋ ค๊ณ  ๋…ธ๋ ฅํ•˜๋Š” ์ฝ”๋”ฉ ์Šคํƒ€์ผ์— ์˜์–ด๋กœ Comment๋ฅผ ๋‹ฌ์•„๋†“์•˜๋‹ค...! > 1. ๊ทธ๋ž˜ํ”„์˜ ์„ธ๋ถ€ ๊ตฌํ˜„์ด ์ •ํ•ด์ง€์ง€ ์•Š์€ ๊ฒฝ์šฐ > 2. ๊ทธ๋ž˜ํ”„์˜ ์ธ์ ‘ ํ–‰๋ ฌ(adjacency matrix)์ด **2D arr

2022๋…„ 10์›” 3์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท
post-thumbnail

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด : ์ƒˆ๋กœ์šด ์‹œ์ž‘

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์˜คํ”ˆ์ฑ„ํŒ…๋ฐฉ์— ๋“ค์–ด๊ฐ€๊ธฐ ์ตœ๊ทผ์— ์šด๋™๋„ ํ•˜๊ณ  ์•„๋ฅด๋ฐ”์ดํŠธ๋„ ํ•ด ๋ณด๊ณ  ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๋ฐ”์œ ์ผ๋“ค์ด ๋งŽ์•„์„œ์ธ์ง€ ์˜ค๋žœ๋งŒ์— ๋ธ”๋กœ๊ทธ ๊ธ€์„ ์“ฐ๋Š” ๊ฒƒ ๊ฐ™๋‹ค! ์—ฌ๋Š ๋•Œ์ฒ˜๋Ÿผ ์ง‘์—์„œ ๋’น๊ตด๊ฑฐ๋ฆฌ๋ฉฐ ์‹œ๊ฐ„ ๋‚  ๋•Œ ๊ฐ€๋” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด๋ฅผ ํ•˜๋˜ ๋‚˜๋Š” ์–ด๋Š ๋‚  ํ•™๊ต ์—๋ธŒ๋ฆฌํƒ€์ž„์„ ๋ณด๋‹ค๊ฐ€ ์ด๋Ÿฐ ๊ธ€์„ ๋ณด๊ฒŒ ๋œ๋‹ค. ๊ตฐ ๋ณต๋ฌด๋ฅผ ๋งˆ์น˜๊ณ  ๋‹ค์Œ ํ•™๊ธฐ๊นŒ์ง€ ์ง‘์—์„œ ์‰ฌ๊ณ  ์žˆ๋˜ ๋‚˜๋Š” ๊ณต๋ถ€๋ฅผ ํ•ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์„ ํ•ด๋„ ์ง€๊ธˆ์ด ์•„๋‹ˆ๋ฉด ์‰ด ์‹œ๊ฐ„์ด ์—†๋‹ค๋Š” ์ƒ๊ฐ์ด ์•ž์„ฐ๋‹ค. ์ง€๊ธˆ์ด ์•„๋‹ˆ๋ฉด ์‰ด ์‹œ๊ฐ„์ด ์—†์„ ๊ฑฐ๋ผ๋Š” ์ƒ๊ฐ์—, ๋†€ ์ˆ˜ ์žˆ์„ ๋•Œ ๋†€์ž๋Š” ์ƒ๊ฐ์—๋Š” ๋ณ€ํ•จ์ด ์—†์ง€๋งŒ ์ด ๊ธ€์„ ๋ณด๊ณ  ๋งค์ผ 1๋ฌธ์ œ ์ •๋„๋ผ๋ฉด ํฐ ๋ถ€๋‹ด ์—†์ด ์ฐธ์—ฌํ•  ์ˆ˜ ์žˆ์„ ๊ฑฐ๋ผ๋Š” ์ƒ๊ฐ์— ์ชฝ์ง€๋ฅผ ๋ณด๋‚ด๊ณ  ์˜คํ”ˆ์ฑ„ํŒ…๋ฐฉ์— ๋“ค์–ด๊ฐ”๋‹ค! ![](https://velog.velcdn.com/images/smilelee

2022๋…„ 10์›” 2์ผ
ยท
0๊ฐœ์˜ ๋Œ“๊ธ€
ยท