๐Ÿ“šํ•œ ์žฅ์œผ๋กœ ๋ณด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€ ์ˆœ์„œ๐Ÿ“š

Moonยท2022๋…„ 10์›” 22์ผ
863
post-thumbnail
post-custom-banner

ย  ์นด์ด์ŠคํŠธ์—์„œ ์ง„ํ–‰๋˜๋Š” SW์ •๊ธ€ ์ปค๋ฆฌํ˜๋Ÿผ์„ ๋ฐ”ํƒ•์œผ๋กœ ์ž‘์„ฑํ•˜์˜€์Šต๋‹ˆ๋‹ค. ๋‚˜์ค‘์— ๋ณต์Šตํ•  ๋•Œ ์ฐพ์•„๋ณด๊ธฐ ์œ„ํ•ด ๋”ฐ๋กœ ์ •๋ฆฌ๋ฅผ ํ–ˆ์Šต๋‹ˆ๋‹ค. ํŒŒํŠธ๋งˆ๋‹ค ์ €์˜ ์‚ฌ์กฑ์ด ๋‹ฌ๋ ค์žˆ๋Š”๋ฐ ์ฐธ๊ณ ํ•˜์‹ค ๋ถ„๋“ค์„ ์œ„ํ•ด ์ €์˜ ์ƒํ™ฉ์„ ๋ง์”€๋“œ๋ฆฌ์ž๋ฉด, python์œผ๋กœ ํ•™์Šต์„ ์ง„ํ–‰ํ•˜์˜€๊ณ  ์•ฝ 4์ฃผ๊ฐ„ ๋งค์ผ ํ‰๊ท  5~6๋ฌธ์ œ ์ •๋„ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.(ํ’€์—ˆ๋‹ค๋Š” ๋ง์ด ๋ถ€๋„๋Ÿฝ๊ฒŒ ๋งŽ์ด ํ•ด๋‹ต์„ ์ฐพ์•„๋ณด๊ธดํ–ˆ๋Š”๋ฐ..) ์ •๊ธ€์— ์ž…์†Œํ•˜๊ธฐ ์ „ ์ฝ”๋”ฉ ๊ณต๋ถ€๋Š” ๊ตญ๋น„๊ต์œก์„ ์ด์ˆ˜ํ•œ ๊ฒƒ์ด ์ „๋ถ€์ž…๋‹ˆ๋‹ค. ๋ฌธ๊ณผ ๋Œ€ํ•™ ์ถœ์‹ ์ด๋ผ ์ฝ”๋”ฉ์— ๋Œ€ํ•ด ์ „ํ˜€ ๋ชจ๋ฅด๋Š” ์ƒํ™ฉ์ด์—ˆ๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€์— ์žˆ์–ด์„œ๋Š” ๋ฐ”๋‹ฅ์—์„œ ์ถœ๋ฐœํ•œ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.
ย  ์ด๋ก  ๊ณต๋ถ€๋Š” ์•„๋ž˜ ์ฑ…์œผ๋กœ ์ง„ํ–‰ํ•˜์˜€์Šต๋‹ˆ๋‹ค!!

Do it! ์ž๋ฃŒ๊ตฌ์กฐ์™€ ํ•จ๊ป˜ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋ฌธ: ํŒŒ์ด์ฌ ํŽธ:๋‚ด ์†์œผ๋กœ ์ง์ ‘ ์ฝ”๋”ฉํ•˜๋ฉฐ ํ™•์ธํ•œ๋‹ค

์•„๋ž˜ ํŒŒํŠธ๋Š” ์ฑ…์˜ ํŒŒํŠธ๊ฐ€ ์•„๋‹Œ ์ •๊ธ€์—์„œ ๋‚˜๋ˆ ์ฃผ์‹  ํŒŒํŠธ์ž…๋‹ˆ๋‹ค.

Part 1. ๋“ฑ๊ต์ค€๋น„๋Š” ์ฐจ๊ทผ์ฐจ๊ทผ.๐Ÿ‹๐Ÿ‹

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ :
๋ฐฐ์—ด, ๋ฌธ์ž์—ด, ๋ฐ˜๋ณต๋ฌธ๊ณผ ์žฌ๊ท€ํ•จ์ˆ˜, ๊ณ„์‚ฐ๋ณต์žก๋„, ์ •๋ ฌ, ์™„์ „ํƒ์ƒ‰, ์ •์ˆ˜๋ก 

์ถ”์ฒœ : ๋‚ด๊ฐ€ ํ˜„์žฌ ์‚ฌ์šฉํ•˜๋Š” ์–ธ์–ด(์˜ˆ๋ฅผ ๋“ค์–ด, Python, C ๋“ฑ)์˜ ๊ธฐ๋ณธ์ ์ธ ์ž…์ถœ๋ ฅ ๋ฐฉ์‹์„ ๋ชจ๋ฅธ๋‹ค๊ฑฐ๋‚˜, ์ž๋ฃŒํ˜•, ์ •๋ ฌ ๋ฐฉ์‹ ๋“ฑ์„ ์ •ํ™•ํžˆ ์•Œ์ง€ ๋ชป ํ•œ๋‹ค๋ฉด ๋ฐ˜๋“œ์‹œ ์ตํžˆ๊ณ  ๋„˜์–ด๊ฐ€์•ผํ•  ํŒŒํŠธ.

