πŸ“š
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
  • Overlapping Subproblem
  • Optimal Substructure
  • λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°
  • Top-down
  • Bottom-up
  • μ‹€μŠ΅
  • 1둜 λ§Œλ“€κΈ°
  • 2Xn 타일링
  • 2xn 타일링 2
  • 1,2,3 λ”ν•˜κΈ°
  • λΆ•μ–΄λΉ΅ νŒλ§€ν•˜κΈ°
  • μ‰¬μš΄ 계단 수
  • 였λ₯΄λ§‰ 수
  • 이친수
  • μŠ€ν‹°μ»€
  • ν¬λ„μ£Όμ‹œμ‹
  • κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄
  • κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄
  • κ°€μž₯ κΈ΄ 바이토닉 λΆ€λΆ„ μˆ˜μ—΄
  • 연속합
  • 계단 였λ₯΄κΈ°
  • 제곱수의 ν•©
  • 타일 μ±„μš°κΈ°
  • νŒŒλ„λ°˜ μˆ˜μ—΄
  • ν•©λΆ„ν•΄
  • μ•”ν˜Έ μ½”λ“œ

Was this helpful?

  1. Algorithm

Dynamic Programming

큰 문제λ₯Ό μž‘μ€ 문제둜 λ‚˜λˆ μ„œ ν‘ΈλŠ” μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€.

  1. Overlapping Subproblem (κ²ΉμΉ˜λŠ” λΆ€λΆ„λ¬Έμ œ)

  2. Optimal Substructure(문제의 정닡을 μž‘μ€ λΆ€λΆ„μ—μ„œ μ•Œ 수 μžˆμ„ λ•Œ) : μž‘μ€ λ¬Έμ œμ—μ„œ κ΅¬ν•œ 정닡은 그것을 ν¬ν•¨ν•˜λŠ” 큰 λ¬Έμ œμ—μ„œλ„ λ™μΌν•˜λ‹€.

이 두가지 속성을 λ§Œμ‘±ν•΄μ•Ό λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°μœΌλ‘œ 문제λ₯Ό ν’€ 수 μžˆλ‹€.

Overlapping Subproblem

  • 문제 : N번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • 문제 : N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • 문제 : N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

μž‘μ€ λ¬Έμ œκ°€ κ²Ήμ³μ•Όν•œλ‹€. 큰 λ¬Έμ œμ™€ μž‘μ€ λ¬Έμ œλŠ” μƒλŒ€μ μ΄λ‹€.

  1. 큰 λ¬Έμ œμ™€ μž‘μ€ 문제λ₯Ό 같은 λ°©λ²•μœΌλ‘œ ν’€ 수 μžˆλ‹€.

  2. 문제λ₯Ό μž‘μ€ 문제둜 μͺΌκ°€ 수 μžˆλ‹€.

Optimal Substructure

문제의 정닡을 μž‘μ€ 문제의 μ •λ‹΅μ—μ„œ ꡬ할 수 μžˆλ‹€.

N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제 = N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제 + N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°

  • 각 λ¬Έμ œλŠ” ν•œλ²ˆλ§Œ ν’€μ–΄μ•Ό ν•œλ‹€.

  • 같은 λ¬Έμ œλŠ” ꡬ할 λ•Œλ§ˆλ‹€ 정닡이 κ°™λ‹€.(Optimal Substructure)

  • 정닡을 κ΅¬ν–ˆμœΌλ©΄, 정닡을 μ–΄λ”˜κ°€μ— λ©”λͺ¨ν•΄λ†“λŠ”λ‹€.(λ°°μ—΄)=>Memoization

Top-down

  1. 문제λ₯Ό μž‘μ€ 문제둜 λ‚˜λˆˆλ‹€.

  2. μž‘μ€ 문제λ₯Ό ν‘Όλ‹€.

  3. μž‘μ€ 문제λ₯Ό ν’€μ—ˆμœΌλ‹ˆ, 이제 문제λ₯Ό ν‘Όλ‹€.

μž¬κ·€ν˜ΈμΆœμ„ μ΄μš©ν•΄μ„œ 문제λ₯Ό μ‰½κ²Œ ν’€ 수 μžˆλ‹€. μ‹œκ°„λ³΅μž‘λ„λŠ” μ±„μ›Œμ•Όν•˜λŠ” 칸의 수 X ν•œ 칸을 μ±„μš°λŠ” λ³΅μž‘λ„(ν•¨μˆ˜ν•˜λ‚˜μ˜ μ‹œκ°„ λ³΅μž‘λ„)이닀.

// cpp
int memo[100]; //memoization
int fibonacci(int n){
    if(n<=1){
        return n;
    }else{
        if(memo[n]>0){
            return memo[n];
        }
        memo[n] = fibonacci(n-1)+fibonacci(n-2);
        return memo[n];
    }
}
# python
# memorization
d = [0] * 100

def fibonacci_recursion(x):

    # 1 or 2 λŠ” 1
    if x == 1 or x == 2:
        return 1

    # 이미 ν•œλ²ˆ 호좜된 적 μžˆλŠ” 값은 κΈ°μ–΅ν•΄λ‘” κ°’ λ°˜ν™˜
    if d[x]!=0:
        return d[x]

    # ν•œλ²ˆλ„ 호좜된적 μ—†λŠ” 값은 μΆ”κ°€
    d[x] = fibonacci_recursion(x-1) + fibonacci_recursion(x-2)
    return d[x]

print(fibonacci_recursion(6))

Bottom-up

  1. 문제λ₯Ό 크기가 μž‘μ€ λ¬Έμ œλΆ€ν„° μ°¨λ‘€λŒ€λ‘œ ν‘Όλ‹€.

  2. 문제의 크기λ₯Ό μ‘°κΈˆμ”© 크게 λ§Œλ“€λ©΄μ„œ 문제λ₯Ό ν‘Όλ‹€.

  3. μž‘μ€ 문제λ₯Ό ν’€λ©΄μ„œ μ™”κΈ° λ•Œλ¬Έμ—, 큰 λ¬Έμ œλŠ” 항상 ν’€ 수 μžˆλ‹€.

