๐Ÿ“š
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
  1. Algorithm

AVL

PreviousMazeNext์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ(Binary Search Tree)

Last updated 4 years ago

Was this helpful?

CtrlK
  • ์‹œ๊ฐ„ ๋ณต์žก๋„
  • Rotation
  • LL
  • LR
  • RR
  • RL
  • ๊ตฌํ˜„
  • height
  • Right Rotation
  • Left Rotation
  • balance
  • ์‚ฝ์ž…
  • ์‚ญ์ œ

Was this helpful?

AVL ํŠธ๋ฆฌ๋Š” Balanced Binary Search Tree์ด๋‹ค. AVL ํŠธ๋ฆฌ๋Š” ๊ฐ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค ์™ผ์ชฝ, ์˜ค๋ฅธ์กฑ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด ์ฐจ์ด์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ๊ฐ€์ง€๊ณ  ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด ์ฐจ์ด๊ฐ€ 1๋ณด๋‹ค ํฌ์ง€์•Š๋‹ค๋Š” ์„ฑ์งˆ์„ ๊ฐ€์ง„๋‹ค.(์œ„ํ‚คํ”ผ๋””์•„ )

์ฆ‰, ์–‘์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด ์ฐจ์ด๊ฐ€ 1์ดํ•˜์ด๋‹ค.

๊ท ํ˜•์žกํžŒ AVL ํŠธ๋ฆฌ๋Š” n๊ฐœ์˜ ์›์†Œ๊ฐ€ ์žˆ์„ ๋•Œ O(logn)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋กœ ๊ฒ€์ƒ‰, ์‚ฝ์ž…, ์‚ญ์ œ๋ฅผ ํ•  ์ˆ˜ ์žˆ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

ํ‰๊ท 

์ตœ์•…์˜ ๊ฒฝ์šฐ

๊ณต๊ฐ„

O(n)

O(n)

๊ฒ€์ƒ‰

O(logn)

O(logn)

์‚ฝ์ž…

O(logn)

O(logn)

์‚ญ์ œ

O(logn)

O(logn)

Rotation

ํŠธ๋ฆฌ์˜ ์žฌ๊ตฌ์„ฑ ์ž‘์—…์„ Rotation(ํšŒ์ „)์ด๋ผ๊ณ  ํ•œ๋‹ค.

LL

         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

y๋Š” z์˜ ์™ผ์ชฝ ์ž์‹, x๋Š” y์˜ ์™ผ์ชฝ ์ž์‹์ด๋‹ค. ์ด๋•Œ T1, T2, T3, T4๋Š” ๊ฐ๊ฐ์˜ ์„œ๋ธŒํŠธ๋ฆฌ์ด๋‹ค.

z์˜ ์˜ค๋ฅธ์กฑ ์ž์‹๊ณผ ์™ผ์ชฝ ์ž์‹์ด ๋ถˆ๊ท ํ˜•ํ•˜๋ฏ€๋กœ right Rotation ํ•œ๋ฒˆ์œผ๋กœ ๊ท ํ˜•์„ ์žก์•„์ค„ ์ˆ˜ ์žˆ๋‹ค.

if (bal > 1 && key < node->left->key) return right_rotate(node);

LR

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

y๋Š” z์˜ ์™ผ์ชฝ ์ž์‹, x๋Š” y์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์ด๋‹ค. ์ด๋Ÿฌํ•œ ๊ฒฝ์šฐ์—๋Š” ํšŒ์ „์„ ๋‘๋ฒˆ์‹œ์ผœ์ค˜์•ผํ•œ๋‹ค. ์šฐ์„  y๋ฅผ ์™ผ์ชฝ ํšŒ์ „์„ ํ•œ๋ฒˆ ์‹œ์ผœ์ฃผ๊ณ  z๋ฅผ ์˜ค๋ฅธ์ชฝ ํšŒ์ „์‹œ์ผœ์ฃผ๋ฉด ๊ท ํ˜•์ด ์žกํžˆ๊ฒŒ ๋œ๋‹ค.

if (bal > 1 && key > node->left->key){
    node->left =  left_rotate(node->left);
    return right_rotate(node);
}

RR

 z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

y๋Š” z์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์ด๊ณ , x๋Š” y์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์ด๋‹ค. ์ด๋Ÿฌํ•œ ๊ฒฝ์šฐ๋Š” LL๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ํ•œ๋ฒˆ์˜ rotation์œผ๋กœ ๊ท ํ˜•์„ ์žก์„ ์ˆ˜ ์žˆ๋‹ค.

