๐Ÿ“š
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
  • ์šฉ์–ด
  • ๊ทธ๋ž˜ํ”„์˜ ํ‘œํ˜„
  • ์ธ์ ‘ ํ–‰๋ ฌ(adjacency matrix)
  • ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ(adjacency list)
  • ๊ฐ„์„  ๋ฆฌ์ŠคํŠธ
  • ์ฐธ์กฐํŽ˜์ด์ง€

Was this helpful?

  1. Algorithm

Graph

PreviousQueueNextTree

Last updated 4 years ago

Was this helpful?

๊ทธ๋ž˜ํ”„๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ผ์ข…์œผ๋กœ ์ •์ (Node, Vertex)๊ณผ ๊ฐ„์„ (Edge)๋กœ ์ด๋ฃจ์–ด์ ธ์žˆ๋‹ค. ๊ฐ„์„ ์€ ์ •์ ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ๋‚˜ํƒ€๋‚ด๋ฉฐ, ์ •์  ์‚ฌ์ด๋ฅผ ์—ฐ๊ฒฐํ•œ๋‹ค.

G = (V,E) ๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค.

์ผ์ƒ์ƒํ™œ์—์„œ ๊ทธ๋ž˜ํ”„๋ฅผ ์˜ˆ๋กœ ๋“ค์–ด๋ณด๋ฉด,

  1. ์ง€ํ•˜์ฒ  ์—ญ : ์ •์  / ์—ญ์‚ฌ์ด : ๊ฐ„์„ 

  2. ๊ต์ฐจ๋กœ : ์ •์  / ๋„๋กœ : ๊ฐ„์„ 

  3. ํŽ˜์ด์Šค๋ถ ์‚ฌ๋žŒ : ์ •์  / ํŒ”๋กœ์šฐ : ๊ฐ„์„ 

์ด ์žˆ๋‹ค.

๋น„์„ ํ˜•๊ตฌ์กฐ๋ž€ i๋ฒˆ์งธ ์›์†Œ๋ฅผ ํƒ์ƒ‰ํ•œ ๋‹ค์Œ ๊ทธ ์›์†Œ์™€ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ์›์†Œ๋ฅผ ํƒ์ƒ‰ํ•˜๋ ค๊ณ  ํ•  ๋•Œ, ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์›์†Œ๊ฐ€ ์กด์žฌํ•˜๋Š” ํƒ์ƒ‰๊ตฌ์กฐ๋ฅผ ๋งํ•œ๋‹ค. ๊ทธ๋ž˜ํ”„ ๋„ ๋น„์„ ํ˜• ๊ตฌ์กฐ์ด๋‹ค.

