๐Ÿ“š
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
  • DFS (๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)
  • ๋ฐฑํŠธ๋ž˜ํ‚น(Backtracking)
  • ํƒ์ƒ‰๊ณผ์ •
  • ์žฅ๋‹จ์ 
  • ๊ตฌํ˜„
  • BFS (๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)
  • ํƒ์ƒ‰๊ณผ์ •
  • Queue
  • ๊ตฌํ˜„
  • ์‹œ๊ฐ„๋ณต์žก๋„
  • DFS vs BFS
  • ๋ฌธ์ œํ’€์–ด๋ณด๊ธฐ
  • DFS์™€ BFS
  • DFS
  • flood_fill
  • n-queen

Was this helpful?

  1. Algorithm

DFS์™€ BFS

Previous์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ(Binary Search Tree)Next๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Dijkstra's Algorithm)

Last updated 4 years ago

Was this helpful?

ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณผ ๊ฒƒ์ด๋‹ค. ๊ทธ๋ž˜ํ”„์˜ ํƒ์ƒ‰์˜ ๋ชฉ์ ์€ ๋ชจ๋“  ์ •์ ์„ 1๋ฒˆ์”ฉ ๋ฐฉ๋ฌธ ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

DFS (๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)

๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์€ ํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋งŒํผ ๊นŠ์ด๊ฐ€๊ธฐ๋•Œ๋ฌธ์— ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ DFS ํƒ์ƒ‰๋ฐฉ๋ฒ•์—์„œ๋Š” ์Šคํƒ(stack)์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•œ๋‹ค.

๋ฐฑํŠธ๋ž˜ํ‚น(Backtracking)

ํƒ์ƒ‰ ๊ณผ์ •์—์„œ ๋ฌดํ•œํžˆ ๊นŠ์ด๊ฐ€๋Š” ๊ฒƒ์„ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด์„œ ๊นŠ์ด์ œํ•œ(depth bound)์„ ๋‘”๋‹ค. depth bound์— ๋„๋‹ฌํ•  ๋•Œ๊นŒ์ง€ ๋ชฉํ‘œ(๋…ธ๋“œ)๊ฐ€ ๋ฐœ๊ฒฌ๋˜์ง€ ์•Š์œผ๋ฉด ๊ทธ ์ „์— ํƒ์ƒ‰ํ•œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ๋˜๋Œ์•„์˜จ๋‹ค. ์ด๋ ‡๊ฒŒ ๋˜๋Œ์•„ ์˜ค๋Š” ๊ณผ์ •์„ ๋ฐฑํŠธ๋ž˜ํ‚น(Backtracking)์ด๋ผ ํ•œ๋‹ค.

ํƒ์ƒ‰๊ณผ์ •

์ตœ๋Œ€ํ•œ ๊นŠ์ˆ™ํžˆ ๋งŽ์€๊ฒƒ์„ ํƒ์ƒ‰ํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋ฉฐ, ์Šคํƒ์„ ์‚ฌ์šฉํ•œ๋‹ค.

  • ์Šคํƒ์„ ์ด์šฉํ•ด ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋งŒํผ ์ตœ๋Œ€ํ•œ ๋งŽ์ด๊ฐ€๊ณ , ๊ฐˆ ์ˆ˜ ์—†์œผ๋ฉด ์ด์ „ ์ •์ ์œผ๋กœ ๋Œ์•„์˜จ๋‹ค.(๋ฐฑํŠธ๋ž™ํ‚น)

  • ๋ฐฉ๋ฌธํ•œ ๊ณณ์€ ํ‘œ์‹œ๋ฅผ ํ•ด๋‘”๋‹ค.(check[i] )

  • ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๊ณณ์€ ๊ฑด๋„ˆ๋„๊ณ , ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณณ์œผ๋กœ ๊ฐ„๋‹ค. ์Šคํƒ์ด ๋น„์›Œ์งˆ ๋•Œ๊นŒ์ง€ ๊ณ„์† pop์„ ํ•œ๋‹ค. ์Šคํƒ์ด ๋น„์–ด์žˆ์œผ๋ฉด DFSํƒ์ƒ‰์ด ์ข…๋ฃŒ๋œ๋‹ค.

์žฅ๋‹จ์ 

