Mystika+Algorithm

'알고리즘/동적 계획법'에 해당되는 글 11건

  1. ALGOSPOT - BOGGLE
  2. ALGOSPOT - SNAIL
  3. ALGOSPOT - JLIS
  4. ALGOSPOT - LIS
  5. BOJ 1660 - 캡틴 이다솜

ALGOSPOT - BOGGLE

알고리즘/동적 계획법

문제

https://algospot.com/judge/problem/read/BOGGLE



풀이

동적 계획법 문제같아서 동적 계획법으로 풀었다. 그래프로 풀 수 있지 않을까라는 생각이 들지만 나는 DP로만 풀었으므로 DP 풀이만 적음.

먼저 findAll()과 solve() 두개의 함수를 작성했다. findAll()은 좌표 [0,0]부터 [4,4]까지, 즉 모든 칸에서 입력받은 문자열을 찾을 수 있는지 확인하는 solve()를 실행시키는 함수이다.

solve함수는 세개의 인자를 받는데 각각 게임판의 y좌표, x좌표, 게임판의 y,x 좌표의 문자열과 비교할 찾을 문자열의 index번째 문자다.

메모이제이션은 dp[y][x][index] = 게임판[y][x] 좌표에서 시작해 word[index] 이후의 문자들을 매칭 시킬수 있는가에 대해 메모이제이션을 적용했다. 입력값이 작아서 최대 250크기 만큼의 배열만 사용하므로 3차원 배열을 사용해도 문제가 없었다.


#include <cstdio>
#include <cstring>
char map[5][6],word[11];
int dp[5][5][10];
int solve(int y, int x, int index){
	int i,j;
	//메모이제이션 값 체크. 초기값 -1이 아니라면 바로 리턴
	int& ret = dp[y][x][index];
	if(ret != -1) return ret;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			//인접한 칸을 검사하며 게임판을 벗어났다면 패스한다.
			if((i==0&&j==0)||y+i<0||y+i>4||x+j<0||x+j>4) continue;

			//매칭되는 문자열을 찾았을때
			if(map[y+i][x+j] == word[index]){
				//다음 문자가 null이라면 즉, 모든 문자를 다 찾았다면 true를 반환한다.
				if(word[index+1] == '\0') return ret = 1;
				//아직 다 찾지 못했으므로 현재 위치에서 시작하는 다음 문자를 찾는 함수를 재귀 호출한다.
				ret = solve(y+i,x+j,index+1);
				//만약 현재 위치에서 문자열 매칭에 성공했다면 더 찾을 필요가 없으므로 바로 1를 반환한다.
				if(ret==1) return ret;
			}
		}			
	}
	//여기까지 왔다면 문자를 찾지 못한것이므로 0을 반환한다.
	return ret = 0;
}
int findAll(){
	int i,j;
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			int& ret = dp[i][j][0];
			if(ret != -1) return ret;
			if(map[i][j] == word[0]){
				ret = solve(i,j,1);
				if(ret) return ret;
			}
		}
	}
	return 0;
}
int main(){
	int i,j,t,n;
	scanf("%d",&t);
	while(t--){
		for(i=0;i<5;i++)
			scanf(" %s",map[i]);
		scanf(" %d",&n);
		while(n--){
			memset(dp,-1,sizeof(int)*250);
			scanf(" %s",word);
			printf("%s %s\n",word,findAll()?"YES":"NO");
		}
	}
}


저작자 표시 비영리 변경 금지
신고

ALGOSPOT - SNAIL

알고리즘/동적 계획법

문제

https://algospot.com/judge/problem/read/SNAIL



풀이

완전 탐색 코드를 먼저 만들었다. 비가 올 확률이 75%이고 비가 올때는 2m, 비가 오지 않을 확률이 25%이고 비가 오지 않을때는 1m씩 올라가므로 그냥 재귀적으로 함수를 호출해주며 m일이 지났을때 우물을 다 올라갔는지 확인해주는 코드를 작성했다.

#include <cstdio>
int n,m;
double solve(int cur, int day){
	if(day == m) return cur >= n;
	return (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		printf("%.10lf\n",solve(0,0));
	}
}


잘 작동하지만 완전 탐색인만큼 큰 입력이 들어오면 엄청 오래 걸린다. 그러므로 메모이제이션을 적용해서 중복 계산을 하지 않도록 코드를 바꿔줘야 한다. dp[height][day] = day일째에 height만큼 올라 왔을때 우물 끝까지 올라갈 확률이라 하고 메모이제이션을 적용했다.


