๐Ÿ“š
TIL
  • README
  • Git
    • Basic
    • Remote Repository
    • Log & Diff
    • Rebase&Cherri-Pick
    • git-flow
  • DevOps
    • Monolithic vs MSA
    • Jenkins ์‹œ์ž‘ํ•˜๊ธฐ
    • Airflow ์‹œ์ž‘ํ•˜๊ธฐ
    • Airflow ์‹œ์ž‘ํ•˜๊ธฐ
    • Build Tools
      • maven
  • ๊ฐœ๋ฐœ ๋ฐฉ๋ฒ•๋ก 
    • TDD
  • Spring
    • IoC
    • Is Spring Bean Thread-Safe?
    • Spring Singleton
    • Component Scan
    • Spring Annotation
    • ์˜์กด ๊ด€๊ณ„ ์ฃผ์ž…(DI)
    • Lombok ํ™œ์šฉํ•˜๊ธฐ
    • Bean ์ƒ๋ช…์ฃผ๊ธฐ์™€ ์ฝœ๋ฐฑ
    • Bean Scope
    • AOP(1) - AOP๋ž€
    • AOP(2) - Aop Proxy
    • AOP(3) - Dynamic Proxy
    • AOP(4) - AspectJ
    • POJO
    • Spring ์„œ๋น„์Šค ๊ตฌ์กฐ
    • Transaction
    • JPA๋ž€?
    • JPA Entity
    • Spring Data JPA
    • Spring Data Specification
    • Model Mapping
    • Cache
    • restTemplate
    • YAML ํŒŒ์ผ ์„ค์ •
    • Spring Boot
      • H2 DB ์„ค์ •
      • ๋‹ค์ค‘ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์„ค์ •
      • Mybatis ์—ฐ๋™ํ•˜๊ธฐ
    • Spring Batch
      • Batch ์‹œ์ž‘ํ•ด๋ณด๊ธฐ
      • Batch Job Flow
      • Job
      • Step
      • Batch Scope & Job Parameter
      • JobRepository์™€ ๋ฉ”ํƒ€ํ…Œ์ด๋ธ”
      • Chunk ์ง€ํ–ฅ ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      • ItemReader
      • ItemProcessor
      • ItemWriter
      • Batch Schedular
      • Job๋ณ„ Bean๋“ฑ๋กํ•˜๊ธฐ
      • Batch ๊ตฌํ˜„์‹œ ๋ฐœ์ƒํ•œ ์˜ค๋ฅ˜ ์ •๋ฆฌ
      • Spring Batch Scaling
        • Multithread Job๊ตฌํ˜„์‹œ ์ด์Šˆ์‚ฌํ•ญ
    • Spring test
      • Junit5
        • ํ…Œ์ŠคํŠธ ์ด๋ฆ„ ํ‘œ๊ธฐ
        • ํ…Œ์ŠคํŠธ ๊ทธ๋ฃน ์‚ฌ์ด์˜ ๊ด€๊ณ„
        • ํƒœ๊ทธ์™€ ํ•„ํ„ฐ๋ง
        • ๋™์  ํ…Œ์ŠคํŠธ
        • ํ…Œ์ŠคํŠธ LifeCycle
        • ํ…Œ์ŠคํŠธ ๋ฉ”์„œ๋“œ
        • ํ…Œ์ŠคํŠธ ์ˆœ์„œ
        • AssertJ
        • ํ…Œ์ŠคํŠธ ๋ณ‘๋ ฌ ์‹คํ–‰
        • AssertJ
        • Mock
      • Spring Boot Test DB ๋ถ„๋ฆฌ
      • Spring Batch Test
  • Web Application
    • Web Server & WAS
    • ๊ด€๋ จ ๊ฐœ๋… - HTTP API, HTML, CSR, SSR
    • Servlet
    • JSP
    • Cookie And Session
    • ์˜ˆ์™ธํŽ˜์ด์ง€
    • Java Bean
    • JDBC
    • Connection Pool
    • ํŒŒ์ผ ์—…๋กœ๋“œ
    • Expression Language
    • JSTL
    • FrontControllerํŒจํ„ด Command ํŒจํ„ด
    • Forwarding
    • MVC
    • ํšŒ์›๊ฐ€์ž…์˜ˆ์ œ
    • ์ฐธ๊ณ 
      • ๊ฐœ๋ฐœํ™˜๊ฒฝ์„ค์ •
  • Java+
    • SOAP/WSDL vs REST
    • WSDL์„ JAVA๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ
    • SOAP ํ†ต์‹  OPEN API๋กœ ๊ฐœ๋ฐœํ•ด๋ณด๊ธฐ
  • Java
    • Basic
      • ๋ณ€์ˆ˜์™€ ํƒ€์ž…
      • ์—ฐ์‚ฐ์ž
      • ์กฐ๊ฑด๋ฌธ๊ณผ ๋ฐ˜๋ณต๋ฌธ
      • ์ฐธ์กฐ ํƒ€์ž…
      • ํด๋ž˜์Šค
      • ์ƒ์†(Inheritance)
      • ์ธํ„ฐํŽ˜์ด์Šค(Interface)
      • ์ค‘์ฒฉ ํด๋ž˜์Šค์™€ ์ค‘์ฒฉ ์ธํ„ฐํŽ˜์ด์Šค
      • ์˜ˆ์™ธ ์ฒ˜๋ฆฌ
      • API - Object, System, Class, Math, Wrapper
      • API - String, StringBuffer, StringBuilder
      • Thread
      • Generic
      • Lambda
      • Collection - List, Set
      • Collection - Map
      • Collection - Tree
      • Collection - Stack, Queue
      • Stream
      • Reflection
      • ์ •๊ทœํ‘œํ˜„์‹
      • GUI
      • UML
      • Serializable
    • Advanced
      • OutOfMemoryError
      • AutoValue
      • meta-annotation
        • @Retention
        • @Target
        • @Repeatable
    • Effective Java 3/E
      • ITEM 1: Static Factory Method(์ •์  ๋ฉ”์†Œ๋“œ)
      • ITEM 2: Builder Pattern
      • ITEM 3: Singleton
      • ITEM 4: Private Constructor
      • ITEM 5: Dependency Injection
      • ITEM 6: Avoid Unnecessary Object
      • ITEM 7: Eliminate Object Reference
      • ITEM 8: Avoid finalizer and cleaner
      • ITEM 9: try-with-resources
      • ITEM 10: The gerneral contract when overriding equlas
      • ITEM 11: Overriding hashCode
      • ITEM 12: overriding toString
      • ITEM 13: overriding clone judiciously
      • ITEM 14: Consider implementing comparable
      • ITEM 15: ํด๋ž˜์Šค์™€ ๋ฉค๋ฒ„์˜ ์ ‘๊ทผ์„ ์ตœ์†Œํ™”ํ•ด๋ผ
      • ITEM 16: Use Accessor methods
      • ITEM 17: ๋ณ€๊ฒฝ ๊ฐ€๋Šฅ์„ฑ์„ ์ตœ์†Œํ™”ํ•ด๋ผ(๋ถˆ๋ณ€ ํด๋ž˜์Šค)
      • ITEM 18: ์ƒ์†๋ณด๋‹จ ์ปดํฌ์ง€์…˜์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 19: ์ƒ์†์„ ๊ณ ๋ คํ•ด ์„ค๊ณ„ํ•˜๊ณ  ๋ฌธ์„œํ™”ํ•ด๋ผ
      • ITEM 20: ์ถ”์ƒ ํด๋ž˜์Šค๋ณด๋‹ค ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์šฐ์„ ํ•˜๋ผ
      • ITEM 21: ์ธํ„ฐํŽ˜์ด์Šค๋Š” ๊ตฌํ˜„ํ•˜๋Š” ์ชฝ์„ ์ƒ๊ฐํ•ด ์„ค๊ณ„ํ•ด๋ผ.
      • ITEM 22: ์ธํ„ฐํŽ˜์ด์Šค๋Š” ํƒ€์ž…์„ ์ •์˜ํ•˜๋Š” ์šฉ๋„๋กœ๋งŒ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 23: ํƒœ๊ทธ ๋‹ฌ๋ฆฐ ํด๋ž˜์Šค๋ณด๋‹ค ํด๋ž˜์Šค ๊ณ„์ธต๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•ด๋ผ
      • ITEM 24: ๋ฉค๋ฒ„ ํด๋ž˜์Šค๋Š” ๋˜๋„๋ก static์œผ๋กœ ๊ตฌํ˜„ํ•ด๋ผ
      • ITEM 25: ํ†ฑ๋ ˆ๋ฒจ ํด๋ž˜์Šค๋Š” ํ•œ ํŒŒ์ผ์— ํ•˜๋‚˜๋งŒ ์ƒ์„ฑํ•ด๋ผ.
      • ITEM 26: Raw type์€ ์‚ฌ์šฉํ•˜์ง€ ๋งˆ๋ผ
      • ITEM 27: ๋น„๊ฒ€์‚ฌ ๊ฒฝ๊ณ ๋ฅผ ์ œ๊ฑฐํ•ด๋ผ
      • ITEM 28: ๋ฐฐ์—ด๋ณด๋‹ค๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 29: ์ด์™•์ด๋ฉด ์ œ๋„ค๋ฆญ ํƒ€์ž…์œผ๋กœ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 30: ์ด์™•์ด๋ฉด ์ œ๋„ค๋ฆญ ๋ฉ”์„œ๋“œ๋กœ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 31 : ํ•œ์ •์  ์™€์ผ๋“œ์นด๋“œ๋ฅผ ์‚ฌ์šฉํ•ด API ์œ ์—ฐ์„ฑ์„ ๋†’์—ฌ๋ผ
      • ITEM 32: ์ œ๋„ค๋ฆญ๊ณผ ๊ฐ€๋ณ€์ธ์ˆ˜๋ฅผ ํ•จ๊ป˜ ์“ธ ๋•Œ๋Š” ์‹ ์ค‘ํ•ด๋ผ
      • ITEM 33: ํƒ€์ž… ์•ˆ์ „ ์ด์ข… ์ปจํ…Œ์ด๋„ˆ๋ฅผ ๊ณ ๋ คํ•ด๋ผ
      • ITEM 34: int ์ƒ์ˆ˜ ๋Œ€์‹  ์—ด๊ฑฐ ํƒ€์ž…์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 35: ordinal ๋ฉ”์„œ๋“œ ๋Œ€์‹  ์ธ์Šคํ„ด์Šค ํ•„๋“œ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 36: ๋น„ํŠธ ํ•„๋“œ ๋Œ€์‹  EnumSet์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 37: ordinal ์ธ๋ฑ์‹ฑ ๋Œ€์‹  EnumMap์„ ์‚ฌ์šฉํ•ด๋ผ
      • TEM 38 : ํ™•์žฅํ•  ์ˆ˜ ์žˆ๋Š” ์—ด๊ฑฐํƒ€์ž…์ด ํ•„์š”ํ•˜๋ฉด ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 39: ๋ช…๋ช… ํŒจํ„ด๋ณด๋‹ค ์• ๋„ˆํ…Œ์ด์…˜์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 40: @Override ์–ด๋…ธํ…Œ์ด์…˜์„ ์ผ๊ด€๋˜๊ฒŒ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 41: ์ •์˜ํ•˜๋ ค๋Š” ๊ฒƒ์ด ํƒ€์ž…์ด๋ผ๋ฉด ๋งˆ์ปค ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 42: ์ต๋ช… ํด๋ž˜์Šค๋ณด๋‹ค๋Š” ๋žŒ๋‹ค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 43: ๋žŒ๋‹ค๋ณด๋‹ค๋Š” ๋ฉ”์„œ๋“œ ์ฐธ์กฐ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 44: ํ‘œ์ค€ ํ•จ์ˆ˜ํ˜• ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 45: ์ŠคํŠธ๋ฆผ์€ ์ฃผ์˜ํ•ด์„œ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 46: ์ŠคํŠธ๋ฆผ์—์„œ ๋ถ€์ž‘์šฉ ์—†๋Š” ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 47: ๋ฐ˜ํ™˜ ํƒ€์ž…์œผ๋กœ๋Š” ์ŠคํŠธ๋ฆผ๋ณด๋‹ค ์ปฌ๋ ‰์…˜์ด ๋‚ซ๋‹ค.
      • ITEM 48: ์ŠคํŠธ๋ฆผ ๋ณ‘๋ ฌํ™”๋Š” ์ฃผ์˜ํ•ด์„œ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 49: ๋งค๊ฐœ๋ณ€์ˆ˜๊ฐ€ ์œ ํšจํ•œ์ง€ ๊ฒ€์‚ฌํ•ด๋ผ
      • ITEM 50: ์ ์‹œ์— ๋ฐฉ์–ด์  ๋ณต์‚ฌ๋ณธ์„ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 51: ๋ฉ”์„œ๋“œ ์‹œ๊ทธ๋‹ˆ์ฒ˜๋ฅผ ์‹ ์ค‘ํžˆ ์„ค๊ณ„ํ•ด๋ผ
      • ITEM 52: ๋‹ค์ค‘์ •์˜๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 53: ๊ฐ€๋ณ€์ธ์ˆ˜๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 54: null์ด ์•„๋‹Œ, ๋นˆ ์ปฌ๋ ‰์…˜์ด๋‚˜ ๋ฐฐ์—ด์„ ๋ฐ˜ํ™˜ํ•ด๋ผ
      • ITEM 55: Optional ๋ฐ˜ํ™˜์€ ์‹ ์ค‘ํ•˜๊ฒŒ ํ•ด๋ผ
      • ITEM 56: ๊ณต๊ฐœ๋œ API ์š”์†Œ์—๋Š” ํ•ญ์ƒ ์ฃผ์„์„ ์ž‘์„ฑํ•ด๋ผ
      • ITEM 57: ์ง€์—ญ๋ณ€์ˆ˜์˜ ๋ฒ”์œ„๋ฅผ ์ตœ์†Œํ™”ํ•ด๋ผ
      • ITEM 58: ์ „ํ†ต์ ์ธ for ๋ฌธ๋ณด๋‹ค๋Š” for-each๋ฌธ์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 59: ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ตํžˆ๊ณ  ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 60: ์ •ํ™•ํ•œ ๋‹ต์ด ํ•„์š”ํ•˜๋‹ค๋ฉด float์™€ double์€ ํ”ผํ•ด๋ผ
      • ITEM 61: ๋ฐ•์‹ฑ๋œ ๊ธฐ๋ณธ ํƒ€์ž…๋ณด๋‹ค๋Š” ๊ธฐ๋ณธ ํƒ€์ž…์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 62: ๋‹ค๋ฅธ ํƒ€์ž…์ด ์ ์ ˆํ•˜๋‹ค๋ฉด ๋ฌธ์ž์—ด ์‚ฌ์šฉ์„ ํ”ผํ•ด๋ผ
      • ITEM 63: ๋ฌธ์ž์—ด ์—ฐ๊ฒฐ์€ ๋А๋ฆฌ๋‹ˆ ์ฃผ์˜ํ•ด๋ผ
      • ITEM 64: ๊ฐ์ฒด๋Š” ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด ์ฐธ์กฐํ•ด๋ผ
      • ITEM 65: ๋ฆฌํ”Œ๋ ‰์…˜๋ณด๋‹ค๋Š” ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 66: ๋„ค์ดํ‹ฐ๋ธŒ ๋ฉ”์„œ๋“œ๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 67: ์ตœ์ ํ™”๋Š” ์‹ ์ค‘ํžˆ ํ•ด๋ผ
      • ITEM 68: ์ผ๋ฐ˜์ ์œผ๋กœ ํ†ต์šฉ๋˜๋Š” ๋ช…๋ช… ๊ทœ์น™์„ ๋”ฐ๋ผ๋ผ
    • ๊ฐ์ฒด์ง€ํ–ฅ ์„ค๊ณ„ ์›์น™(SOLID)
    • ๋””์ž์ธํŒจํ„ด
      • Strategy Pattern
      • Template Method Pattern
      • Factory Method Pattern
      • Singleton
      • Delegation
      • Proxy
      • Adapter Pattern
    • ์‹ค์Šต
      • ์ธํ„ฐํŽ˜์ด์Šค ์‹ค์Šต - Vehicle
      • ์ธํ„ฐํŽ˜์ด์Šค ์‹ค์Šต - Remote
      • GUI ์‹ค์Šต - Calculator
      • GUI ์‹ค์Šต - button
      • GUI ์‹ค์Šต - lotto
      • Thread ์‹ค์Šต - ์ขŒ์„์˜ˆ์•ฝ, ๋ฉ”์„ธ์ง€๋ณด๋‚ด๊ธฐ
    • Jar vs War
  • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค
    • KEY
    • Index
    • Transaction
    • Trigger
    • Procedure / Function
    • Package
    • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๋ฐฐ์›€ํ„ฐ
      • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์‹œ์Šคํ…œ
      • ๊ด€๊ณ„๋ฐ์ดํ„ฐ ๋ชจ๋ธ
      • ๊ด€๊ณ„๋Œ€์ˆ˜์™€ SQL
    • MySQL
      • Database๋ž€
      • MySQL ์‹œ์ž‘ํ•˜๊ธฐ
      • MySQL Database
      • MySQL Table
      • CRUD
      • ๊ด€๊ณ„ํ˜• ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค
      • Server์™€ Client
    • PostgreSQL
    • NoSQL
      • Install Cassandra on mac
      • Cassandra๋ž€?
      • NiFi๋ž€
  • Algorithm
    • String
    • Recursion
    • Dynamic Programming
    • Array, Struct, Pointer
    • Math
    • Sort
    • List
    • Stack
    • Queue
    • Graph
    • Tree
    • Maze
    • AVL
    • ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ(Binary Search Tree)
    • DFS์™€ BFS
    • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Dijkstra's Algorithm)
    • Red-Black ํŠธ๋ฆฌ
    • A* ์•Œ๊ณ ๋ฆฌ์ฆ˜
    • Heap
    • Huffman Coding
    • Priority Queue
    • Bellman-Ford ์•Œ๊ณ ๋ฆฌ์ฆ˜
    • C++
      • Class
      • STL
        • STL pair
        • STL Container - Associate Container
        • STL Container - Sequence Container
        • STL Container - Container Adapter
  • JavaScript
    • JABASCRIPT BASIC
    • Shallow Copy vs Deep Copy
    • OBJECT MODEL
    • NODE
    • ๋™๊ธฐ ์ฒ˜๋ฆฌ vs ๋น„๋™๊ธฐ ์ฒ˜๋ฆฌ
    • AJAX
    • CALLBACK
    • PROMISE
    • DEFERRER
    • UNDERSCORE
    • WEBPACK
    • SCOPE
    • EXECUTION CONTEXT
    • Image Object
    • BFCache๋ž€?
    • history.scrollRestoration
    • Intersection Observer
    • JWT - JSON Web Token
    • HTML vs JSON
  • Vue.js
    • ํ™˜๊ฒฝ์„ค์ •
    • Vue.js๋ž€?
    • Vue Instance
    • Vue Component
    • Vue Router
    • HTTP ํ†ต์‹ 
    • Template
    • Single File Component
    • Vue Animation
    • Vuex
    • Djnago์™€ ์—ฐ๋™ํ•˜๊ธฐ
  • Backbone.js
    • Model
    • Collection
    • Sync
    • view
  • Node.js
    • Doit! - ๋…ธ๋“œ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋Œ€ํ‘œ์ ์ธ ์„œ๋ฒ„์™€ ์šฉ๋„
    • Doit! - ๋…ธ๋“œ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ณ  ๊ฐœ๋ฐœ ๋„๊ตฌ ์„ค์น˜ํ•˜๊ธฐ
    • Doit! - ๋…ธ๋“œ ๊ฐ„๋‹จํ•˜๊ฒŒ ์‚ดํŽด๋ณด๊ธฐ
    • Doit! - ๋…ธ๋“œ์˜ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์™€ ์นœํ•ด์ง€๊ธฐ
    • Doit! - ๋…ธ๋“œ์˜ ๊ธฐ๋ณธ ๊ธฐ๋Šฅ ์•Œ์•„๋ณด๊ธฐ
    • Doit! - ์›น ์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
    • Doit! - ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์‚ฌ์šฉํ•˜๊ธฐ
    • Doit! - ์ต์Šคํ”„๋ ˆ์Šค ํ”„๋กœ์ ํŠธ๋ฅผ ๋ชจ๋“ˆํ™”ํ•˜๊ธฐ
    • Doit! - ๋ทฐ ํ…œํ”Œ๋ฆฟ ์ ์šฉํ•˜๊ธฐ
    • Doit! - ํŒจ์ŠคํฌํŠธ๋กœ ์‚ฌ์šฉ์ž ์ธ์ฆํ•˜๊ธฐ
    • Doit! - ์ฑ„ํŒ…์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
    • Doit! - JSON-RPC ์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
  • Python
    • Warning-Could not import the lzma module
    • Pandas
      • Pandas ์ž๋ฃŒ๊ตฌ์กฐ
      • Pandas ๋ฐ์ดํ„ฐ ์ž…์ถœ๋ ฅ
      • DataFrame Data ์‚ดํŽด๋ณด๊ธฐ
      • ์‹œ๊ฐํ™” ๋„๊ตฌ - Matplotlib
  • ML
    • ์ถ”์ฒœ ์‹œ์Šคํ…œ
      • Collaborative Filtering
      • Matrix Factorization
  • Django
    • Basic
      • ํ™˜๊ฒฝ์„ค์ •
      • About Django
      • Start Django Project
      • Secret Key ๊ด€๋ฆฌํ•˜๊ธฐ
      • Settings ๋ถ„๋ฆฌํ•˜๊ธฐ
      • Django App
      • Django View & URL (1)
      • Django Model
        • MySQL ์—ฐ๋™
      • Django Admin
      • Django View & URL (2)
      • Django Template
      • Django Template & View & URL
      • Django Static
      • Django form
    • Advanced
      • Django Generic View
      • Django Automated Testing
      • Django Extenstion Template
      • Django Model Package
      • Django OpenSSL setting
    • REST framework
      • Rest API
      • Serializers
      • ViewSet
    • Error
      • ํ™˜๊ฒฝ์„ค์ • zlib ์˜ค๋ฅ˜๋ฐœ์ƒ
      • ModuleNotFoundError
    • ํŒจํ‚ค์ง€
      • django-debug-toolbar
    • Vue.js ์—ฐ๋™ํ•˜๊ธฐ
  • Ruby
    • variable & input/output
    • ์กฐ๊ฑด๋ฌธ
    • ๋ฐ˜๋ณต๋ฌธ
    • Array & Hash
    • Method
    • Proc&Lamda
    • Class
  • Ruby on Rails
    • Scaffolding
    • Controller
    • Model
    • Model-M:N relation
    • Model Validation
    • ๋ฉ‹์‚ฌ 10์ฃผ์ฐจ ์ˆ˜์—…(Tip)
  • HTML/CSS
    • Udacity - Intro to HTML/CSS
    • Udacity - Responsive Web Design
    • Udacity - Responsive Images
    • HTML Basic
    • CSS Basic
    • HTML5 Sementic Tag
    • HTML ํ…์ŠคํŠธ ๊ด€๋ จ ํƒœ๊ทธ๋“ค
    • HTML5 ๋ฉ€ํ‹ฐ๋ฏธ๋””์–ด
    • HTML ํผ ๊ด€๋ จ ํƒœ๊ทธ๋“ค
    • ํ…์ŠคํŠธ ๊ด€๋ จ ์Šคํƒ€์ผ
    • ์ƒ‰์ƒ๊ณผ ๋ฐฐ๊ฒฝ์„ ์œ„ํ•œ ์Šคํƒ€์ผ
    • ๋ ˆ์ด์•„์›ƒ์„ ์œ„ํ•œ ์Šคํƒ€์ผ
    • CSS ํฌ์ง€์…”๋‹
    • ๋‹ค์žฌ๋‹ค๋Šฅํ•œ CSS3 ์„ ํƒ์ž
    • CSS์™€ ์• ๋‹ˆ๋ฉ”์ด์…˜
    • ๋ฐ˜์‘ํ˜• ์›น์ด๋ž€?
  • OS(์šด์˜์ฒด์ œ)
    • Linux
      • Daemon
      • Cron
      • ํ”„๋กœ์„ธ์Šค ๊ด€๋ จ ๋ช…๋ น์–ด
      • ํ…์ŠคํŠธ ํŒŒ์ผ ๋ช…๋ น์–ด
  • Network
    • ๋„คํŠธ์›Œํฌ ๊ธฐ๋ณธ ๊ฐœ๋…
    • ๋„คํŠธ์›Œํฌ ๊ธฐ๋ณธ ๊ทœ์น™
    • ๋ฌผ๋ฆฌ ๊ณ„์ธต
    • ๋ฐ์ดํ„ฐ ๋งํฌ ๊ณ„์ธต
    • ๋„คํŠธ์›Œํฌ ๊ณ„์ธต
    • ์ „์†ก ๊ณ„์ธต
    • ์‘์šฉ ๊ณ„์ธต
    • ๋„คํŠธ์›Œํฌ ์ „์ฒด ํ๋ฆ„
    • ๋ฌด์„  ๋žœ
  • IT ๊ธฐํƒ€์ง€์‹
    • NAS๋ž€