์šฉ์–ด

  • ๋…ธ๋“œ(Node) or ์ •์ (Vertex)

  • ๊ฐ„์„ (Edge) or ๋งํฌ(link): ์ •์ ๊ฐ„์˜ ๊ด€๊ณ„

  • ๊ฒฝ๋กœ(Path) : ์ •์  A์—์„œ B๋กœ๊ฐ€๋Š” ๊ฒฝ๋กœ

    • ์ž๋™์ฐจ ๋„ค๋น„๊ฒŒ์ด์…˜ ๋น ๋ฅธ๊ธธ ์ฐพ๊ธฐ(์ตœ๋‹จ ๊ฒฝ๋กœ)

  • ์‚ฌ์ดํด(Cycle) or ํšŒ๋กœ : ์ •์  A์—์„œ ๋‹ค์‹œ A๋กœ ๋Œ์•„์˜ค๋Š” ๊ฒฝ๋กœ (์‹œ์ž‘ ๋…ธ๋“œ == ๋„์ฐฉ ๋…ธ๋“œ)

  • ๋‹จ์ˆœ ๊ฒฝ๋กœ์™€ ๋‹จ์ˆœ ์‚ฌ์ดํด : ๊ฐ™์€ ์ •์ ์„ ๋‘๋ฒˆ ์ด์ƒ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š๋Š” ๊ฒฝ๋กœ/์‚ฌ์ดํด

    • ์ผ๋ฐ˜์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ๋กœ์™€ ์‚ฌ์ดํด์€ ๋‹จ์ˆœ ๊ฒฝ๋กœ/์‚ฌ์ดํด์ด๋‹ค.

  • Directed Graph(๋ฐฉํ–ฅ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„)

  • Undirected Graph(๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„ ) == Bidirection Graph(์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„)

    • A-E๋Š” Aโ†’E์™€ Eโ†’A๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.

    • ์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋Š” ๋ชจ๋‘ Directed Graph๋กœ ๋ณ€๊ฒฝํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๋‹ค.

    • ์ผ๋ฐ˜์ ์œผ๋กœ ๊ทธ๋ž˜ํ”„๋ผํ•˜๋ฉด ๋ฐฉํ–ฅ์ด์—†๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ๋งํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

  • Multiple Edge : ๋‘ ์ •์  ์‚ฌ์ด์— ๊ฐ„์„ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ผ ์ˆ˜๋„ ์žˆ๋‹ค.

    • a-c๋Š” ์—ฐ๊ฒฐํ•˜๋Š” ๊ฐ„์„ ์ด 2๊ฐœ์ด๋‹ค.

    • ๋‘ ๊ฐ„์„ ์€ ์„œ๋กœ ๋‹ค๋ฅธ ๊ฐ„์„ ์ด๋‹ค.

  • Loop(๋ฃจํ”„) : ๊ฐ„์„ ์˜ ์–‘ ๋ ์ ์ด ๊ฐ™์€ ๊ฒฝ์šฐ(4๋ฒˆ)

  • ๊ฐ€์ค‘์น˜(Weight) : ๊ฐ„์„ ์— ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ์ด๋‹ค.

    • ์ด๋™ ๊ฑฐ๋ฆฌ, ์ด๋™ํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„, ํ•„์š”ํ•œ ๋น„์šฉ ๋“ฑ๋“ฑ๋“ฑ

    • ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” 1์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๋ฉด๋œ๋‹ค.

  • ์ฐจ์ˆ˜(degree) : ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜์ด๋‹ค.

    • ์œ„์˜ ๊ฐ€์ค‘์น˜ ๊ทธ๋ฆผ์œผ๋กœ ์˜ˆ๋ฅผ ๋“ค์–ด๋ณด์ž๋ฉด

      • 1์˜ ์ฐจ์ˆ˜ : 2

      • 2์˜ ์ฐจ์ˆ˜ : 4

    • Directed Graph์˜ ๊ฒฝ์šฐ์—๋Š” ์ฐจ์ˆ˜๊ฐ€ ๋‘๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.

      • in-degree(์ •์ ์œผ๋กœ ๋“ค์–ด์˜ค๋Š” ๊ฐ„์„ ์˜ ์ˆ˜)

      • out-degree(์ •์ ์—์„œ ๋‚˜๊ฐ€๋Š” ๊ฐ„์„ ์˜ ์ˆ˜)

๊ทธ๋ž˜ํ”„์˜ ํ‘œํ˜„

๊ทธ๋ž˜ํ”„์˜ ํ‘œํ˜„์€ ๊ทธ๋ž˜ํ”„๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค. ์ด๋•Œ ์ •์ ์˜ ์ˆ˜๋Š” ์ •์ˆ˜๋กœ ์ €์žฅํ•˜๊ฒŒ ๋˜๊ณ , ๊ฐ„์„ ์€ ์ •์  ์‚ฌ์ด์˜ ๊ด€๊ณ„๋ฅผ ์ €์žฅํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๊ฐ„์„ ์„ ์ €์žฅํ•˜๋Š” ๊ฒƒ์ด ๊ทธ๋ž˜ํ”„๋ฅผ ์ €์žฅํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