int d[100];
int fibonacci(int n){
    d[0]=1;
    d[1]=1;
    for(int i=2;i<=n;i++){
        d[i]=d[i-1]+d[i-2];
    }
    return d[n];
}
# bottom-up

# dp table
d = [0] * 100

def fibonacci_loop(n):
    d[1] = 1
    d[2] = 1

    for i in range(3,n+1):
        d[i] = d[i-1]+d[i-2]

    print(d[n])

fibonacci_loop(99)

memoization을 ν•  λ•Œ 무엇을 기둝해야할지 μ •μ˜ν•˜λŠ” 것이 μ΅œμš°μ„ μ΄λ‹€.

Top-down(memorization) 방식은 'ν•˜ν–₯식'이라고도 ν•˜λ©°, bottom-up 방식은 '상ν–₯식'이라고도 ν•œλ‹€. DP의 μ „ν˜•μ μΈ ν˜•νƒœλŠ” bottom-up 방식이닀.

Bottom-up λ°©μ‹μ—μ„œ μ‚¬μš©λ˜λŠ” κ²°κ³Ό μ €μž₯용 리슀트(λ°°μ—΄)λŠ” DP ν…Œμ΄λΈ” 이라 λΆ€λ₯΄λ©°, memorization은 Top-down 방식에 κ΅­ν•œλ˜μ–΄ μ‚¬μš©λ˜λŠ” ν‘œν˜„μ΄λ‹€.

μ‹€μŠ΅

1둜 λ§Œλ“€κΈ°

D[N] = N을 1둜 λ§Œλ“œλŠ”λ° ν•„μš”ν•œ μ—°μ‚°μ˜ μ΅œμ†Ÿκ°’ 1. N이 3으둜 λ‚˜λˆ„μ–΄ λ–¨μ–΄μ§€λ©΄, 3으둜 λ‚˜λˆˆλ‹€. D[N/3]+1 2. N이 2둜 λ‚˜λˆ„μ–΄ λ–¨μ–΄μ§€λ©΄, 2둜 λ‚˜λˆˆλ‹€. D[N/2]+1 3. 1을 λΊ€λ‹€. D[N-1]+1

=> D[N]=min(1,2,3)

top-down

#include <iostream>

//Top-Down(μž¬κ·€)
int d[1000001];
int divn(int n){
    if(n==1) return 0;
    if(d[n]>0) return d[n];
    //-1
    d[n]=divn(n-1)+1;
    if(n%2==0){
        int temp=divn(n/2)+1;
        if(d[n]>temp) d[n] = temp;
    }
    if(n%3==0){
        int temp=divn(n/3)+1;
        if(d[n]>temp) d[n] = temp;
    }
    return d[n];
}

bottom-up

//Bottom-up
void divbu(int n){
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=d[i-1]+1;
        if(i%2==0 && d[i]>d[i/2]+1){
            d[i]=d[i/2]+1;
        }
        if(i%3==0 && d[i]>d[i/3]+1){
            d[i]=d[i/3]+1;
        }
    }
    printf("%d",d[n]);
}

2Xn 타일링

2Xn μ§μ‚¬κ°ν˜•μ„ 1x2,2x1νƒ€μΌλ‘œ μ±„μš°λŠ” λ°©λ²•μ˜ 수 => D[n]=2xiμ§μ‚¬κ°ν˜•μ„ μ±„μš°λŠ” λ°©λ²•μ˜ 수 => D[n]=D[n-1]+D[n-2]

이 λ•Œ, n=0일 λ•Œλ„ 경우의 수이기 λ•Œλ¬Έμ— 1을 좜λ ₯ν•œλ‹€.

bottom-up

#include <iostream>
using namespace std;

int d[10001];
int main() {
    int x;
    cin >> x;
    d[1]=1;
    d[0]=1;
    for(int i=2;i<=x;i++){
        d[i]=d[i-1]+d[i-2];
        d[i]%=10007;
    }
    cout << d[x] << "\n";
}

2xn 타일링 2

2Xn μ§μ‚¬κ°ν˜•μ„ 1x2,2x1,2x2νƒ€μΌλ‘œ μ±„μš°λŠ” λ°©λ²•μ˜ 수 => D[n]=2xiμ§μ‚¬κ°ν˜•μ„ μ±„μš°λŠ” λ°©λ²•μ˜ 수 => D[n]=D[n-1]+2*D[n-2]

bottom-up

#include <iostream>
using namespace std;

int d[10001];
int main() {
    int x;
    cin >> x;
    d[1]=1;
    d[0]=1;
    for(int i=2;i<=x;i++){
        d[i]=d[i-1]+2*d[i-2];
        d[i]%=10007;
    }
    cout << d[x] << "\n";
}

1,2,3 λ”ν•˜κΈ°

μ •μˆ˜ n을 1,2,3의 μ‘°ν•©μœΌλ‘œ λ‚˜νƒ€λ‚΄λŠ” λ°©λ²•μ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제 => D[n]=μ •μˆ˜ n을 1,2,3의 μ‘°ν•©μœΌλ‘œ λ‚˜νƒ€λ‚΄λŠ” λ°©λ²•μ˜ 수 => λ§ˆμ§€λ§‰μ— μ˜€λŠ” μˆ˜κ°€ μ€‘μš”ν•˜λ‹€. => D[n]=D[n-1]+D[n-2]+D[n-3]

bottom-up

#include <iostream>
using namespace std;

int d[10001];
int main() {
    int t;
    cin >> t;
    while(t--){
        int x;
        cin >> x;
        d[1]=1;
        d[0]=1;
        d[2]=2;
        for(int i=2;i<=x;i++){
            d[i]=d[i-1]+d[i-2]+d[i-3];
        }
        cout << d[x] << "\n";
    }
}

λΆ•μ–΄λΉ΅ νŒλ§€ν•˜κΈ°