์žฅ์ 

  • ํ˜„์žฌ ๊ฒฝ๋กœ์ƒ์˜ ๋…ธ๋“œ๋“ค๋งŒ ๊ธฐ์–ตํ•˜๋ฉด ๋˜๋ฏ€๋กœ ์ €์žฅ๊ณต๊ฐ„์˜ ์†Œ์š”๊ฐ€ ๋น„๊ต์  ์ ๋‹ค.

  • ๋ชฉํ‘œ๋…ธ๋“œ๊ฐ€ ๊นŠ์€ ๋‹จ๊ณ„์— ์žˆ์„ ๊ฒฝ์šฐ์— ํ•ด๋ฅผ ๋นจ๋ฆฌ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๋‹จ์ 

  • ํ•ด๊ฐ€ ์—†๋Š” ๊ฒฝ๋กœ์— ๋„ˆ๋ฌด ๊นŠ์ด ๋น ์ง€๊ฒŒ ๋  ๊ฐ€๋Šฅ์„ฑ์ด ์ž‡๋‹ค. ๋”ฐ๋ผ์„œ ์‹ค์ œ ๊ฒฝ์šฐ์—๋Š” ๋ฏธ๋ฆฌ ์ง€์ •ํ•œ ์ž„์˜์˜ ๊นŠ์ด(depth bound)๊นŒ์ง€๋งŒ ํƒ์ƒ‰ํ•˜๊ณ  ๋ชฉํ‘œ๋…ธ๋“œ๋ฅผ ๋ฐœ๊ฒฌํ•˜์ง€ ๋ชปํ•˜๋ฉด ๋‹ค์Œ ๊ฒฝ๋กœ๋ฅผ ๋”ฐ๋ผ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด ์œ ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

  • ์–ป์–ด์ง„ ๊ฒฝ๋กœ๊ฐ€ ์ตœ๋‹จ ๊ฒฝ๋กœ๊ฐ€ ์•„๋‹ ์ˆ˜ ์žˆ๋‹ค. ๋ชฉํ‘œ๊นŒ์ง€์˜ ๊ฒฝ๋กœ๊ฐ€ ์—ฌ๋Ÿฌ๊ฐœ์ธ ๋ฌธ์ œ์— ๋Œ€ํ•ด์„œ DFS๋Š” ๋ชฉํ‘œ์— ๋„๋‹ฌํ•˜๋ฉด ํƒ์ƒ‰์„ ์ข…๋ฃŒํ•˜๋ฏ€๋กœ, ์ด๋•Œ ์ฐพ์€ ๊ฒฝ๋กœ๋Š” ์ตœ์ ์˜ ๊ฒฝ๋กœ๊ฐ€ ์•„๋‹ ์ˆ˜ ์žˆ๋‹ค.

๊ตฌํ˜„

๊ทธ๋ž˜ํ”„๊ฐ€ disconnected์ด๊ฑฐ๋‚˜ ํ˜น์€ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋ผ๋ฉด DFS์— ์˜ํ•ด์„œ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ๋‹ค.

์Šˆ๋„์ฝ”๋“œ

 DFS(G, v)
    visited[v] <- yes
    for each node adjacent to x do                                                                        
        if visited[v] = NO then
            DFS(G, u);
    end
end

์ธ์ ‘ํ–‰๋ ฌ ๊ตฌํ˜„

dfs(x)๋Š” x๋ฅผ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. ์žฌ๊ท€ ํ˜ธ์ถœ์„ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

void dfs(int x){
    check[x] = true; //๋ฐฉ๋ฌธํ•œ ๊ฒƒ ํ‘œ์‹œ
    printf("%d ",x);
    //๋‹ค์Œ ์ •์  ๋ฐฉ๋ฌธ
    for(int i=1;i<=n;i++){
        //๊ฐ„์„ ์ด ์žˆ๊ณ , ๋ฐฉ๋ฌธ์„ ํ•˜์ง€ ์•Š์•˜์„ ๊ฒฝ์šฐ
        if(a[x][i]==1 && check[i]==false) dfs(i);
    }
}
//์ธ์ ‘ํ–‰๋ ฌ ๋ฐฑํŠธ๋ฆญํ‚น ๊ธฐ๋ฒ•
//๋ฐ˜๋ณต๋ฌธ n^2๋ฒˆ ์‹คํ–‰
bool visited[101];
void dfs(int k)
{
    for(int i=0;i<=n;i++)
        if(G[k][i] && !visited[G[k][i]])
        {
            visited[G[k][i]]=true;
            dfs(G[k][i]);
        }
    return;
}
  • ์‹œ๊ฐ„๋ณต์žก๋„ : V*O(V) = O(V^2)