또한 아래와 같은 부분에 대해 고민을 하며 코드를 작성했다.

  • double은 -1로 memset이 안되는거 같다. > 그래서 직접 for문으로 값을 초기화시켰다.
  • 올라갈 수 있는 최대 높이는 N이 아니다. > N-1에서 비가 와 N+1까지 올라갈 수 있는 경우가 있으므로 배열 크기를 1 더 잡아줘야 한다.
#include <cstdio>
int n,m;
double dp[1003][1001];
double solve(int cur, int day){
	if(day == m) return cur >= n;
	if(cur >= n) return 1.;
	double& ret = dp[cur][day];
	if(ret != -1.)	return ret;
	return ret = (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=1002;i++)
			for(int j=0;j<=1000;j++)
				dp[i][j] = -1.0;
		printf("%.10lf\n",solve(0,0));
	}
}



저작자 표시 비영리 변경 금지
신고

ALGOSPOT - JLIS

알고리즘/동적 계획법

문제

https://algospot.com/judge/problem/read/JLIS



풀이

이 문제를 완전 처음에.. 그러니까 동적계획법이 뭔지도 모르고 접했을때는 그냥 두 수열을 중복되는 수 없이 한 수열로 합친 다음에 합친 수열의 길이를 출력하게 했다. 놀랍게도 이 방식이 예제 입력에 대해서는 제대로 된 답을 출력해주기 때문에 코드를 제출했으나 당연히 WA를 받았다.

그리고 몇 일 전에 LIS 문제를 해결한 뒤 이 문제를 다시 접했는데 이 때는 LIS와 비슷하게 해결하면 될 줄 알았다. 두 수열의 LIS를 각각 구한뒤 각 수열의 길이를 출력하는 방법을 생각해보았으나 세 번째 예제인 $A=\{10, 20, 30\}, B=\{10, 20, 30, 1, 2\}$같은 경우에서는 A,B 수열 모두 $\{10, 20, 30\}$가 LIS이므로 6을 반환하지만 실제로는 $A=\{10, 20, 30\}, B=\{1, 2\}$인 5가 답이다.

LIS 문제는 한 개의 수열에 대한 인덱스 값을 인수로 받는 solve(int)를 작성했었는데 이 문제도 비슷하게 두개의 수열의 인덱스 값을 각각 받는 solve(int, int)를 작성하면 될 것 같았다. 문제를 해결하는 코드를 작성하면서 아래와 같은 부분에 대해 유의하며 작성했다.

  • 모든 원소의 값은 signed integer 범위에 들어간다. 즉, 최소값은 INT_MIN이다.
  • 한 수열의 원소를 아무것도 선택하지 않는 상태가 있을 수 있다.
위 부분을 생각하며 아래와 같은 코드를 작성했다. 처음에는 두 수열 모두 아무것도 시작하지 않은 상태(-1, -1)로 시작하며 재귀적으로 solve(Ai, Bi)를 호출하여 JLIS를 구하게 했다. 



#include <cstdio>
#include <cstring>
#include <climits>
int n,m,A[100],B[100],dp[101][101];
int max(int a, int b){return a>b?a:b;}
int solve(int Ai, int Bi){
	int &ret = dp[Ai+1][Bi+1];
	if(ret != -1) return ret;
	ret = 0;
	int pA, pB, pivot;
	pA = Ai == -1 ? INT_MIN : A[Ai];
	pB = Bi == -1 ? INT_MIN : B[Bi];
	pivot = max(pA,pB);
	for(int i=Ai+1;i<n;i++)
		if(pivot < A[i])
			ret = max(ret, solve(i,Bi)+1);
	for(int i=Bi+1;i<m;i++)
		if(pivot < B[i])
			ret = max(ret, solve(Ai,i)+1);
	return ret;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int i;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		memset(dp,-1,sizeof(int)*101*101);
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		for(i=0;i<m;i++)
			scanf("%d",&B[i]); 
		printf("%d\n",solve(-1,-1));
	}
}


저작자 표시 비영리 변경 금지
신고

ALGOSPOT - LIS

알고리즘/동적 계획법

문제


풀이

가장 긴 증가하는 수열의 길이를 찾는 문제이다. 알고리즘 공부를 처음 시작했을무렵 이 문제를 접했을때는 정말 어떻게 풀어야할지 막막했었다 ㅠㅠ. 문제를 풀고 나니 이미 4달전에 해결 한 문제인데 기억이 나지 않는걸 보면 제대로 공부하지 않았던게 아닐까 싶다.


