๋ถ๋ฅ ์ ์ฒด๋ณด๊ธฐ
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)
2021.07.18Spanning Tree Minimum Spanning Tree ๋ฅผ ์์ํ๊ธฐ ์ ์, Spanning Tree๊ฐ ๋ฌด์์ธ์ง ์ ๋ฆฌํด๋ณด์. Spanning Tree Condition ์ ์ฅํธ๋ฆฌ ๋ผ๊ณ ๋ ํ๋ ์คํจ๋ ํธ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ด ์ฑ๋ฆฝํด์ผํ๋ค. N๊ฐ์ ์ ์ ์ ๊ฐ์ง๋ ๊ทธ๋ํ์์ ์ต์ N-1 ๊ฐ์ ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ค. ๊ทธ๋ํ์ ๋ชจ๋ ์ ์ ์ ํฌํจํ๋ค. ๊ทธ๋ํ์ ๋ชจ๋ ์ ์ ์ ๊ฐ์ง๊ณ ์์ด์ผ ์ ์ฅํธ๋ฆฌ์ ์กฐ๊ฑด์ด ๋ง์กฑ๋๊ธฐ ๋๋ฌธ์, ๊ฐ์ ์ ๊ฐฏ์๋ ํญ์ N-1 ๊ฐ๊ฐ ๋ ์ ๋ฐ์ ์๊ณ , N-1๊ฐ์ ๊ฐ์ ๊ณผ N๊ฐ์ ์ ์ ์ผ๋ก ์ด๋ฃจ์ด์ง ๊ทธ๋ํ๋ ์ ์ฒด ๊ทธ๋ํ์ ๋ํ ์ฌ์ดํด์ด ์กด์ฌํ ์ ์๊ธฐ ๋๋ฌธ์ ํญ์ ํธ๋ฆฌ์ ํํ๊ฐ ๋๋ค. ๋ฐ๋ผ์ ์ฐ๋ฆฌ๊ฐ DFS๋ BFS ๋ก ํ์ํ๋ฉด ๊ฐ ์ ์ ๋ค์ ์ฐ๊ฒฐํ๊ฒ ๋๋ฉด ์์ฐ์ค๋ฝ๊ฒ Spanning Tree ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์๊ณ ๊ฒฝ๋ก(Critical Path)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์๊ณ ๊ฒฝ๋ก(Critical Path)
2021.07.18Critical Path (์๊ณ๊ฒฝ๋ก) ๋ฐฉํฅ ๊ทธ๋ํ๋ ์์์ ๋ ฌ์์ ๋ณด์๋ ๊ฒ ์ฒ๋ผ ์ด๋ค ์์๋ฅผ ํํํ๋ ๊ฒ์ด ๊ฐ๋ฅํ๋ค. Critical Path ๋ ๋ฐฉํฅ ๊ทธ๋ํ์์ ์ด๋ค ์ ์ ๊น์ง ๋๋ฌํ๋๋ฐ ๊ฐ์ฅ ์ค๋ ๊ฑธ๋ฆฌ๋ ๊ฒฝ๋ก๋ฅผ ์๋ฏธํ๋ค. ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๊ฒ์ด ๋ ์๋ฏธ์๊ฒ ๋๊ปด์ง ์๋ ์๊ฒ ์ง๋ง, ๊ฐ์ฅ ์ค๋๊ฑธ๋ฆฌ๋ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ค๋ฉด, ๊ฐ๋ฅํ ๋ชจ๋ ๊ฒฝ๋ก๊ฐ ํด๋น ๊ฒฝ๋ก์ ๊ฑฐ๋ฆฌ๋ ์๊ฐ ์ด๋ด๋ก ๋ง์น ์ ์๋ค๋ ๊ฒ์ ์๋ฏธํ๊ธฐ ๋๋ฌธ์ ์๋นํ ์๋ฏธ๊ฐ ์๋ค. Alogrithm Concepts ์ด ์๊ณ ๋ฆฌ์ฆ ์ ๋ต์์๋ DFS๊ฐ ์ฌ์ฉ๋๋ค. ์ฌ์ค์ Topological Sort์์ ์ฌ์ฉํ๋ ๊ฐ๋
์ด ๋ค์ ๋ฑ์ฅํ๋ค. Topological Sort ๋ฅผ ์ฌ์ฉํ๊ฒ๋๋ฉด ๊ฐ ์ ์ ๋ง๋ค ๊ฑธ๋ฆฌ๋ ์ต๋ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ ์๊ฒ ๋๋๋ฐ ์ด๋ฒ์๋ ๊ฐ ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ฐํ ์ฐ๊ฒฐ ์์(Strongly Connected Component)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ฐํ ์ฐ๊ฒฐ ์์(Strongly Connected Component)
2021.07.18Strongly Connected Component ๊ฐํ ์ฐ๊ฒฐ ์์(SCC) ๋ผ๊ณ ๋ ํ๋ Strongly Connected Component ๋ ๋ฐฉํฅ ๊ทธ๋ํ์์ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ด ์ฑ๋ฆฝํ๋ ์ ์ ๋ค์ ์งํฉ์ด๋ค. SCC ๋ด์ ์๋ ์ด๋ค ๋ ์ ์ ์ ๋ํ ๊ฒฝ๋ก๊ฐ ํญ์ ์กด์ฌํ๋ค. ์ฆ, ์ฌ์ดํด์ด ์กด์ฌํ๋ค. ์๋ก ๋ค๋ฅธ SCC์ ์ํ๋ ๋ ์ ์ ์ ์๋ก ์๋ฐฉํฅ์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์๋ค. ์ฆ, SCC ๊ฐ์๋ ์ฌ์ดํด์ด ์กด์ฌํ ์ ์๋ค. ์์ ๊ฐ์ ๊ทธ๋ํ์์ {A, B, C}, {C, D}, {F, G}, {H} ๋ค ๊ฐ์ Strongly Connected Component ๊ฐ ์๋ ๊ฒ์ ํ์ธํ ์ ์๋ค. Algorithm ๊ทธ๋ํ์์ Strongly Connected Graph๋ฅผ ์ฐพ๋ ๊ฒ์ ์ฐ๋ฆฌ๊ฐ ๋์ผ๋ก ํ๋ฒ์ ์ ์ ์๋ ๊ฒ๊ณผ๋ ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊น์ด ์ฐ์ ํ์(DFS)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊น์ด ์ฐ์ ํ์(DFS)
2021.07.18Depth First Search DFS๋ ๊ทธ๋ํ๋ฅผ ์ํํ๊ธฐ ์ํด ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ต์ผ๋ก, ํ ๋
ธ๋๋ก๋ถํฐ ์์ํด์ ์์๋
ธ๋๋ฅผ ๊ณ์ ๋ฐ๋ผ๊ฐ๋ฉฐ ๋ ์ด์ ์์๋
ธ๋๊ฐ ๋ํ๋์ง ์์ ๋๊น์ง ์งํํ๊ณ ๋ ์ด์ ์๋
๊ฐ ์์ ๋๋ ์๋ ๊ธธ์ ๋ค์ ๊ฑฐ์ฌ๋ฌ ์ฌ๋ผ๊ฐ๋ฉฐ ํ์ํ์ง ์์ ๋ค๋ฅธ ๋
ธ๋๋ค์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ์ํํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. Algorithm Steps DFS ๋ฅผ ์ ์ฉํ๊ธฐ ์ํ ๋ค์ํ ๋ฐฉ๋ฒ์ด ์์ง๋ง ๊ฐ์์์ ์๊ฐ๋ ๋ฐฉ๋ฒ์ ์๊น์ ํตํด ๊ฐ ๋
ธ๋์ ์ํ๋ฅผ ํํํ๊ณ , ํด๋น ๋
ธ๋๊ฐ ๋ฐ๊ฒฌ๋ ์๊ฐ(์ค์ ์๊ฐ์ ๊ธฐ๋กํ์ง ์๋๋ค), ํ์์ด ๋๋ ์๊ฐ์ ๊ธฐ๋กํ๋ ๋ฐฉ๋ฒ์ผ๋ก ๋
ธ๋๋ค์ ์ํํ๋ค. Node State DFS๊ฐ ํ์ํ ๊ฐ ๋
ธ๋ ํน์ vertex ๋ ๋ค์ ์ธ๊ฐ ์ค ํ๋์ ์๊น๋ก ์ํ๋ฅผ ๋ํ๋ธ๋ค. White : ์์ง ๋ฐ๊ฒฌ๋์ง..
์ค๋์ ๋ฐฐ์ #7
์ค๋์ ๋ฐฐ์ #7
2021.07.182021.07.17 ์ค๋์ ๋ฐฐ์ ์ค๋ ํ ์ผ. ์ค์ํํธ ๊ณต์๋ฌธ์๋ฅผ ํ ์ฅ ๋ฒ์ญํ๋ฉด์ ๊ณต๋ถํ๋ค. ์ค๋์ ์ฃผ์ ๋ Methods ํ๋ค๋ณด๋ ๋ญ๊ฐ ์ ์ฉ์ ๋ชปํ๊ณ ์ด๋์ ์ฃผ์๋ค์ ๊ฒ๋ง ์๊ฒ๋ ๊ฒ ๊ฐ์์ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ์๋ค. ํ๋ก๊ทธ๋๋จธ์ค์์ ๋ ๋ฒจ1 ๋ฌธ์ ๋ฅผ ํ์๊ณ 35๋ฌธ์ ๋ฅผ ํ์๋ค. ๋ธ๋ก๊ทธ๋ฅผ ์ด์ ํ๊ณ ์๋ค. ๊นํ ๋ธ๋ก๊ทธ๋ ๋ฐ๋ก ๊ด๋ฆฌํ ํ์๊ฐ ์์ ๊ฒ ๊ฐ์์ ํฐ์คํ ๋ฆฌ๋ก ์ค์ํ ๋ด์ฉ๋ค๋ง ๊ณจ๋ผ์ ์ด์ ํ ๊ณํ์ด๋ค. ์ค๋ ์๋ก ๋ฐ๊ฒฌํ ๊ฒ. ๋ฌธ์์ด์ ์ฒ๋ฆฌํ ๋๋ ๋ฐฐ์ด๋ก ๋ง๋ค์ด์ ์ฒ๋ฆฌํ๋๊ฒ ํจ์ฌ ์ฝ๋ค. ๋ฐฐ์ด์ ํน์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์์์ ๊ฐ์๋ฅผ ์
๋๋ filter๋ก ์ธ์ด์ฃผ๋ ๋ฐฉ๋ฒ๋ ์๋ค. map, filter, reduce๋ฅผ ์ฌ์ฉํ๋ฉด ์ฝ๋๊ฐ ์์ฒญ๋๊ฒ ๊ฐ๋จํด์ง๋ค. ์ค์ํํธ์ ํ๋ณํ์ ๋ฏธ์ณค๋ค. ๊ทธ๋ฅ ๋ง ๊ฐ๋ค๋ฃ์ด๋ ๋ณํ์ด ๋๋ค. ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋๋น ์ฐ์ ํ์(BFS)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋๋น ์ฐ์ ํ์(BFS)
2021.07.18Breadth-First Search ๋๋น ์ฐ์ ํ์์ผ๋ก๋ ๋ถ๋ฆฌ๋ BFS ์ญ์ ๊ทธ๋ํ๋ฅผ ํ์ํ๊ธฐ ์ํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. DFS๋ ํ ๋
ธ๋์ ๋ํด์ ์ ์ผ ๊น์ํ ์์น์ ์๋ ๋ ๋ฒจ๊น์ง ๋ด๋ ค๊ฐ ํ์ํ์ง๋ง BFS๋ ํ ๋ ๋ฒจ์ ์๋ ๋ชจ๋ ๋
ธ๋๋ฅผ ๋ค ํ์ํ๊ณ ๋ค์ ๋ ๋ฒจ๋ก ์ด๋ํ๋ ๋ฐฉ๋ฒ์ผ๋ก ํ์์ ์งํํ๋ค. BFS๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋๋ฐ ์ ์ฉํ๊ฒ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๊ณ queue ๋ฅผ ์ฌ์ฉํ์ฌ ๊ตฌํํ๋ค. Algorithm Steps Node State ์ด๋ฒ ๊ฐ์์์ ์ค๋ช
ํ BFS๋ ์๊น์ ํตํด์ ๊ฐ ๋
ธ๋์ ์ํ๋ฅผ ํํํ๊ฒ ๋๋ค. White : ์ฒ์ ๋ฐ๊ฒฌ๋ ๋
ธ๋ Gray : ๋ฐ๊ฒฌ์ ๋์์ง๋ง ์์ง ํด๋น ๋
ธ๋์ ์ด์๋
ธ๋๋ค์ด ๋ชจ๋ ํ์๋์ง๋ ์์ ๋
ธ๋ Black : ํด๋น ๋
ธ๋์ ์ด์๋
ธ๋๋ค์ด ๋ชจ๋ ๋ฐฉ๋ฌธ๋ ๋
ธ๋ Distance ๊ฐ ๋ ๋ฒจ..
[Swift] ๋ฌธ์์ด์ ์ซ์๋ง ์๋์ง ํ์ธํ๊ธฐ
[Swift] ๋ฌธ์์ด์ ์ซ์๋ง ์๋์ง ํ์ธํ๊ธฐ
2021.07.18๋ฐฉ๋ฒ 1: Int ๋ก ํ๋ณํ ํ๊ธฐ ๋ฌธ์๋ฅผ ํ๋์ฉ ๋ฝ์์ isLetter ํ๋กํผํฐ๋ก ํ์ธํ ์๋ ์์ง๋ง, ๊ฐ์ฅ ์ฌ์ด ๋ฐฉ๋ฒ์ Int ๋ก ํ๋ณํ์ ์๋ํด๋ณด๋ ๊ฒ์ด๋ค. ๋ฌธ์์ด์ ์ซ์๋ง ์กด์ฌํ๋ค๋ฉด ๋ฌธ์์ด์ด ์ ์์ ์ผ๋ก ์ ์๋ก ๋ณํ๋๊ณ , ์๋๋ผ๋ฉด nil์ด ๋ฐํ๋๋ค. let str = "1234" if let convertedNum = Int(str) { print("\(convertedNum): \(type(of: convertedNum))") } else { print("Cannot convert string into number") } // Prints: "1234: Int" ๋ฐฉ๋ฒ 2: allSatisfy ๋ฉ์๋ ์ฌ์ฉํ๊ธฐ ๋ฌธ์์ด์๋ allSatisfy ๋ฉ์๋๊ฐ ์๋ค. ๋ฉ์๋์ ์ธ์๋ก ๋ฌธ์๋ฅผ ๊ฒ์ฌํ ํด๋ก์ ๋ฅผ ์ฃผ๋ฉด ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem)
2021.07.17Knapsack Problem Knapsack Problem, ๋ฐฐ๋ญ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์์ ๋งค์ฐ ์ ๋ช
ํ ๋ฌธ์ ์ด๋ค. ์ด๋ค ๋ฐฐ๋ญ์ด ์๊ณ ๊ทธ ๋ฐฐ๋ญ์์ ๋ฃ์ ์ ์๋ ์ต๋ ๋ฌด๊ฒ๊ฐ K๋ผ๊ณ ํ์. ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ N๊ฐ์ ๋ฌผ๊ฑด์ด ๊ฐ๊ธฐ ๋ค๋ฅธ ๊ฐ์น V๋ฅผ ๊ฐ์ง๊ณ ์๊ณ ๊ฐ ๋ฌผ๊ฑด๋ง๋ค ๋ค๋ฅธ ๋ฌด๊ฒ W๋ฅผ ๊ฐ์ง๊ณ ์์ ๋, ๋ฐฐ๋ญ์ด ์ต๋ํ ๊ฐ์น๊ฐ ๋์ ๋ฌผ๊ฑด๋ค์ ๋ด์ ์ ์๋ ์กฐํฉ์ ์ฐพ๋ ๋ฌธ์ ์ด๋ค. ๋
์ ๋ฌธ์ ๋ Fractional Knapsack, ์ฆ ๋ฌผ๊ฑด์ ์ชผ๊ฐค ์ ์์ด ๋ฌด๊ฒ๋ ๊ฐ์น๊ฐ ์์์ ๋จ์๋ก ๋๋๋ ๋ฌธ์ , ๋๋ 0-1 Knapsack ๋ฌผ๊ฑด์ ์ชผ๊ฐค ์ ์์ด ๋ฌด๊ฒ์ ๊ฐ์น๊ฐ ๋ฌด์กฐ๊ฑด ์ ์ํํ๋ฅผ ๊ฐ์ง๋ ๋ ์ ํ์ผ๋ก ๋๋๋ค. ์ด๋ฒ์๋ 0-1 Knapsack ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ ๋ํด์ ์๊ฐํด๋ณด์. Brute Force App..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํํ๋ง ์ฝ๋(Huffman Code Problem)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํํ๋ง ์ฝ๋(Huffman Code Problem)
2021.07.17Huffman Code Problem ํํ๋ง ์ฝ๋๋ ๋ฌธ์๋ฅผ ๋ฐ์ดํฐ๋ก ํํํ ๋ ๋ ์ ์ ๋ฐ์ดํฐ์์ ์ฌ์ฉํ๋ฉด์ ๋ฌธ์๋ฅผ ํํํ๊ธฐ ์ํด ๋ฐ์ดํฐ๋ฅผ ์์ถํ๋ ๋ฐฉ๋ฒ์ด๋ค. Basic Idea ์ด ๋ฐฉ๋ฒ์ ๊ธฐ๋ณธ์ ์ธ ์์ด๋์ด๋ ๋ฌธ์์ด๋ฅผ ์ด์ง์๋ก ํํํ ๋, ํด๋น ๋ฌธ์ฅ์ด์์ ๊ฐ์ฅ ์์ฃผ ๋ฑ์ฅํ๋ ๋ฌธ์๋ฅผ ๋ค๋ฅธ ๋ฌธ์๋ณด๋ค ๋ ์งง๊ฒ ํํํ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฐ๋ฐ ์ด๋ ๊ฒ ์ด์ง ์ฝ๋์ ๊ธธ์ด๋ฅผ ๊ฐ๋ณ์ผ๋ก ๋ง๋ค๋ฉด, ์ด์ง ์ฝ๋๋ฅผ ๋ค์ ๋ฌธ์์ด๋ก ๋ณํํ ๋, ์ด๋์์ ๋์ด์ ๋ฌธ์๋ฅผ ํด๋
ํด์ผํ๋์ง ์ ์๊ฐ ์๊ฒ ๋๋ค. ์๋ฅผ ๋ค์ด A ๋ผ๋ ๋ฌธ์๊ฐ 1001 ๋ก ํํ๋์๊ณ , B ๋ผ๋ ๋ฌธ์๊ฐ 100 ์ผ๋ก ํํ๋์๋ค๋ฉด, 1001001 ์ด๋ผ๋ ์ฝ๋๊ฐ ์์ ๋, ์ฒซ ๋ฌธ์๋ฅผ B๋ก๋ ํด์ํ ์ ์๊ณ , A๋ก๋ ํด์ํ ์ ์๊ฒ๋๋ค. ์ง๊ธ์ ์ฐ๋ฆฌ์๊ฒ ์ฃผ์ด์ง ์ฝ๋์ ๊ธธ์ด๊ฐ ์งง..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy Alogorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy Alogorithm)
2021.07.17Greedy Algorithm ํ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ ํ๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฌธ์ ๋ฅผ ๋จ๊ณ์ ์ผ๋ก ํด๊ฒฐํ๋ฉด์, ํ ๋จ๊ณ๋ง๋ค ๊ทธ ์๊ฐ์ ์ต์ ์ solution ์ด๋ผ๊ณ ์๊ฐ๋๋ solution์ ์ ํํด์ ์ต์ข
์ ์ธ solution์ ์ฐพ์๊ฐ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ต์ด๋ค. Local Optimum and Global Optimum Solution ์ด๋ ์ด๋ค ๋จ๊ณ์์ ๋ณด์ด๋ ์ต์ ์ solution์ local optimum ์ด๋ผ๊ณ ํ๊ณ , ์ ์ฒด ๋ฌธ์ ์ ๋ํ ์ต์ ์ solution์ global optimum ์ด๋ผ๊ณ ํ๋ค. ํ์ง๋ง ๋ชจ๋ ๋ฌธ์ ๊ฐ local optimum์ ํตํด global optimum์ ๋ง๋ค ์ ์์ง๋ ์๋ค. ์ฐ๋ฆฌ๊ฐ ์ธ์์ ์ด๋ฉด์ ํ์ฌ ์๊ฐ์ ์ต์ ์ ์ ํ์ ํ๋ค๊ณ ์๊ฐํ์ง๋ง ๋์ค์ ์ง๋๊ณ ๋ณด๋ฉด ๊ทธ๊ฒ ์ต์ ์ด ์๋..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ฅ ๊ณตํต ๋ถ๋ถ ์์ด(LCS)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ฅ ๊ณตํต ๋ถ๋ถ ์์ด(LCS)
2021.07.17Logest Common Subequence ์ฐ๋ฆฌ ๋ง๋ก ์ต์ฅ ๊ณตํต ๋ถ๋ถ ์์ด์ด๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ด๋ค ๋ฌธ์์ด์ด ๋ ๊ฐ ์์ ๋, ๋ ์์ด ์ฌ์ด์ ์๋ ๊ณตํต์ ์ธ ๋ฌธ์๋ค์ ๊ฐ์ฅ ๊ธด ์กฐํฉ์ ์ฐพ๋ ๋ฌธ์ ์ด๋ค. ์๋ฅผ ๋ค์ด ๋ค์ ๋ ๋ฌธ์์ด์ด ์๋ค๊ณ ํ์. X = (A, B, C, B, D, A, B) Y = (B, D, C, A, B, A) ๋ ๋ฌธ์์ด์ ์ฌ์ด์๋ ๋ง์ ๋ถ๋ถ ๋ฌธ์์ด๋ค์ด ์๋๋ฐ, ๋ฌธ์๊ฐ ํ๋ ๋ฟ์ธ ๋ถ๋ถ ๋ฌธ์์ด์ ์ ์ธํ๊ณ ๋ชจ๋ ๋์ดํด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค: A, B A, B, A B, C B, C, B C, B C, B, A B, D B, D, A B, D, A, B ์ด ์ค์์ ๊ฐ์ฅ๊ธด ๋ถ๋ถ ๋ฌธ์์ด์ B,D,A,B๊ฐ ๋ ๊ฒ์ด๋ค. Brute-Force ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์ ๋จผ์ ๋ธ๋ฃจํธ ํฌ์ค๋ก ๋ชจ๋ ๊ฒฝ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ ฌ ๊ณฑ์
๋ฌธ์ (Matrix Chain Multiplication)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ ฌ ๊ณฑ์ ๋ฌธ์ (Matrix Chain Multiplication)
2021.07.17DP: Matrix Chain Multiplication (MCM problem) Dynamic Programming ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ํน์ ํ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ธฐ ๋ณด๋ค๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ์ํ ์ ๋ต ์ค ํ๋๋ผ๊ณ ํ ์ ์๋ค. ์ธ๋ป ๋ณด๋ฉด Divde-and-Conquer๋ ๋น์ทํด๋ณด์ด์ง๋ง ๋์ ํฐ ์ฐจ์ด๊ฐ ์๋ค. Optimization DP๋ ๋ฌธ์ ๋ฅผ ์ต์ ํํ ์ ์๋ ๋ ์์ ๋ฌธ์ ๋ฅผ ์ฐพ์ ์ ์ฐจ ํฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ์์ด๋ค. ๋ง์ฝ ์ด๋ค ๋ฌธ์ ์ Solution์ด S ๋ผ๊ณ ํ๋ค๋ฉด, DP๋ S๋ณด๋ค ์์ ๋ฌธ์ ๋ค์ ์ต์ ์ Solution์ ๋ชจ๋ ๋ชจ์ ํฉ์น ๊ฒ์ด๋ผ๊ณ ํ ์ ์๋ค. ๋ฐ๋ผ์, ๋ ์์ ๋ฌธ์ ๋ฅผ ๋จผ์ ํด๊ฒฐํจ์ผ๋ก ํฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ๋๋ฌธ์, bottom-up ๋ฐฉ์์ด๋ผ๊ณ ํ ์ ์๋ค. Divde-and-Conquer vs...