DP 문제의 경우 공식을 생각해야 하는데 어려운 문제의 경우 굉장히 어렵습니다.
책에 실린 실전 문제 중 특별히 어려운 문제는 없다.
1로 만들다
문제는 주어진 정수 X를 1로 만드는 최소 연산 수를 찾는 것입니다.
작업 유형
- X%5 == 0이면 5로 나눕니다.
- X%3 == 0이면 3으로 나눕니다.
- X%2 == 0 나누기 2인 경우
- X-1을 하다
DP 문제를 풀 때 초기 값을 설정하고 나머지는 최대 값으로 채우거나 비워 둘 수 있습니다.
이 질문에서 지표 1, 2, 3, 5의 값을 1로 설정할 수 있습니다.
네 번째 값을 찾으면 문제 공식을 찾을 수 있습니다.
dp(4) = 최소(dp(4-1)+1 , dp(4/2)+1)
산술을 알고 있다면 dp(산술 결과) + 1을 비교하여 최소값을 찾는 공식을 만들 수 있습니다.
dp(i) = min( dp(i-1)+1, dp(i/2)+1, dp(i/3)+1, dp(i/5)+1 )
이때 min에 포함된 비그룹 값이 계산 가능한 값이다.
(나누거나 -1)
int main() {
int X;
int i;
int small;
scanf("%d", &X);
dp(1) = 0;
dp(2) = 1;
dp(3) = 1;
dp(5) = 1;
for (i = 4; i <= X; i++) {
small = 30001;
if (i % 5 == 0) {
small = min(small, dp(i / 5) + 1);
}
if (i % 3 == 0) {
small = min(small, dp(i / 3) + 1);
}
if (i % 2 == 0) {
small = min(small, dp(i / 2) + 1);
}
small = min(small, dp(i - 1) + 1);
dp(i) = small;
}
printf("%d", dp(X));
}
/*
26
*/
개미 전사
문제는 주어진 N 종류의 음식에서 얻을 수 있는 최대 음식 수를 찾는 것입니다.
나는 개인적으로 이 질문이 마지막 질문보다 쉽다고 생각하지만, 반 제곱 더 어렵습니다.
문제 상황은 다음과 같습니다.
- 적어도 한 블록 떨어진 곳에 식품 창고를 약탈할 수 있습니다.
조건은 첫 번째 및 두 번째 열에 대한 초기 dp 값을 설정해야 함을 알려줍니다.
초기값은 각 곡물 창고의 값입니다.
이전 질문과 마찬가지로 이 질문도 세 번째 열의 dp 값을 계산하면서 수식을 얻을 수 있습니다.
dp(3) = min( dp(1)+arr(3), dp(2) )
현재 dp 값은 한 칸을 넘어야 하므로 이전 칸의 dp 값과 현재 칸의 값과 이전 칸의 dp 값의 합 중 작은 값이 됩니다.
수식에 대입하면 다음과 같이 됩니다.
dp(i) = min( dp(i-1), dp(i-2)+arr(i) )
int max(int a, int b) {
if (a < b) return b;
return a;
}
int main() {
int N;
int arr(1001), dp(1001);
int i;
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d", &arr(i));
}
dp(0) = arr(0);
dp(1) = max(dp(0), arr(1));
//dp(2) = max(dp(0) + arr(2), dp(1));
for (i = 2; i < N; i++) {
dp(i) = max(dp(i - 2) + arr(i), dp(i - 1));
}
printf("%d", dp(N - 1));
}
/*
4
1 3 1 5
*/
바닥 공사
어릴때부터(도형채우기..) 어려웠던 수업이라 처음으로 풀어보는 수업입니다.
하지만 이 문제를 풀고 나니 앞으로 같은 유형의 문제를 쉽게 풀 수 있을 것 같다.
문제는 폭이 N이고 길이가 2인 바닥이 1×2, 2×1, 2×2 타일로 채워진 모든 경우의 수를 찾는 것입니다.
1<=N<=1000의 값을 입력하고 출력값은 796796으로 나눈 나머지를 출력해야 합니다.
문제를 풀 때 바닥을 왼쪽에서 오른쪽으로 채우는 것을 생각하고 그림을 그려 문제를 풀면 쉽게 공식이 떠오를 수 있습니다.
해당 타일은 가로 길이가 1과 2 두 개이므로 초기 값은 각각 1과 2입니다.
가로 방향의 길이는 2가지이므로 왼쪽부터 채우면 i-1, i-2로 생각할 수 있습니다.
이때, 주어진 타일 폭은 1×2와 2×2의 2가지 경우가 있으므로 i-2의 2가지 경우가 있다.
이 질문은 모든 경우의 경우의 수를 구하는 것이므로 비교 후 dp 값을 최소값이나 최대값으로 설정하는 대신 이전 값을 더하면 됩니다.
이것을 생각하면 N이 3이면 공식을 얻을 수 있습니다.
dp(3) = dp(2) + dp(1) + dp(1)
dp(i) = dp(i-1) + dp(i-2) x 2
int max(int a, int b) {
if (a < b) return b;
return a;
}
int main() {
int N;
int dp(1001);
int i;
scanf("%d", &N);
dp(1) = 1;
dp(2) = 3;
//dp(3) = dp(2) + dp(1) * 2;
for (i = 3; i <= N; i++) {
dp(i) = dp(i - 1) + dp(i - 2) * 2 % 796796;
}
printf("%d", dp(N));
}
/*
3
*/
효과적인 통화 구성
이것은 첫 번째 질문과 거의 같습니다.
차이점은 나눌 수를 허용한다는 것입니다.
N개의 통화 단위를 입력으로 하고 M을 그 단위 중 가장 작은 통화 단위로 만드는 문제입니다.
먼저 dp 값을 최대값으로 초기화합니다(타이틀에 있는 money의 최대값은 10000이므로 10001로 설정 가능). 그런 다음 dp의 초기 값에 대한 인덱스로 입력 통화 단위를 설정하고 dp(coin())을 1로 설정합니다.
(2원이 있다면 dp(2)는 1이고 동전 1개가 2원이 됩니다.
) 동전의 최소값에서 M까지 N단위로 나누고 비교하여 최소값을 얻습니다.
이 문제를 스스로 해결하는 것도 쉽습니다.
2,3의 경우
dp(1) = 최대
dp(2) = 1
dp(3) = 1
dp(4) = 최소( dp(4) , dp(4-2) + 1 , dp(4-3) + 1) = 최소(최대, 2, 최대) = 2
dp(5) = 최소( dp(5) , dp(5-2) +1 , dp(5-3) +1) = 최소(최대, 2, 2) = 2dp(i) = min( dp(i) , dp(i-coin(0))+1, dp(i-coin(1))+1, …, dp(i-coin(j))+ 하나)
#define MAX 10001
int coin(101);
int dp(101);
int N, M;
int min(int a, int b) {
if (a > b) return b;
return a;
}
int findMin(int num) {
int i;
int small=dp(num);
for (i = 0; i < N; i++) {
if (num - coin(i) > 0) {
small = min(dp(num - coin(i))+1, small);
}
}
return small;
}
int main() {
int i;
scanf("%d %d", &N, &M);
for (i = 1; i <= M; i++) {
dp(i) = MAX;
}
//3원 종류가 있으면 dp(3)은 1개로 만들 수 있음
for (i = 0; i < N; i++) {
scanf("%d", &coin(i));
dp(coin(i)) = 1;
}
sort(coin, coin + N);
for (i = coin(0); i <= M; i++) {
dp(i) = findMin(i);
//printf("dp(%d): %d\n", i, dp(i));
}
if (dp(M) == MAX) printf("-1");
else printf("%d", dp(M));
}
/*
2 15
2
3
3 4
3
5
7
*/
http://www.yes24.com/product/goods/91433923
파이썬을 이용한 코딩 테스트입니다 – YES24
나동빈의 유튜브 라이브 https://www.youtube.com/c/dongbinnaIT 카카오, 삼성전자, 네이버, 라인, 취업준비생이라면 누구나!
취업 성공의 열쇠는 알고리즘 면접!
IT 구직자
www.yes24.com