/* DP. 1로 만들기 – 3가지 연산(나누기3, 나누기2, 빼기1)이용 1 만들기 최소연산횟수 */
D[i]: 숫자 i에 대해서 최소 연산 횟수
D[i] = min(D[i-1]+1, (i%2==0) ? D[i/2], (i%3==0) ? D[i/3])
D[1]=1, D[2]=1, D[3]=1
/* DP. 피보나치 */
D[0] = 0
D[1] = 1
D[i] = D[n-2] + D[n-1]
/* DP. 파스칼의 삼각형 */
D[i][j] = (j==0 || j==i) ? 1 : D[i-1][j-1] + D[i-1][j]
/* DP. LCS – Longest Common Sequence */
Xm=<x1 x2 ... xm> Yn=<y1 y2 yn>
D[i][j] : X의 i번째 길이까지, Y의 j번째 길이 까지의 LCS 길이
D[i][j] = D[i-1][j-1] + 1, when xi == yi
= max(D[i-1][j], D[i][j-1], when xi != yj
D[i][0] = 0, D[0][j]=0
/* DP. 집합 – A,B에서 하나씩 빼서, 가장 최소차 합 구하기 */
- 두 집합을 소팅
- 같이 차례대로 빼내야 함.
D[i][j] : A에서 1~i까지, B에서 1~j까지 사용했을 때, 최소 합
D[i][j] = D[i-1][j-1] + abs(A[i] - B[j])
if(i>j && D[i][j] > D[i-1][j]) D[i][j] = D[i-1][j]
if(i<j && D[i][j] > D[i][j-1]) D[i][j] = D[i][j-1]
/* DP. 배낭 */
w[i]: i번째 보석의 무게, v[i]:i번째 보석의 가치
D[i][j] : 0~i개까지의 보석을 사용하고, j무게 만큼의 제한이 있을 때, 취할 수 있는 최대 보석 가치
D[i][j] = (w[i] < j) ? max(D[i-1][j], D[i-1][j-w[i]] + v[i]) : D[i-1][j]
D[0][j]=0
/* DP. 롤러코스트 – N개의 부품. L길이 롤러코스트. 총예산 B. 각 부품: Xi,Ci,Fi */
M[i][k]: i가 끝점인 곳에 위치한 k번째 부품 {x,f,c}
D[i][j]: i 길이 까지, j예산내에서 만들 수 있는 최대 재미값
D[i][j]=-1
newVal = D[M[i][k].x][j-M[i][k].c] + M[i][k].f
D[i][j] = (D[i][j]==-1 || D[i][j] < newVal) ? newVal
where
j > M[i][k].c
D[i-M[i][k].x][j-M[i][k].c] != -1
ans = max(D[L][i])
/* DP. 피보나치의 0,1 리턴 횟수 */
D[i][j] : 숫자 i에 대해서 j가 리턴되는 회수. 이 때 j=0 or 1
D[i][0] = D[i-1][0] + D[i-2][0]
D[i][1] = D[i-1][1] + D[i-2][1]
D[0][0] = 1, D[0][1] = 0
D[1][0] = 0, D[1][1] = 1;
/* DP. 이친수 – 0으로 시작하지 않고, 1이 연속 나타나지 않는 이진수 개수*/
D[i][0]: 0으로 끝나며, i자리인 이친수 개수
D[i][1]: 1으로 끝나며, i자리인 이친수 개수
D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]
D[0][0] = D[0][1] = 0
D[1][0] = 0, D[1][1] =1
/* DP. 인접한 1인 비트의 수 */
D[i][j][0] : 0으로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[i][j][1] : 1로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[1][0][0] = D[1][0][1] = 1
2 <= i <= n, 0 <= j < i
D[i][j][0] = D[i-1][j][0] + D[i-1][j][1]
D[i][j][1] = D[i-1][j][0] + D[i-1][j-1][1]
/* DP. 동전1 – n종류의 동전. 가치가가 K가 되도록하는 경우의 수 */
P[i]: i번째 동전의 가치
D[i][j] : 동전 i개를 써서, j원이 되게하는 경우의 수
D[i][j] = Sum(D[i-1][j-k*P[i]]), 0 <= k <= j/P[i]
D[0][0]=1
/* DP. 동전2 - n종류의 동전, K가 되도록하는 최소 동전갯수 */
p[i] : i번째 동전 가치. 1<=i<=n
D[i] : i원이 되는데 사용되는 최소동전갯수 (-1:impossible) 0<=i<=k
D[k]=?
D[i] = MIN(D[j] + D[i-j]), 0<=j<=(i/2) //D[3] = MIN(D[0]+D[3], D[1]+D[2])
where D[j], D[i-j]가 존재할 때
[구현]
//1.초기화: 각 동전 한 종류로 만들 수 있는 금액 최솟값을 구해 놓는다.
D[i] = -1, 1<=i<k
tmp = p[i] * j; D[tmp] = (D[p[i] * j] == -1) ? j : min(D[tmp],j);
D[0]=0
D[i] = (D[i]===-1) ? D[j] + D[i-j] : min(D[i], D[j] + D[i-j], 2<=i<=k, 1<=j<=(k/p[i])
/* DP. 포도주 시식 – 연속 3잔 마실 수 없음 */
- D[i] : i번째 포도주까지 최댓값
- 제일 마지막 포도주를 기준으로 해서, 아래 3가지 경우 중 최댓값.
1)안마시는 경우 D[i-1]
2)마시고, n-1 번째것을 마신 경우: V[i] + V[i-1] + D[i-3]
3)마시고, n-1번째것을 안 마신 경우: V[i] + D[i-2]
cf)유사문제로 계단 문제가 있는데, 이 경우 제일 마지막 계단은 무조건 밟는 것으로, 포도주 문제와 약간 다름. 계단 처럼 무조건 마지막 계단을 밟는 경우는, 위의 2번 3번 케이스만 고려하면 됨
/* DP. 막대기 – n종류 막대기. 총길이가 k가 되도록하는 경우의 수 */
- n개가 아닌, n종류라는 데 주의. 즉, 1종류를 여러번 사용 가능
- D[i][j]: i개까지의 막대기를 이용해서, j 길이 만큼을 만들 수 있는 경우의 수
- D[0][0]=1 ==> 0개의 막대기를 이용해서 길이 0만큼 만들 수 있는 경우의 수
D[i][j] = Sum(D[i-1][j - k x s[i]), 0 <= k <= j/s[i]
==> i개까지 막대기를 사용해서 j길이만큼을 만들 수 있는 경우의 수는,
한 개 덜 사용하면서(i-1개 사용하면서), i번째 막대기를 0번~j/s[i]번까지 사용할 때의 경우의 수를 모두 합한 것.
즉, i번째 막대기를 안 사용할 수도 있고, 1개 사용할 수도 2개 사용할 수도 있는 것.
최대 몇개까지 사용할 수 있는 가는, j - k x s[i] > 0 이므로, k <= j/s[i] 일 때까지.
/* DP. 합분해 – 0~N까지의 정수 K개를 더해 N이되는 경우의 수 */
- D[K][N]을 구하는 것. 숫자를 K개 더해서 그 합이 N이 되는 경우의 수
- D[i][j]: 숫자를 i개 더해서, 그 합이 j가 되는 경우의 수
- D[i][j] = D[i-1][j] + D[i-1][j-1] + ... +D[i-1][0]
= Sum(D[i-1][j – k]), 0 <= k <= j
==> i개 더해서 합이 j가 되는 경우의 수는, i-1개 사용해서 j가 된 후 0을 더하거나(i번째 수로 0을 선택), i-1개 사용해서 합이 j-1인 상태에서 i번째로 1을 사용하거나, j-2에서 2를 사용하는 등의 조합이 가능(수는 0~j까지 존재하니깐)
- D[0][0]=1 ==> 숫자 0개를 더해서 그 합이 0이되는 경우의 수는 1
/* DP. 돌다리 건너기 – 문자열 돌다리 2개를, 목표 문자열순이되게 번갈아가면서 밟는 경우수*/
An = 목표 문자열
Bm : 천사 돌다리
Cm : 악마 돌다리
D[i][j][0] : 천사돌다리로 끝나면서, i번째 목표문자열까지, j번째 돌다리문자를 이용해서 만들 수 있는 최대 경우 수
D[i][j][1] : 악마돌다리로 끝나면서, ...
if(A[i] == B[j]) //목표문자열 i번째와 천사돌다리 j번째가 같다면
D[i][j][0] = Sum(D[i-1][k][1]), 0<= k <= j-1 // (j-1)까지의 악마돌다리에서의 경우의 수 합
if(A[i] == C[j]) //목표문자열 i번째와 악마돌다리 j번째가 같다면
D[i][j][1] = Sum(D[i-1][k][0]), 0<= k <= j-1 // (j-1)까지의 천사돌다리에서의 경우의 수 합
D[0][0][0] = D[0][0][1] = 1
//0번째 목표문자열, 0번째 돌다리문자 이용 경우의 수로, 1의 의미가 좀 약하지만,
//이렇게 해야 위의 점화식의 Sum값이 제대로 동작
ans = Sum(D[n][k][0] + D[n][k][1]), 1<= k <=m //모두 더해줌에 유의. 달랑 D[n][m][0] + D[n][m][1] 이 아님
//돌다리의 끝까지인 m까지 사용안하고도, 목표문자열을 만족시킬 수 있기 때문
/* DP. 마트료시카 - LIS */
- LIS(Longest Increasing Subsequence) 문제임. 즉, 최장 증가 수열을 찾는 것
- D[i]: 1~i번째 까지 인형을 사용해서 담을 수 있는 최대 인형 개수
- i번째 인형과, j=1~(i-1)번째 인형을 차례대로 비교. 그중에서 i번째 인형보다 작은인형들 중 가장 최대인 D[j]가 D[i]값이 됨
for(int j=1;j<i;++j) if(s[i] > s[j]) D[i] = max(D[i],D[j])
- 기본으로 모든 D[i]값은, i번째 인형 자기 자신을 담을 수 있으므로 1이상. 즉, i번째 인형을 처리할 때 D[i]++
- 이렇게 1~N까지 구한 D[i]중에서 최댓값이 답
for (i = 1; i <= n; i++){
for (j = 1; j<i; j++){
if (s[j] < s[i]) d[i] = max(d[i], d[j]);
}
d[i]++;
ans = max(ans, d[i]);
}
/* DP. 폐지 줍기 – N * N 격자에서 폐지 최대값 */
- D[i][j] : (i,j)칸에서의 폐지 최대값
D[1][1] = a[1][1]
D[i][j] = max(D[i][j-1], D[i-1][j]) + a[i][j]
==> a[i][j] += max(a[i][j-1], a[i-1][j] 로도 가능
/* DP. 조약돌 놓기 – 3 x n 테이블에 조약돌 최대값되게 놓기 */
- 1~i열까지의 최대합을 고려해보면, i열에 대해서, 다음과 같은 4가지 패턴으로 분류할 수 있다.
i 열 (i-1)열
1)1행 값이 선택된 경우 max(패턴2, 패턴3) + 1행값
2)2행 max(패턴1, 패턴3) + 2행값
3)3행 max(패턴1, 패턴2) + 3행값
4)1행과 3행 패턴2 + 1행값 + 3행값
- D[i][p] : i열이 패턴 p로 놓일 때의 최고 점수
W[i][p] : i열이 패턴 p로 놓일 때, i열에 돌이 놓인곳의 점수 합 ->테이블값으로부터 미리 구해둔다.
- D[i][p] = max(D[i][q] + W[i][p] , i>=2 , q:p와 양립하는 패턴
D[1][p] = W[1][p]
- 슈도코드
for (i = 2 to n)
for (p = 1 to 4)
D[i][p] = max(D[i][q]) + W[i][p]
return max(D[n][p]), p:1~4
/* DP. 행렬곱 순서 */
D[i][j]: i번째 행렬에서부터 j번째 행렬까지의 최소 곱
D[i][j] = min(D[i][k] + D[k+1][j] + P[i-1] * P[k] * P[j]), i<= k <j
D[i][j] = 0 , when i == j
for (int r = 1; r <= (N - 1); ++r) { //행렬을 몇개씩 묶으면서 시도해볼까를 나타냄. 1이면 두 개.
for (int i = 1; i <= (N - r); ++i) { //i번째 행렬부터,
int j = i + r; //j번째째 행렬까지
int low = INT_MAX;
int minK;
for (int k = i; k < j; ++k) { //k의 범위=[i,j)
int tmp = D[i][k] + D[k + 1][j] + P[i - 1] * P[k] * P[j];
if (tmp < low) {
low = tmp;
minK = k;
}
}
D[i][j] = low;
T[i][j] = minK; //괄호순서를 저장
}
}
//괄호 프린트하기
예를 들어 행렬 A1, A2, A3 가 있을 때, 계산결과 T테이블 값이 다음과 같이 도출되었다 하자.
T[1][2] = 1, T[2][3] = 2, T[1][3] = 2 나머지는 갱신안되어 zero
이것은 (A1A2)A3 로 계산되어야한다는 것을 의미. (if i==T[i][j] --> 그대로)
void print_array(int i, int j) {
if (i == j) printf("A%d", i);
else {
printf("(");
print_array(i, T[i][j]);
print_array(T[i][j] + 1, j);
printf(")");
}
}
//실제 행렬곱
vector<vector<int> > doMulti(vector<vector<int> > a, vector<vector<int> > b) {
int p, q, r;
p = a.size(); q = b.size(); r = b[0].size();
vector<vector<int> > c(p,vector<int>(r,0));
for (int i = 0; i < p; ++i) {
for (int j = 0; j < r; ++j) {
c[i][j] = 0;
for (int k = 0; k < q; ++k) c[i][j] += a[i][k] * b[k][j];
}
}
return c;
}
vector<vector<int> > multi(int i, int j) {
if (i == j) return v[i];
return doMulti(multi(i,T[i][j]), multi(T[i][j]+1,j));
}
-끝-
'알고리즘 > 알고리즘 노트' 카테고리의 다른 글
| [코드모음] - 문자열 (0) | 2016.08.19 |
|---|---|
| [코드모음]-정렬, 자료구조 (0) | 2016.08.19 |
| [코드모음]-기하, (0) | 2016.08.19 |
| [코드 모음]-탐색, 그래프 (0) | 2016.08.16 |
| [수학]-문제 (0) | 2016.08.11 |