ํŒŒ์ด์ฌ

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

6. Union Find(ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) : MST - 1

Union Find (ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) MST - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. MST ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋˜ ๋„์ค‘ ์ƒ๊ฐ๋‚˜์„œ ํฌ์ŠคํŒ… ํ•˜๊ฒŒ ๋๋‹ค. ๋งค์ฃผ ์ฃผ๋ง๋งˆ๋‹ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ์ •๋ฆฌ๋ฅผ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ ๊ณ„์† ์‹คํŒจํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค... ใ…Žใ…Ž;; ์˜ค๋Š˜ ๋‹ค๋ค„๋ณผ ์ฃผ์ œ๋Š” MST, ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๊ธฐ๋ณธ ๋ฒ ์ด์Šค์ธ Union Find์ด๋‹ค. ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์—๋Š” ๋Œ€ํ‘œ์ ์œผ๋กœ ํฌ๋ฃจ์Šค์นผ(Kruskal)๊ณผ ํ”„๋ฆผ(Prim) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค. Union FInd๋Š” ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ต์‹ฌ์ด๋ผ๊ณ  ๋งํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿผ Union Find๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณด์ž. Union Find๋Š” ๋ง ๊ทธ๋Œ€๋กœ Union, ์ง‘ํ•ฉ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ทธ๋ž˜ํ”„ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด๋“ค ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ์•Œ์•„๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ ์˜ˆ์‹œ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. www.acmicpc.net/problem/1260 1260๋ฒˆ: DFS์™€ BFS ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— DFS๋ฅผ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python] 10217. KCM Travel - GOLD โ… 

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. 10217๋ฒˆ: KCM Travel ๊ฐ๊ณ ์˜ ๋…ธ๋ ฅ ๋์— ์ฐฌ๋ฏผ์ด๋Š” 2014 Google Code Jam World Finals์— ์ง„์ถœํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ๊ตฌ๊ธ€์—์„œ ์˜จ ์ดˆ๋Œ€์žฅ์„ ๋ฐ›๊ณ  ๊ธฐ๋ปํ–ˆ๋˜ ๊ฒƒ๋„ ์ž ์‹œ, ์ฐฌ์ฐฌํžˆ ์ฝ์–ด๋ณด๋˜ ์ฐฌ๋ฏผ์ด๋Š” ์ค‘์š”ํ•œ ์‚ฌ์‹ค์„ ์•Œ์•„์ฐจ๋ ธ๋‹ค. ์ตœ๊ทผ์˜ ๋Œ€์„ธ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ ํŒŒ์ผ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ์ž์—ฐ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ์—๋Š” T๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ์ค„์—๋Š” ๊ณตํ•ญ์˜ ์ˆ˜ N (2 โ‰ค N โ‰ค 100), ์ด ์ง€์›๋น„์šฉ M (0 โ‰ค M โ‰ค 10,000), ํ‹ฐ์ผ“์ •๋ณด์˜ ์ˆ˜ K (0 โ‰ค K โ‰ค 10,000)๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ K๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ ํ‹ฐ์ผ“์˜ ์ถœ๋ฐœ๊ณตํ•ญ u, ๋„์ฐฉ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python / C++] 1956. ์šด๋™ - GOLD โ…ฃ

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. 1956๋ฒˆ: ์šด๋™ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 โ‰ค V โ‰ค 400, 0 โ‰ค E โ‰ค V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 โ‰ค V โ‰ค 400, 0 โ‰ค E โ‰ค V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. (a โ†’ b์ž„์— ์ฃผ์˜) ๊ฑฐ๋ฆฌ๋Š” 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. (a, b) ์Œ์ด ๊ฐ™์€ ๋„๋กœ๊ฐ€ ์—ฌ๋Ÿฌ ๋ฒˆ ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ์†Œ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„

www.acmicpc.net/problem/1707 1707๋ฒˆ: ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E(1โ‰คEโ‰ค200,000)๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ •์ ์—๋Š” 1๋ถ€ํ„ฐ V๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค. ์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ E๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.

