알고리즘스터디 1주차 - dynamic programming

다이나믹 프로그램은 이전에 스터디할 때 한 번 다뤘던 소재에다가 점.화.식만 잘 쓰면 된다는 스터디장님의 말이 있었지만 사실 기억이 가물가물하므로 동빈나 유튜브 보고 공부했습니당. 재미써여 

근데 선생님,,,, 피보나치랑 이후 문제들이랑 넘 차이가 나지 않나요,,,,? 휴ㅠ

 

개미전사 문제는 이전 스터디 때 한 번 풀었어서 스윽 보고 지나갔다 . 

 

1로 만들기 문제는 감을 못잡다가 설명을 조금 듣고 문제를 풀었을 때

2의 배수o/x , 3의 배수 o/x , 5의 배수 o,x 이렇게 총 8가지의 경우에 대해서 조건문을 달았는데

나동빈 선생님 설명듣고 이해해버림 ㅠㅠ 개쩔어

뭘 하든 1을 뺀 것보다는 빠르게 감소할거다. 그래서 -1한 값을 default 값으로 설정해준다.  

만약 2,3,5 중 하나라도 배수관계가 아니라면 -1을 해야하니까!

만약 2와 5의 배수인 경우 2로 나눈 것보다 5로 나눈 게 더 빠르게 값이 감소할거다.

그렇기 때문에 2로 나눠서 d[i]값에 저장하고 이후 5로 나눈 값이 어차피 더 작기때문에 d[i]랑 나눴을 때 더 작기때문에 상관없어진다 헠 개쩜 ㅠㅠ 어떻게 이렇게 생각하는 걸까  

 

효율적인 화폐구성 

내가 구상한 건 이렇다. 맞았는지 틀렸는지는 모르지만 우선 예제는 맞게 나온다. 

만들어내야하는 금액이 15고 , 화폐단위가 2,3이라면 

f(15)는 min(f(12) , f(13))  . . . 이런식으로 생각을 했다.

#include<iostream>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> value;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	value.resize(n); // 동전
	vector<int>arr(m+1, 10001); //dp
	int coin_value;
	for (int i = 0; i < n; i++) scanf("%d", &value[i]);
	sort(value.begin(), value.end()); // 동전 오름차순 정렬

	for (int i = 1; i < m + 1; i++) {
		for (int j = 0; j < n; j++) {
			coin_value = value[j];
			if (i - coin_value == 0) arr[i] = 1;
			if (i - coin_value > 0) arr[i] = min(arr[i], arr[i - coin_value] + 1);
		}
	}
	if (arr[m] == 10001) printf("-1");
	else printf("%d", arr[m]);
}

ㄹㅇ 나동빈 선생님 천재같다. 

만약 2로만 만들 수 있는 수가 있으면 쭉 dp값을 업데이트해준다. 그 후 3으로만 혹은 3을 추가해서 만들 수 있는 값이 있으면 쭉 업데이트해주는 방식이다.  다양하게 생각하는 법을 많이 배워가는 거 같다. 이거 진짜 감탄함 ㅠ

 

금광문제

내가 생각한 코드 (맞았는지 틀렸는지 모름)

#include<iostream>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int arr[20][20] = {0};
int dp[20][20] = { 0 };
//vector < vector <int> > arr;
//vector < vector <int> > dp;
int main() {
	int test , n, m;
	scanf("%d", &test);
	for (int t = 0; t < test; t++) {

		scanf("%d %d", &n, &m);
		//arr.resize(n + 1, vector<int>(m + 1, 0));
		//dp.resize(n + 1, vector<int>(m + 1, 0));

		//주어진 배열에 nxm 입력
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				scanf("%d", &arr[j][k]);
				dp[j][k] = arr[j][k];
			}
		}
		for (int j = 1; j <= m; j++) {
			for (int k = 1; k <= n; k++) {
				if (k == 1) dp[k][j] = max(dp[k][j - 1], dp[k + 1][j - 1]) + arr[k][j];
				if (k == n) dp[k][j] = max(dp[k - 1][j - 1], dp[k][j - 1]) + arr[k][j];
				dp[k][j] = max({ dp[k - 1][j - 1] , dp[k][j - 1] , dp[k + 1][j - 1] }) + arr[k][j];
			}
		}
		int max_gold = dp[1][m];
		for (int j = 1; j <= n; j++) {
			if (dp[j][m] > max_gold) max_gold = dp[j][m];
			}
		printf("%d\n", max_gold);
	}
}