if (bal < -1 && key > node->right->key) return left_rotate(node);

RL

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

y๋Š” z์˜ ์˜ค๋ฅธ์ชฝ์ž์‹, x๋Š” y์˜ ์™ผ์ชฝ ์ž์‹์ด๋‹ค .์ด๋Ÿฌํ•œ ๊ฒฝ์šฐ๋Š” ์œ„์˜ LR๊ณผ ์ • ๋ฐ˜๋Œ€์ธ ๊ฒฝ์šฐ์ด๋‹ค. ์ด ๋•Œ๋Š” ์˜ค๋ฅธ์ชฝ ํšŒ์ „ ํ›„ ์™ผ์ชฝ ํšŒ์ „์„ ํ•˜๋ฉด ๊ท ํ˜•์„ ๋งž์ถœ ์ˆ˜ ์žˆ๋‹ค.

if (bal < -1 && key < node->right->key){
    node->right = right_rotate(node->right);
    return left_rotate(node);
}

๊ตฌํ˜„

typedef struct node{
    int key;
    struct node * left, *right;
    int height; // ๋†’์ด
}Node;

Node * new_node(int key){
    Node * new = (Node *)malloc(sizeof(Node));
    new->key = key;
    new->height = 0; //์ƒˆ๋กœ์šด ๋…ธ๋“œ๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ๋‹จ๋ง ๋…ธ๋“œ์˜ height๋ฅผ ๊ฐ€์ง„๋‹ค.
    new->left = new->right = NULL;
    return new;
}

height

int height(Node * node){
    if(node == NULL) return -1;
    return node->height;
}

Right Rotation

/*
         z                                      y(l) 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z(node)
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3(r) T4
    / \
  T1   T2

*/
Node * right_rotate(Node * node){
    Node * l = node->left;
    Node * r = l->right;

    l->right = node;
    node->left = r;

    node->height = 1+MAX(height(node->left),height(node->right));
    l->height = 1+MAX(height(l->left),height(l->right));

    return l;
}

Left Rotation

/*
 z                                 y(r)
 /  \                            /     \ 
T1   y     Left Rotate(z)       z(node)  x
    /  \   - - - - - - - ->    / \      / \
   T2   x                     T1 T2(l) T3  T4
       / \
     T3  T4
*/

Node * left_rotate(Node * node){
    Node * r = node->right;
    Node * l = r->left;

    r->left = node;
    node->right =l;

    node->height = 1+MAX(height(node->left),height(node->right));
    r->height = 1+MAX(height(r->left),height(r->right));

    return r;
}

balance

int balance(Node * node){
    if(node == NULL) return 0;
    // ์–‘์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด๋ฅผ ๋น„๊ตํ•œ๋‹ค.
    return height(node->left)-height(node->right);
}

์‚ฝ์ž…

์œ„์˜ Rotation์„ ์ด์šฉํ•ด์„œ ์‚ฝ์ž…์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

  1. ์šฐ์„  BST์˜ ์‚ฝ์ž…๊ณผ ๊ฐ™์ด ์‚ฝ์ž…ํ•œ๋‹ค.

  2. ํ˜„์žฌ์˜ height๊ฐ’์„ updateํ•ด์ค€๋‹ค.

  3. balanceํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.(-1๋ฏธ๋งŒ 1์ดˆ๊ณผ ๋ถˆ๊ท ํ˜•)

  4. ๋ถˆ๊ท ํ˜•ํ•˜๋‹ค๋ฉด LL, LR, RR, RL ์˜ ๊ฐ๊ฐ์˜ ๊ฒฝ์šฐ์— ๋งž๊ฒŒ rotationํ•ด์ค€๋‹ค.