์ธ์ ‘๋ฆฌ์ŠคํŠธ ์‚ฌ์šฉ

ํ•ญ์ƒ ์žˆ๋Š” ๊ฐ„์„ ๋งŒ ์ €์žฅํ•œ๋‹ค.

void dfs(int x){
    check[x] = true; //๋ฐฉ๋ฌธํ•œ ๊ฒƒ ํ‘œ์‹œ
    printf("%d ",x);
    //๋‹ค์Œ ์ •์  ๋ฐฉ๋ฌธ
    // a[x]๋Š” x์™€ ์—ฐ๊ฒฐ๋œ ์ •์ ์ด๋‹ค.
    for(int i=1;i<a[x].size();i++){
        int y = a[x][i];
        if(check[y]==false)dfs(y);
    }
}
//์ธ์ ‘๋ฆฌ์ŠคํŠธ ๋ฐฑํŠธ๋ž™ํ‚น ๊ธฐ๋ฒ•
//๋ฐ˜๋ณต๋ฌธ m๋ฒˆ์‹คํ–‰
bool visited[101];
void dfs(int k)
{
    for(int i=0;i<G[i].size();i++)
        if(!visited[G[k][i].to])
        {
            visited[G[k][i].to]=true;
            dfs(G[k][i]);
        }
    return;
}
  • ๋ชจ๋“  ์ •์ ์„ ํ•œ๋ฒˆ์”ฉ ๊ฑฐ์น˜๊ณ  ๋ชจ๋“  ๊ฐ„์„ ์„ ํ•œ๋ฒˆ์”ฉ ๊ฒ€์‚ฌํ•˜๊ฒŒ ๋œ๋‹ค.

  • ์‹œ๊ฐ„๋ณต์žก๋„ O(V+E)

BFS (๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)

ํ˜„์žฌ ์ •์ ์—์„œ ๊นŠ์ด๊ฐ€ 1์ธ ์ •์ ์„ ๋ชจ๋‘ ํƒ์ƒ‰ํ•œ ๋’ค ๊นŠ์ด๋ฅผ ๋Š˜๋ ค๊ฐ€๋Š” ๋ฐฉ์‹์ด๋‹ค. ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰์€ ๋ฐฑํŠธ๋ž™์„ ํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋Œ€์‹ ์— ํ˜„์žฌ ์ •์ ์—์„œ ๊นŠ์ด๊ฐ€ 1์ธ ์ •์ ์„ ๋ชจ๋‘ ๋ฐฉ๋ฌธํ•ด์•ผํ•˜๋ฏ€๋กœ ํ(queue)๋ผ๋Š” FIFO(First In First Out)์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•ด ํ˜„์žฌ ์ •์ ์—์„œ ๊นŠ์ด๊ฐ€ 1 ๋” ๊นŠ์€ ๋ชจ๋“  ์ •์ ์„ ์ˆœ์ฐจ์ ์œผ๋กœ ํ์— ์ €์žฅํ•ด ํƒ์ƒ‰์— ํ™œ์šฉํ•œ๋‹ค.

std::queue()๋ฅผ ํ™œ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ตํž ํ•„์š”๊ฐ€ ์žˆ๋‹ค.

BFS๋ฅผ ํ•˜๋ฉด์„œ ๊ฐ ๋…ธ๋“œ์— ๋Œ€ํ•ด์„œ ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

ํƒ์ƒ‰๊ณผ์ •

  • L0 = {s}, s๋Š” ์ถœ๋ฐœ ๋…ธ๋“œ

  • L1 = L0์˜ ๋ชจ๋“  ์ด์›ƒ ๋…ธ๋“œ๋“ค

  • L2 = L1์—์„œ ๋ชจ๋“  ์ด์›ƒ๋“ค ์ค‘ L0์— ์†ํ•˜์ง€ ์•Š๋Š” ๋…ธ๋“œ๋“ค

  • ...

  • LN = Ln์—์„œ ๋ชจ๋“  ์ด์›ƒ๋“ค ์ค‘ Ln-1์— ์†ํ•˜์ง€ ์•Š๋Š” ๋…ธ๋“œ๋“ค

๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ˆœ์„œ๋กœ ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

Queue