๋ฌธ์ œ๋ฒˆํ˜ธ์ฃผ์ œ๋ฌธ์ œ์ œ๋ชฉ๊ณต๋ถ€ํฌ์ธํŠธ
2557์ž…์ถœ๋ ฅHello World์ผ๋‹จ ๋งž์œผ๋ฉด ๊ธฐ๋ถ„ ์ข‹์Œ
10869์ž…์ถœ๋ ฅ์‚ฌ์น™์—ฐ์‚ฐ/, //์˜ ์ฐจ์ด๋Š”?
2588์ž…์ถœ๋ ฅ๊ณฑ์…ˆ์ž๋ฃŒํ˜•, ์ž๋ฆฟ์ˆ˜๋ณ„ ์ถœ๋ ฅ
2753์กฐ๊ฑด๋ฌธ์œค๋…„if else
10871๋ฐ˜๋ณต๋ฌธX๋ณด๋‹ค ์ž‘์€ ์ˆ˜๋ฐ˜๋ณต๋ฌธ(end์™€sep์€ ๋ค)
8958๋ฐฐ์—ดOXํ€ด์ฆˆ์ธ๋ฑ์Šค , ์ด์ค‘for๋ฌธ
4344๋ฐฐ์—ดํ‰๊ท ์€๋„˜๊ฒ ์ง€์†Œ์ˆ˜์  ์ถœ๋ ฅ
11654๋ฌธ์ž์—ด์•„์Šคํ‚ค ์ฝ”๋“œ์•„์Šคํ‚ค ์ฝ”๋“œ๋Š” ๋“ ๋“ ํ•œ ๊ตญ๋ฐฅ
1152๋ฌธ์ž์—ด๋‹จ์–ด์˜ ๊ฐœ์ˆ˜split, remove
2869์ˆ˜ํ•™๋‹ฌํŒฝ์ด๋Š” ์˜ฌ๋ผ๊ฐ€๊ณ ์‹ถ๋‹ค๋‚˜๋Š” ์ง‘ ๊ฐ€๊ณ  ์‹ถ๋‹ค(import math)
1978์ˆ˜ํ•™์†Œ์ˆ˜ ์ฐพ๊ธฐ์ปดํ“จํŒ… ์‚ฌ๊ณ 
10872์žฌ๊ท€ํ•จ์ˆ˜ํŒฉํ† ๋ฆฌ์–ผ๊ณตํฌ์˜ ์žฌ๊ท€ ์‹œ์ž‘
1914์žฌ๊ท€ํ•จ์ˆ˜ํ•˜๋…ธ์ด ํƒ‘print๋ฅผ ์–ด๋””์— ๋‘˜๊นŒ?
9663์žฌ๊ท€ํ•จ์ˆ˜N-Queen๋ฐฉ๋ฌธํ•œ ์ง€์—ญ ์ฒดํฌ, ์žฌ๊ท€
2750์ •๋ ฌ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ๋ญ์•ผ ์‰ฝ๋„ค(์ง€์˜ฅ์˜ 3์—ฐ๋ฒ™ ์‹œ์ž‘)
2751์ •๋ ฌ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ2์–ด? ์‹œ๊ฐ„์ดˆ๊ณผ?(sys.stdin.readline)
10989์ •๋ ฌ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ3์–ด? ๋ฉ”๋ชจ๋ฆฌ์ดˆ๊ณผ?(๋„์ˆ˜์ •๋ ฌ)
1181์ •๋ ฌ๋‹จ์–ด ์ •๋ ฌ๊ธ€์ž ํฌ๊ธฐ ์ˆœ ์ •๋ ฌ, ์ค‘๋ณต์ œ๊ฑฐ
2390์™„์ „ํƒ์ƒ‰์ผ๊ณฑ ๋‚œ์Ÿ์ดpermutation, combination
10819์™„์ „ํƒ์ƒ‰์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœmax, abs, itertools ์ข…ํ•ฉ์„ ๋ฌผ์…‹ํŠธ

ย  ํŒŒํŠธ1 ์ค‘ ๋‚˜๋ฅผ ๊ฐ€์žฅ ๊ณจ์น˜ ์•„ํ”„๊ฒŒ ํ•œ ์นœ๊ตฌ๋Š” ๋‹ค๋ฆ„ ์•„๋‹Œ ์žฌ๊ท€(recursion).. ํŒŒํŠธ1 ํŠน์„ฑ์ƒ ์—ฌ๊ธฐ ๋‚˜์˜จ ๊ฐœ๋…์ด๋‚˜ ํ’€์ด ๋ฐฉ์‹์€ ํŒŒํŠธ4๊นŒ์ง€ ์ญˆ์šฑ ์ด์–ด์ง€๋Š”๋ฐ ์žฌ๊ท€๋Š” ์•„๋ฌด๋ฆฌ ์ ‘ํ•ด๋„ ์‰ฝ์ง€๊ฐ€ ์•Š์•˜๋‹ค. ๊ทธ๋ž˜๋„ ํŒŒํŠธ4๊นŒ์ง€ ๊ณต๋ถ€๋ฅผ ๋งˆ์น˜๊ณ  ๋‹ค์‹œ ๋Œ์•„์™€์„œ ํ’€์–ด๋ณด๋‹ˆ ์ƒˆ๋กœ์šด ๋Š๋‚Œ์ด์—ˆ๋‹ค. ํŠนํžˆ, N-Queen์„ ์ฒ˜์Œ ํ’€ ๋•Œ๋งŒ ํ•ด๋„ DFS๋ฅผ ๋ชจ๋ฅด๋‹ค๋ณด๋‹ˆ๊นŒ ๋„ˆ๋ฌด ์–ด๋ ค์› ๋Š”๋ฐ DFS๋ฅผ ํ•™์Šตํ•˜๊ณ  ์™€์„œ ๋‹ค์‹œ ๋ณด๋‹ˆ ์ด๋Ÿฐ ๊ฑฐ์˜€๊ตฌ๋‚˜!! ํ•˜๊ฒŒ ๋˜๋Š” ๊ทธ๋Ÿฐ ์ฆ๊ฑฐ์›€์ด ์žˆ๋‹ค.