Powered by GitBook
On this page
  • ํŠธ๋ฆฌ์˜ ์šฉ์–ด
  • Performance of Tree Operation
  • Non-Binary Tree
  • Binary Tree(์ด์ง„ ํŠธ๋ฆฌ)
  • Binary Tree ์„ฑ์งˆ
  • Binary Tree ์ข…๋ฅ˜
  • Link ๋ฐฉ๋ฒ• ๊ตฌํ˜„
  • ํŠธ๋ฆฌ์˜ ํ‘œํ˜„
  • ํŠธ๋ฆฌ์˜ ๋ถ€๋ชจ๋งŒ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹
  • ๋ฐฐ์—ด ํ‘œํ˜„(์ด์ง„ ํŠธ๋ฆฌ)
  • Tree Traversal(ํŠธ๋ฆฌ์˜ ์ˆœํšŒ)
  • Preorder(์ „์œ„ ์ˆœํšŒ)
  • Inorder(์ค‘์œ„์ˆœํšŒ)
  • Postorder(ํ›„์œ„์ˆœํšŒ)
  • Binary Tree Traversal ๊ตฌํ˜„
  • ํŠธ๋ฆฌ์˜ ํƒ์ƒ‰
  • ํŠธ๋ฆฌ์˜ ๋ถ€๋ชจ์ฐพ๊ธฐ
  • ์ฐธ๊ณ ์ž๋ฃŒ

