일상/Today I Learned

[λ°λΈŒμ½”μŠ€ Day5] 2022.10.21

YJzero 2022. 10. 21. 22:25

 

πŸ“–μ˜€λŠ˜ 배운  것

 

트리

: λ…Έλ“œλ‘œ κ΅¬μ„±λ˜μ–΄ 있으며 λͺ¨λ“  정점이 μ—°κ²°λœ κ·Έλž˜ν”„μ΄λ‹€.

 

루트(Root): λΆ€λͺ¨κ°€ μ—†λŠ” λ…Έλ“œ, 졜고 정점
λ…Έλ“œ(Node): κ΅¬μ„±μš”μ†Œ
κ°„μ„ (Edge): λ…Έλ“œμ™€ λ…Έλ“œ κ°„μ˜ μ—°κ²°μ„ 
λ¦¬ν”„λ…Έλ“œ(Leaf Node): μžμ‹μ΄ μ—†λŠ” λ…Έλ“œ
레벨(Level): λ…Έλ“œμ—μ„œ νŠΉμ • λ…Έλ“œκΉŒμ§€μ˜ 깊이
 λ””그리(Degree): λ…Έλ“œμ˜ μžμ‹μ˜ 수/κ°„μ„ μ˜ 수
깊이(depth): λ£¨νŠΈμ—μ„œ νŠΉμ • λ…Έλ“œκΉŒμ§€μ˜ κ°„μ„ μ˜ 수
높이(height): λ¦¬ν”„μ—μ„œ νŠΉμ • λ…Έλ“œκΉŒμ§€ κ°€μž₯ κΈ΄ 경둜의 κ°„μ„ μ˜ 수

 

νŠΉμ§•
  • 루트 정점을 μ œμ™Έν•œ λͺ¨λ“  μžμ‹ λ…Έλ“œλŠ” ν•˜λ‚˜μ˜ λΆ€λͺ¨ λ…Έλ“œλ₯Ό κ°€μ§„λ‹€.
  • λ…Έλ“œκ°€ n개인 νŠΈλ¦¬λŠ” 항상 n-1개의 간선을 κ°€μ§„λ‹€.

 

μ’…λ₯˜
  • 편ν–₯트리 : λͺ¨λ“  λ…Έλ“œλ“€μ΄ ν•˜λ‚˜μ˜ μžμ‹λ§Œμ„ κ°€μ§„ 경우
  • μ΄μ§„νŠΈλ¦¬: 각 λ…Έλ“œμ˜ μžμ‹ λ…Έλ“œκ°€ 2개 μ΄ν•˜μΈ 경우

          -μ™„μ „ μ΄μ§„νŠΈλ¦¬: λ§ˆμ§€λ§‰ λ ˆλ²¨μ„ μ œμ™Έν•˜κ³  정점이 λͺ¨λ‘ μ±„μ›Œμ Έ μžˆλŠ” 경우

          -포화 μ΄μ§„νŠΈλ¦¬: λ§ˆμ§€λ§‰ λ ˆλ²¨λ„ λͺ¨λ‘ μ±„μ›Œμ Έ μžˆλŠ” 경우

 


 

μš°μ„ μˆœμœ„ 큐

:μš°μ„ μˆœμœ„κ°€ 높은 μš”μ†Œκ°€ λ¨Όμ € λ‚˜κ°€λŠ” 큐

 

 

νž™

:μ™„μ „ μ΄μ§„νŠΈλ¦¬μ˜ μΌμ’…μœΌλ‘œ μš°μ„ μˆœμœ„ 큐λ₯Ό κ΅¬ν˜„ν•˜λŠ” 자료ꡬ쑰

μš”μ†Œκ°€ μ‚½μž…, μ‚­μ œλ  λ–„λ§ˆλ‹€ λ°”λ‘œ μ •λ ¬λ˜λŠ” νŠΉμ§•μ΄ μžˆλ‹€.

νž™μ˜ μ’…λ₯˜
  • μ΅œλŒ€ νž™

     : λΆ€λͺ¨ λ…Έλ“œμ˜ ν‚€ 값이 μžμ‹ λ…Έλ“œμ˜ ν‚€ 값보닀 κ°™κ±°λ‚˜ 큰 경우

 

  • μ΅œμ†Œ νž™

     :λΆ€λͺ¨ λ…Έλ“œμ˜ ν‚€ 값이 μžμ‹ λ…Έλ“œμ˜ ν‚€ 값보닀 κ°™κ±°λ‚˜ μž‘μ€ 경우

 

 

 

트라이

:λ¬Έμžμ—΄μ„ μ €μž₯ν•˜κ³  효율적으둜 νƒμƒ‰ν•˜κΈ° μœ„ν•œ 트리 ν˜•νƒœμ˜ 자료ꡬ쑰

 

νŠΉμ§•
  • 검색어 μžλ™μ™„μ„±, 사전 μ°ΎκΈ° 등에 μ‘μš©λ  수 μžˆλ‹€.
  • λ¬Έμžμ—΄μ„ λΉ λ₯΄κ²Œ 찾을 수 μžˆλ‹€.
  • μžμ‹ λ…Έλ“œλ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터λ₯Ό λͺ¨λ‘ μ €μž₯ν•΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ— μ €μž₯ 곡간을 많이 μ‚¬μš©ν•œλ‹€.

 

 

πŸ’­λ°°μš΄ 점

자료ꡬ쑰 μ–΄λ ΅λ‹€~~ κ°•μ˜λ“€μœΌλ©΄ 으음 κ·Έλ ‡κ΅° ν•˜κ³  μ΄ν•΄λ˜μ§€λ§Œ 문제둜 λ§Œλ‚˜λ©΄?? 이게 무슨 μ†Œλ¦¬μ§€?? μ‹Άμ–΄ μ§„λ‹€. 직접 κ΅¬ν˜„ν•΄λ³΄λ©΄μ„œ μ΅μˆ™ν•΄μ§€κ³  λ¬Έμ œλ„ 많이 풀어봐야 ν•  것 κ°™λ‹€. 

 

 

 

πŸ’»μ•žμœΌλ‘œ 배우고 싢은 것

-자료ꡬ쑰 λ³΅μŠ΅ν•˜κΈ°

 

 

참고자료

-ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ κ°•μ˜

-https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

-https://yoongrammer.tistory.com/68