아무튼 이 문제는 처음에 완전 탐색 코드를 짜고 접근했다. 첫번째 수(0번째)부터 N-1번째 수 까지 모든 경우를 돌면서 가장 긴 LIS를 찾는 코드이다.

#include <stdio.h>
int n,num[500];
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 0;
	for(i=pos+1;i<n;i++){
		if(num[pos] < num[i]){
			ret = max(ret, solve(i)+1);
		}
	}
	return ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&num[i]);
		}
		for(i=0;i<n-1;i++){
			ans = max(ans, solve(i));
		}
		printf("%d\n",ans);
	}
	return 0;
}


위 코드는 메모이제이션을 적용하지 않은 코드라 같은 값을 여러번 구한다. 그러니 여기서 메모이제이션을 적용해줘야한다. 메모이제이션을 적용할 dp 배열을 만들고 dp[x] = x번째 수부터 시작할때 가장 긴 LIS의 길이의 값을 저장하게 하였다.

#include <stdio.h>
#include <string.h>
int n,num[500],dp[500]; //dp[x] == -1이면 x번째 수부터 시작하는 LIS 길이를 아직 구하지 않은것이다
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 1;
	//이미 pos번째 수부터 시작하는 LIS 길이를 구했다면 바로 반환한다.
	if(dp[pos] != -1) return dp[pos];
	
	//pos번째 수보다 뒤에있는 더 큰 모든 수들을 확인하며 LIS의 길이를 찾는다.
	for(i=pos+1;i<n;i++)
		if(num[pos] < num[i])
			ret = max(ret, solve(i)+1);
	//메모이제이션하고 반환한다.
	return dp[pos] = ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		memset(dp,-1,sizeof(dp));
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		//0번째 수부터 n-1번째 수까지 돌면서 LIS 길이를 찾는다.
		for(i=0;i<n-1;i++)
			ans = max(ans, solve(i));
		
		printf("%d\n",ans);
	}
	return 0;
}


저작자 표시 비영리 변경 금지
신고

BOJ 1660 - 캡틴 이다솜

알고리즘/동적 계획법

문제

https://www.acmicpc.net/problem/1660


풀이

주어진 N을 가지고 사면체를 최소로 만들어 N을 0으로 만드는것이 목표이다. 다르게 말하자면 그냥 동전 교환 문제이다.

만약 항상 한 개의 사면체를 만들만큼만 N이 주어진다면 좋겠지만 탐욕법으로 풀 수 있겠지만 동전 1문제 처럼 이 문제는 탐욕적으로 풀 수 없는 케이스가 있다.

예를들어 N이 50일때 탐욕법을 이용해 풀면 $45+3+1+1$가 답이되어 4개가 답이 되지만 실제로는 $20+20+10$로 3개가 최소이다.

동전 문제와는 다르게 이 문제는 사면체 수가 주어지지 않는데 이 값들은 여러번 사용할 것이므로 사면체 수를 구해놓고 배열에 저장해놓는다면 시간을 매우매우 줄일수 있다.

만약 입력값이 작다면 그냥 풀어도 되지만 문제 최대 입력이 300,000이고 이 값이 들어왔을때 메모이제이션을 적용하지 않는다면 시간 초과가 발생하게 된다. 메모이제이션은 이 문제에서 원하는 DP[N] = N으로 만들수 있는 최소 사면체 수로 적용하면 된다.


PS 처음에는 Top-down으로 풀려고 했는데 어쩌다보니 Bottom-up 풀이가 되어버렸다. 나중에 Top-down으로도 다시 짜봐야겠다.

//mincost[n] = n으로 만들수 있는 최소 사면체 수 //sum[n] = n 사이즈 사면체를 만드는데 필요한 대포알의 수

#include <stdio.h> #define INT_MAX 98765431 int sum[130]={0},mincost[300001]={0}; int min(int a, int b){ return a<b?a:b; } int solve(int ball, int pos,int count){ if(ball<0) return INT_MAX; if(mincost[ball]) return mincost[ball]; if(pos<1) return INT_MAX; if(ball == 0) return count; mincost[ball] = min(solve(ball-sum[pos],pos,count)+1, solve(ball,pos-1,count)); return mincost[ball]; } int main(){ int i=0,n,maxp; scanf("%d",&n); while(++i){ sum[i] = i*(i+1)*(i+2)/6; if(sum[i] >= 300000) break; } maxp=i-1; for(i=1;i<=n;i++){ solve(i,maxp,0); } printf("%d",mincost[n]); }


저작자 표시 비영리 변경 금지
신고