๋ณดํ†ต ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์—์„œ๋Š” ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜(n)๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜(m)์„ ์ž…๋ ฅ ๋ฐ›๊ณ  ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜๋งŒํผ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ๊ฐ„์„ ์˜ ์ •๋ณด๋ฅผ ์ž…๋ ฅ ๋ฐ›๋Š”๋‹ค.

// ์–‘๋ฐฉํ–ฅ์ธ ๊ฒฝ์šฐ
5 6
A B
A E
B D
C D
C E
D E

๋ฐฉํ–ฅ์ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๋ผ๋ฉด ์ธ์ ‘ํ–‰๋ ฌ์€ ๋น„๋Œ€์นญ์ด๋‹ค.

์ธ์ ‘ ํ–‰๋ ฌ(adjacency matrix)

๊ทธ๋ž˜ํ”„์—์„œ ์ •์ (node)๊ณผ ๊ฐ„์„ (edge)๋“ค์˜ ์—ฐ๊ฒฐ๊ด€๊ณ„๋ฅผ ์ •์‚ฌ๊ฐ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„ํ•œ ๊ฒƒ์ด๋‹ค.

๊ทธ๋ž˜ํ”„ G = (V, E)๋ฅผ n >= 1(n์€ ์ •์ ์ด ์ˆ˜)์˜ ์ •์ ์˜ ๊ฐ€์ง„ ๊ทธ๋ž˜ํ”„๋ผ๊ณ  ํ•˜์˜€์„ ๋•Œ ๊ทธ๋ž˜ํ”„ G์— ๋Œ€ํ•œ ์ธ์ ‘ํ–‰๋ ฌ์˜ ํฌ๊ธฐ๋Š” n * n์ด๋ฉฐ a[n, n] ํฌ๊ธฐ์˜ 2์ฐจ์› ๋ฐฐ์—ด๋กœ ํ‘œํ˜„๋œ๋‹ค. ์ด๋•Œ a[n, n]์—์„œ a[i, j] โˆˆ E(G)๋ผ๋ฉด 1๊ฐ’์„ ์•„๋‹ˆ๋ผ๋ฉด 0์˜ ๊ฐ’์„ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค.

๊ฐ€์ค‘์น˜ ์—†๋Š” ๊ฒฝ์šฐ

์ •์ ์˜ ๊ฐœ์ˆ˜๋ฅผ V๊ฐœ๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, V*V ํฌ๊ธฐ์˜ ์ด์ฐจ์› ๋ฐฐ์—ด์„ ์ด์šฉํ•œ๋‹ค.

// i์—์„œ j๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์ด ์žˆ์„ ๋•Œ
A[i][j] = 1
// i์—์„œ j๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์ด ์—†์„ ๋•Œ
A[i][j] = 0
//์œ„์˜ ์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(B)
0 1 0 0 1
1 0 0 1 0
0 0 0 1 1
0 1 1 0 1
1 0 1 1 0
  • Undirected Graph ์—์„œ๋Š” A[i][j] == A[j][i] ์ด๋‹ค.

  • ์—†๋Š” ๊ฐ„์„ ๋„ ์ €์žฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ž˜ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.(์‰ฌ์šด ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ์‚ฌ์šฉ)

#include <cstdio>

int a[10][10];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;
         scanf("%d %d",&u,&v);
        a[u][v]=a[v][u]=1; // ์–‘๋ฐฉํ–ฅ
        //๋‹จ๋ฐฉํ–ฅ์ธ ๊ฒฝ์šฐ์—๋Š” a[u][v]=1;๋งŒ ํ•ด์ฃผ๋ฉด๋œ๋‹ค.
    }
}

๊ฐ€์ค‘์น˜ ์žˆ๋Š” ๊ฒฝ์šฐ

๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ์„ ๊ฒฝ์šฐ์—๋Š” ๊ฐ€์ค‘์น˜๋„ ๊ฐ™์ด ์ €์žฅํ•ด์ฃผ๋ฉด๋œ๋‹ค.

// i์—์„œ j๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์ด ์žˆ์„ ๋•Œ
A[i][j] = w
// i์—์„œ j๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์ด ์—†์„ ๋•Œ
A[i][j] = 0