Was this helpful?

  1. Algorithm

Tree

PreviousGraphNextMaze

Last updated 4 years ago

Was this helpful?

ํŠธ๋ฆฌ(tree)๋Š” ์‚ฌ์ดํด์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„๋กœ ๊ณ„์ธต์ ์ธ ๊ตฌ์กฐ(๋‚˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์œ„์•„๋ž˜ ๊ด€๊ณ„๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ)๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.

  • ์ •์ (node)์˜ ๊ฐœ์ˆ˜ : V

  • ๊ฐ„์„ (edge)์˜ ๊ฐœ์ˆ˜ : V-1

๊ทธ๋ ‡๋‹ค๋ฉด ์ •์ ์ด V๊ฐœ ๊ฐ„์„ ์ด V-1๊ฐœ๋ผ๋ฉด ํŠธ๋ฆฌ์ผ๊นŒ? No! ๋ชจ๋“  ์ •์ ์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๋ฉด tree์ด๋‹ค.

ํŠธ๋ฆฌ๋Š” 1:n ๊ด€๊ณ„๋ฅผ ๊ฐ€์ง€๋Š” ๋น„์„ ํ˜• ๊ตฌ์กฐ์ด๋‹ค.

ํŠธ๋ฆฌ์˜ ์šฉ์–ด