λΆ•μ–΄λΉ΅ i개λ₯Ό νŒ”μ•„μ„œ 얻을 수 μžˆλŠ” 수읡 P[i]일 λ•Œ, N개λ₯Ό λͺ¨λ‘ νŒλ§€ν•΄μ„œ 얻을 수 μžˆλŠ” μ΅œλŒ€ μˆ˜μ΅κ΅¬ν•˜κΈ° => D[n]=n개λ₯Ό λͺ¨λ‘ νŒλ§€ν•΄μ„œ 얻을 수 μžˆλŠ” μ΅œλŒ€μˆ˜μ΅

λΆ•μ–΄λΉ΅ 수

가격

남은 λΆ•μ–΄λΉ΅μ˜ 수

μ΅œλŒ€μˆ˜μ΅ κ°€λŠ₯ν•œ 경우

1

P[1]

n-1

P[1]+D[n-1]

2

P[2]

n-2

P[2]+D[n-2]

...

...

...

...

n-1

P[n-1]

1

P[n-1]+D[1]

n

P[n]

0

P[n]+D[0]

=> D[n] = max(P[i]+D[n-i])(1<=i<=n)

#include <iostream>
using namespace std;

int d[10001];//λΆ•μ–΄λΉ΅ n개λ₯Ό νŒ”μ•„μ„œ 얻을 수 μžˆλŠ” μ΅œλŒ€μˆ˜μ΅
int p[10001];
int main(){
    int n;//λΆ•μ–΄λΉ΅μ˜ 수
    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            d[i]=max(d[i],d[i-j]+p[j]);
        }
    }
    cout<<d[n];
}

μ‰¬μš΄ 계단 수

μΈμ ‘ν•œ 자리의 차이가 1이 λ‚˜λŠ” 수λ₯Ό 계단 수라고 ν•œλ‹€. ex)45656 길이가 N인 계단 수의 개수λ₯Ό κ΅¬ν•˜μ—¬λΌ.(0으둜 μ‹œμž‘ν•˜λŠ” μˆ˜λŠ” μ—†λ‹€.)

=> D[N][L]=N자리 κ³„λ‹¨μˆ˜, λ§ˆμ§€λ§‰ 수 L L -> L+1 or L-1 => D[N][L]=D[N-1][L-1]+D[N-1]+D[L+1]

#include <iostream>
using namespace std;

int d[101][9];
int main(){
    int n,ans=0;
    scanf("%d",&n);

    for(int j=1;j<=9;j++){
        d[1][j]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<=9;j++){
            d[i][j]=0;
            if(j-1>=0)d[i][j]+=d[i-1][j-1];
            if(j+1<=9)d[i][j]+=d[i-1][j+1];
        }
    }
    for(int j=0;j<=9;j++){
        ans+=d[n][j];
    }
    printf("%d",ans);
}

였λ₯΄λ§‰ 수

였λ₯΄λ§‰ μˆ˜λŠ” 수의 μžλ¦¬κ°€ μ˜€λ¦„μ°¨μˆœμ„ μ΄λ£¨λŠ” 수λ₯Ό λ§ν•œλ‹€. 이 λ•Œ, μΈμ ‘ν•œ μˆ˜κ°€ 같아도 μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μΉœλ‹€. 예λ₯Ό λ“€μ–΄, 2234와 3678, 11119λŠ” 였λ₯΄λ§‰ μˆ˜μ΄μ§€λ§Œ, 2232, 3676, 91111은 였λ₯΄λ§‰ μˆ˜κ°€ μ•„λ‹ˆλ‹€. 수의 길이 N이 μ£Όμ–΄μ‘Œμ„ λ•Œ, 였λ₯΄λ§‰ 수의 개수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. μˆ˜λŠ” 0으둜 μ‹œμž‘ν•  수 μžˆλ‹€.

=> D[N][L]=N자리 였λ₯΄λ§‰μˆ˜, λ§ˆμ§€λ§‰μˆ˜ L => D[N][L]=sum(D[N-1][k])(0<=k<=L)

#include <iostream>
using namespace std;

int d[1001][10];
int main(){
    int n;
    scanf("%d",&n);

    for(int j=0;j<=9;j++){
        d[1][j]=1;
    }
    for(int i=2;i<=n;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=j;k++)
                d[i][j]+=d[i-1][k];
    int ans=0;
    for(int j=0;j<=9;j++){
        ans+=d[n][j];
    }
    printf("%d",ans);
}

이친수

0κ³Ό 1둜만 이루어진 수λ₯Ό μ΄μ§„μˆ˜λΌ ν•œλ‹€. μ΄λŸ¬ν•œ μ΄μ§„μˆ˜ 쀑 νŠΉλ³„ν•œ μ„±μ§ˆμ„ κ°–λŠ” 것듀이 μžˆλŠ”λ°, 이듀을 이친수(pinary number)라 ν•œλ‹€. μ΄μΉœμˆ˜λŠ” λ‹€μŒμ˜ μ„±μ§ˆμ„ λ§Œμ‘±ν•œλ‹€.

  • μ΄μΉœμˆ˜λŠ” 0으둜 μ‹œμž‘ν•˜μ§€ μ•ŠλŠ”λ‹€.

  • μ΄μΉœμˆ˜μ—μ„œλŠ” 1이 두 번 μ—°μ†μœΌλ‘œ λ‚˜νƒ€λ‚˜μ§€ μ•ŠλŠ”λ‹€. 즉, 11을 λΆ€λΆ„ λ¬Έμžμ—΄λ‘œ κ°–μ§€ μ•ŠλŠ”λ‹€.

예λ₯Ό λ“€λ©΄ 1, 10, 100, 101, 1000, 1001 등이 μ΄μΉœμˆ˜κ°€ λœλ‹€. ν•˜μ§€λ§Œ 0010101μ΄λ‚˜ 101101은 각각 1, 2번 κ·œμΉ™μ— μœ„λ°°λ˜λ―€λ‘œ μ΄μΉœμˆ˜κ°€ μ•„λ‹ˆλ‹€.

=> D[n]=D[n-1]+D[n-2] (n자리 2친수 = n번째 μžλ¦¬μ— 0+n번째 μžλ¦¬μ— 1)

#include <iostream>
using namespace std;

int d[91];
int main(){

    int n;
    scanf("%d",&n);

    d[1]=1;
    d[2]=1;

    for(int i=3;i<=n;i++){
        d[i]=d[i-1]+d[i-2];
    }

    printf("%d",d[n]);
}

μŠ€ν‹°μ»€

μŠ€ν‹°μ»€ 2nκ°œκ°€ 2Xnλͺ¨μ–‘μœΌλ‘œ λ°°μΉ˜λ˜μ–΄μžˆλ‹€. μŠ€ν‹°μ»€ ν•œ μž₯을 λ–Όλ©΄ 변을 κ³΅μœ ν•˜λŠ” μŠ€ν‹°μ»€λŠ” λͺ¨λ‘ μ°’μ–΄μ Έμ„œ μ‚¬μš©ν•  수 μ—†λ‹€. 점수의 합을 μ΅œλŒ€λ‘œ λ§Œλ“œλŠ” 문제. 즉, 2n개의 μŠ€ν‹°μ»€ μ€‘μ—μ„œ 점수의 합이 μ΅œλŒ€κ°€ λ˜λ©΄μ„œ μ„œλ‘œ 변을 곡유 ν•˜μ§€ μ•ŠλŠ” μŠ€ν‹°μ»€ 집합을 ꡬ해야 ν•œλ‹€.

=> D[n][s]=2Xn μŠ€ν‹°μ»€ μƒνƒœ s

  • s = 0은 λœ―μ§€ μ•ŠμŒ

    • D[n][0]=n-1μ—΄μ—μ„œ μŠ€ν‹°μ»€λ₯Ό μ–΄λ–»κ²Œ λœ―μ—ˆλŠ”μ§€ 상관이 μ—†λ‹€. => max(D[n-1][0],D[n-1][1],D[n-1][2])

  • s = 1은 μœ„μͺ½ μŠ€ν‹°μ»€ 뜯음

    • D[n][1]= n-1μ—΄μ˜ μœ„μͺ½ μŠ€ν‹°μ»€λŠ” 뜯으면 μ•ˆλ¨. max(D[n-1][0],D[n-1][2])+A[n][0]

  • s = 2λŠ” μ•„λž˜μͺ½ μŠ€ν‹°μ»€ 뜯음

    • D[n][1]= n-1μ—΄μ˜ μ•„λž˜μͺ½ μŠ€ν‹°μ»€λŠ” 뜯으면 μ•ˆλ¨. max(D[n-1][0],D[n-1][1])+A[n][1]

=> max(D[n][0],D[n][1],D[n][2])

#include <iostream>
using namespace std;

int d[100000][3];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);

        int array[n][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&array[j][i]);
            }
        }
        d[0][0]=0;
        d[0][1]=array[0][0];
        d[0][2]=array[0][1];
        for(int i=1;i<n;i++){
            d[i][0]=max(max(d[i-1][0], d[i-1][1]),d[i-1][2]);
            d[i][1]=max(d[i-1][0],d[i-1][2])+array[i][0];
            d[i][2]=max(d[i-1][0],d[i-1][1])+array[i][1];
        }
        printf("%d\n",max(max(d[n-1][0],d[n-1][1]),d[n-1][2]));
    }
}

ν¬λ„μ£Όμ‹œμ‹

  1. 포도주 μž”μ„ μ„ νƒν•˜λ©΄ κ·Έ μž”μ— λ“€μ–΄μžˆλŠ” ν¬λ„μ£ΌλŠ” λͺ¨λ‘ λ§ˆμ…”μ•Ό ν•˜κ³ , λ§ˆμ‹  ν›„μ—λŠ” μ›λž˜ μœ„μΉ˜μ— λ‹€μ‹œ 놓아야 ν•œλ‹€.

  2. μ—°μ†μœΌλ‘œ 놓여 μžˆλŠ” 3μž”μ„ λͺ¨λ‘ λ§ˆμ‹€ μˆ˜λŠ” μ—†λ‹€.

1λΆ€ν„° nκΉŒμ§€μ˜ λ²ˆν˜Έκ°€ λΆ™μ–΄ μžˆλŠ” n개의 포도주 μž”μ΄ μˆœμ„œλŒ€λ‘œ ν…Œμ΄λΈ” μœ„μ— 놓여 있고, 각 포도주 μž”μ— λ“€μ–΄μžˆλŠ” ν¬λ„μ£Όμ˜ 양이 μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€μž₯ λ§Žμ€ μ–‘μ˜ 포도주λ₯Ό λ§ˆμ‹€ 수 μžˆλ„λ‘ ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

D[i][j] = A[1]~A[n]κΉŒμ§€ 포도주λ₯Ό λ§ˆμ…§μ„ λ•Œ λ§ˆμ‹€ 수 μžˆλŠ” ν¬λ„μ£Όμ˜ μ΅œλŒ€ μ–‘

  • 0λ²ˆμ—°μ† : A[i]λ₯Ό λ§ˆμ‹œμ§€ μ•ŠμŒ

    • max(D[i-1][0],D[i-1][1],D[i-1][2])

  • 1λ²ˆμ—°μ† : A[i-1]을 λ§ˆμ‹œμ§€ μ•ŠμŒ.

    • D[i-1][0]+A[i]

  • 2λ²ˆμ—°μ† : A[i-1]λ§ˆμ‹œκ³ , A[i-2]λ§ˆμ‹œμ§€ μ•ŠμŒ

    • D[i-1][1]+A[i]

#include <iostream>
using namespace std;

int d[10001][3];
int main(){
    int n;
    scanf("%d",&n);

    int g[n];

    for(int i=1;i<=n;i++){
        scanf("%d",&g[i]);
    }

    d[0][0]=d[0][1]=d[0][2]=0;

    for(int i=1;i<=n;i++){
        d[i][0]= max(max(d[i-1][0],d[i-1][1]),d[i-1][2]);
        d[i][1]= d[i-1][0]+g[i];
        d[i][2]= d[i-1][1]+g[i];
    }
    printf("%d",max(max(d[n][0],d[n][1]),d[n][2]));
}

D[i] = A[1]~A[n]κΉŒμ§€ 포도주λ₯Ό λ§ˆμ…§μ„ λ•Œ λ§ˆμ‹€ 수 μžˆλŠ” ν¬λ„μ£Όμ˜ μ΅œλŒ€ μ–‘

  • 0λ²ˆμ—°μ† : A[i]λ₯Ό λ§ˆμ‹œμ§€ μ•ŠμŒ

    • D[i-1]

  • 1λ²ˆμ—°μ† : A[i-1]을 λ§ˆμ‹œμ§€ μ•ŠμŒ.

    • D[i-2]+A[i]

  • 2λ²ˆμ—°μ† : A[i-1]λ§ˆμ‹œκ³ , A[i-2]λ§ˆμ‹œμ§€ μ•ŠμŒ

    • D[i-3]+A[i-1]+A[i]

=> D[i]=max(D[i-1], D[i-2]+A[i], D[i-3]+A[i-1]+A[i])

d[0]=0;
d[1]=g[1];
d[2]=g[1]+g[2];

for(int i=3;i<=n;i++){
    d[i]= max(max(d[i-1],d[i-2]+g[i]),d[i-3]+g[i]+g[i-1]);
}

κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄

μˆ˜μ—΄ Aκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

예) μˆ˜μ—΄ A = {10, 20, 10, 30, 20, 50} 인 κ²½μš°μ— κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ€ A = {10, 20, 10, 30, 20, 50} 이고, κΈΈμ΄λŠ” 4이닀.

D[i]= A[1]~A[n]κΉŒμ§€ μˆ˜μ—΄μ΄ μžˆμ„ λ•Œ, A[i]λ₯Ό λ§ˆμ§€λ§‰μœΌλ‘œ ν•˜λŠ” κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ˜ 길이(A[i]λ₯Ό λ°˜λ“œμ‹œ ν¬ν•¨ν•΄μ•Όν•œλ‹€.)

#include <iostream>
using namespace std;

int d[1001];
int main(){
    int n; //μˆ˜μ—΄μ˜ 크기
    scanf("%d",&n);

    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<n;i++){
        d[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]>a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
        }
    }
    int maxd=0;
    for(int i=0;i<n;i++){
        if(maxd<d[i])maxd=d[i];
    }
    printf("%d",maxd);
}

κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄

μˆ˜μ—΄ Aκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

예) μˆ˜μ—΄ A = {10, 30, 10, 20, 20, 10} 인 κ²½μš°μ— κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ€ A = {10, 30, 10, 20, 20, 10} 이고, κΈΈμ΄λŠ” 3이닀.

D[i]= A[1]~A[n]κΉŒμ§€ μˆ˜μ—΄μ΄ μžˆμ„ λ•Œ, A[i]λ₯Ό λ§ˆμ§€λ§‰μœΌλ‘œ ν•˜λŠ” κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ˜ 길이(A[i]λ₯Ό λ°˜λ“œμ‹œ ν¬ν•¨ν•΄μ•Όν•œλ‹€.)

#include <iostream>
using namespace std;

int d[1001];
int main(){
    int n; //μˆ˜μ—΄μ˜ 크기
    scanf("%d",&n);

    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<n;i++){
        d[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]<a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
        }
    }
    int maxd=0;
    for(int i=0;i<n;i++){
        if(maxd<d[i])maxd=d[i];
    }
    printf("%d",maxd);
}

κ°€μž₯ κΈ΄ 바이토닉 λΆ€λΆ„ μˆ˜μ—΄

μˆ˜μ—΄ Sκ°€ μ–΄λ–€ 수 Skλ₯Ό κΈ°μ€€μœΌλ‘œ S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 λ§Œμ‘±ν•œλ‹€λ©΄, κ·Έ μˆ˜μ—΄μ„ 바이토닉 μˆ˜μ—΄μ΄λΌκ³  ν•œλ‹€.

예) {10, 20, 30, 25, 20}κ³Ό {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 μˆ˜μ—΄μ΄μ§€λ§Œ, {1, 2, 3, 2, 1, 2, 3, 2, 1}κ³Ό {10, 20, 30, 40, 20, 30} 은 바이토닉 μˆ˜μ—΄μ΄ μ•„λ‹ˆλ‹€.

κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄(D1)κ³Ό κ°€μž₯ κΈ΄ κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄(D2)λ₯Ό κ΅¬ν•œλ‹€μŒ D1+D2-1을 κ΅¬ν•˜λ©΄λœλ‹€.

#include <stdio.h>
/*
 μˆ˜μ—΄ Sκ°€ μ–΄λ–€ 수 Skλ₯Ό κΈ°μ€€μœΌλ‘œ S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 λ§Œμ‘±ν•œλ‹€λ©΄, κ·Έ μˆ˜μ—΄μ„ 바이토닉 μˆ˜μ—΄μ΄λΌκ³  ν•œλ‹€.

 예λ₯Ό λ“€μ–΄, {10, 20, 30, 25, 20}κ³Ό {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 μˆ˜μ—΄μ΄μ§€λ§Œ,  {1, 2, 3, 2, 1, 2, 3, 2, 1}κ³Ό {10, 20, 30, 40, 20, 30} 은 바이토닉 μˆ˜μ—΄μ΄ μ•„λ‹ˆλ‹€.

 μˆ˜μ—΄ Aκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ·Έ μˆ˜μ—΄μ˜ λΆ€λΆ„ μˆ˜μ—΄ 쀑 바이토닉 μˆ˜μ—΄μ΄λ©΄μ„œ κ°€μž₯ κΈ΄ μˆ˜μ—΄μ˜ 길이λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

 첫째 쀄에 μˆ˜μ—΄ A의 크기 N이 μ£Όμ–΄μ§€κ³ , λ‘˜μ§Έ μ€„μ—λŠ” μˆ˜μ—΄ Aλ₯Ό 이루고 μžˆλŠ” Aiκ°€ μ£Όμ–΄μ§„λ‹€. (1 ≀ N ≀ 1,000, 1 ≀ Ai ≀ 1,000)
 */
int d[1001];
int d2[1001];
int main() {
    int n;
    scanf("%d",&n);
    int a[n+1];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        d[i]=1;
        for(int j=0;j<=i;j++){
            if(a[i]>a[j]&&d[i]<d[j]+1){
                d[i]=d[j]+1;
            }
        }
    }
    for (int i=n-1; i>=0; i--) {
        d2[i] = 1;
        for (int j=i+1; j<n; j++) {
            if (a[i] > a[j] && d2[j]+1 > d2[i]) {
                d2[i] = d2[j]+1;
            }
        }
    }
    int ans =0 ;
    for(int i=0;i<n;i++){
        if(ans<d[i]+d2[i]-1){
           ans=d[i]+d2[i]-1;
        }
    }

    printf("%d",ans);
    return 0;
}

연속합

n개의 μ •μˆ˜λ‘œ 이루어진 μž„μ˜μ˜ μˆ˜μ—΄μ΄ μ£Όμ–΄μ§„λ‹€. μš°λ¦¬λŠ” 이 쀑 μ—°μ†λœ λͺ‡ 개의 숫자λ₯Ό μ„ νƒν•΄μ„œ ꡬ할 수 μžˆλŠ” ν•© 쀑 κ°€μž₯ 큰 합을 κ΅¬ν•˜λ €κ³  ν•œλ‹€. 단, μˆ«μžλŠ” ν•œ 개 이상 선택해야 ν•œλ‹€.

예) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 μ΄λΌλŠ” μˆ˜μ—΄μ΄ μ£Όμ–΄μ‘Œλ‹€κ³  ν•˜μž. μ—¬κΈ°μ„œ 정닡은 12+21인 33이 정닡이 λœλ‹€.

D[i]=A[i]둜 λλ‚˜λŠ” μ΅œλŒ€ 연속합

  • A[i-1]둜 λλ‚˜λŠ” 연속합에 포함 D[i-1]+A[i]

  • μƒˆλ‘œμš΄ 연속합 μ‹œμž‘ A[i]

#include <iostream>
using namespace std;

int d[100001]; //A[i]둜 λλ‚˜λŠ” μ΅œλŒ€ 연속합

int main(){
    int n; //μ—°μ†λœ 숫자의 수
    scanf("%d",&n);

    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    d[0]=a[0];
    for(int i=1;i<n;i++){
        d[i]=max(d[i-1]+a[i],a[i]);
    }
    int ans=d[0];
    for(int i=1;i<n;i++){
        if(ans<d[i])ans=d[i];
    }
    printf("%d",ans);
}

계단 였λ₯΄κΈ°

계단 였λ₯΄κΈ° κ²Œμž„μ€ 계단 μ•„λž˜ μ‹œμž‘μ λΆ€ν„° 계단 κΌ­λŒ€κΈ°μ— μœ„μΉ˜ν•œ λ„μ°©μ κΉŒμ§€ κ°€λŠ” κ²Œμž„μ΄λ‹€. 각각의 κ³„λ‹¨μ—λŠ” μΌμ •ν•œ μ μˆ˜κ°€ μ“°μ—¬ μžˆλŠ”λ° 계단을 밟으면 κ·Έ 계단에 μ“°μ—¬ μžˆλŠ” 점수λ₯Ό μ–»κ²Œ λœλ‹€.

  1. 계단은 ν•œ λ²ˆμ— ν•œ 계단씩 λ˜λŠ” 두 계단씩 였λ₯Ό 수 μžˆλ‹€. 즉, ν•œ 계단을 λ°ŸμœΌλ©΄μ„œ μ΄μ–΄μ„œ λ‹€μŒ κ³„λ‹¨μ΄λ‚˜, λ‹€μŒ λ‹€μŒ κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€.

  2. μ—°μ†λœ μ„Έ 개의 계단을 λͺ¨λ‘ λ°Ÿμ•„μ„œλŠ” μ•ˆλœλ‹€. 단, μ‹œμž‘μ μ€ 계단에 ν¬ν•¨λ˜μ§€ μ•ŠλŠ”λ‹€.

  3. λ§ˆμ§€λ§‰ 도착 계단은 λ°˜λ“œμ‹œ λ°Ÿμ•„μ•Ό ν•œλ‹€.

    λ”°λΌμ„œ 첫 번째 계단을 밟고 이어 두 번째 κ³„λ‹¨μ΄λ‚˜, μ„Έ 번째 κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€. ν•˜μ§€λ§Œ, 첫 번째 계단을 밟고 이어 λ„€ 번째 κ³„λ‹¨μœΌλ‘œ μ˜¬λΌκ°€κ±°λ‚˜, 첫 번째, 두 번째, μ„Έλ²ˆμ§Έ 계단을 μ—°μ†ν•΄μ„œ λͺ¨λ‘ λ°Ÿμ„ μˆ˜λŠ” μ—†λ‹€.

D[i][j]=i번째 계단에 μ˜¬λžμ„ λ•Œ 총 점수의 μ΅œλŒ€κ°’. (i번째 계단은 j개 μ—°μ†ν•΄μ„œ 였λ₯Έ 계단)

  • D[i][0]=0κ°œμ—°μ†(i번째 계단에 μ˜¬λΌκ°€μ•Ό ν•˜κΈ° λ•Œλ¬Έμ— λΆˆκ°€λŠ₯ν•œ 경우)

  • D[i][1]=1κ°œμ—°μ†(i-1은 밟으면 μ•ˆλœλ‹€.)=max(D[i-2][1],D[i-2][2])+a[i]

  • D[i][2]=2κ°œμ—°μ†(i번째 계단은 λ°Ÿμ•„μ•Όν•˜κ³ , λ°˜λ“œμ‹œ 1개 μ—°μ†ν•΄μ„œ 올라온 κ³„λ‹¨μ΄μ–΄μ•Όν•œλ‹€.)=D[i-1][1]+a[i]

#include <iostream>
using namespace std;

int d[301][3]; //A[i]둜 λλ‚˜λŠ” μ΅œλŒ€ 점수

int main(){
    int n; //κ³„λ‹¨μˆ˜
    scanf("%d",&n);

    int a[n];//각 계단 점수
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    d[0][1]=a[0];
    d[1][1]=a[1];
    d[1][2]=a[1]+a[0];
    for(int i=2;i<n;i++){
        d[i][1]=max(d[i-2][1],d[i-2][2])+a[i];
        d[i][2]=d[i-1][1]+a[i];
    }
    printf("%d",max(d[n-1][1],d[n-1][2]));
}

μ΄λ•Œ 경우의 수둜 λ°–μœΌλ‘œ λΉΌμ€€λ‹€λ©΄ 2μ°¨μ›μ—μ„œ 1μ°¨μ›μœΌλ‘œ 차원을 쀄일 수 μžˆλ‹€.

D[i]=i번째 계단에 μ˜¬λΌκ°”μ„ λ•Œ, μ΅œλŒ€ 점수

  • 1개 연속 : i-1번째 계단은 밟으면 μ•ˆλ¨

    • i-2λŠ” λ°˜λ“œμ‹œ λ°Ÿμ•˜μ–΄μ•Ό 함

    • D[i-2]+A[i]

  • 2개 연속 : i-1번째 계단은 밟고, i-2λŠ” 밟으면 μ•ˆλ¨

    • i-3번째 계단은 λ°˜λ“œμ‹œ λ°Ÿμ•„μ•Ό 함

    • D[i-3]+A[i-1]+A[i]

#include <iostream>
using namespace std;

int d[301]; //A[i]둜 λλ‚˜λŠ” μ΅œλŒ€ 점수
int a[301];//각 계단 점수
int main(){
    int n; //κ³„λ‹¨μˆ˜
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    d[1]=a[1];
    d[2]=a[1]+a[2];

    for(int i=3;i<=n;i++){
        d[i]=max(d[i-2]+a[i],d[i-3]+a[i-1]+a[i]);
    }
    printf("%d",d[n]);
}

제곱수의 ν•©

μ–΄λ–€ μžμ—°μˆ˜ N은 그보닀 μž‘μ€ μ œκ³±μˆ˜λ“€μ˜ ν•©μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€. 예λ₯Ό λ“€μ–΄ 11=3^2+1^2+1^2(3개 ν•­)이닀. 이런 ν‘œν˜„λ°©λ²•μ€ μ—¬λŸ¬ κ°€μ§€κ°€ 될 수 μžˆλŠ”λ°, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 ν•­)도 κ°€λŠ₯ν•˜λ‹€. 이 경우, μˆ˜ν•™μž μˆŒν¬λΌν…ŒμŠ€λŠ” β€œ11은 3개 ν•­μ˜ 제곱수 ν•©μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλ‹€.”라고 λ§ν•œλ‹€. λ˜ν•œ 11은 그보닀 적은 ν•­μ˜ 제곱수 ν•©μœΌλ‘œ ν‘œν˜„ν•  수 μ—†μœΌλ―€λ‘œ, 11을 κ·Έ ν•©μœΌλ‘œμ¨ ν‘œν˜„ν•  수 μžˆλŠ” 제곱수 ν•­μ˜ μ΅œμ†Œ κ°œμˆ˜λŠ” 3이닀.

D[i]=μžμ—°μˆ˜ N을 μ΄λ ‡κ²Œ μ œκ³±μˆ˜λ“€μ˜ ν•©μœΌλ‘œ ν‘œν˜„ν•  λ•Œμ— κ·Έ ν•­μ˜ μ΅œμ†Œκ°œμˆ˜

  • λ§ˆμ§€λ§‰ν•­μ΄ μ€‘μš”ν•˜λ‹€.

  • min(D[i-j^2]+1) (1<=i<=j^2)

#include <iostream>
using namespace std;

int d[100001]; //μ œκ³±ν•©μœΌλ‘œ ν‘œν˜„ν•˜λŠ” μ΅œμ†Œν•­ 개수
int main(){
    int n; //μžμ—°μˆ˜
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        d[i]=i; //1^2으둜 ν‘œν˜„ν•œ 개수(즉, μ΅œλŒ€ν•­)
        for(int j=1;j*j<=i;j++){
            if(d[i]>d[i-j*j]+1)d[i]=d[i-j*j]+1;
        }
    }
    printf("%d",d[n]);
}

타일 μ±„μš°κΈ°

3Γ—N 크기의 벽을 2Γ—1, 1Γ—2 크기의 νƒ€μΌλ‘œ μ±„μš°λŠ” 경우의 수λ₯Ό κ΅¬ν•΄λ³΄μž.

D[i]=3Xiλ₯Ό μ±„μš°λŠ” λ°©λ²•μ˜ 수

  • D[i]=3*D[i-2]+2*D[i-4]+2*D[i-6]+...

#include <iostream>
using namespace std;

int d[31]; //3*iλ₯Ό ν‘œν˜„ν•  수 μžˆλŠ” 경우의 수
int main(){
    int n;
    scanf("%d",&n);
    d[0]=1;
    for (int i=2; i<=n; i+=2) {
        d[i] = d[i-2]*3;
        for (int j=i-4; j>=0; j-=2) {
            d[i] += d[j]*2;
        }
    }
    printf("%d",d[n]);
}

νŒŒλ„λ°˜ μˆ˜μ—΄

κ·Έλ¦Όκ³Ό 같이 μ‚Όκ°ν˜•μ΄ λ‚˜μ„  λͺ¨μ–‘μœΌλ‘œ 놓여져 μžˆλ‹€. 첫 μ‚Όκ°ν˜•μ€ μ •μ‚Όκ°ν˜•μœΌλ‘œ λ³€μ˜ κΈΈμ΄λŠ” 1이닀. κ·Έ λ‹€μŒμ—λŠ” λ‹€μŒκ³Ό 같은 κ³Όμ •μœΌλ‘œ μ •μ‚Όκ°ν˜•μ„ 계속 μΆ”κ°€ν•œλ‹€. λ‚˜μ„ μ—μ„œ κ°€μž₯ κΈ΄ λ³€μ˜ 길이λ₯Ό k라 ν–ˆμ„ λ•Œ, κ·Έ 변에 길이가 k인 μ •μ‚Όκ°ν˜•μ„ μΆ”κ°€ν•œλ‹€.

νŒŒλ„λ°˜ μˆ˜μ—΄ P(N)은 λ‚˜μ„ μ— μžˆλŠ” μ •μ‚Όκ°ν˜•μ˜ λ³€μ˜ 길이이닀. P(1)λΆ€ν„° P(10)κΉŒμ§€ 첫 10개 μˆ«μžλŠ” 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이닀.

N이 μ£Όμ–΄μ‘Œμ„ λ•Œ, P(N)을 κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

D[i]=P(i)νŒŒλ„λ°˜ μˆ˜μ—΄

  • D[i-2]+D[i-3]

  • D[i-5]+D[i-1]

#include <iostream>
using namespace std;

int d[101]; //νŒŒλ„λ°˜μˆ˜μ—΄
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        d[0]=0;
        d[1]=d[2]=1;
        for (int i=3; i<=n; i++) {
            d[i] = d[i-2]+d[i-3];
        }
        printf("%d\n",d[n]);
    }
}

ν•©λΆ„ν•΄

0λΆ€ν„° NκΉŒμ§€μ˜ μ •μˆ˜ K개λ₯Ό λ”ν•΄μ„œ κ·Έ 합이 N이 λ˜λŠ” 경우의 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

λ§μ…ˆμ˜ μˆœμ„œκ°€ 바뀐 κ²½μš°λŠ” λ‹€λ₯Έ 경우둜 μ„Όλ‹€(1+2와 2+1은 μ„œλ‘œ λ‹€λ₯Έ 경우). λ˜ν•œ ν•œ 개의 수λ₯Ό μ—¬λŸ¬ 번 μ“Έ μˆ˜λ„ μžˆλ‹€.

D[K][N]=μ •μˆ˜ 0λΆ€ν„° NκΉŒμ§€μ˜ μ •μˆ˜ K개λ₯Ό λ”ν•΄μ„œ N이 λ§Œλ“€μ–΄μ§€λŠ” 경우의 수

  • +=D[K-1][N-L] (0<=L<=N)

#include <iostream>
using namespace std;

long long int d[201][201]; //ν•©λΆ„ν•΄
int main(){
    int n,k;
    scanf("%d %d",&k,&n);
    d[0][0]=1LL;
    for(int i=1;i<=k;i++){
        for(int j=0;j<=n;j++){
            for(int l=0;l<=j;l++){
                d[i][j]+=d[i-1][j-l];
                d[i][j]%=1000000000;
            }
        }
    }
    printf("%lld",d[k][n]);
}

μ•”ν˜Έ μ½”λ“œ

상근: κ·Έλƒ₯ κ°„λ‹¨νžˆ μ•”ν˜Έν™” ν•˜μž. Aλ₯Ό 1이라고 ν•˜κ³ , BλŠ” 2둜, 그리고 ZλŠ” 26으둜 ν•˜λŠ”κ±°μ•Ό. μ„ μ˜: 그럼 μ•ˆλΌ. λ§Œμ•½, "BEAN"을 μ•”ν˜Έν™”ν•˜λ©΄ 25114κ°€ λ‚˜μ˜€λŠ”λ°, 이걸 λ‹€μ‹œ κΈ€μžλ‘œ λ°”κΎΈλŠ” 방법은 μ—¬λŸ¬κ°€μ§€κ°€ μžˆμ–΄. 상근: κ·Έλ ‡λ„€. 25114λ₯Ό λ‹€μ‹œ μ˜μ–΄λ‘œ λ°”κΎΈλ©΄, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6κ°€μ§€κ°€ λ‚˜μ˜€λŠ”λ°, BEAN이 λ§žλŠ” λ‹¨μ–΄λΌλŠ”κ±΄ μ‰½κ²Œ μ•Œμˆ˜ μžˆμž–μ•„? μ„ μ˜: μ˜ˆκ°€ μ μ ˆν•˜μ§€ μ•Šμ•˜λ„€ γ… γ…  λ§Œμ•½ λ‚΄κ°€ 500자리 κΈ€μžλ₯Ό μ•”ν˜Έν™” ν–ˆλ‹€κ³  해봐. κ·Έ λ•ŒλŠ” λ‚˜μ˜¬ 수 μžˆλŠ” 해석이 정말 λ§Žμ€λ°, κ·Έκ±Έ μ–Έμ œ 닀해봐? 상근: μ–Όλ§ˆλ‚˜ λ§Žμ€λ°? μ„ μ˜: κ΅¬ν•΄λ³΄μž! μ–΄λ–€ μ•”ν˜Έκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ·Έ μ•”ν˜Έμ˜ 해석이 λͺ‡ κ°€μ§€κ°€ λ‚˜μ˜¬ 수 μžˆλŠ”μ§€ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

D[i]=i번째 λ¬ΈμžκΉŒμ§€ ν•΄μ„ν–ˆμ„ λ•Œ, λ‚˜μ˜¬ 수 μžˆλŠ” ν•΄μ„μ˜ κ°€μ§“ 수

  • 1자리 μ•”ν˜Έ(0μ œμ™Έ)

  • 2자리 μ•”ν˜Έ(10~26)

PreviousRecursionNextArray, Struct, Pointer

Last updated 4 years ago

Was this helpful?