์ตœ๋Œ€ํ•œ ๋„“๊ฒŒ ๊ฐ€๋Š”๊ธธ์„ ํƒ์ƒ‰ํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋ฉฐ, ํ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. ํ๋ฅผ ์ด์šฉํ•ด์„œ ์ง€๊ธˆ ์œ„์น˜์—์„œ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์„ ๋ชจ๋‘ ํ์— ๋„ฃ๋Š” ๋ฐฉ์‹์ด๋‹ค.

  • BFS๋Š” ํ์— ๋„ฃ์„ ๋•Œ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ์ฒดํฌ(check[i])ํ•ด์•ผํ•œ๋‹ค.

    • ํ์—์„œ popํ•œ ๋…ธ๋“œ๋“ค ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋ชจ๋“  ์ด์›ƒ ๋…ธ๋“œ๋ฅผ ํ์— ๋„ฃ์œผ๋ฉด์„œ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ์ฒดํฌํ•ด์ค€๋‹ค.

    • Queue๊ฐ€ ๋นŒ๋•Œ๊นŒ์ง€ ์ง„ํ–‰ํ•ด์ค€๋‹ค.

๊ตฌํ˜„

๊ทธ๋ž˜ํ”„๊ฐ€ disconnected์ด๊ฑฐ๋‚˜ ํ˜น์€ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋ผ๋ฉด BFS์— ์˜ํ•ด์„œ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ๋‹ค.

์Šˆ๋„์ฝ”๋“œ

BFS(G, s)// ๊ทธ๋ž˜ํ”„ G์™€ ์ถœ๋ฐœ ๋…ธ๋“œ s
    Q <- รธ; // ํ๋ฅผ ํ•˜๋‚˜ ์ƒ์„ฑ
    Enqueue(Q,s);
    while Q!=รธ do
        u <- Dequeue(Q)
        for each v adjacent to u do                                                                     
            if v is unvisited then
                mark v is visited;
                Enqueue(Q,v);
            end;
        end;
    end;

์ธ์ ‘ ํ–‰๋ ฌ

queue<int> q;
check[1]= true;
q.push(1);
while(!q.empty()){
    int x = q.front;
    q.pop();
    printf("%d ",x);
    //๋‹ค์Œ ์ •์ ์„ ์ฐพ๊ธฐ
    for(int i=1;i<=n;i++){
        if(a[x][i]==1&&check[i]==false){
            check[i]=true;
            q.push(i);
        }
    }
}
//์ธ์ ‘ํ–‰๋ ฌ
bool visited[101];

void bfs(int k)
{
    std::queue<int> Q;
    Q.push(k), visited[k]=1;
    while(!Q.empty())
    {
        int current = Q.front();Q.pop();
        for(int i=0;i<G[current].size();i++)
            if(G[current][i]&&!vistited[G[current][i]])
            {
                visited[G[current][i]]=1;
                Q.push(G[current][i]);
            }
    }
}

์ „์ฒด ํƒ์ƒ‰ํ•˜๋Š”๋ฐ ์žˆ์–ด์„œ ๋ฐ˜๋ณต๋ฌธ์„ n^2๋ฒˆ ์‹คํ–‰ํ•˜๊ฒŒ๋œ๋‹ค.

  • ์‹œ๊ฐ„๋ณต์žก๋„ O(V^2)

์ธ์ ‘ ๋ฆฌ์ŠคํŠธ

queue<int> q;
check[1]= true;
q.push(1);
while(!q.empty()){
    int x = q.front;
    q.pop();
    printf("%d ",x);
    //๋‹ค์Œ ์ •์ ์„ ์ฐพ๊ธฐ
    for(int i=1;i<a[x].size;i++){
        int y = a[x][i];
        if(check[y]==false){
            check[y]=true;
            q.push(i);
        }
    }
}
//์ธ์ ‘๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ–ˆ์„ ๊ฒฝ์šฐ
#include <queue>
bool visited[101];

void bfs(int k)
{
    std::queue<int> Q;
    Q.push(k), visited[k]=1;
    while(!Q.empty())
    {
        int current = Q.front();Q.pop();
        for(int i=0;i<G[current].size();i++)
            if(!vistited[G[current][i]])
            {
                visited[G[current][i]]=1;
                Q.push(G[current][i]);
            }
    }
}

์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐ ์žˆ์–ด์„œ ๋ฐ˜๋ณต๋ฌธ์„ m๋ฒˆ ์‹คํ–‰ํ•˜๊ฒŒ ๋œ๋‹ค.