( ์œ„์˜ ๊ทธ๋ฆผ์„ ๊ธฐ์ค€์œผ๋กœ ์„ค๋ช… )

  • ์ •์ /๋…ธ๋“œ(node) : ํŠธ๋ฆฌ์˜ ๊ตฌ์„ฑ์š”์†Œ( A, B, C, D, E, F, G, H, I, J )

  • ๋ฃจํŠธ(root) : ๋ถ€๋ชจ๊ฐ€ ์—†๋Š” ๋…ธ๋“œ, ํŠธ๋ฆฌ์˜ ์‹œ์ž‘ ๋…ธ๋“œ ( A )

  • ๊ฐ„์„ (edge, link) : ๋…ธ๋“œ์™€ ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„  (A,B), (A,C), ...

  • ์„œ๋ธŒํŠธ๋ฆฌ(subtree) : ํ•˜๋‚˜์˜ ๋…ธ๋“œ์™€ ๊ทธ ๋…ธ๋“œ์˜ ์ž์†์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ํŠธ๋ฆฌ

    • ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋งํฌ๋ฅผ ๋Š์–ด ์ƒ์„ฑ๋˜๋Š” ํŠธ๋ฆฌ์ด๋‹ค.

    • ๊ฐ ๋…ธ๋“œ๋Š” ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋งŒํผ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ ๊ฐ–๋Š”๋‹ค.

  • ํ˜•์ œ๋…ธ๋“œ(sbling node) : ๋ถ€๋ชจ๋…ธ๋“œ๊ฐ€ ๊ฐ™์€ ์ž์‹ ๋…ธ๋“œ๋“ค

    • B-C , D-E, F-G, H-I

  • ์กฐ์ƒ๋…ธ๋“œ( ancestor ) : ๊ฐ„์„ ์„ ๋”ฐ๋ผ ๋ฃจํŠธ ๋…ธ๋“œ ๊ฒฝ๋กœ์— ์žˆ๋Š” ๋ชจ๋“  ๋…ธ๋“œ๋“ค

    • H์˜ ์กฐ์ƒ๋…ธ๋“œ : D, B, A

  • ์ž์‹๋…ธ๋“œ( descendants ) : ์„œ๋ธŒํŠธ๋ฆฌ์— ์žˆ๋Š” ํ•˜์œ„ ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ

    • B์˜ ์ž์‹๋…ธ๋“œ : D, E, H, I, J

  • ๋ ˆ๋ฒจ(level) : ํŠธ๋ฆฌ์˜ ๊ฐ ์ธต์˜ ๋ฒˆํ˜ธ(๋ฃจํŠธ์˜ level์„ 0์œผ๋กœ ํ•˜๋Š” ๊ฒฝ์šฐ์™€ 1๋กœํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ์žˆ๋‹ค.)

  • ๊นŠ์ด(depth) : ๋ฃจํŠธ์—์„œ๋ถ€ํ„ฐ ๊ฑฐ๋ฆฌ

    • root์—์„œ๋ถ€ํ„ฐ ํ•ด๋‹น๋…ธ๋“œ๊นŒ์ง€์˜ edge or node ๊ฐœ์ˆ˜

  • ๋†’์ด(height) : ๋‹จ๋ง๋…ธ๋“œ์—์„œ ๋ถ€ํ„ฐ ๊ฑฐ๋ฆฌ

    • ๋…ธ๋“œ์˜ ๋†’์ด : ๋…ธ๋“œ์—์„œ ๋‹จ๋ง๋…ธ๋“œ์— ์ด๋ฅด๋Š” edge์˜ ๊ฐœ์ˆ˜

    • ํŠธ๋ฆฌ์˜ ๋†’์ด : ๊นŠ์ด ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’

      • Empty(null) tree์˜ height = -1 (์™œ๋ƒํ•˜๋ฉด height๋Š” ํฌ์ธํ„ฐ๊ฐ€ ์•„๋‹ˆ๋ผ ์ˆซ์ž๋กœ ํ‘œํ˜„ํ•˜๊ธฐ ๋•Œ๋ฌธ์—!)

      • Single-element tree์˜ height = 0

  • ์ฐจ์ˆ˜(degree) : ๋…ธ๋“œ๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜

    • A์˜ degree : 3 / B์˜ degree : 2

    • ํŠธ๋ฆฌ์˜ ์ฐจ์ˆ˜ : ํŠธ๋ฆฌ์— ์žˆ๋Š” ๋…ธ๋“œ์˜ ์ฐจ์ˆ˜ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’

  • ๋‹จ๋ง๋…ธ๋“œ(terminal, external, leaf node) : degree / height๊ฐ€ 0์ธ ๋…ธ๋“œ, ์ž์‹๋…ธ๋“œ๊ฐ€ ์—†๋Š” ๋…ธ๋“œ์ด๋‹ค.

  • ๋น„๋‹จ๋ง๋…ธ๋“œ(nonterminal, internal node) : ์ ์–ด๋„ ํ•˜๋‚˜์˜ ์ž์‹์„ ๊ฐ€์ง€๋Š” ๋…ธ๋“œ

  • ํฌ๋ฆฌ์ŠคํŠธ(forest) : ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์ง‘ํ•ฉ

    • ํŠธ๋ฆฌ A์—์„œ A๋ฅผ ์ œ๊ฑฐํ•˜๋ฉด ์ž์‹๋…ธ๋“œ B, C์— ๋Œ€ํ•œ ์„œ๋ธŒํŠธ๋ฆฌ๊ฐ€ ์ƒ๊ธฐ๊ณ , ์ด๋“ค์˜ ์ง‘ํ•ฉ์€ forest๊ฐ€๋œ๋‹ค.

Performance of Tree Operation

Operations

Times

size, isEmpty

O(1)

elements, nodes

O(n)

replace

O(1)

root, parent

O(1)

children(v)

O(Cv)

isInternal, isExternal, isRoot

O(1)

๋ชจ๋“  ์—ฐ์‚ฐ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” n๋ฒˆ ์ด๋‚ด์— ๋๋‚˜์„œ ์—„์ฒญ ๋น ๋ฅธ ๊ตฌ์กฐ์ด๋‹ค.

Non-Binary Tree

non-binary tree์˜ ๋…ธ๋“œ๋Š” element, parent node, children์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌ์กฐ์ด๋‹ค.

Binary Tree(์ด์ง„ ํŠธ๋ฆฌ)

์ž์‹์„ ์ตœ๋Œ€ 2๊ฐœ๋งŒ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํŠธ๋ฆฌ๋ฅผ ์ด์ง„ํŠธ๋ฆฌ(binary tree)๋ผ๊ณ ํ•œ๋‹ค.

  A                A
 /        !=          \
B                  B

๊ฐ’์ด ๊ฐ™๋”๋ผ๋„ ์™ผ์ชฝ ํŠธ๋ฆฌ์™€ ์˜ค๋ฅธ์ชฝ ํŠธ๋ฆฌ๋Š” ๋‹ค๋ฅธ ํŠธ๋ฆฌ๋กœ ๋ณธ๋‹ค.

  • ์ž์‹์ด ์ตœ๋Œ€ 2๊ฐœ์ด๋ฏ€๋กœ ๋ชจ๋“  ๋…ธ๋“œ์˜ degree๋Š” 2์ดํ•˜์ด๋‹ค. (=subtree ์ตœ๋Œ€ 2๊ฐœ)

  • ๊ตฌํ˜„์ด ํŽธ๋ฆฌํ•˜๋‹ค.

Decision tree / ์—ฐ์‚ฐ๋ฐฉ์‹ / Search์— ๋งŽ์ด ์‚ฌ์šฉ

Binary Tree ์„ฑ์งˆ

  • ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ n๊ฐœ์ด๋ฉด, ๊ฐ„์„ ์˜ ์ˆ˜๋Š” n-1๊ฐœ์ด๋‹ค.

  • ๋†’์ด(height)๊ฐ€ h์ธ ์ด์ง„ํŠธ๋ฆฌ์˜ ์ž์‹ ๋…ธ๋“œ ์ˆ˜

    • ์ตœ๋Œ€ 2^h -1

    • ์ตœ์†Œ h

  • n๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ์ด์ง„ํŠธ๋ฆฌ์˜ ๋†’์ด

    • ์ตœ๋Œ€ n

    • ์ตœ์†Œ log(n+1)

Binary Tree ์ข…๋ฅ˜

Full Binary Tree (= Proper binary tree)

๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ 0๊ฐœ ๋˜๋Š” 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” ํŠธ๋ฆฌ

Complete Binary Tree

๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•˜๊ณ  ๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์™„์ „ํžˆ ์ฑ„์›Œ์ ธ ์žˆ์œผ๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์˜ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๊ฐ€๋Šฅํ•œ ํ•œ ๊ฐ€์žฅ ์™ผ์ชฝ์— ์žˆ๋‹ค. ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ h์—์„œ 1๋ถ€ํ„ฐ 2h-1 ๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ๋˜ ๋‹ค๋ฅธ ์ •์˜๋Š” ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์˜ ์žŽ ๋…ธ๋“œ๊ฐ€ (์•„๋งˆ๋„ ๋ชจ๋‘) ์ œ๊ฑฐ๋œ ํฌํ™” ์ด์ง„ ํŠธ๋ฆฌ๋‹ค. ์–ด๋–ค ์ €์ˆ ์ž๋Š” ์™„์ „(complete)๋ผ๋Š” ์šฉ์–ด๋ฅผ ์‚ฌ์šฉํ•ด ์œ„์—์„œ ์ •์˜ํ•œ ํฌํ™” ์ด์ง„ ํŠธ๋ฆฌ ๋Œ€์‹ , ์ด๋Ÿฌํ•œ ์ข…๋ฅ˜์˜ ํŠธ๋ฆฌ๋ฅผ ๊ฑฐ์˜ ์™„์ „ํ•œ(almost complete) ์ด์ง„ ํŠธ๋ฆฌ ๋˜๋Š” ๋Œ€์ฒด๋กœ ์™„์ „ํ•œ(nearly complete) ์ด์ง„ ํŠธ๋ฆฌ๋ผ๊ณ  ํ•˜๋Š” ๊ฒฝ์šฐ๋„ ์žˆ๋‹ค. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•ด ํšจ์œจ์ ์œผ๋กœ ํ‘œํ˜„ ๊ฐ€๋Šฅํ•˜๋‹ค.(์œ„ํ‚คํ”ผ๋””์•„)

Perfect Binary Tree

