์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 | 29 | 30 | 31 |
- UIKit
- arkit
- BOJ
- combine
- BFS
- realm
- Xcode
- RxSwift
- SnapKit
- MVVM
- CollectionView
- designpattern
- Lv2
- raywenderlich
- ๋ฐฑ์ค
- tableView
- ios
- Kuring
- Flutter
- visionOS
- ํ๋ก๊ทธ๋๋จธ์ค
- Swfit
- TCA
- swift
- node.js
- rxcocoa
- XCTest
- SwiftUI
- ํจ์คํธ์บ ํผ์ค
- reactorkit
- Today
- Total
๋ชฉ๋กdp (2)
lgvv98
chapter 8. DP โ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP)์ ๋ํด์ ์์๋ณด์! DP๋ ํ๊ต ์์ ์๊ฐ์ ํผ๋ณด๋์น๋ฅผ ๊ณต๋ถํ๋ฉด์ ๊ณ์ฐํ ๋ถ๋ถ์ ๊ณ์ฐํ์ง ์๋ ๊ฒ์ผ๋ก ๋ฐฐ์ ๋๋ฐ, ๊ทธ ๋น์์๋ ๊ทธ๊ฒ DP์ธ์ง ๋ชฐ๋์ ์๊ณ ๋ฆฌ์ฆ์ ํ๋ฉด์ DP์ ๊ฐ์ ๋ฌธ์ ๋ค์ ์ ๋ชปํธ๋๋ฐ, ์ด๋ฒ์ ๊ณต๋ถํด ๋ณด๋๊น ๊ทธ ์ฌ๊ณ ๋ฅผ ์ป์ด์ ์กฐ๊ธ ์์ ๊ฐ๋ ์๊น ์๋ฅ๋๋ ์ ํ์ ๋ฌธ์ ์ ์ ๋ ๋๋ฌด๋๋ ์ฝํ๋๋ฐ, DP๋ ์ ํ์์ด ๊ฑฐ์ ๋ฒ ์ด์ค๋ค..? ์๋ฌดํผ ์ด์ฌํ ํด๋ณด์. โ 1๋ก ๋ง๋ค๊ธฐ ์ ํ์์ ์ด์ฉํ๋๋ฐ, ํน์ ํ ์์ ๊ฐ์ ์ ํด์ ์ง์ ๊ทธ๋ฌ๋ณด๋ฉด ๋ฌธ์ ๋ฅผ ๋ง๋๋๋ฐ ๋์์ด ๋ง์ด ๋๋ค. ๋ํ, ๋ณดํ ์ ๋ฐฉ์์ผ๋ก ๊ณ์ฐํ๋๊ฒ ์กฐ๊ธ ๋ ์ด๋์ด ์๋ค๊ณ ํ๊ณ , ์์ฒญ ์ด๋ ต์ง๋ ์์ผ๋๊น ํ๋ฒ ํด๋ณด์. ๋น์ทํ ๋ฌธ์ ๋ฅผ ๋ฐฑ์ค์์ ์ฐพ์ ํ์ด๋ณด์. ๐ ๋ฐฑ์ค๋ฌธ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ํ์์ ๋ง๋ค์ด..
BOJ 11726 2 x n ํ์ผ๋ง โ BOJ 11726 2 x n ํ์ผ๋ง ์ด ๋ฌธ์ ๋ ์๊ฐ๋ณด๋ค ์ด๋ ค์ ๋ค. ์ฌ์ค ๋๋๋น ์๊ณ ๋ฆฌ์ฆ dpํธ์์ ๋ณธ ๊ธฐ์ต์ด ์๋๋ฐ, ์ด๋ฅผ ์ง์ ํ์ด๋ณด๋ ค๋๊น ๋์ ํ ์๊ฐ์ด ๋์ง ์์๋ค. ์ฌ์ค ์ฑ ์ ํด์ค๋ ์ ์ดํด๊ฐ ๊ฐ์ง ์์๋๋ฐ, dp๋ฅผ ๋ณด๋ฉด ๋ณผ์๋ก ์ํ์ ์ธ ์ฌ๊ณ ๊ฐ ๊ฐ๋ ฅํ๊ฒ ํ์ํ ๊ฒ ๊ฐ๋ค. ํ์ด์ ํด์ค์ด ์ดํด๊ฐ ๊ฐ์ง ์์์ ๋ค๋ฅธ ๋ถ์ ๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํ์๋ค. 1x2, 2x1 ๋๊ฐ์ ํ์ผ์ด ์๋ค. n = 1 : | 1๊ฐ n = 2 : ||, = 2๊ฐ n = 3 : |||, =l, l= 3๊ฐ n = 4 : llll, ll=, l=l, =ll, == 5๊ฐ n = 5 : lllll, lll=, ll=l, l=ll, =lll, l==, =l=, ==l 8๊ฐ ์ด๋ฐ ํจํด์ ์ฐพ์ ์ ์๋ค. ์ฐธ๊ณ ํ..