아 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ자꾸 vector range를 벗어난다고해서 두시간 고민하다가 그냥 평범하게 배열로 풀었더니 바로 된다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

난 맨 위(K==1)랑 맨 아래(K -== n) 일 때 예외처리 해줬는데 천재 나동빈님은 아래처럼 푸셨다.

c++ 캡쳐하기 힘들어서 어차피 로직은 똑같을 테니까 python 캡쳐함. 전체적인 흐름은 똑같아서 살짝 뿌듯하당ㅎㅎ

하지만 선생님은 up , left . down을 만들어서 맨 윗줄 즉 행이 0일떄는 up=0,  행이 n-1일때는 down = 0으로 하셨당.

 

병사 배치하기

생각보다 쉬운데? 하고 풀었는데 답이 아니다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 이렇게 단순할 리가 없지 으익

이 문제의 기본 아이디어는 가장 긴 증가하는 부분수열이라는 전형적인 다이나믹 프로그래밍 문제의 아이디어(LIS 알고리즘)라고 한다.  이 아이디어를 조금 수정해서 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있다고 한다. 

 

-----------------------------------------------------------------------------------------------------------------------------

백준 1463번 1로 만들기 (www.acmicpc.net/problem/1463) 

#include<iostream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> arr;

int main() {
	int n;
	scanf("%d", &n);
	arr.resize(n+1);

	for (int i = 2; i < n+1; i++) {
		arr[i] = arr[i - 1] + 1; //  d[i-1]은 -1 , +1 은 counting
		if (i % 2 == 0) arr[i] = min(arr[i], arr[i / 2]+1);
		if (i % 3 == 0) arr[i] = min(arr[i], arr[i / 3]+1);
	}
	printf("%d", arr[n]);
}

 

위에서 풀었던 거랑 똑같다

 

백준 2579번 계단 오르기 ( www.acmicpc.net/problem/2579 )

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int arr[301];
int dp[301];

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 1; i < n+1; i++) scanf("%d", &arr[i]);
	dp[1] = arr[1];
	dp[2] = max(arr[2], dp[1] + arr[2]);

	for (int i = 3; i < n + 1; i++) {
		dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]);
	}
	printf("%d", dp[n]);
}

 

이거 뭔가 쉬운듯 어려운듯 어렵다.  그냥 연속으로 3번 밟을 수 없게 알고리즘을 짰는데 예제는 맞는데 

3, 1, 2, 3 같은 반례가 존재한다.

마지막 계단은 꼭 밟아야되니까 이전 계단을 밟거나 이전전 계단을 밟거나 둘 중 하나인데 

만약! 이전 계단을 밟았다면 세칸연속이면 안되니까 두칸 더 전 계단을 밟았을 거다 .

이게 뭔 소리인지 이해가 안 간다 나도 ㅎ핳하하ㅏㅎ

무슨 얘기냐면 

그럼 무조건 여기

여길 밟았다?

마지막계단

마지막 계단(n) 기준으로 바로 이전 계단(n-1)을 밟았다면 무조건 (n-3)계단을 밟았을 거다. 

여기서 점화식을 만들면 된다 . 

d[i] = max (d[i-2]+arr[i] , d[i-3]+arr[i-1]+arr[i]) 요려켕 어렵다 어려워