1.테이블 정의하기
0과 1이 몇 번 출력되었는지 기록하기 위해 2차원 배열을 사용해서 정의한다
d[i][0] = fibonacci(i)를 실행했을 때 0이 출력된 횟수
d[i][1] = fibonacci(i)를 실행했을 때 1이 출력된 횟수
2. 점화식 구하기
피보나치를 응용해서 구하면
d[k][0] = d[k-1][0] + d[k-2][0]
d[k][1] = d[k-1][1] + d[k-2][1]
3.초기값 설정
d[0][0] = 1
d[1][1] = 1
코드
import java.io.BufferedWriter
import java.io.OutputStreamWriter
fun main(args: Array<String>) {
var t = readLine()!!.toInt()
val d = Array(45) { IntArray(2) { 0 } }
d[0][0] = 1
d[1][1] = 1
val bw = BufferedWriter(OutputStreamWriter(System.out))
while (t-- != 0) {
val n = readLine()!!.toInt()
for (i in 2..n) {
d[i][0] = d[i - 1][0] + d[i - 2][0]
d[i][1] = d[i - 1][1] + d[i - 2][1]
}
// 0 출력 횟수, 1 출력 횟수
bw.append("${d[n][0]} ${d[n][1]}\n")
}
bw.close()
}
BOJ 2747. 피보나치 수
kotlin
import java.util.*
fun main() {
val n = Scanner(System.`in`).nextInt()
val d = IntArray(n+1)
d[1] = 1
for (i in 2..n) {
d[i] = d[i-1] + d[i-2]
}
println("${d[n]}")
}
1. 테이블 정의하기
d[i][j] = (i,j) 까지 왔을 때 합의 최댓값
2. 점화식 구하기
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
1층
d[0][0] = 7
2층
d[1][0] = d[0][0] + 3
d[1][1] = d[0][0] + 8
3층
d[2][0] = d[1][0] + 8
d[2][1] = max(d[1][0], d[1][1]) + 1
d[2][2] = d[1][1] + 0
i가 삼각형의
- 왼쪽에 위치해 있을 때 합의 최댓값은 -> d[i][j] = d[i-1][j] + d[i][j]
- 오른쪽에 위치해 있을 때 합의 최댓값은 -> d[i][j] = d[i-1][j-1] + d[i][j]
- 중앙에 위치해 있을 때 합의 최댓값은 -> d[i][j] = max(d[i-1][j] + d[i][j], d[i-1][j-1] + d[i][j])
3. 초기값 설정하기
d[i][j] 테이블에 삼각형 값을 직접 저장하여 초기값은 따로 설정하지 않는다
코드
import java.util.*
import java.io.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val d = Array(n+1) { IntArray(n+1) }
var st: StringTokenizer
repeat(n) { i ->
st = StringTokenizer(readLine())
repeat(i+1) { j ->
d[i][j] = st.nextToken().toInt()
}
}
var max = d[0][0]
for (i in 1 until n) {
for (j in 0..i) {
when (j) {
0 -> d[i][j] += d[i-1][j] // 왼쪽에 위치
i -> d[i][j] += d[i-1][j-1] // 오른쪽에 위치
// 중앙에 위치
else -> d[i][j] += max(d[i-1][j], d[i-1][j-1])
}
max = max(d[i][j], max)
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("$max")
bw.close()
}
1문제에서 2*2 타일이 추가된 버전
1. 테이블 정의
d[i] = 2*i 직사각형을 1*2, 2*1, 2*2 타일로 채우는 방법의 수
2. 점화식 구하기
2xn 타일링 1에서와 같은 원리로 결국 채우는 패턴은 세가지다
| 2*1 | 2*(n-1) |
2*1로 채우고 남은 영역인 2*(n-1) 영역을 채우는 방법을 구한다
| 1 * 2 | 2 * (n-2) |
| 1 * 2 |
1*2 2개로 채우고 남은 영역인 2*(n-2) 영역을 채우는 방법을 구한다
| 2 * 2 | 2 * (n-2) |
2*2로 채우고 남은 영역인 2 * (n-2) 영역을 채우는 방법을 구한다
따라서 d[i] = d[i-1] + d[i-2] * 2
3. 초기값 설정
d[i-2] 가 연산에 들어가기 때문에 2까지 초기값으로 설정해준다
d[1] = 1
d[2] = 3
코드
import java.io.BufferedWriter
import java.io.OutputStreamWriter
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val d = IntArray(1005) // n이 1인 경우를 고려하여 n+1이 아닌 넉넉한 수로 잡아준다
d[1] = 1
d[2] = 3
for (i in 3..n) {
d[i] = (d[i-2] * 2 + d[i-1]) % 10007
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${d[n]}")
bw.close()
}
이진수 중 다음 조건을 만족하면 이친수라고 한다
- 0으로 시작하지 않을 것
- 두번 연속 1이 나타나지 않을 것
1. 테이블 정의하기
d[i][0] = i 자리수의 이친수 중 0으로 끝나는 수
d[i][1] = i 자리수의 이친수 중 1로 끝나는 수
2. 점화식 만들기
1. 한자리 수 : 1
2. 두자리 수: 10
3. 세자리 수: 100, 101
4. 네자리 수: 1000, 1001, 1010
5. 다섯자리 수: 10000, 100001, 10010, 10100, 10101
-> 1 뒤에는 0만 사용 가능, 0 뒤에는 1, 0 둘다 사용 가능
-> 전단계 이친수가 몇개인지, 각각의 마지막이 어떤 숫자로 끝나는지를 알아야 한다
d[1][0] = 0, d[1][1] = 1
d[2][0] = d[1][1], d[2][1] = 0
d[3][0] = d[2][0], d[3][1] = d[2][0]
d[4][0] = d[3][0] + d[3][1], d[4][1] = d[3][0]
d[5][0] = d[4][0] + d[4][1], d[5][1] = d[4][0]
d[k][0] = d[k-1][0] + d[k-1][1], d[k][1] = d[k-1][0]
k 자리수 이친수의 수 - d[k][0] + d[k][1]
3. 초기값 설정
d[1][1] = 1
주의 - n의 범위가 90 이하이기 때문에 이친수가 엄청 큰 수가 될 수도 있다. Long타입을 사용하도록 한다
코드
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val d = Array(n+1) { LongArray(2) { 0 } }
d[1][1] = 1
for (i in 2..n) {
d[i][0] = d[i-1][0] + d[i-1][1]
d[i][1] = d[i-1][0]
}
print("${d[n][0] + d[n][1]}")
}
부분합 알고리즘을 사용한다
prefixSum[i] = prefixSum[i-1] + a[i]
1. 테이블 정의하기
d[i] = i번째 숫자까지의 연속합의 최댓값
2.점화식 구하기
10 -4 3 1 5 6 -35 12 21 -1d[1] = 10
d[2] = 10 -4
d[3] = 10 + 3
d[i]는 이전 연속합과 a[i] 값을 더하거나 더하지 않거나이기 때문에 다음과 같다
- 이전 위치 연속합 > 현 위치 값 : 이전 위치 연속합 + 현 위치 값
- 이전 위치 연속합 < 현 위치 값 : 현 위치값
d[i] = max(d[i-1] + arr[i], arr[i])
3. 초기값 설정
d[1] = arr[1]
max = d[1]
코드
import java.io.*
import java.util.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
// 수열 입력 받기
val n = readLine().toInt()
val arr = IntArray(100010)
val st = StringTokenizer(readLine())
val d = IntArray(100010)
arr[1] = st.nextToken().toInt()
d[1] = arr[1]
var max = d[1]
for (i in 2..n) {
arr[i] = st.nextToken().toInt()
d[i] = max(d[i-1] + arr[i], arr[i])
max = max(d[i], max)
}
println("$max")
}
// 문제 예시
A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합이 최대가 되는 증가 부분수열은 {1, 2, 50, 60}으로 합은 113
1. 테이블 정의하기
d[i] = i번째 숫자까지의 증가 부분 수열의 합의 최댓값
2.점화식 구하기
1. 현 위치에서 이전에 있는 값과 비교하며 증가하는 수열인지 판단한다 (현 위치 값 > 이전 값)
2. 증가하는 수열일 경우, 현재 부분 수열 최댓값 < 이전 값의 부분 수열 최댓값 + 현재값 이라면 최댓값을 갱신한다
d[cur] = max(d[before] + arr[cur], d[cur])
3. 초기값 설정
부분수열은 자기 자신 하나만 존재하는 경우도 포함하기 때문에 d에 미리 arr의 값을 설정해둔다
코드
import java.io.*
import java.util.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine()!!.toInt()
val arr = IntArray(n)
val d = IntArray(n)
val st = StringTokenizer(readLine())
repeat(n) {
arr[it] = st.nextToken().toInt()
d[it] = arr[it]
}
var max = d[0]
for (curIdx in 0 until n) { // i: 0 ~ n
for (i in 0 until curIdx) { // j : 0 ~ i-1 (이전 값 탐색)
if (arr[curIdx] > arr[i]) {
d[curIdx] = max(d[i] + arr[curIdx], d[curIdx])
max = max(d[curIdx], max)
}
}
}
println("$max")
}
A = {10, 20, 10, 30, 20, 50} 일 때,
가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}
1. 테이블 정의하기
d[i] = i 번째 숫자까지의 증가하는 부분 수열의 최대 길이
2. 점화식 구하기
비슷한 문제를 두세개는 푼거 같은데 익숙해지지 않아서 한번 정리했다
코드
import java.util.*
import java.io.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val arr = IntArray(n)
val st = StringTokenizer(readLine())
repeat(n) {
arr[it] = st.nextToken().toInt()
}
var max = 1
val d = IntArray(n) { 1 }
for (i in 0 until n) {
for (j in 0 until i) {
if (arr[i] > arr[j]) {
d[i] = max(d[i], d[j]+1)
max = max(d[i], max)
}
}
}
println("$max")
}
수열에서 보이는 규칙 (앞 + 뒤 숫자를 더해주면 그 다음 숫자를 구할 수 있다)
1, 1, 1, 2, 2, 3, 4, 5, 7, 9
1+1 = 2
1+1 = 2
1+2 = 3
2+2 = 4
2+3 = 5
3+4=7
4+5 =9
1.테이블 정의하기
d[i] = 파도반 수열 P(N) 나선에 있는 정삼각형 한변의 길이
2.점화식 구하기
d[i] = d[i-3] + d[i-2]
3. 초기값 설정
a[1] = 1
a[2] = 1
a[3] = 1
코드
import java.io.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var t = readLine().toInt()
val bw = BufferedWriter(OutputStreamWriter(System.out))
val d = LongArray(110) { 1 }
while (t-- != 0) {
val n = readLine().toInt()
for (i in 4..n) {
d[i] = d[i-3] + d[i-2]
}
bw.write("${d[n]}\n")
}
bw.close()
}덧셈을 하는 과정에서 엄청 큰 수가 나올 수도 있기 때문에 최대 수를 넣어보고 범위를 체크하자
범위가 크지 않아서 완탐도 가능할 것 같았지만 dp 연습중이니 dp로 풀었다 (BOJ 15486번 퇴사2의 경우엔 완탐이 절대 불가능)
1. 테이블 정의하기
d[i] = i일 상담을 했을 때 얻을 수 있는 최대 이익
2. 점화식 구하기
| 일자 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| t | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| p | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
n -> 1 순으로 테이블을 채운다.
i번째날 일을 할때의 pay와 안할때의 pay를 비교하여 큰 값으로 d[i]를 갱신한다
- i번째날 일을 한다
- 오늘 일하게 되면 i+t[i]날도 일하기 때문에 오늘의 수익과 i+t[i]날 수익을 더한다
- d[i+t[i]] + p[i]
- i번째날 일을 안한다면 수익은 그대로다
- d[i] = d[i+1]
코드
import java.io.*
import java.util.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val t = IntArray(20)
val p = IntArray(20)
val d = IntArray(20)
val endDay = n+1
var st: StringTokenizer
for (i in 1..n) {
st = StringTokenizer(readLine())
t[i] = st.nextToken().toInt()
p[i] = st.nextToken().toInt()
}
var max = 0
for (i in n downTo 1) {
if (i + t[i] <= endDay) { // 상담 가능
d[i] = max(d[i + t[i]] + p[i], d[i+1])
} else d[i] = d[i+1] // 상담 불가
max = max(d[i], max)
}
println("$max")
}
배낭 문제라고 할 만큼 유명한 문제라고 한다. 이 배낭 문제는 dp로 풀 수 있다
k만큼 배낭을 채울 수 있을 때, 배낭 속 물건들의 가치 합이 최대가 되도록 만들어야 한다
d[i][j] = i 번 물건에 대하여 배낭의 무게가 j 일 때, 가질 수 있는 최대 가치
먼저 dp 테이블을 채우는 경우의 수와 그때 가방에 담은 물건의 가치 합을 구하는 시나리오를 써보자
경우 1. 물건의 무게가 가방의 용량보다 크다면 가방에 물건을 담을 수 없다 -> 가치는 그대로 유지
경우 2. 물건의 무게가 가방의 용량보다 작다면 가방에 물건을 담을 수 있다 -> max(2-1, 2-2)
- 2-1. 물건을 담는다 -> 가방에 담겨진 물건의 가치 + 현재 담으려는 물건의 가치
- 2-2. 물건을 담지 않는다 -> 가치는 그대로 유지
이제 시나리오대로 dp 테이블을 채워보자
1번 물건의 무게는 6이고 가치는 13일 때, 이 물건을 수용할 수 있는 건 배낭의 용량이 6, 7일 때이다
1번 물건을 넣기 전에는 아무런 물건도 담겨져 있지 않기 때문에 총 가치는 13이다
| 물건 번호 \ 배낭 용량 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 아무 물건도 안넣음 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1번 (w: 6, v: 13) | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2번 | |||||||
| 3번 | |||||||
| 4번 |
2번 물건의 무게는 4, 가치는 8일 때, 이 물건을 수용할 수 있는 가방은 4이상의 용량을 가져야 한다
이전에 1번 물건을 담았지만, 1번 물건은 무게가 4보다 크기 때문에 영향을 주지 않는다.
따라서 2번 물건을 4 용량을 가진 가방에 담았을 때 가치는 8이 된다
용량이 5인 가방에 무게가 4인 물건을 넣는다면, 가방 속에는 이미 무게가 1인 물건이 들어 있었을 것이다.
따라서 d[1][1] (가방 속에 들어있던 가치) + 8(현재 물건의 가치) 하면 8이 된다
2번 물건을 6,7 용량을 가진 배낭에 넣을 수 있지만, 2 시나리오에 따라 이미 6,7 안에 들어있는 가치가 현재 가치보다 크기 때문에 넣지 않는다.
| 물건 번호 \ 배낭 용량 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 아무 물건도 안넣음 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1번 (w: 6, v: 13) | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2번 (w: 4, v: 8) | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3번 | |||||||
| 4번 |
이런 식으로 테이블을 채운다면 아래와 같이 완성된다
| 물건 번호 \ 배낭 용량 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 아무 물건도 안넣음 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1번 (w: 6, v: 13) | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2번 (w: 4, v: 8) | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3번 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| 4번 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
코드
import java.io.*
import java.util.*
import kotlin.math.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
val n = st.nextToken().toInt() // 물품 수
val k = st.nextToken().toInt() // 버틸 수 있는 무게
val w = IntArray(n+1) // 물품의 무게
val v = IntArray(n+1) // 물품의 가치
for (i in 1..n) {
st = StringTokenizer(readLine())
w[i] = st.nextToken().toInt()
v[i] = st.nextToken().toInt()
}
val d = Array(n+1) { IntArray(k+1) } // 무게당 가질 수 있는 최고의 가치
for (i in 1..n) { // 배낭에 넣을 물건의 번호
for (j in 1..k) { // 무게 (가방의 현재 총 용량)
if (j >= w[i]) { // i번째 물건의 무게가 가방 안에 들어갈 수 있음
// 물건을 넣지 않았을 경우, 넣었을 경우 고려
d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + v[i])
} else d[i][j] = d[i-1][j]
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${d[n][k]}")
bw.close()
}
BOJ 11722. 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
d[i] = i 번째 숫자까지 왔을 때 만들 수 있는 가장 긴 감소하는 부분 수열의 길이
kotlin
import java.io.*
import java.util.*
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val arr = IntArray(n)
val st = StringTokenizer(readLine())
repeat(n) {
arr[it] = st.nextToken().toInt()
}
val d = IntArray(n) { 1 }
var answer = 1
for (i in 1 until n) {
for (j in i-1 downTo 0) {
if (arr[i] < arr[j]) { // 감소하는 부분수열 조건
d[i] = max(d[i], d[j]+1)
answer = max(d[i], answer)
}
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("$answer")
bw.close()
}
'알고리즘&자료구조' 카테고리의 다른 글
| 정렬 알고리즘 활용 문제 풀이 (0) | 2023.02.07 |
|---|---|
| DP: Dynamic Programming (0) | 2023.01.19 |
| kotlin 문자열 자르기 (0) | 2023.01.11 |
| 시뮬레이션 (0) | 2022.12.31 |
| 백트래킹 (0) | 2022.12.24 |
