μμ μ λ ¬
μμ μ λ ¬μ΄λ?
μμ μ λ ¬ Topological Sorting μ΄λ λ°©ν₯μ΄ μλ κ·Έλνμ μ μ λ€μ λ³μ λ°©ν₯μ κ±°μ€λ₯΄μ§ μλλ‘ λμ΄νλ κ²μ μλ―Ένλ€. μ¦ ν μ μ μ λλ¬νκΈ° μ λ¨Όμ κ±°μ³μΌ νλ μ μ λ€μ μμκ° μλ κ²½μ° μ¬μ©νλ μκ³ λ¦¬μ¦μ΄λ€.
λ§μ½ νΉμ μκ°κ³Όλͺ©μ μ μκ³Όλͺ©μ΄ μλ€λ©΄ κ·Έ μ μκ³Όλͺ©λΆν° μκ°ν΄μΌ νλ―λ‘, νΉμ κ³Όλͺ©λ€μ μκ°ν΄μΌ ν λ μμ μ λ ¬μ ν΅ν΄ μ¬λ°λ₯Έ μκ° μμλ₯Ό μ°ΎμλΌ μ μλ€. μ΄μ κ°μ΄ μ ν κ΄κ³κ° μ μλ κ·Έλν ꡬ쑰 μμμ μ ν κ΄κ³μ λ°λΌ μ λ ¬νκΈ° μν΄ μμ μ λ ¬μ μ΄μ©ν μ μλ€. μ λ ¬μ μμλ λ°©ν₯μ΄ μλ (μ ν₯μ) κ·Έλνμ ꡬ쑰μ λ°λΌ μ¬λ¬ κ°μ μ’ λ₯κ° λμ¬ μ μλ€. μμ μ λ ¬μ΄ μ±λ¦½νκΈ° μν΄μλ λ°λμ κ·Έλνμ μνμ΄ μ‘΄μ¬νμ§ μμμΌ νλ€. μ¦, κ·Έλνκ° λΉμν μ ν₯ κ·Έλν directed acyclic graph μ¬μΌ νλ€.
μμ μ λ ¬μ μνκ³Όμ
- μκΈ° μμ μ κ°λ¦¬ν€λ λ³μ΄ μλ μ μ μ μ°Ύλλ€.
- μ°Ύμ μ μ μ μΆλ ₯νκ³ μΆλ ₯ν μ μ κ³Ό κ·Έ μ μ μμ μΆλ°νλ λ³μ μμ νλ€.
- μμ§ κ·Έλνμ μ μ μ΄ λ¨μμμΌλ©΄ 1λ‘ λμκ°κ³ , μλλ©΄ μκ³ λ¦¬μ¦μ μ’ λ£νλ€.
μμ
![Topological Sorting Example](https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Directed_acyclic_graph_2.svg/610px-Directed_acyclic_graph_2.svg.png)
μ κ·Έλνμμ μ μ xλ‘λΆν° yλ‘μ κ°μ μ μΌ xκ° yλ₯Ό μμνκΈ° μ μ νλμ΄μΌ ν¨μ λνλΈλ€. μ΄ κ·Έλνλ₯Ό λμμΌλ‘ μμ μ λ ¬ μκ³ λ¦¬μ¦μ μννλ©΄ λ€μκ³Ό κ°λ€. (κ°μ₯ μμ μ λΆν°)
νμ°¨ | 쑰건 | μν | μΆλ ₯ |
---|---|---|---|
1 | 2λ₯Ό κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | λ€μ μ μ μΌλ‘ λμ΄κ°λ€ | - |
2 | 3μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 3μ μΆλ ₯, μ μ 3κ³Ό κ°μ <3, 8>, <3, 10> μ μμ | 3 |
3 | 5λ₯Ό κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 5λ₯Ό μΆλ ₯, μ μ 5μ κ°μ <5, 11> μμ | 3 5 |
4 | 7μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 7μ μΆλ ₯, μ μ 7κ³Ό κ°μ <7, 11>, <7, 8> μμ | 3 5 7 |
5 | 8μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 8μ μΆλ ₯, μ μ 8κ³Ό κ°μ <8, 9> μμ | 3 5 7 8 |
6 | 9λ₯Ό κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | λ€μ μ μ μΌλ‘ λμ΄κ°λ€ | 3 5 7 8 |
7 | 10μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | λ€μ μ μ μΌλ‘ λμ΄κ°λ€ | 3 5 7 8 |
8 | 11μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 11μ μΆλ ₯, μ μ 11κ³Ό κ°μ <11,2>, <11, 9>, <11, 10>μ μμ | 3 5 7 8 11 |
9 | λ¨μ μ μ 2λ₯Ό κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 2λ₯Ό μΆλ ₯, μ μ 2 μμ | 3 5 7 8 11 2 |
10 | λ¨μ μ μ 9λ₯Ό κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 9λ₯Ό μΆλ ₯, μ μ 9 μμ | 3 5 7 8 11 2 9 |
11 | λ¨μ μ μ 10μ κ°λ¦¬ν€λ κ°μ μ΄ μλ€ | 10μ μΆλ ₯, μ μ 10 μμ | 3 5 7 8 11 2 9 10 |
12 | λ¨μμλ μ μ μ΄ μλ€ | 루νλ₯Ό μ’ λ£νλ€ | 3 5 7 8 11 2 9 10 |
μκ³ λ¦¬μ¦
μμ μ λ ¬μ μΌλ°μ μΈ μκ³ λ¦¬μ¦μ μ μ μ μμ λ Έλμ μ ν μ€ν μκ°μ κ°λλ€. $O(|V|+|E|)$
λ μμλ³Ό κ²
- Kahn μκ³ λ¦¬μ¦
- DFS μκ³ λ¦¬μ¦μ κΈ°λ°ν μμ μ λ ¬ λ체
- Parallel μκ³ λ¦¬μ¦
'DevLog π¨ > Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[DevLog] [Alogorithm] μ λ ¬ Sorting Problem (0) | 2023.08.13 |
---|