๋งŒ์•ฝ ๊ฐ€์ค‘์น˜๊ฐ€ 0<=w์ผ ๊ฒฝ์šฐ์—๋Š” ๊ฐ„์„ ์ด ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ ์ €์žฅํ•ด์ฃผ๋ฉด๋œ๋‹ค.

ํ•˜์ง€๋งŒ ๊ฐ€์ค‘์น˜์˜ ๋ฒ”์œ„๊ฐ€ ์ •์ˆ˜๋ผ๋ฉด! 1. ๊ฐ„์„ ์˜ ์กด์žฌ ์—ฌ๋ถ€(1,0)๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด 2. ๊ฐ€์ค‘์น˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด ์„ ์กฐํ•ฉํ•ด์„œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

//์œ„์˜ ์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„
0 6 0 0 1
6 0 0 8 0
0 0 0 2 3
0 8 2 0 4
1 0 3 4 0
#include <cstdio>

int a[10][10];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v,w;
         scanf("%d %d %d",&u,&v,&w);
        a[u][v]=a[v][u]=w;
    }
}

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

  • O(V^2)

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

  • ์–ด๋–ค ๋…ธ๋“œ v์— ์ธ์ ‘ํ•œ ๋ชจ๋“  ๋…ธ๋“œ ์ฐพ๊ธฐ O(n)์‹œ๊ฐ„

  • ์–ด๋–ค ์—์ง€(u,v)๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ๊ฒ€์‚ฌ O(1)

์ธ์ ‘ ๋ฆฌ์ŠคํŠธ(adjacency list)

์ธ์ ‘ํ–‰๋ ฌ์€ ํ‘œํ˜„ํ•  ๋•Œ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์•˜๋˜ ๋ถ€๋ถ„๊นŒ์ง€ ๋ชจ๋‘ ํ‘œํ˜„์ด ๋œ๋‹ค. (์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ๋ถ€๋ถ„์„ 0์œผ๋กœ ํ‘œํ˜„ํ•œ๋‹ค.) ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•  ๋•Œ์—๋„ 0๊นŒ์ง€ ๋ชจ๋‘ ์กฐ์‚ฌ๋ฅผ ํ•ด์•ผํ•˜๋ฏ€๋กœ ํšจ์œจ์ด ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์€๋ฐ ์ธ์ ‘๋ฆฌ์ŠคํŠธ๋Š” ์ด๋Ÿฌํ•œ ๋‹จ์ ์„ ๊ทน๋ณตํ•œ๋‹ค.

๊ฐ€์ค‘์น˜ ์—†๋Š” ๊ฒฝ์šฐ(c++)

linked list๋ฅผ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•œ๋‹ค. ์ด ๋•Œ A[i]๋Š” i์™€ ์—ฐ๊ฒฐ๋œ ์ •์ ์„ linked list๋กœ ํฌํ•จํ•˜๊ณ  ์žˆ๋‹ค.(i์™€ ์—ฐ๊ฒฐ๋œ ์ •์ ์ด ์ด ๋ช‡๊ฐœ์ธ์ง€ ์•Œ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.)

A[1] B E
A[2] A D
A[3] D E
A[4] B C E
A[5] A C D

์ด๋•Œ ์—ฐ๊ฒฐ๋œ ์ •์ ์„ ์ €์žฅํ•˜๋ฏ€๋กœ ๊ฐ„์„ ์„ ๋‚˜ํƒ€๋‚ด๊ฒŒ ๋œ๋‹ค. ๋ชจ๋“  ๊ฐ„์„ ์ด ํ•œ๋ฒˆ ์”ฉ ์ €์žฅ(O(E)=๊ฐ„์„ ์˜ ์ˆ˜)๋œ๋‹ค.

vector๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ

๊ทธ๋Ÿฐ๋ฐ, linked list๋Š” ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ์‹œ๊ฐ„์ด ์˜ค๋ž˜๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์—, ์ฃผ๋กœ vector์™€ ๊ฐ™์ด ๊ธธ์ด๋ฅผ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฐ์—ด์„ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•œ๋‹ค.

