Mystika+Algorithm

'전체'에 해당되는 글 27건

  1. ALGOSPOT - LIS
  2. BOJ 1931 - 회의실 배정
  3. BOJ 1660 - 캡틴 이다솜
  4. BOJ 9358 - 순열 접기 게임
  5. BOJ 2668 - 숫자고르기

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 1931 - 회의실 배정

알고리즘/탐욕법

문제


풀이

이 문제를 해결하려면 여러가지 방법을 생각해볼 수 있다. 예를 들어 가장 먼저 시작하는 회의부터 선택하기, 가장 시간이 짧은 회의부터 선택하기 등이 있을 텐데 이런 방법으로는 이 문제를 해결 할 수 없다. 


가장 먼저 시작하는 회의부터 선택 할 경우 아래와 같이 늦게 시작하는 회의가 더 짧을 수 있는 경우의 반례가 존재하므로 최적의 답을 구할 수 없다. 원래 탐욕법으로는 최적을 구하기 보다 최적에 가까운 답을 구하는게 보통이지만 이 문제는 최적의 답(또는 최적의 답 중 하나)을 구할 수 있기 때문에 이 방법을 사용하여 답을 구할 수 없다.






가장 짧은 회의부터 선택할 경우에는 아래와 같이 먼저 시작하고 회의 시간이 더 긴 회의를 시작할 경우 더 많은 회의를 선택할 수 있는 경우가 존재하기 때문에 최적의 답을 구할 수 없다.



코드 상에서 위 방법들에 대한 반례에 대해 처리한다고 해도 결국 다른 반례가 나오기 때문에 위 방법들로는 해결할 수가 없다.

이 문제를 해결하는 방법은 가장 빨리 끝나는 회의부터 선택하는 것인데 가장 빨리 끝나는 회의를 선택할수록 그 뒤에 선택할 수 있는 회의시간이 늘어나기 때문에 어떤 경우라도 가장 많이 선택할 수 있다.



코드는 아래와 같이 짰다. 회의의 시작시간과 종료 시간을 가지고 있는 meeting 구조체를 만들고(이 부분은 pair를 사용하여도 된다) 모든 회의를 종료 시간이 빠른 순(만약 종료 시간이 같다면 시작 시간이 빠른 순)으로 정렬한 다음 모든 회의를 확인하면서 선택할 수 있는 가장 빨리 끝나는 회의를 선택하게 하였다.

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

struct meeting{
	int start,end;
};

int cmp(const meeting &a, const meeting &b){
	if(a.end == b.end)
		return a.start < b.start;
	return a.end < b.end;
}

int main() {
	int n,i,s,e,last=-1,c=0;
	meeting t;
	vector<meeting> v;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&s,&e);
		t.start = s;
		t.end = e;
		v.push_back(t);
	}
	sort(v.begin(),v.end(),cmp);
	for(i=0;i<n;i++){
		if(v[i].start >= last){
			last = v[i].end;
			c++;
		}
	}
	printf("%d",c);
	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]); }


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

BOJ 9358 - 순열 접기 게임

알고리즘/구현

문제

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

풀이

주어진 수열의 첫번째 수와 N번째 수를 더해 새 수열에 넣고, 두번째 수와 N-1번째 수를 더해 다시 새 수열에 넣고.. 이 작업을 수열의 길이가 2가 될 때까지 반복한 후 왼쪽 수가 큰지 오른쪽 수가 큰지 비교하는 문제이다.

이 문제는 양방향 큐, 즉 Deque(Double Ended Queue, [덱])를 사용하면 쉽게 풀수 있다. 새 수열을 만드는 과정에서 왼쪽 수(front)와 오른쪽 수(back)를 쉽게 큐에서 꺼낼수(pop) 있어 전체적인 코드가 짧아지고 구현이 간편해진다.

#include <cstdio>
#include <deque>
using namespace std;

int main() {
	int t,i,j,x,n;
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d",&n);
		deque<int> dq;
		for(j=0;j<n;j++){
			scanf("%d",&x);
			dq.push_back(x);
		}
		while(1){
			if(dq.size() == 2) break;
			deque<int> cur;
			while(!dq.empty()){
				cur.push_back(dq.front()+dq.back());
				dq.pop_front();
				if(!dq.empty()) dq.pop_back();
			}
			while(!cur.empty()){
				dq.push_back(cur.front());
				cur.pop_front();
			}
		}
		printf("Case #%d: %s\n",i,dq[0]>dq[1]?"Alice":"Bob");
	}
	return 0;
}


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

BOJ 2668 - 숫자고르기

알고리즘/DFS∕BFS

문제

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

풀이

주어진 배열에서 순환하는 요소가 총 몇개인지 카운팅하고, 순환하는 요소들을 오름차순으로 출력하는 문제이다. 아래의 예제 이미지를 보면 순환하는 요소는 1-3, 5 이렇게 3개이다.



정점 N에서 시작하는 순환 배열이 존재하는가를 확인하려면 도착점을 N으로 두고 MAP[N]부터 시작해서 마지막에 N으로 오는가를 확인하면 된다. 만약 N으로 오지 않고 이미 방문했던 정점을 다시 방문한다면 순환 배열이 존재하지 않는다는 뜻이다.

나는 따로 방문을 표시할 배열과 사이클 여부를 표시할 배열을 따로 만들지 않고 방문을 표시할 배열의 값을 0, 1, 2로 구분지어 방문하지 않음, 방문함, 이미 방문했고 사이클이다 라고 정의하여 O(2N)의 공간을 사용하였다.

#include <stdio.h>
int n,map[101]={0},visit[101]={0};
int isCircular(int start, int cur, int count){
	if(visit[cur]) return 0;
	visit[cur] = 1;
	if(start == cur) {
		
		int i;
		for(i=1;i<=n;i++){
			if(visit[i] == 1) visit[i]=2;
		}
		return count+1;
	}
	return isCircular(start,map[cur],count+1);
}
int main(){
	int i,j,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&map[i]);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(visit[j]==1) visit[j]=0;
		}
		ans += isCircular(i,map[i],0);
	}
	printf("%d\n",ans);
	for(i=1;i<=n;i++){
		if(visit[i]==2)
			printf("%d\n", i);
	}
}


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