백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
● 400 - 다이나믹 프로그래밍 1
다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다.
아래의 다이나믹 프로그래밍 프로그래밍1) 맛보기 강의를 가져왔다.
피보나치수를 예를 들어서 설명해 준다.
메모이제이션을 설명해준다.
탑다운과 바텀업도 알려준다.
-
탑다운 -> 재귀함수
-
바텀업 -> 작은문제부터 차례대로 푼다.
-
f[0] = 0;
-
f[1] = 1;
-
for(int i ~
-
이런 스타일
-
문제풀이전략
- 점화식을 만들자.
- 문제를 많이 풀면서 감을 잡는것이 중요하다.
● 400 - 다이나믹 프로그래밍 1
- 1로 만들기
- 2×n 타일링
- 2×n 타일링 2
- 1, 2, 3 더하기
- 카드 구매하기
- 카드 구매하기 2
- 1, 2, 3 더하기 5
- 쉬운 계단 수
- 이친수
- 가장 긴 증가하는 부분 수열
- 가장 긴 증가하는 부분 수열 4
- 연속합
- 제곱수의 합
- 합분해
이 블로그를 참고하자 instories.tistory.com/28
1463 1로 만들기 - 실버3 www.acmicpc.net/problem/1463
2×n 타일링 - 실버3 www.acmicpc.net/problem/11726
2×n 타일링 2 - 실버3 www.acmicpc.net/problem/11727
1, 2, 3 더하기 - 실버3 www.acmicpc.net/problem/9095
카드 구매하기 - 실버1 www.acmicpc.net/problem/11052
카드 구매하기 2 - 실버1 www.acmicpc.net/problem/16194
1, 2, 3 더하기 5 - 실버1 www.acmicpc.net/problem/11052
쉬운 계단 수 - 실버1 www.acmicpc.net/problem/10844
이친수 - 실버3 www.acmicpc.net/problem/2193
가장 긴 증가하는 부분 수열 -
가장 긴 증가하는 부분 수열 4 - 골드4 www.acmicpc.net/problem/14002
연속합 - 실버2
지금까지 모두 더한 값과 현재 값을 비교했는데 현재 값이 더 크다면 기존 합은 버리고 새로 시작
c++
int arr[n];
int dp[n];
for (i = 0; i < n; i++) scanf("%d", &arr[i]);
dp[0] = arr[0];
ans = dp[0];
for (i = 1; i < n; i++) {
dp[i] = max(dp[i-1] + arr[i], arr[i]);
ans = max(ans, dp[i]);
}
제곱수의 합 - 실버3 www.acmicpc.net/problem/1699
합분해 - 골드5 www.acmicpc.net/problem/2225
● 401 - 다이나믹 프로그래밍 1 (연습)
구)다이나믹 프로그래밍 문제풀이1 - 맛보기강의
- 1, 2, 3 더하기 3
- RGB거리 구)
- 동물원 구)
- 오르막 수
- 스티커
- 포도주 시식
- 정수 삼각형구)
- 가장 큰 증가 부분 수열
- 가장 긴 감소하는 부분 수열
- 가장 긴 바이토닉 부분 수열
- 연속합 2
- 타일 채우기
백준 1, 2, 3 더하기 3 - 실버2
백준 1149 RGB거리 - 실버1
[][][] (R,G,B)
[][][] (minGB+R, minRB+G, minRG+B)
[][][] (minGB+R, minRB+G, minRG+B)
...
[][][]
마지막줄의 3개중 가장작은값
백준 1309 동물원 - 실버1 www.acmicpc.net/problem/1309
오르막 수
스티커 - 실버2www.acmicpc.net/problem/9465
백준 2156 포도주 시식 - 실버1www.acmicpc.net/problem/2156
3번 연속 불가
-
가능한 종류
-
0번 연속가능: 안마시겠다는 뜻
-
dp[n] = dp[n-1]
-
-
1번 연속가능
-
dp[n] = dp[n-2] + p[n]
-
-
2번 연속가능
-
dp[n] = dp[n-3] + p[n-1] + p[n]
-
n-3 이 존재하므로, n은 3부터 시작 가능하고, n=1과 n=2는 초기화시켜준다.
-
-
-
점화식
-
dp[n] = 포도주 n개 일때, 가장 많이 마실 수 있는 양
-
p[n] = n번째 포도주의 양
-
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int p[] = new int[n+1];
int dp[] = new int[n+1];
for(int i = 1; i <= n; i++)
p[i] = sc.nextInt();
dp[1] = p[1];
if(n>1) dp[2] = p[1] + p[2];
for(int i = 3; i <= n; i++) {
dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+p[i], dp[i-3] + p[i-1] + p[i]));
}
System.out.println(dp[n]);
}
백준 1932 정수 삼각형 (숫자삼각형) - 실버1
역시 기초 강의부터 그냥 돈주고 들을걸 그랬다.
가장 큰 증가 부분 수열 - 실버2www.acmicpc.net/problem/11055
가장 긴 감소하는 부분 수열 - 실버2www.acmicpc.net/problem/11722
가장 긴 바이토닉 부분 수열 - 골드3www.acmicpc.net/problem/11054
백준 13398 연속합 2 - 골드5www.acmicpc.net/problem/13398
배열이 두줄 필요하다.
윗줄은 제거않는버전, max(아무것도 안더한거, 지금까지더한거)+현재값
아랫줄은 하나제거한버전, max(하나뺀거+현재값더한거, 윗줄의이전최대값(즉,현재값을제거한것))
ans = max(max(윗줄, 아랫줄), 이전답)
근데 얼핏생각하며 아랫줄버전에서 계속 하나지운거에 또지우고 또지우고 그런 dp를 할수도 있지 않을까 싶은데..
잘 생각해보면,
1, -1, -1, 2 인 경우
1라운드
윗줄에서 1
아랫줄에서 1
2라운드 1, -1
윗줄에서 0
아랫줄에서 1(-1을 제거하였음)
3라운드 1, -1, -1
윗줄에서 -1
아랫줄에서 1(이미하나제거되어있음)+-1, -1(이미하나제거되있음) 중에 두번째꺼를 선택하게 되면 두개를 제거하는건데 동시에 맨처음꺼만 선택한 수열이됨
ans 는 현재 1
4라운드 1, -1, -1, 2
윗줄에서 2(현재값)
아랫줄에서 0+2, -1
ans는 2가됨
이런식으로 초기화 되므로, 연속해서 숫자를 빼줄 가능성은 없어짐
dp[0][0] = a[0];
dp[0][1] = a[0];
ans = max(dp[0][0], dp[0][1]);
for (int i = 1; i < n; i++)
{
dp[i][0] = max(0, dp[i - 1][0]) + a[i];
dp[i][1] = max(dp[i - 1][1] + a[i], dp[i - 1][0]);
ans = max(max(dp[i][0],dp[i][1]), ans);
}
타일 채우기 - 실버2
● 402 - 다이나믹 프로그래밍 1 (도전)
백준 1309 동물원 - 실버1www.acmicpc.net/problem/1309
첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. <- 이말은 출력의 첫째줄에 경우의 수의 결과를 쓰라는것이다.
동물원의 첫째줄에 사자를 배치하는 경우가 아닌...
[][][] (없음,왼,오)
[][][] (없음+왼+오, 없음+오, 없음+왼)
...
[][][]
이런식으로 구해서 마지막줄의 합을 출력하면 된다.
백준 RGB거리 2 - 골드4www.acmicpc.net/problem/17404
이전문제는 [][][][]직선거리 모양이었는데, 이번문제는 [1][][][][N] 1번과 N번이 붙어있는 원형모양이다.
[][][]
[][][]
[][][]
...
[][][]
를 구할 때,
[R][x][x]
...
[][G][B]
로 시작한 경우의 G,B
[X][G][X]
...
[R][][B]
RB
[X][x][B]
...
[R][G][]
를 구해서 6개의 중 가장 작은 값이 답.
백준 2225 합분해 - 골드5www.acmicpc.net/problem/2225
0부터 N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수
9 6
0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 6
0 0 0 0 1 5
0 0 0 1 1 4
0 0 1 1 1 3
0 1 1 1 1 2
1 1 1 1 1 1
이런식..
순서가 바뀌면 다른 경우임
예를들면
0 0 0 0 0 6 과
6 0 0 0 0 0 은 다른 경우
K-1개 + 1개 = N
[N-L] + L = N
DP[K][N] = Sigma(DP[K-1][N-L])
0 <= L <= N
for(i=0부터 n까지)
DP[1개][값i] = 1가지
for(i=1부터 k까지)
for(j = 0부터 n 까지)
for(l = 0 부터 j까지)
dp[i][j] += dp[i-1][j-1]; // dp[K][N] 까지 가는동안 계속 "dp[i-1][j-l]"를 더한다.
.
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
백준 알고리즘 강의 후기(코드플러스): 중급2 - 다이나믹 프로그래밍2 (DP2)
백준 알고리즘 강의 후기(코드플러스): 중급3 - 다이나믹 프로그래밍3 (DP3)
.