#include <cstdio>
#include <vector>
using namespace std;
vector<int> a[10];

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

์ฃผ์˜ํ• ์ ์ด ํ•œ๊ฐ€์ง€ ์žˆ๋‹ค. cpp์—์„œ vector์˜ ํ‘œํ˜„์— ์ฃผ์˜ํ•ด์•„ํ•œ๋‹ค.

  • vector<int> a(10) ์€ ํฌ๊ธฐ๊ฐ€ 10์ธ 1์ฐจ์› ๋ฐฐ์—ด์„ ์˜๋ฏธํ•œ๋‹ค. (=int a[10])

  • vector<int> a[10] ์€ int a๋ฐฐ์—ด์ด 10๊ฐœ๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

#include <cstdio>
#include <vector>
using namespace std;

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

๊ฐ€์ค‘์น˜ ์—†๋Š” ๊ฒฝ์šฐ(c)

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int vertext;
    struct node * next;
}Node;


typedef struct graph{
    int num_vertex; //vertex ์ˆ˜
    Node ** adjList;
}Graph;

Node * new_node(int v){
    Node * new = (Node *)malloc(sizeof(Node));
    new->vertext = v;
    new->next = NULL;
    return new;
}

Graph * create_graph(int verNum){
    Graph * g = (Graph *)malloc(sizeof(Graph));
    g->num_vertex = verNum;

    // verNum๊ฐœ์˜ ์ •์ ์„ ๊ฐ€์ง€๋Š” ์ธ์ ‘๋ฆฌ์ŠคํŠธ
    g->adjList = malloc(verNum*sizeof(Node));
    for(int i=0;i<verNum;i++)g->adjList[i] = NULL;
    return g;
}

void add_edge(Graph * g, int src, int dest){
    // src์—์„œ dest๋กœ๊ฐ€๋Š” edge ์ถ”๊ฐ€
    Node * new = new_node(dest);
    new->next = g->adjList[src];
    g->adjList[src] = new;

    // dest์—์„œ src๋กœ ๊ฐ€๋Š” edge์ถ”๊ฐ€
    new = new_node(src);
    new->next = g->adjList[dest];
    g->adjList[dest] = new;

}

void print_graph(Graph * g){
    int v;
    for(v=0;v<g->num_vertex;v++){
        Node * tmp = g->adjList[v];
        printf("์ธ์ ‘๋ฆฌ์ŠคํŠธ %d ์ •์ \n",v);
        while(tmp){
            printf(" -> %d",tmp->vertext);
            tmp=tmp->next;
        }
        printf("\n");
    }
}
int main(int argc, const char * argv[]) {
    Graph* graph = create_graph(6);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 2);
    add_edge(graph, 1, 2);
    add_edge(graph, 1, 4);
    add_edge(graph, 1, 3);
    add_edge(graph, 2, 4);
    add_edge(graph, 3, 4);
    add_edge(graph, 4, 6);
    add_edge(graph, 5, 1);
    add_edge(graph, 5, 6);

    print_graph(graph);

    return 0;
}
์ธ์ ‘๋ฆฌ์ŠคํŠธ 0 ์ •์ 
 -> 2 -> 1
์ธ์ ‘๋ฆฌ์ŠคํŠธ 1 ์ •์ 
 -> 5 -> 3 -> 4 -> 2 -> 0
์ธ์ ‘๋ฆฌ์ŠคํŠธ 2 ์ •์ 
 -> 4 -> 1 -> 0
์ธ์ ‘๋ฆฌ์ŠคํŠธ 3 ์ •์ 
 -> 4 -> 1
์ธ์ ‘๋ฆฌ์ŠคํŠธ 4 ์ •์ 
 -> 6 -> 3 -> 2 -> 1
์ธ์ ‘๋ฆฌ์ŠคํŠธ 5 ์ •์ 
 -> 6 -> 1