Part 2. ์—„๋งˆ ๋‚ด ๊ต๋ณต๋ฐ”์ง€ ์–ด๋”จ์–ด?๐Ÿค”๐Ÿค”

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ :
์ด๋ถ„ํƒ์ƒ‰, ๋ถ„ํ• ์ •๋ณต, ์Šคํƒ, ํ, ์šฐ์„ ์ˆœ์œ„ ํ

ย ์ถ”์ฒœ : ๋‚ด๊ฐ€ ์„ค๊ณ„ํ•œ ๋…ผ๋ฆฌ๋Š” ๋งž์œผ๋‚˜, ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š”๋ฐ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋งŽ์ด ๋‚œ๋‹ค๋ฉด ๊ผญ ์ตํ˜€์•ผ ํ•  ํŒŒํŠธ. ์ปดํ“จํŒ… ์‚ฌ๊ณ ๋กœ์˜ ์ „ํ™˜์—์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•œ ํŒŒํŠธ๊ฐ€ ์•„๋‹Œ๊ฐ€ ์‹ถ์Œ. ์‹œ๊ฐ„๋ณต์žก๋„(time complexity)๋ฅผ ๋”ฐ์ง€์ง€ ์•Š๊ณ  ์ฝ”๋“œ๋ฅผ ์งœ๋Š” ๊ฑด ์ปดํ“จํ„ฐ๊ณผํ•™์—์„œ ์ง€์–‘๋˜์–ด์•ผ ํ•  ๋ฐฉํ–ฅ์ž„์„ ์ ˆ์‹คํžˆ ํ™•์ธ.

๋ฌธ์ œ๋ฒˆํ˜ธ์ฃผ์ œ๋ฌธ์ œ์ œ๋ชฉ๊ณต๋ถ€ํฌ์ธํŠธ
2805์ด๋ถ„ํƒ์ƒ‰๋‚˜๋ฌด ์ž๋ฅด๊ธฐ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ ํ›„, start, end๊ฐ’์œผ๋กœ mid๋ฅผ ์ฐพ์ž
2110์ด๋ถ„ํƒ์ƒ‰๊ณต์œ ๊ธฐ ์„ค์น˜์ฝ”๋“œ๊ฐ€ ์ง„ํ–‰๋˜๋Š” ๊ณผ์ •์„ ์™„๋ฒฝํžˆ ์ดํ•ดํ•ด์•ผ ํ’€ ์ˆ˜ ์žˆ์Œ
16564์ด๋ถ„ํƒ์ƒ‰ํžˆ์˜ค์Šค ํ”„๋กœ๊ฒŒ์ด๋จธstart, end๋ฅผ ๋ญ๋กœ ์žก์„๋ž˜?
1629๋ถ„ํ• ์ •๋ณต๊ณฑ์…ˆ๋ถ„ํ• ์ •๋ณต์€ ์žฌ๊ท€๊ฐ€ ํ•„์ˆ˜, ๋‚˜๋จธ์ง€๋ถ„๋ฐฐ์—ฐ์‚ฐ๋ฒ•์น™
2630๋ถ„ํ• ์ •๋ณต์ƒ‰์ข…์ด ๋งŒ๋“ค๊ธฐ์–ด๋””๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚˜๋ˆŒ ์ง€ ๋ณด์ด๋‚˜์š”?
2261๋ถ„ํ• ์ •๋ณต๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋‘์ ๋…ผ๋ฆฌ๊ตฌ์กฐ ์งœ๊ธฐ๊ฐ€ ๊นŒ๋‹ค๋กญ์ง€๋งŒ ์งœ๊ณ  ๋ณด๋ฉด ์‰ฌ์šด.
10828์Šคํƒ์ŠคํƒLast In First Out
9012์Šคํƒ๊ด„ํ˜ธ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  ์Šคํƒ์„ ๋ชป ๋– ์˜ฌ๋ฆฐ๋‹ค๋ฉด..?
2504์Šคํƒ๊ด„ํ˜ธ์˜ ๊ฐ’์ปดํ“จํŒ… ์‚ฌ๊ณ  ์ „ํ™˜์ด ํ•„์š”ํ•ด
2493์Šคํƒํƒ‘์‹œ๊ฐ„ ๋นŒ๊ฒŒ์ด์ธ ๋„ ํฌ๊ธฐํ•œ ๋‚ด ํ’€์ด(์™„์ „ํƒ์ƒ‰)
2164ํ์นด๋“œ2popleft()๋Š” ์ผ๋‹จ ์“ฐ๋ฉด ํŠ€์–ด๋‚˜๊ฐ
11866ํ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ 0deque๋ฅผ ํ™œ์šฉํ•œ ์ปดํ“จํŒ… ์‚ฌ๊ณ 
3190ํ๋ฑ€๋ฐฉํ–ฅ ๋ฌธ์ œ, bfs๋ฅผ ์•Œ๊ณ ๋‚˜๋‹ˆ ๋‹ค๋ฅธ ๋ฌธ์ œ๋กœ ๋ณด์ธ๋‹ค!
11279์šฐ์„ ์ˆœ์œ„ ํ์ตœ๋Œ€ ํž™heappop์€ ๊ฐ’์ด ๊ฐ€์žฅ ๋‚ฎ์€ ๊ฑธ ๋ฑ‰๋Š”๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด?
1655์šฐ์„ ์ˆœ์œ„ ํ๊ฐ€์šด๋ฐ๋ฅผ ๋งํ•ด์š”๊ฐ€์šด๋ฐ๋ฅผ ๋งํ•˜๋Š” tree๊ฐ€ ์žˆ๋‹ค?
13334์šฐ์„ ์ˆœ์œ„ ํ์ฒ ๋กœ์ •๋ ฌ๋งŒ ์ž˜ ํ•œ๋‹ค๋ฉด ์‰ฌ์šด ๋ฌธ์ œ.

ย  ํŒŒํŠธ2์˜ ํ•ต์‹ฌ์€, binary search, divide and conquer ๋“ฑ์„ ์ž˜ ํ™œ์šฉํ•˜์—ฌ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋‚ฎ์ถ”๋Š” ๊ฑฐ ๊ฐ™๋‹ค. ์ฒ˜์Œ ๊ณต๋ถ€ํ•  ๋•Œ๋Š” ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๋ญ”์ง€ ๋ชฐ๋ผ์„œ ๊ณ ์ƒํ–ˆ๋‹ค. ๋ถ„๋ช… ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ๋‹ต์ด ๋‚˜์˜ค๊ณ  ๋‚ด ๋น„์ฃผ์–ผ ์ŠคํŠœ๋””์˜ค์—์„œ๋„ ์˜ฌ๋ฐ”๋ฅธ ๋‹ต์ด ์ถœ๋ ฅ๋˜๋Š”๋ฐ ์ œ์ถœ๋งŒ ํ•˜๋ฉด ์‹œ๊ฐ„์ดˆ๊ณผ๋ž€๋‹ค. ์ด์ œ๋Š” ๋ฌธ์ œ๋ฅผ ๋ฐ›์œผ๋ฉด, n, m ๊ฐ’์˜ ๋ฒ”์œ„๋ถ€ํ„ฐ ํ™•์ธํ•˜๊ฒŒ ๋œ๋‹ค. ๋ฌผ๋ก  ๊ทธ๋ ‡๋‹ค๊ณ  ํ•˜์—ฌ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์ •๋ฐ€ํžˆ ๊ณ„์‚ฐํ•˜๋Š” ๊ฑด ์•„๋‹ˆ์ง€๋งŒ, ๋Œ€์ถฉ ์™„์ „ํƒ์ƒ‰์„ ํ•˜๋ฉด ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋œจ๊ฒ ๊ตฌ๋‚˜ ์ •๋„๋Š” ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ปดํ“จํ„ฐ์—๊ฒŒ ๋„˜๊ฒจ์ค„ ๋•Œ ๋ถˆํ•„์š”ํ•œ ๋ถ€๋ถ„์€ ์ณ๋‚ด๊ณ  ๋‚ด๊ฐ€ ์›ํ•˜๋Š” ๋‹ต์„ ๋น ๋ฅด๊ฒŒ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ๊ทธ๋Ÿฐ ์ด์œ ์ฝ”๋“œ๋ฅผ ์งค ์ˆ˜ ์žˆ๋„๋ก ์—ด์‹ฌํžˆ ๊ณต๋ถ€ํ•ด๋ณด์ž!

Part 3. ๊ทธ๋ž˜ํ”„๐Ÿ”„๋ฅผ ๋ชจ๋ฅด๋ฉด ๋„ˆ๋Š” ๊ฐˆ ์ˆ˜ ์—†๋‹ค๐Ÿ”™

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ :
๊ทธ๋ž˜ํ”„(vertex, edge, node, arc), BFS, DFS, ์œ„์ƒ์ •๋ ฌ

์ถ”์ฒœ : ์ฃผ์–ด์ง€๋Š” ๋ฐ์ดํ„ฐ ๊ฐ„์˜ ๊ด€๊ณ„๊ฐ€ ๋ณด์ธ๋‹ค๋ฉด, ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ๋…ธ๋“œ ๊ฐ„ ์—ฐ๊ฒฐ์„ ๋‹ค ํ–ˆ๋Š”๋ฐ ๊ทธ ๋‹ค์Œ์„ ๋ชจ๋ฅด๊ฒ ๋‹ค๋ฉด ๋ฐ˜๋“œ์‹œ ์ตํ˜€์•ผ ํ•  ํŒŒํŠธ.