www.acmicpc.net/problem/7562 7562๋ฒˆ: ๋‚˜์ดํŠธ์˜ ์ด๋™ ์ฒด์ŠคํŒ ์œ„์— ํ•œ ๋‚˜์ดํŠธ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์•„๋ž˜ ๊ทธ๋ฆผ์— ๋‚˜์™€์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ดํŠธ๋Š” ๋ช‡ ๋ฒˆ ์›€์ง์ด๋ฉด ์ด ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ์„ธ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์—๋Š” ์ฒด์ŠคํŒ์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด l(4 โ‰ค l โ‰ค 300)์ด ์ฃผ์–ด์ง„๋‹ค. ์ฒด์ŠคํŒ์˜ ํฌ๊ธฐ๋Š” l ร— l์ด๋‹ค. ์ฒด์ŠคํŒ์˜ ๊ฐ ์นธ์€ ๋‘ ์ˆ˜์˜ ์Œ {0, ..., l-1} ร— {0, ..., l-1}๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๋‘˜์งธ ์ค„๊ณผ ์…‹์งธ ์ค„์—๋Š” ๋‚˜์ดํŠธ๊ฐ€ ํ˜„์žฌ ์žˆ๋Š” ์นธ, ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ๊ฐ ํ…Œ..

โ›น๏ธ ๋ผ์ดํ”„/์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ

[์Šค์ฝ”ํŽ˜ 2021] Startup Coding Festival 2021 - 1์ฐจ ์˜ˆ์„  ๊ฒฐ๊ณผ

๋™์•„๋ฆฌ ํ†ก๋ฐฉ์— ๊ด€๋ จ ๊ณต์ง€๊ฐ€ ์˜ฌ๋ผ์™€์„œ ๋ฐฑ์ค€๋„ ์–ด๋Š์ •๋„ ํ’€์–ด๋ดค๊ฒ ๋‹ค ์‹ถ์–ด์„œ ์‹ค๋ ฅ์„ ํ…Œ์ŠคํŠธํ•  ๊ฒธ, ์นด์นด์˜ค ์ฝ”ํ…Œ ์ค€๋น„ํ•˜๋Š” ๊ฒธ ํ•ด์„œ ์Šค์ฝ”ํŽ˜์— ์ฐธ๊ฐ€ํ•˜๊ฒŒ ๋๋‹ค! ์Šค์ฝ”ํŽ˜ 2021, SCOFE 2021 ์Šคํƒ€ํŠธ์—… ๊ธฐ์—…๋“ค์ด ์ฃผ์ตœํ•˜๋Š” ์ฝ”๋”ฉํ…Œ์ŠคํŠธ์˜€๋‹ค! ์™“์ฑ , ์˜์นด, ์˜ค๋Š˜์˜ ์ง‘, ๋งˆ์ผ“์ปฌ๋ฆฌ, ๋ธŒ๋žœ๋””, ๋ฒˆ๊ฐœ์žฅํ„ฐ ๋‹ค๋“ค ํ•œ๋ฒˆ์”ฉ์€ ๋“ค์–ด๋ณธ ์ด๋ฆ„์ด๋ผ๊ณ  ์ƒ๊ฐํ•œ๋‹ค! ๋ฌธ์ œ๋งˆ๋‹ค ํŠน์ • ๊ธฐ์—…์ด ๋“ค์–ด๊ฐ€์žˆ์—ˆ๋˜๊ฑฐ๋ณด๋ฉด ๊ธฐ์—…๋ณ„๋กœ 1๋ฌธ์ œ์”ฉ ์ถœ์ œํ•œ ๊ฒƒ์œผ๋กœ ๋ณด์ธ๋‹ค. ์–ธ์–ด๋Š” ๋‚ด๊ฐ€ ์ œ์ผ ์ข‹์•„ํ•˜๋Š” ํŒŒ์ด์ฌ์œผ๋กœ ์ง„ํ–‰ํ–ˆ๋‹ค. ์ด ๋ฌธ์ œ 6๋ฌธ์ œ. ๋ฐฐ์ ์€ 20 / 20 / 20 / 20 / 30 / 30 ์œผ๋กœ ์ด์  140์ ์ด์˜€๋‹ค. ๋‚ด๊ฐ€ ํš๋“ํ•œ ์ ์ˆ˜๋Š” ๋Œ€๋žต 110์  ์ •๋„ ๋˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค. ๋ฌธ์ œ๋ณ„๋กœ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋ฅผ ๋ชจ๋‘ ํ†ต๊ณผํ•˜๋ฉด "๋งž์•˜์Šต๋‹ˆ๋‹ค" ๊ฐ€ ์ถœ๋ ฅ๋œ๋‹ค. ๋ฌธ์ œ๋‹น ํ™•์ธํ•  ์ˆ˜ ์žˆ๋Š” ํ…Œ์ŠคํŠธ ์ผ€..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 1904๋ฒˆ. 01ํƒ€์ผ