๋ชจ๋“  ๋‚ด๋ถ€ ๋…ธ๋“œ๊ฐ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋ฉฐ ๋ชจ๋“  ์žŽ ๋…ธ๋“œ๊ฐ€ ๋™์ผํ•œ ๊นŠ์ด ๋˜๋Š” ๋ ˆ๋ฒจ์„ ๊ฐ–๋Š”๋‹ค.

Skewed Binary Tree

ํ•œ์ชฝ์œผ๋กœ ๊ธฐ์šธ์–ด์ง„ ํŠธ๋ฆฌ์ด๋‹ค.

Link ๋ฐฉ๋ฒ• ๊ตฌํ˜„

#include <stdio.h>
#include <stdlib.h>
#define MAX(a,b) (((a)>(b))?(a):(b))

typedef struct node{
    int data;
    struct node *left, *right;
}Node;

Node * new_node(int data){
    Node * new = (Node *)malloc(sizeof(Node));
    new->data = data;
    new->left = NULL;
    new->right = NULL;

    return new;
}

height

int get_height(Node * node){
    int height = -1;

    if(node!=NULL)height = 1 + MAX(get_height(node->left),get_height(node->right));

    return height;
}

๋…ธ๋“œ ์ˆ˜

int get_node_count(Node * node){
    int count = 0;
    if(node!=NULL)count = 1 + get_node_count(node->left)+get_node_count(node->right);
    return count;
}

๋…ธ๋“œ data์˜ ํ•ฉ + ๊ณผ์ •

int calc_direc_size(Node *node, char *s)
{
    int left_size=0, right_size=0;
    printf("%s ",s);
    if (node==NULL) { printf("    NULL return \n");return 0;}
    else {
        printf("    node : %d \n", node->data);
        left_size += calc_direc_size(node->left,"left");
        right_size += calc_direc_size(node->right,"right");

        return (node->data +left_size + right_size);
    }
}

๋…ธ๋“œ์˜ level

int node_level(Node *node, int key, int level)
{
    int downlevel;

    if (node == NULL)return -1;

    // node์˜ ๋ฐ์ดํ„ฐ ์ฐพ๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฐ™๋‹ค๋ฉด level์„ ๋ฆฌํ„ดํ•ด์ค€๋‹ค.
    if (node->key == key) return level;

    // tree์˜ ์™ผ์ชฝ ๋…ธ๋“œ level์ด ๋‚ด๋ ค๊ฐˆ ์ˆ˜๋ก +1์”ฉ ํ•ด์ค€ํ›„ ๊ทธ ๊ฐ’์„ ์ €์žฅ ๋ฆฌํ„ด
    downlevel = node_level(node->left, key, level+1);
    if (downlevel != -1) return downlevel;
    // tree์˜ ์˜ค๋ฅธ์ชฝ ๋…ธ๋“œ level์ด ๋‚ด๋ ค๊ฐˆ ์ˆ˜๋ก +1์”ฉ ํ•ด์ค€ํ›„ ๊ทธ ๊ฐ’์„ ์ €์žฅ
    downlevel = node_level(node->right, key, level+1);
    return downlevel;
}

ํŠธ๋ฆฌ์˜ ํ‘œํ˜„

ํŠธ๋ฆฌ์˜ ๋ถ€๋ชจ๋งŒ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹

ํŠธ๋ฆฌ์˜ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๋ถ€๋ชจ๋ฅผ ํ•˜๋‚˜ ๋˜๋Š” 0๊ฐœ๋งŒ ๊ฐ€์ง€๊ธฐ ๋•Œ๋ฌธ์— ๋ถ€๋ชจ๋งŒ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋‹ค.

i

1

2

3

4

5

6

7

8

9

parent[i]

0

-1

1

-1

3

1

-1

6

3

  • ์žฅ์  : ํ•œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ๋ฐ”๋กœ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.

  • ๋‹จ์  : ์ž์‹๋…ธ๋“œ๋ฅผ ์ฐพ๊ธฐ ํž˜๋“ค๋‹ค.

๋ฐฐ์—ด ํ‘œํ˜„(์ด์ง„ ํŠธ๋ฆฌ)

์ด์ง„ ํŠธ๋ฆฌ์˜ ๊ฒฝ์šฐ์—๋Š” ๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ถ€๋ชจ์˜ ๋…ธ๋“œ๊ฐ€ x์ธ ๊ฒฝ์šฐ์— ์ž์‹๋…ธ๋“œ๋Š” ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ (2*x, 2*x+1) ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด๋œ๋‹ค. (์ฃผ์˜์‚ฌํ•ญ index๋Š” 1๋ถ€ํ„ฐ ์‹œ์ž‘!ํ•œ๋‹ค๋Š” ์ ์„ ์ฃผ์˜ํ•ด์•ผํ•œ๋‹ค.)

๋…ธ๋“œ x์˜ ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค๋Š” x/2๋กœ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

๋‹ค์Œ (a)์˜ ์ด๋ฏธ์ง€์ฒ˜๋Ÿผ ํ•œ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ์žˆ์„ ๋•Œ 5๊ฐœ์˜๋…ธ๋“œ๋ฅผ ์ €์žฅํ•˜๊ธฐ์œ„ํ•ด์„œ ๋ฐฐ์—ด ํฌ๊ธฐ๊ฐ€ 10์ด ํ•„์š”ํ•˜๋ฏ€๋กœ ๋น„ํšจ์œจ์ ์ด๋‹ค.

์ด๋Ÿฐ ๊ฒฝ์šฐ๋Š” ์•„๋ž˜์™€ ๊ฐ™์€ perfect binary ํŠธ๋ฆฌ์—์„œ ํšจ์œจ์ ์ด๋‹ค.

์ด์ฐจ์›๋ฐฐ์—ด

A[i][0] = i์˜ ์™ผ์ชฝ ์ž์‹
A[i][1] = i์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹

๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ €์žฅํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฐ ๊ฒฝ์šฐ๋Š” ๋งŽ์ด ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.

Link

ํฌ์ธํ„ฐ๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ถ€๋ชจ๋…ธ๋“œ๊ฐ€ ์ž์‹๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

Tree Traversal(ํŠธ๋ฆฌ์˜ ์ˆœํšŒ)

ํŠธ๋ฆฌ์˜ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ์ˆœ์„œ์ด๋‹ค.

Preorder(์ „์œ„ ์ˆœํšŒ)

  1. ๋…ธ๋“œ ๋ฐฉ๋ฌธ(pre)

  2. ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

  3. ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

ํ”„๋ฆฌ ์˜ค๋”๋Š” ๊ทธ๋ž˜ํ”„์˜ DFS์™€ ์ˆœ์„œ๊ฐ€ ๊ฐ™๋‹ค.