๋ฌธ์ œ๋ฒˆํ˜ธ์ฃผ์ œ๋ฌธ์ œ์ œ๋ชฉ๊ณต๋ถ€ํฌ์ธํŠธ
1991๊ทธ๋ž˜ํ”„ํƒ์ƒ‰๊ธฐ๋ณธํŠธ๋ฆฌ์ˆœํšŒ์ „์œ„์ˆœํšŒ, ์ค‘์œ„์ˆœํšŒ, ํ›„์œ„์ˆœํšŒ
1260๊ทธ๋ž˜ํ”„ํƒ์ƒ‰๊ธฐ๋ณธDFS์™€ BFSDFS์™€ BFS๋ฅผ ๋ฐฐ์šฐ๊ณ  ์‹ถ๋‹ค๋ฉด ์ด๊ฑธ ๊ผญ ๋จผ์ €
5639๊ทธ๋ž˜ํ”„ํƒ์ƒ‰๊ธฐ๋ณธ์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ์ด์ง„ํƒ์ƒ‰์„ ์ƒํ™œํ™”ํ•ฉ์‹œ๋‹ค!
1197๊ทธ๋ž˜ํ”„ํƒ์ƒ‰๊ธฐ๋ณธ์ตœ์†Œ์ŠคํŒจ๋‹ํŠธ๋ฆฌKruskal, Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜
11725DFSํŠธ๋ฆฌ์˜ ๋ถ€๋ชจ์ฐพ๊ธฐ์žฌ๊ท€ ๊ตฌ์กฐ๋ฅผ ์™„๋ฒฝํžˆ ์ดํ•ดํ–ˆ๋‹ค๋ฉด ์‰ฌ์›€
1707DFS์ด๋ถ„ ๊ทธ๋ž˜ํ”„-+-+-+๊ฐ€ ํ•ต์‹ฌ
21606DFS์•„์นจ ์‚ฐ์ฑ…DFS๊ฐ€ ์–ด๋–ค ๊ฐ’์„ returnํ•˜๋Š” ์ง€๊ฐ€ ํฌ์ธํŠธ
14888DFS์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐDFS๋Š” ์žฌ๊ท€๋‹ค!(์กฐํ•ฉํ’€์ด๋ž‘ ์‹œ๊ฐ„ ๋น„๊ต)
2573DFS๋น™์‚ฐ๋ถ„ํ• ์ •๋ณต, DFS, ๋ฐฉํ–ฅ ์‚ผ์œ„์ผ์ฒด
2178BFS๋ฏธ๋กœ ํƒ์ƒ‰BFS๋Š” deque์„ ์“ฐ๋ฉด ํŽธ๋ฆฌํ•ด
18352BFSํŠน์ •๊ฑฐ๋ฆฌ์˜๋„์‹œ์ฐพ๊ธฐ์ด ๋•Œ๋Š” ๋ชฐ๋ž์ง€ BFS+DP๋ผ๋Š” ๊ฑธ
1916BFS์ตœ์†Œ๋น„์šฉ๊ตฌํ•˜๊ธฐ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜(heapq๋งŒ ์ผ์„ ๋ฟ์ธ๋ฐ!)
7569BFSํ† ๋งˆํ† 3์ฐจ์› BFS
3055BFSํƒˆ์ถœBFS๊ฐ€ ๋™์‹œ์— 2๊ฐœ๊ฐ€ ๋ˆ๋‹ค๋ฉด?
2252์œ„์ƒ์ •๋ ฌ์ค„์„ธ์šฐ๊ธฐ์ง„์ž…์ฐจ์ˆ˜๊ฐ€ 0์ธ ๋…ธ๋“œ๋ถ€ํ„ฐ ์‹œ์ž‘
2637์œ„์ƒ์ •๋ ฌ์žฅ๋‚œ๊ฐ์กฐ๋ฆฝ์œ„์ƒ์ •๋ ฌ ๊ตฌ์กฐ ์žก๊ธฐ ์ข‹์€ ๋ฌธ์ œ

ย  ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€์— ์žฌ๋ฏธ๋ฅผ ๋Š๋ผ๊ธฐ ์‹œ์ž‘ํ•œ ํŒŒํŠธ. ๋ฌธ์ œ๋Š” ์ด์ „ ํŒŒํŠธ๋“ค์— ๋น„ํ•ด ์–ด๋ ค์›Œ ์ง์ ‘ ํ’€์ง€ ๋ชป ํ•œ ๋ฌธ์ œ๊ฐ€ ๋งŽ์ง€๋งŒ, DFS์™€ BFS ๋ฐฉ์‹์— ๋Œ€ํ•œ ๊ธฐ์ดˆ๊ฐ€ ์žกํžˆ๊ณ  ๋‚˜๋‹ˆ ๋‹ค๋ฅธ ์‚ฌ๋žŒ์ด ์ž‘์„ฑํ•œ ์ฝ”๋“œ๋ฅผ ๋ด๋„ ์ดํ•ดํ•˜๊ธฐ ์ˆ˜์›”ํ•˜์˜€๋‹ค. ํŒŒํŠธ3๋ถ€ํ„ฐ ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ฒƒ๋ณด๋‹ค ์ด์ „์— ๋ฐฐ์› ๋˜ ๊ฒƒ์„ ํ™œ์šฉํ•˜๋ฉด ์‹œ๊ฐ„์„ ๋‹จ์ถ•ํ•˜๊ธฐ๊ฐ€ ์ข‹์•˜๋‹ค. ์—ฌ๋‹ด์œผ๋กœ ์ด์ง„๊ฒ€์ƒ‰ํŠธ๋ฆฌ(5639)๋ฅผ ํ’€ ๋•Œ, ์ค‘๊ฐ„ mid๊ฐ’์„ ์ฐพ๋Š” ๊ณผ์ •์ด ๋‚˜์˜ค๋Š”๋ฐ ๋‚˜๋Š” ์™„์ „ํƒ์ƒ‰์„ ํ†ตํ•ด mid๊ฐ’์„ ์ฐพ์•˜๋”๋‹ˆ ์‹œ๊ฐ„โฐ์ด 3700ms์ด๋‚˜ ๋‚˜์˜จ ๋ฐ˜๋ฉด, ์ด์ง„ํƒ์ƒ‰์„ ์ˆ˜ํ–‰ํ•œ ์ฝ”๋“œ๋Š” 100ms๋ฐ–์— ๋‚˜์˜ค์ง€ ์•Š์•˜๋‹ค. ์‹œ๊ฐ„์„ ์ค„์ผ ์š”์†Œ๊ฐ€ ๋ณด์ธ๋‹ค๋ฉด ์ตœ๋Œ€ํ•œ ์ค„์—ฌ๋ณด์ž!!

