๐ฎ ์จ-์์ค
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์๊ณ ๊ฒฝ๋ก(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 : ์์ง ๋ฐ๊ฒฌ๋์ง..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋๋น ์ฐ์ ํ์(BFS)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋๋น ์ฐ์ ํ์(BFS)
2021.07.18Breadth-First Search ๋๋น ์ฐ์ ํ์์ผ๋ก๋ ๋ถ๋ฆฌ๋ BFS ์ญ์ ๊ทธ๋ํ๋ฅผ ํ์ํ๊ธฐ ์ํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. DFS๋ ํ ๋
ธ๋์ ๋ํด์ ์ ์ผ ๊น์ํ ์์น์ ์๋ ๋ ๋ฒจ๊น์ง ๋ด๋ ค๊ฐ ํ์ํ์ง๋ง BFS๋ ํ ๋ ๋ฒจ์ ์๋ ๋ชจ๋ ๋
ธ๋๋ฅผ ๋ค ํ์ํ๊ณ ๋ค์ ๋ ๋ฒจ๋ก ์ด๋ํ๋ ๋ฐฉ๋ฒ์ผ๋ก ํ์์ ์งํํ๋ค. BFS๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋๋ฐ ์ ์ฉํ๊ฒ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๊ณ queue ๋ฅผ ์ฌ์ฉํ์ฌ ๊ตฌํํ๋ค. Algorithm Steps Node State ์ด๋ฒ ๊ฐ์์์ ์ค๋ช
ํ BFS๋ ์๊น์ ํตํด์ ๊ฐ ๋
ธ๋์ ์ํ๋ฅผ ํํํ๊ฒ ๋๋ค. White : ์ฒ์ ๋ฐ๊ฒฌ๋ ๋
ธ๋ Gray : ๋ฐ๊ฒฌ์ ๋์์ง๋ง ์์ง ํด๋น ๋
ธ๋์ ์ด์๋
ธ๋๋ค์ด ๋ชจ๋ ํ์๋์ง๋ ์์ ๋
ธ๋ Black : ํด๋น ๋
ธ๋์ ์ด์๋
ธ๋๋ค์ด ๋ชจ๋ ๋ฐฉ๋ฌธ๋ ๋
ธ๋ Distance ๊ฐ ๋ ๋ฒจ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ฐฐ๋ญ ๋ฌธ์ (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...
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด(LIS)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด(LIS)
2021.07.17์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด(LIS) Longest Increasing Subsequence ๋ฅผ ์ค์ฌ์ LIS๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ ์ด ์๊ณ ๋ฆฌ์ฆ์ ์์ด์์ ์ฐ์์ ์ผ๋ก ๊ฐ์ด ์ฆ๊ฐํ๋ ์์๋ค์ ์ฐ๊ฒฐ์์ผฐ์ ๋, ๊ทธ ๊ธธ์ด๊ฐ ๊ฐ์ฅ ๊ธธ์ด์ง๋ ์์ด์ ๊ธธ์ด๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ค. ์๋ฅผ ๋ค์ด, ์๋ A๋ผ๋ ๋ฐฐ์ด์ ๋ค์๊ณผ ๊ฐ์ด ๊ฐ๋ค์ด ๋ค์ด ์๋ค๊ณ ํ์. index 0 1 2 3 4 5 6 A[index] 5 2 3 8 1 4 7 ์ด ๊ฒฝ์ฐ์์ ์ฐ๋ฆฌ๊ฐ ์ป์ ์ ์๋ ์ฆ๊ฐ ๋ถ๋ถ ์์ด์ 5 > 8 2 > 3 > 8 2 > 3 > 4 > 7 3 > 8 3 > 4 > 7 1 > 4 > 7 4 > 7 ์ด๊ณ , ์ด ์ค ๊ธธ์ด๊ฐ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐ ๋ถ๋ถ ์์ด์ 3๋ฒ์ ์๋ ๊ธธ์ด 4์ง๋ฆฌ ์์ด์ด๋ค. LIS๋ฅผ ๊ตฌํ๋ ์ ๋ต์ 1) Dynamic Programming, 2) ..