Inorder(์ค‘์œ„์ˆœํšŒ)

  1. ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

  2. ๋…ธ๋“œ ๋ฐฉ๋ฌธ(in)

  3. ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

Binary Search Tree์—์„œ Delete ๊ตฌํ˜„์‹œ ์ฃผ๋กœ ์‚ฌ์šฉ

Postorder(ํ›„์œ„์ˆœํšŒ)

  1. ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

  2. ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒ ํŠธ๋ฆฌ ํ”„๋ฆฌ์˜ค๋”

  3. ๋…ธ๋“œ ๋ฐฉ๋ฌธ(post)

file ๋“œ๋ผ์ด๋ธŒ์—์„œ ๋“œ๋ผ์ด๋ธŒ ์šฉ๋Ÿ‰์„ ๊ณ„์‚ฐํ•  ๋•Œ ์‚ฌ์šฉ๋˜๋Š” ๋ฐฉ๋ฒ•

์ด์ง„ํŠธ๋ฆฌ๊ฐ€ ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” preorder์™€ postorder๋งŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

Binary Tree Traversal ๊ตฌํ˜„

linked list

void preorder(Node * node){
    if (node == NULL)
        return;

    printf("%d ", node->data);
    preorder(node->left);
    preorder(node->right);
}

void inorder(Node * node)
{
    if (node == NULL)
        return;

    inorder(node->left);
    printf("%d ", node->data);
    inorder(node->right);
}


void postorder(Node * node){
    if (node == NULL)
        return;

    postorder(node->left);
    postorder(node->right);
    printf("%d ", node->data);
}

์ฒซ์งธ ์ค„์—๋Š” ์ด์ง„ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N(1โ‰คNโ‰ค26)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ ๋…ธ๋“œ์™€ ๊ทธ์˜ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ, ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋…ธ๋“œ์˜ ์ด๋ฆ„์€ A๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์˜๋ฌธ์ž ๋Œ€๋ฌธ์ž๋กœ ๋งค๊ฒจ์ง€๋ฉฐ, ํ•ญ์ƒ A๊ฐ€ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๋œ๋‹ค. ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” .์œผ๋กœ ํ‘œํ˜„๋œ๋‹ค.

#include <iostream>
using namespace std;
int A[26][2];

void preorder(int x){
    if(x==-1) return;
    cout << char(x+'A');
    preorder(A[x][0]);
    preorder(A[x][1]);
}
void inorder(int x){
    if(x==-1) return;
    inorder(A[x][0]);
    cout << char(x+'A');
    inorder(A[x][1]);
}
void postorder(int x){
    if(x==-1) return;
    postorder(A[x][0]);
    postorder(A[x][1]);
    cout << char(x+'A');
}

int main(int argc, const char * argv[]) {
    int n; //๋…ธ๋“œ์˜ ์ˆ˜
    scanf("%d",&n);

    while(n--){
        char node, left, right;
        cin>>node>>left>>right;
        node -= 'A';
        if(left == '.'){
            A[node][0]=-1;
        }else{
            A[node][0]=left-'A';
        }

        if(right == '.'){
            A[node][1]=-1;
        }else{
            A[node][1]=right-'A';
        }
    }

    preorder(0);
    printf("\n");
    inorder(0);
    printf("\n");
    postorder(0);
    printf("\n");

}

ํŠธ๋ฆฌ์˜ ํƒ์ƒ‰

ํŠธ๋ฆฌ๋Š” ์‚ฌ์ดํด์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„์ด๊ธฐ ๋•Œ๋ฌธ์— ์ž„์˜์˜ ๋‘ ์ •์  ์‚ฌ์ด์˜ ๊ฒฝ๋กœ๋Š” 1๊ฐœ์ด๋‹ค. ๋”ฐ๋ผ์„œ BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด์„œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ฃจํŠธ ์—†๋Š” ํŠธ๋ฆฌ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ๋•Œ, ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ๋ฅผ 1์ด๋ผ๊ณ  ์ •ํ–ˆ์„ ๋•Œ, ๊ฐ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

  • ์ž…๋ ฅ : ์ฒซ์งธ ์ค„์— ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N (2 โ‰ค N โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N-1๊ฐœ์˜ ์ค„์— ํŠธ๋ฆฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋œ ๋‘ ์ •์ ์ด ์ฃผ์–ด์ง„๋‹ค.

  • ์ถœ๋ ฅ : ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N-1๊ฐœ์˜ ์ค„์— ๊ฐ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ ๋ฒˆํ˜ธ๋ฅผ 2๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
vector<int> a[100000];
bool check[100000];
int depth[100000];
int parent[100000];

void bfs(){
    queue<int> q;
    depth[1]=0;parent[1]=0;
    check[1]=true;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for(int y : a[x]){
            if (check[y] == false) {
                depth[y]=depth[x]+1;
                check[y] = true;
                parent[y]=x;
                q.push(y);
            }
        }
    }

}
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    bfs();

    for(int i=2;i<=n;i++){
        printf("%d\n",parent[i]);
    }
    return 0;
}

์ฐธ๊ณ ์ž๋ฃŒ

non-binary tree search and insertion - Stack Overflow
representation of treeรฌย—ย รซยŒย€รญย•ยœ รฌยยดรซยฏยธรฌยงย€ รชยฒย€รฌยƒย‰รชยฒยฐรชยณยผ

๊ทธ๋ž˜ํ”„( )์˜ ๊ฒฝ์šฐ์—๋Š” DFS์™€ BFS ๊ฐ€ ์žˆ์—ˆ๋‹ค. ํŠธ๋ฆฌ์—์„œ๋„ ๋‘ ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ํŠธ๋ฆฌ์—์„œ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” 3๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค. ์„ธ ๋ฐฉ๋ฒ•์˜ ์ฐจ์ด๋Š” ๋…ธ๋“œ ๋ฐฉ๋ฌธ์„ ์–ธ์ œ ํ•˜๋ƒ์˜ ์ฐจ์ด ์ด๋‹ค.

ํŠธ๋ฆฌ์˜ ํƒ์ƒ‰์€ DFS/BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด์„œ ํ•  ์ˆ˜ ์žˆ๋‹ค. ( ์ฐธ์กฐ)

11. Graph
2์ฐจ์› ๋ฐฐ์—ด
13. DFS์™€ BFS
ํŠธ๋ฆฌ์˜ ๋ถ€๋ชจ์ฐพ๊ธฐ
https://www.geeksforgeeks.org/