Part 4. ํ•˜๊ต ํ›„ ๋ถ„์‹์ง‘. ๋ญ˜ ๋จน์–ด์•ผ ์ œ์ผ ํ–‰๋ณตํ• ๊นŒ?๐Ÿ˜‹๐Ÿฅ˜๐Ÿ˜‹

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ :
๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ(DP), ๊ทธ๋ฆฌ๋””

์ถ”์ฒœ : ์žฌ๊ท€, ๋ถ„ํ• ์ •๋ณต์€ ์–ด๋Š ์ •๋„ ์ดํ•ดํ•˜๊ณ  ์žˆ์ง€๋งŒ ํ’€์ด ์ƒ ์‹œ๊ฐ„์ดˆ๊ณผ ํ˜น์€ ๋ฉ”๋ชจ๋ฆฌ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค๋ฉด ๊ณต๋ถ€ํ•˜๊ธฐ ์ข‹์€ ํŒŒํŠธ. ํŠนํžˆ, ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋ฉด ๋Œ€๋ถ€๋ถ„ ์•ž์„œ ๋ฐœ์ƒํ•œ ๋ฌธ์ œ๊ฐ€ ํ•ด๊ฒฐ๋  ์ˆ˜ ์žˆ์œผ๋‚˜ ์ ์žฌ์ ์†Œ์— ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด 'ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค'๋ฅผ ๋งž์ดํ•  ์ˆ˜ ์žˆ์œผ๋‹ˆ ์ฃผ์˜!

๋ฌธ์ œ๋ฒˆํ˜ธ์ฃผ์ œ๋ฌธ์ œ์ œ๋ชฉ๊ณต๋ถ€ํฌ์ธํŠธ
2748DPํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜2๋ฐ”ํ…€์—…, ํƒ‘๋‹ค์šด 2๊ฐ€์ง€ ๋ชจ๋‘ ํ•™์Šตํ•ด๋ณด์ž
1904DP01ํƒ€์ผ์ ํ™”์‹์„ ์ฐพ๋Š” ๊ฒŒ ์ค‘์š”ํ•˜๋‹ค!
9084DP๋™์ „DPํ…Œ์ด๋ธ” ๋งŒ๋“ค๊ธฐ, ์žฌ๊ท€ํ•ด ๊ตฌ์ƒํ•˜๊ธฐ
9251DPLCSDPํ…Œ์ด๋ธ” x์ถ•,y์ถ• ์žก๊ธฐ
12865DP์•„์ฃผ ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญKnapsack ์•Œ๊ณ ๋ฆฌ์ฆ˜(๊ตญ๋ฐฅ ๋ฌธ์ œ)
11053DP๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ ๋ คํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„
2098DP์™ธํŒ์› ์ˆœํšŒ๋น„ํŠธ๋งˆ์Šคํ‚น, ๋˜ ๋“ฑ์žฅํ•œ DFS+DP
2253DP์ ํ”„DP๋Š” ๋ชจ๋“  ํ…Œ์ด๋ธ”์„ ์ฑ„์›Œ์•ผํ•œ๋‹ค.
11047๊ทธ๋ฆฌ๋””๋™์ „ 0์•ž์„  ์„ ํƒ์ด ๋’ค์— ์˜ํ–ฅ์„ ์ฃผ๋ฉด ์•ˆ๋œ๋‹ค
1541๊ทธ๋ฆฌ๋””์žƒ์–ด๋ฒ„๋ฆฐ ๊ด„ํ˜ธํ’€์ด๋ฅผ ๋ณด๊ณ  ์ œ์ผ ์ถฉ๊ฒฉ๋ฐ›์€ ์ปดํ“จํŒ… ์‚ฌ๊ณ (Thinking)
1931๊ทธ๋ฆฌ๋””ํšŒ์˜์‹ค ๋ฐฐ์ •๊ทธ๋ฆฌ๋””๋Š” ์ •๋ ฌ์ด ํ•ต์‹ฌ
1700๊ทธ๋ฆฌ๋””๋ฉ€ํ‹ฐํƒญ ์Šค์ผ€์ค„๋ง๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‚ฌ์šฉ ํŒ๋‹จ ๊ทผ๊ฑฐ๋ฅผ ์ฐพ๊ธฐ