์ตœ๋‹จ ๊ฒฝ๋กœ

  • ์ž…๋ ฅ : ๋ฐฉํ–ฅ ํ˜น์€ ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ G(V,E), ๊ทธ๋ฆฌ๊ณ  ์ถœ๋ฐœ๋…ธ๋“œ s

  • ์ถœ๋ ฅ : ๋ชจ๋“  ๋…ธ๋“œ v์— ๋Œ€ํ•ด์„œ

    • d[v] = s๋กœ๋ถ€ํ„ฐ v๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ธธ์ด(์—ฃ์ง€์˜ ์ˆ˜)

    • ฯ€[v] = s๋กœ๋ถ€ํ„ฐ v๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ์ƒ์—์„œ v์˜ ์ง์ „ ๋…ธ๋“œ(predecessor)

BFS(G, s)// ๊ทธ๋ž˜ํ”„ G์™€ ์ถœ๋ฐœ ๋…ธ๋“œ s
    Q <- รธ;
    d[v]<-0;
    ฯ€[v]<-null;
    Enqueue(Q,s);
    while Q!=รธ do
        u <- Dequeue(Q)
        for each v adjacent to u do                                                                      
            if v is unvisited then //์ผ๋ฐ˜์ ์œผ๋กœ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ฒƒ์€ -1๋กœ ๋„ฃ์–ด๋‘๊ณ  ๊ตฌํ•œ๋‹ค.
                mark v is visited;
                d[v]<-d[u]+1;
                ฯ€[v]<-u;
                Enqueue(Q,v);
            end;
        end;
    end;
// ์ตœ๋‹จ๊ฒฝ๋กœ ์ถœ๋ ฅ
PRINT-PATH(G,s,v)
    if v=s then
        print s;
    else if ฯ€[v] = null then
        print "no path from s to v exists";                                                               
    else
        PRINT-PATH(G,s,ฯ€[v]);
        print v;
    end.

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

  • ์‹œ๊ฐ„๋ณต์žก๋„ O(V+E)

DFS vs BFS

DFS

BFS

๋™์ž‘ ์›๋ฆฌ

์Šคํƒ

ํ

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

์žฌ๊ท€

ํ ์ž๋ฃŒ๊ตฌ์กฐ ์ด์šฉ

๋ฌธ์ œํ’€์–ด๋ณด๊ธฐ

๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ์™€ BFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋Š” ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ , ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ์—†๋Š” ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์ด๋‹ค.

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

using namespace std;
vector<int> a[1001];
bool check[1001];


