[TIL] 220117

leesyongΒ·2022λ…„ 1μ›” 17일
0

TIL

λͺ©λ‘ 보기
152/204
post-thumbnail

πŸ“ 였늘 ν•œ 것

  1. 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜ 볡슡

πŸ“š 배운 것 (볡슡)

1. 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜

  • [TIL] 211025

    • λ°©ν–₯ κ·Έλž˜ν”„
    • 무방ν–₯ κ·Έλž˜ν”„
    • λ„ˆλΉ„ μš°μ„  탐색
    • κ·Έλž˜ν”„ λ°μ΄ν„°λ² μ΄μŠ€
    • 가쀑 κ·Έλž˜ν”„
  • [TIL] 211026

    • λ‹€μ΅μŠ€νŠΈλΌ μ•Œκ³ λ¦¬μ¦˜ πŸ™‹β€β™€οΈ
    • 곡간 λ³΅μž‘λ„

λ„ˆλΉ„ μš°μ„  νƒμƒ‰μ˜ νš¨μœ¨μ„±μ€ O(V+E)라고 ν•  수 μžˆλ‹€.

[ 정점 처리 ]
κ·Έλž˜ν”„μ— V개의 정점이 μžˆμ„ λ•Œ, νμ—μ„œ V번 μ‚­μ œν•œλ‹€.

[ κ°„μ„  처리 ]
κ·Έλž˜ν”„μ— E개의 간선이 μžˆμ„ λ•Œ, μΈμ ‘ν•œ 정점을 2E번 ν™•μΈν•œλ‹€. (λΉ…μ˜€λŠ” μƒμˆ˜ λ¬΄μ‹œ)

μ‹œκ°„ λ³΅μž‘λ„μ—μ„œ O(1)은, λ°μ΄ν„°μ˜ 크기와 상관없이, μ•Œκ³ λ¦¬μ¦˜ 속도가 μƒμˆ˜λΌλŠ” λœ»μ΄λ‹€. 곡간 λ³΅μž‘λ„μ—μ„œ O(1)은, λ°μ΄ν„°μ˜ 크기와 상관없이, μ•Œκ³ λ¦¬μ¦˜μ΄ μ†Œλͺ¨ν•˜λŠ” λ©”λͺ¨λ¦¬κ°€ μƒμˆ˜λΌλŠ” λœ»μ΄λ‹€.


✨ 내일 ν•  것

  1. ν΄λ‘œμ € / μž¬κ·€ ν•¨μˆ˜
profile
λŠ₯λ™μ μœΌλ‘œ μ‚΄μž, ν–‰λ³΅ν•˜κ²ŒπŸ˜

0개의 λŒ“κΈ€