ย  DP์™€ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋‘ ์ฃผ์–ด์ง„ ์ƒํ™ฉ์ด ์ตœ์ ๋ถ€๋ถ„๊ตฌ์กฐ(Optimal substructure)๋ฅผ ๋งŒ์กฑํ•ด์•ผ ์‚ฌ์šฉ๊ฐ€๋Šฅํ•˜๋ฉฐ, ์žฌ๊ท€ํ•ด๋ฅผ ๊ฐ€์ ธ์•ผํ•œ๋‹ค. ์ตœ์ ๋ถ€๋ถ„๊ตฌ์กฐ๋ผ๋Š” ๋ง์ด ์‰ฝ๊ฒŒ ์™€๋‹ฟ์ง€ ์•Š์•˜์œผ๋‚˜, CLRS ์ฑ…์—์„œ LCS ๋ฌธ์ œ๋ฅผ ์นœ์ ˆํžˆ ์„ค๋ช…ํ•ด์ฃผ๋Š” ๋ถ€๋ถ„์ด ๋‚˜์˜ค๋Š”๋ฐ ๊ทธ ๋ถ€๋ถ„์„ ํ•™์Šตํ•˜๋ฉฐ ์ตœ์ ๋ถ€๋ถ„๊ตฌ์กฐ์— ๋Œ€ํ•ด ์ดํ•ดํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฒฝ์šฐ, ์•ž์˜ ์„ ํƒ์ด ์ดํ›„ ์„ ํƒ์— ์˜ํ–ฅ์„ ์ฃผ์ง€ ์•Š์•„์•ผํ•œ๋‹ค๋Š” ์กฐ๊ฑด์ด ๊นŒ๋‹ค๋กœ์› ๋‹ค.

ย  ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋งˆ์ง€๋ง‰ ํŒŒํŠธ๋ฅผ ํ•˜๋Š” ์ค‘์ธ๋ฐ๋„ ์—ฌ์ „ํžˆ ์ปดํ“จํŒ… ์‚ฌ๊ณ ๋กœ์˜ ์ „ํ™˜์€ ์‰ฝ์ง€ ์•Š์€ ๊ฒƒ ๊ฐ™๋‹ค. ์ •๊ธ€ ์šด์˜์ง„ ๋ถ„๋“ค๊ณผ ํ‹ฐํƒ€์ž„์„ ๊ฐ–๋Š” ์‹œ๊ฐ„์ด ์žˆ์–ด ํฌ๋ž˜ํ”„ํ†ค ์žฅ๋ณ‘๊ทœ ์˜์žฅ๋‹˜๊ป˜ ์งˆ๋ฌธ์„ ๋“œ๋ ธ๋‹ค. ์ปดํ“จํ„ฐ๋„ ๊ฒฐ๊ตญ ์ธ๊ฐ„์ด ์‚ฌ๊ณ ํ•œ ๊ฑธ ์ˆ˜ํ–‰ํ•˜๋Š” ๊ธฐ๊ณ„์ธ๋ฐ ๋น ๋ฅธ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๋ณด์ด๋Š” ์ฝ”๋“œ๋“ค์„ ๋ณด๋ฉด ์ „ํ˜€ ์ดํ•ด๊ฐ€ ๊ฐ€์ง€์•Š๋Š”๋ฐ ๊ทธ ์ฝ”๋“œ๋ฅผ ๋ณด๊ณ  ๊ณต๋ถ€ํ•˜๋Š”๊ฒŒ ๋งž๋Š” ์ง€ ์—ฌ์ญค๋ณด์•˜๋‹ค. ์–ด๋Š ์ •๋„ ๋‚˜๋Š” ๋‚ด๊ฐ€ ๋งž๋‹ค๋Š” ์ƒ๊ฐ์— ๋“œ๋ฆฐ ์งˆ๋ฌธ์ด์—ˆ์œผ๋‚˜ ์˜์žฅ๋‹˜์˜ ๋Œ€๋‹ต์€ ์ถฉ๊ฒฉ์ ์ด์—ˆ๋‹ค.

๊ทธ๊ฒŒ ์ปดํ“จํ„ฐ์— ์ ํ•ฉํ•œ ์ฝ”๋“œ์ด๋ฉฐ, ์ดํ•ด๊ฐ€ ๋˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๊ณต๋ถ€ํ•˜๋Š” ์ดˆ๊ธฐ์—๋Š” ๊ทธ ์ฝ”๋“œ๋ฅผ ํ†ต์งธ๋กœ ์™ธ์šฐ๋Š” ๊ฒŒ ํ•„์š”ํ•˜๋‹ค