void dfs(int node) {
    check[node] = true;
    printf("%d ",node);
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    //memset์€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ดˆ๊ธฐํ™” ํ•˜๋Š” ํ•จ์ˆ˜
    //1๋ฒˆ ํŒŒ๋ผ๋ฏธํ„ฐ๋Š” ๊ฐ’์„ ๋ณต์‚ฌํ•  ๊ณณ์ด๊ณ , 2๋ฒˆ ํŒŒ๋ผ๋ฏธํ„ฐ๋Š” ์ดˆ๊ธฐํ™”ํ•  ๊ฐ’, ๋งˆ์ง€๋ง‰์€ ์–ผ๋งˆ๋งŒํผ์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ดˆ๊ธฐํ™” ํ•  ๊ฒƒ์ธ์ง€ ํ•˜๋Š” ํฌ๊ธฐ์ด๋‹ค.
    memset(check,false,sizeof(check));
    check[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        printf("%d ",node);
        for (int i=0; i<a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}
int main() {
    int n, m, start;
    scanf("%d %d %d",&n,&m,&start);
    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);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    dfs(start);
    puts("");
    bfs(start);
    puts("");
    return 0;
}

DFS

flood_fill

์ง€๋ขฐ์ฐพ๊ธฐ, ๋ฟŒ์š”๋ฟŒ์š” ๋“ฑ ๊ฒŒ์ž„์—์„œ ๋งŽ์ด ํ™œ์šฉ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜. ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰์„ ๊ตฌํ˜„ํ•œ๋‹ค. ํ•˜์ง€๋งŒ ์žฌ๊ท€์˜ ๊นŠ์ด๊ฐ€ ๋„ˆ๋ฌด ์ปค์ง€๋ฉด runtime error๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค. ๊นŠ์ด๊ฐ€ ๋„ˆ๋ฌด ํฌ๋‹ค๊ณ  ํŒ๋‹จ๋˜๋ฉด ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰์œผ๋กœ ์ฒ˜๋ฆฌํ•˜๊ฑฐ๋‚˜ ์žฌ๊ท€๋Œ€์‹  ์Šคํƒ์„ ์ด์šฉํ•œ๋‹ค.

dfsํ•จ์ˆ˜ ๋ถ€๋ถ„์˜ 4๋ฐฉํ–ฅ ํƒ์ƒ‰์„ dx,dy๋ฅผ ์ด์šฉํ•ด ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ๋‹ค.

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

void dfs(int a, int b, int c)
{
    A[a][b]=c;
    for(int i=0;i<4;i++)
        if(safe(a+dx[i],b+dy[i])&&A[a+dx[i]][b+dy[i]]==1)
            dfs(a+dx[i],b+dy[i],c);
}

n-queen

n*n์ฒด์Šค ๋ณด๋“œํŒ์— n๊ฐœ์˜ queen์„ ์„œ๋กœ ๊ณต๊ฒฉํ•˜์ง€ ๋ชปํ•˜๋„๋ก ๋ฐฐ์น˜ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋‚ด๋Š” ๋ฌธ์ œ. ๋Œ€๊ฐ์„  ๊ฒ€์‚ฌํ•˜๋ฉด์„œ ๊ฐ€์•ผํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์œ ์šฉํ•˜๋‹ค.

  • ํ€ธ์€ 8๋ฐฉํ–ฅ์œผ๋กœ ๋ชจ๋‘ ๊ณต๊ฒฉํ•  ์ˆ˜ ์žˆ๋‹ค.

    1. ์ฒซ ๋ฒˆ์งธ ํ–‰, ์ฒซ ๋ฒˆ์งธ ์—ด์— ํ€ธ์„ ๋†“๋Š”๋‹ค.

    2. ๋‹ค์Œ ํ–‰์—์„œ ๊ฐ€๋Šฅํ•œ ๊ฐ€์žฅ ์™ผ์ชฝ ์—ด์— ํ€ธ์„ ๋†“๋Š”๋‹ค.

    3. n๋ฒˆ์งธ ์—ด์— ๋” ์ด์ƒ ํ€ธ์„ ๋†“์„ ์ˆ˜ ์—†๋‹ค๋ฉด ๋ฐฑํŠธ๋ž™ํ•œ๋‹ค.

    4. ๋งˆ์ง€๋ง‰ ํ–‰์— ํ€ธ์„ ๋†“์œผ๋ฉด ํ•˜๋‚˜์˜ ํ•ด๋ฅผ ๊ตฌํ•œ ๊ฒƒ์ด๋‹ค.

    5. ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ์กฐ์‚ฌํ•  ๋•Œ๊นŒ์ง€ ๋ฐฑํŠธ๋ž˜ํ‚นํ•ด๊ฐ€๋ฉฐ ํ•ด๋“ค์„ ๊ตฌํ•œ๋‹ค.

๊นŠ์ด์šฐ์„ ํƒ์ƒ‰์„ ํ•˜๋ฉฐ ํ•ด๋ฅผ ๊ตฌํ•  ๋•Œ๋งˆ๋‹ค ์นด์šดํŠธํ•ด ์›ํ•˜๋Š” ํ•ด๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. ์—ด๊ณผ ๋Œ€๊ฐ์„ ๋งŒ ๊ฒ€์‚ฌํ•˜๋ฉด ๋œ๋‹ค. ๋Œ€๊ฐ์„ ์€ ํ–‰+์—ด ์œ„์น˜์— ์ฒดํฌํ•ด ๊ธฐ์šธ๊ธฐ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋Œ€๊ฐ์„  ์ƒ์— ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š”์ง€ ์—†๋Š”์ง€ ํ™•์ธํ•œ๋‹ค. ๊ธฐ์šธ๊ธฐ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋Œ€๊ฐ์„ ์€ ํ–‰๊ณผ ์—ด์˜ ์ฐจ๊ฐ€ ์ผ์ •ํ•˜๋‹ค. n+(ํ–‰-์—ด)์˜ ์œ„์น˜์— ์ฒดํฌ. ๋ฐฑํŠธ๋ž™ ์‹œ์— ๊ฐ€์žฅ ์ค‘์š”ํ•œ ์ ์€ ์ฒดํฌ๋ฐฐ์—ด์— ๊ธฐ๋กํ•ด ๋‘์—ˆ๋˜ ์ฒดํฌ๋ฅผ ๋ชจ๋‘ ํ•ด์ œํ•ด์•ผํ•œ๋‹ค.

DFS์™€ BFS