๊ฐ€์ค‘์น˜ ์žˆ๋Š” ๊ฒฝ์šฐ

A[1] (B,6) (E,1)
A[2] (A,1) (D,8)
A[3] (D,2) (E,3)
A[4] (B,8) (C,2) (E,4)
A[5] (A,1) (C,3) (D,4)
#include <cstdio>
#include <vector>
using namespace std;

vector<pair<int,int>> a[10];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
;
    for(int i=0;i<m;i++){
        int u,v,w;
         scanf("%d %d %d",&u,&v,&w);
        a[u].push_back(make_pair(v,w);
        a[v].push_back(make_pair(u,w);
    }
}

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

  • O(E)

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

  • ์–ด๋–ค ๋…ธ๋“œ v์— ์ธ์ ‘ํ•œ ๋ชจ๋“  ๋…ธ๋“œ ์ฐพ๊ธฐ O(degree(v))

  • ์–ด๋–ค ์—ฃ์ง€(u,v)๊ฐ€ ์กด์žฌํ•˜๋Š” ์ง€ ๊ฒ€์‚ฌ O(degree(u))

๊ฐ„์„  ๋ฆฌ์ŠคํŠธ

STL, array list๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ๊ฐ„์„ ๋ฆฌ์ŠคํŠธ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ฐ„์„ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐฐ์—ด์„ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•˜๋ฉฐ, ๊ฐ„์„ ์„ ๋ชจ๋‘ ์ €์žฅํ•œ๋‹ค.

  • ์•ž ์ •์ ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ

E[0] = A B
E[1] = A E
E[2] = B A
E[3] = B D
E[4] = C D
E[5] = C E
E[6] = D B
E[7] = D C
E[8] = D E
E[9] = E A
E[10] = E C
E[11] = E D
  • ๊ฐ ๊ฐ„์„ ์˜ ์•ž ์ •์ ์„ ๊ธฐ์ค€์œผ๋กœ ๊ฐœ์ˆ˜๋ฅผ ์„ผ๋‹ค.

i

0

1

2

3

4

5

cnt[i]

0

2

2

2

3

3

  • ๊ฐ ์ •์ ์˜ ๊ฐ„์„ ์ˆ˜์˜ ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•œ๋‹ค.

i

0

1

2

3

4

5

cnt[i]

0

2

4

6

9

12

  • i๋ฒˆ๊ณผ ์—ฐ๊ฒฐ๋œ ๊ฐ„์„ ์€ E[cnt[i-1]]๋ถ€ํ„ฐ E[cnt[i]-1]๊นŒ์ง€ ์ด๋‹ค.

    • 3๋ฒˆ๊ณผ ์—ฐ๊ฒฐ๋œ ๊ฐ„์„ ์€ E[4]~E[6-1]๊นŒ์ง€

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

  • O(E)

์ฐธ์กฐํŽ˜์ด์ง€

std::vector()๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ฐ„๋‹จํ•˜๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ( )์ด๋•Œ ์ธ์ ‘ํ–‰๋ ฌ๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๊ณต๊ฐ„์„ ์ ๊ฒŒ ์‚ฌ์šฉํ•œ๋‹ค. ๊ฐ ์ •์ ์—์„œ ์—ฐ๊ฒฐ๋˜๋Š” ๋ฆฌ์ŠคํŠธ์˜ ์ˆœ์„œ๋Š” ์ค‘์š”ํ•˜์ง€ ์•Š๋‹ค.

A[i]๋Š” i์™€ ์—ฐ๊ฒฐ๋œ ์ •์ ๊ณผ ๊ทธ ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋ฅผ linked list๋กœ ํฌํ•จํ•œ๋‹ค. ์ด๋•Œ vector ์ปจํ…Œ์ด๋„ˆ์˜ ํƒ€์ž…์œผ๋กœ pair๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.( )

vector ์•Œ์•„๋ณด๊ธฐ
pair ์•Œ์•„๋ณด๊ธฐ
https://kingpodo.tistory.com/46