1541 ๋ฌธ์ œ๊ฐ€ ๋”ฑ ์ข‹์€ ์˜ˆ์‹œ์ธ ๊ฑฐ ๊ฐ™๋‹ค. ๋‚˜์˜ ์‚ฌ๊ณ ๋กœ๋Š” int๋กœ ์ „ํ™˜ํ•˜์—ฌ ์•ž์—์„œ๋ถ€ํ„ฐ ์ฐจ๊ทผ์ฐจ๊ทผ ๊ณ„์‚ฐ์„ ํ•˜๋Š” ๊ฒŒ ๋งž๋‹ค๊ณ  ์ƒ๊ฐํ•˜์˜€๊ณ  ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ ธ์ง€๋งŒ 40์ค„์ด ๋„˜์–ด๊ฐ€๋Š” ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜์˜€๋‹ค. ๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์˜ ์ฝ”๋“œ๋ฅผ ๋ณด๋Š”๋ฐ, ๋‹จ 10์ค„๋„ ์•ˆ๋˜๋Š” ์ฝ”๋“œ๋กœ ๋„ˆ๋ฌด๋‚˜ ์‰ฝ๊ฒŒ ๋‹ต์„ ์ฐพ๋Š”๊ฒŒ ๋†€๋ผ์› ๋‹ค. ์ด๋Ÿฐ ๋ถ€๋ถ„๋“ค์ด ์•„์ง ๋งŽ์ด ๋ถ€์กฑํ•œ ๊ฑฐ ๊ฐ™์ง€๋งŒ ๋ฐฐ์šฐ๋Š” ์žฌ๋ฏธ๊ฐ€ ์žˆ์–ด ์•ž์œผ๋กœ ๋‹ฌ๋ ค๊ฐ€ ๋‚˜๋„ ๋ˆ„๊ตฐ๊ฐ€ ๊ฐํƒ„ํ•  ์ˆ˜ ์žˆ๋Š” ๊ทธ๋Ÿฐ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜๊ณ ์‹ถ๋‹ค.

profile
์•ˆ๋…•ํ•˜์„ธ์š”. Moon์ž…๋‹ˆ๋‹ค!
post-custom-banner

22๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2022๋…„ 10์›” 23์ผ

์ •๋ฆฌ๊ฐ€ ์•„์ฃผ ๊ตฟ์ž…๋‹ˆ๋‹ค :)

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 25์ผ

ํ•™์Šต์ค‘์ธ ์–ธ์–ด๊ฐ€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ•์˜๊ฐ€ ์žˆ๋Š” ์–ธ์–ด๊ฐ€ ์•„๋‹ˆ๋ผ์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€ ์ˆœ์„œ๋ฅผ ์ฐพ๊ณ  ์žˆ์—ˆ๋Š”๋ฐ, ๋ฐฑ์ค€ ๋ฌธ์ œ๋ž‘ ๊ฐ™์ด ์ •๋ฆฌ ํ•ด์ฃผ์‹ ๊ฒŒ ๋งค์šฐ ๋„์›€์ด ๋์Šต๋‹ˆ๋‹ค! ๊ฐ์‚ฌํ•ฉ๋‹ˆ๋‹ค!

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 26์ผ

์ •๋ง ๊ฐ์‚ฌํ•ฉ๋‹ˆ๋‹ค ํ•ญ์ƒ ์ˆœ์„œ์— ์žˆ์–ด์„œ ๊ณ ๋ฏผํ•˜๊ณ  ์žˆ์—ˆ๋Š”๋ฐ ์ €์˜ ๊ณ ๋ฏผ์— ๋”ฑ ๋งž๋Š” ๊ธ€์ด๋„ค์š” ํ–‰๋ณตํ•œ ํ•˜๋ฃจ ๋˜์„ธ์š”

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 26์ผ

์ด์•ผ ์ •๋ฆฌ ๊ตฟ

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 27์ผ

๋งจ ์ฒซ๋ฒˆ์งธ ๋ฐฑ์ค€ ๋งํฌ์ธ HelloWorld๊ฐ€ ์ž˜๋ชป๋˜์–ด 404 ์—๋Ÿฌ๋œน๋‹ˆ๋‹ค..

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 28์ผ

๊ฒŒ์‹œ๊ธ€ ์ž˜ ๋ณด๊ณ  ๊ฐ‘๋‹ˆ๋‹ค ;)

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 29์ผ

Your writing is really informative, especially because it's so meaningful and updated. Thanks for sharing this wonderful post!

Your writing is really great. Iโ€™m so glad I read it. It kept me hooked the whole way through.

Thanks for this information. I really appreciate the information that you have provided.

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 10์›” 30์ผ

์ •๋ฆฌ๋ฅผ ๋„ˆ๋ฌด ์ž˜ํ•ด๋‘์…จ๋„ค์š” ใ…Žใ…Ž ์ž˜๋ณด๊ณ  ๊ฐ‘๋‹ˆ๋‹ค

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 11์›” 2์ผ

๋ฒจํŠธ๋ Œ๋“œ ๋ณด๊ณ ์™”์Šต๋‹ˆ๋‹ค~~

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2022๋…„ 11์›” 18์ผ

๋ฌธ์ œ๋ฒˆํ˜ธ ๋ˆ„๋ฅด๋ฉด ๋ฐ”๋กœ ์ด๋™๋˜๋Š” ๋””ํ…Œ์ผ๊นŒ์ง€..... ๐Ÿ˜

1๊ฐœ์˜ ๋‹ต๊ธ€
comment-user-thumbnail
2024๋…„ 5์›” 2์ผ

์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€๋ฅผ ์–ด๋””์„œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์•ผ ๋ ์ง€ ๋ชฐ๋ž๋Š”๋ฐ ๋„˜ ๋„์›€๋ผ์š”. ์งฑ์ด์—์š”!

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ
comment-user-thumbnail
2024๋…„ 8์›” 5์ผ

์ตœ๊ณ ๊ทœ์„ฑ์•„ ๊ณ ๋งˆ์›Œ!

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