Node * insert(Node * node, int key){

    // 1. ๋จผ์ € Binary Search Tree์˜ ์‚ฝ์ž…๊ณผ ๊ฐ™์ด ์‚ฝ์ž…ํ•œ๋‹ค.
    if (node == NULL)
        return(new_node(key));

    if (key < node->key)node->left  = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    else return node; //๊ฐ’์ด ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” BST์˜ ์‚ฝ์ž…๊ณผ ๊ฐ™์ง€ ์•Š๊ณ  ๋ฐ”๋กœ ๋ฆฌํ„ดํ•ด์ค€๋‹ค.

    // 2. height๊ฐ’์„ ๋ณ€๊ฒฝํ•ด์ค€๋‹ค.
    node->height = 1 + MAX(height(node->left),height(node->right));

    // 3. balanceํ•œ์ง€ ํ™•์ธ์„ ํ•œ๋‹ค.(-1๋ฏธ๋งŒ 1์ดˆ๊ณผ๋ฉด ๋ถˆ๊ท ํ˜•)
    int bal = balance(node);

    // 4. ๋ถˆ๊ท ํ˜•ํ•œ ๊ฒฝ์šฐ์— rotation!
    // LL
    if (bal > 1 && key < node->left->key) return right_rotate(node);

    // RR
    if (bal < -1 && key > node->right->key) return left_rotate(node);

    // LR ๋‘๋ฒˆํšŒ์ „(left->right)
    if (bal > 1 && key > node->left->key){
        node->left =  left_rotate(node->left);
        return right_rotate(node);
    }

    // RL
    if (bal < -1 && key < node->right->key){
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }

    return node;
}

์‚ญ์ œ

  1. ์šฐ์„  BST์˜ ์‚ญ์ œ์™€ ๊ฐ™์ด ์‚ญ์ œํ•˜๋‹ค.

  2. ํ˜„์žฌ ๋…ธ๋“œ๋Š” ๋ฐ˜๋“œ์‹œ ์‚ญ์ œ๋…ธ๋“œ์˜ ์กฐ์ƒ๋…ธ๋“œ ์ค‘ ํ•˜๋‚˜์—ฌ์•ผํ•œ๋‹ค.

  3. ํ˜„์žฌ์˜ height๊ฐ’์„ updateํ•ด์ค€๋‹ค.

  4. balanceํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.(-1๋ฏธ๋งŒ 1์ดˆ๊ณผ ๋ถˆ๊ท ํ˜•)

  5. ๋ถˆ๊ท ํ˜•ํ•˜๋‹ค๋ฉด LL, LR, RR, RL ์˜ ๊ฐ๊ฐ์˜ ๊ฒฝ์šฐ์— ๋งž๊ฒŒ rotationํ•ด์ค€๋‹ค.

Node* delete(Node* root, int key){
    Node * tmp;

    // 1. BST ์‚ญ์ œ
    if (root == NULL) return root;
    if ( key < root->key )root->left = delete(root->left, key);
    else if( key > root->key ) root->right = delete(root->right, key);
    else{// ํ‚ค๊ฐ’์ด ๊ฐ™์œผ๋ฉด ๊ทธ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œ
        if(root->left == NULL || root->right == NULL){
            if(root->left!=NULL)tmp = root->left;
            else tmp =root->right;

            // ์ž์‹์ด ์—†๋Š” ๊ฒฝ์šฐ
            if (tmp == NULL){
                tmp = root;
                root = NULL;
            }
            else *root = *tmp; // ์ž์‹์ด ํ•œ๊ฐœ์ธ ๊ฒฝ์šฐ

            free(tmp);
        }else{//์ž์‹์ด ๋‘๊ฐœ์ธ ๊ฒฝ์šฐ

            tmp = min(root->right);
            root->key = tmp->key;
            root->right = delete(root->right, tmp->key);
        }
    }

    // ์‚ญ์ œ ํ›„์— root๊ฐ€ NULL์ธ๊ฒฝ์šฐ
    if (root == NULL) return root;

    // ํ˜„์žฌ height๋ฅผ updateํ•ด์ค€๋‹ค.
    root->height = 1 + MAX(height(root->left),height(root->right));

    // balance ๊ฐ’์„ ๊ฐ€์ ธ์˜จ๋‹ค.
    int bal = balance(root);

    // ๋ถˆ๊ทœ์น™ํ•œ ๊ฒฝ์šฐ
    // LL
    if (bal > 1 && balance(root->left) >= 0)
        return right_rotate(root);

    // LR
    if (bal > 1 && balance(root->left) < 0){
        root->left =  left_rotate(root->left);
        return right_rotate(root);
    }

    // RR
    if (bal < -1 && balance(root->right) <= 0)
        return left_rotate(root);

    // RL
    if (bal < -1 && balance(root->right) > 0){
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }

    return root;
}