www.acmicpc.net/problem/1904 1904๋ฒˆ: 01ํƒ€์ผ ์ง€์›์ด์—๊ฒŒ 2์ง„ ์ˆ˜์—ด์„ ๊ฐ€๋ฅด์ณ ์ฃผ๊ธฐ ์œ„ํ•ด, ์ง€์›์ด ์•„๋ฒ„์ง€๋Š” ๊ทธ์—๊ฒŒ ํƒ€์ผ๋“ค์„ ์„ ๋ฌผํ•ด์ฃผ์…จ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด ๊ฐ๊ฐ์˜ ํƒ€์ผ๋“ค์€ 0 ๋˜๋Š” 1์ด ์“ฐ์—ฌ ์žˆ๋Š” ๋‚ฑ์žฅ์˜ ํƒ€์ผ๋“ค์ด๋‹ค. ์–ด๋Š ๋‚  ์ง“๊ถ‚์€ ๋™์ฃผ๊ฐ€ ์ง€์›์ด www.acmicpc.net ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000,000) ์ถœ๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ง€์›์ด๊ฐ€ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด๊ฐ€ N์ธ ๋ชจ๋“  2์ง„ ์ˆ˜์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ 15746์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์–ธ๋œป๋ณด๋ฉด ์–ด๋ ค์›Œ ๋ณด์ผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ํƒ€์ผ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜์—๋Š” ๊ทœ์น™์ด ์žˆ๋‹ค. N 1 2 3 4 5 6 7 2์ง„ ์ˆ˜์—ด์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜ 1 2 3 5 8 13 21 ํ”ผ๋ณด๋‚˜์น˜์™€ ๊ฐ™์€ ์ ํ™”์‹์„ ๊ฐ€์ง„๋‹ค. f(n) = f(n-..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 9184๋ฒˆ. ์‹ ๋‚˜๋Š” ํ•จ์ˆ˜ ์‹คํ–‰

www.acmicpc.net/problem/9184 9184๋ฒˆ: ์‹ ๋‚˜๋Š” ํ•จ์ˆ˜ ์‹คํ–‰ ์ž…๋ ฅ์€ ์„ธ ์ •์ˆ˜ a, b, c๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์€ -1 -1 -1๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, ์„ธ ์ •์ˆ˜๊ฐ€ ๋ชจ๋‘ -1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์„ ์ œ์™ธํ•˜๋ฉด ์—†๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์€ ์„ธ ์ •์ˆ˜ a, b, c๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์€ -1 -1 -1๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, ์„ธ ์ •์ˆ˜๊ฐ€ ๋ชจ๋‘ -1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์„ ์ œ์™ธํ•˜๋ฉด ์—†๋‹ค. ์ถœ๋ ฅ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๊ฐ๊ฐ์˜ a, b, c์— ๋Œ€ํ•ด์„œ, w(a, b, c)๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• dp๋ฅผ ํ™œ์šฉํ•œ๋‹ค. ํ•ด๊ฒฐ ๊ณผ์ • [0][0][0] ~ [20][20][20]์˜ 3์ฐจ์› ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜๊ณ  ๊ฐ ์กฐ๊ฑด๋ณ„๋กœ ๋‚˜๋ˆˆ๋‹ค. ํŠน์ • ๋ฒ”์œ„ ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 1003๋ฒˆ. ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜

www.acmicpc.net/problem/1003 1003๋ฒˆ: ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 40๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜ ๋˜๋Š” 0์ด๋‹ค. ์ถœ๋ ฅ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ํ”ผ๋ณด๋‚˜์น˜ ์žฌ๊ท€ ํ•จ์ˆ˜์— ๊ด€ํ•œ ๋ฌธ์ œ๋‹ค. 0๊ณผ 1์ด ํ˜ธ์ถœ๋˜๋Š” ํšŸ์ˆ˜ ์ž์ฒด๋„ ๊ทœ์น™์ด ์žˆ์Œ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. 0 1 2 3 4 5 6 7 0 1 0 1 1 2 3 5 8 1 0 1 1 2 3 5 8 13 ์œ„์™€ ๊ฐ™์ด ํ˜ธ์ถœ๋˜๋Š” ํšŸ์ˆ˜๋„ (n-2) + (n-1..

kodo_o
'ํŒŒ์ด์ฌ' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก