μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- SQL
- λμ ν©
- λ¨Έμ§μνΈ
- μ€λΈμ
- λ³ν©μ λ ¬
- λ°±μ€
- μμνμ
- μ λ ¬
- κΉμ΄μ°μ νμ
- μν
- db
- ν°μ€ν 리μ±λ¦°μ§
- μκ³ λ¦¬μ¦
- DFS
- κ·Έλννμ
- λμ κ³νλ²
- λ°μ΄ν°λ² μ΄μ€
- ꡬν
- κ·Έλν
- DP
- λλΉμ°μ νμ
- λ€μ΄λλ―Ήνλ‘κ·Έλλ°
- μ°μ μμν
- νμ΄μ¬
- νλ‘κ·Έλλ¨Έμ€
- LIS
- μλ£κ΅¬μ‘°
- BFS
- μμꡬνκΈ°
- 그리λ
λͺ©λ‘μ 체 κΈ (108)
πππ°πΈ π£πΆπ΅ π΄π΅π¦π’π₯πΊ
λ¬Έμ μ¨λΌμΈ μ μ§μ κ°μ ν μ¬λλ€μ λμ΄μ μ΄λ¦μ΄ κ°μ ν μμλλ‘ μ£Όμ΄μ§λ€. μ΄λ, νμλ€μ λμ΄κ° μ¦κ°νλ μμΌλ‘, λμ΄κ° κ°μΌλ©΄ λ¨Όμ κ°μ ν μ¬λμ΄ μμ μ€λ μμλ‘ μ λ ¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ μ¨λΌμΈ μ μ§ νμμ μ Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 100,000) λμ§Έ μ€λΆν° Nκ°μ μ€μλ κ° νμμ λμ΄μ μ΄λ¦μ΄ 곡백μΌλ‘ ꡬλΆλμ΄ μ£Όμ΄μ§λ€. λμ΄λ 1λ³΄λ€ ν¬κ±°λ κ°μΌλ©°, 200λ³΄λ€ μκ±°λ κ°μ μ μμ΄κ³ , μ΄λ¦μ μνλ²³ λμλ¬Έμλ‘ μ΄λ£¨μ΄μ Έ μκ³ , κΈΈμ΄κ° 100λ³΄λ€ μκ±°λ κ°μ λ¬Έμμ΄μ΄λ€. μ λ ₯μ κ°μ ν μμλ‘ μ£Όμ΄μ§λ€. μΆλ ₯ 첫째 μ€λΆν° μ΄ Nκ°μ μ€μ κ±Έμ³ μ¨λΌμΈ μ μ§ νμμ λμ΄ μ, λμ΄κ° κ°μΌλ©΄ κ°μ ν μμΌλ‘ ν μ€μ ν λͺ μ© λμ΄μ μ΄λ¦μ 곡백μΌλ‘ ꡬλΆν΄ μΆλ ₯νλ€. μ λ ¬..
λ¬Έμ μ μ Xμ μ¬μ©ν μ μλ μ°μ°μ λ€μκ³Ό κ°μ΄ μΈ κ°μ§ μ΄λ€. Xκ° 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ©΄, 3μΌλ‘ λλλ€. Xκ° 2λ‘ λλμ΄ λ¨μ΄μ§λ©΄, 2λ‘ λλλ€. 1μ λΊλ€. μ μ Nμ΄ μ£Όμ΄μ‘μ λ, μμ κ°μ μ°μ° μΈ κ°λ₯Ό μ μ ν μ¬μ©ν΄μ 1μ λ§λ€λ €κ³ νλ€. μ°μ°μ μ¬μ©νλ νμμ μ΅μκ°μ μΆλ ₯νμμ€. μ λ ₯ 첫째 μ€μ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 106λ³΄λ€ μκ±°λ κ°μ μ μ Nμ΄ μ£Όμ΄μ§λ€. μΆλ ₯ 첫째 μ€μ μ°μ°μ νλ νμμ μ΅μκ°μ μΆλ ₯νλ€. DPλ₯Ό μ΄μ©νμ¬ ν μ μλ λ¬Έμ . 1. Nμ΄ 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ©΄, 3μΌλ‘ λλλ€ β‘οΈ D[N] = D[N/3] + 1 2. Nμ΄ 2λ‘ λλμ΄ λ¨μ΄μ§λ©΄, 2λ‘ λλλ€ β‘οΈ D[N] = D[N/2] + 1 3. 1μ λΊλ€ β‘οΈ D[N] = D[N - 1] + 1 κ·Έλ¬λ ..

'μ½λ© ν μ€νΈλ₯Ό μν μλ£ κ΅¬μ‘°μ μκ³ λ¦¬μ¦ with C++' λ₯Ό μ°Έκ³ νμ¬ μμ±νμμ΅λλ€. 1. λμ κ³νλ² ; dynamic programming 1.1 κ°λ λΆν μ 볡 ν¨λ¬λ€μ κ°λ μ νμ₯ν κ²μΌλ‘, ν° λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλμ΄ νΈλ λ¬Έμ λ₯Ό μΌμ»«λ λ§μ΄λ€. μΈλ» λ¬Έμ λ₯Ό 보면 λΉμ·νλ€ μκ°λ μ μμ§λ§, λΆν μ 볡과 ꡬλΆλλ λμ κ³νλ²λ§μ νΉμ±μ λ€μκ³Ό κ°λ€. 1. μ€λ³΅λλ λΆλΆ λ¬Έμ (overlapping subproblem) 2. μ΅μ λΆλΆ ꡬ쑰(optimal substructure) λ€μκ³Ό κ°μ μμ±μ λ§μ‘±ν΄μΌ λμ κ³νλ²μ ν΅ν΄ λ¬Έμ λ₯Ό ν΄κ²°ν μ μλ€. μ 체 λ¬Έμ κ° λ 립μ μΈ λΆλΆ λ¬Έμ λ‘ λλλ λΆν μ 볡 λ¬Έμ μ λ¬λ¦¬ λμ κ³νλ²μμλ μ€λ³΅λλ λΆλΆ λ¬Έμ κ° λ°λ³΅μ μΌλ‘ λ±μ₯νλ€. λν μ΅μ λΆλΆ ꡬ..