알고리즘 2인 스터디 #3주차 - 박성훈

1주차때 얘기했던 난이도 올려보겠다는 약속을 지키기 위해

고군분투중인 박성훈이다.

잡소리 없이 바로 이번주의 야무진 문제들을 알아보자.

 

#1 백준 8983 - 사냥꾼 ( G4 ) 

https://blog.koderpark.dev/363

백준 BOJ 8983 - 사냥꾼

사대에서 동물을 매칭하는 일반적 발상이 아닌,

동물에 사대를 매칭해주는 정반대의 사고를 필요로 하는 문제.

 

사대의 좌표를 정렬해준 뒤,

동물의 x좌표와 사대의 좌표를 비교해서 가장 가까운 사대를 찾는다.

찾는 과정에서 시간초과를 막기 위해서 이분탐색 알고리즘을 사용해야 함에 유의할것.

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int N,M,X;

int main(){
	int a,b;
	cin >> M >> N >> X;
	for(int i=0; i<M; i++){
		cin >> a;
		v.push_back(a);
	}
	
	sort(v.begin(), v.end());
	int ans = 0;
	
	for(int i=0; i<N; i++){
		cin >> a >> b;
		
		
		int val = 998244353;
		int idx = lower_bound(v.begin(), v.end(), a)-v.begin();
		if(idx != 0) val = min(val, abs(v[idx-1]-a) + b);
		if(idx != M) val = min(val, abs(v[idx]-a) + b);
		
		if(val <= X) ans++;
	}
	
	cout << ans;
	return 0;
}

 

#2 백준 15922 - 아우으 우아으이야!! ( G5 )

욱제님이 출제작업으로 많은 고통을 겪으셨나 보다.

출제의 고통이 가지런히 이 문제에 녹아있다.

https://blog.koderpark.dev/364

백준 BOJ 15922 - 아우으 우아으이야!!

구간 [s,e] 를 정렬해주고

왼쪽 방향에서 오른쪽 방향으로 훑고 지나가는

스위핑 알고리즘을 사용해주면 된다.

 

스위핑의 기초적인 구현을 묻고 있는 문제라서, 별도의 복잡한 설명이 필요없다.

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<pair<int,int>> p;

int main(){
	int N,a,b;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a >> b;
		p.push_back({a,b});
	}
	
	int ans = 0;
	int s = p[0].x;
	int e = p[0].y;
	
	for(int i=1; i<N; i++){
		if(e >= p[i].x) e = max(p[i].y, e);
		else{
			ans += e-s;
			s = p[i].x;
			e = p[i].y;
		}
	}
	
	ans += e-s;
	cout << ans;
}

 

#3 백준 1208 - 부분수열의 합 ( G1 )

https://blog.koderpark.dev/368

백준 BOJ 1208 - 부분수열의 합 2

죽어라 오르지 않는 내 solved.ac 레이팅을 무려 1이나 올려주는 문제.

N이 절반인 <boj 1182 부분수열의 합> 을 해결하고 와야 한다.

 

N이 20일때의 풀이를 간단히 설명하자면

arr[i]를 선택하는 경우 선택하지 않는 경우 두가지에 대해 모두 탐색해서

전체 연산횟수가 2^20 = 100만+a 가 되게끔 브루트포싱을 진행해주면 된다.

 

밋인더미들 알고리즘을 사용해야 하는데,

밋인더미들 알고리즘은 이런 문제와 같이 브루트포싱을 할때 지수꼴의 시간복잡도가 필요할때

특히 유용하다.

 

입력으로 받은 배열을 크기가 N/2 인 두 배열 A와 B로 쪼개준다.

각각의 A와 B에서 1182번과 같은 해답을 적용해서 A와 B에서 만들수 있는 모든 수들을 저장한 다음,

한쪽 배열 A를 순회하며 다른쪽 배열 B에 원하는 값이 있는지를 O(logN)에 찾아주면 된다.

찾는 방법에는 std::map 이나 이분탐색 등이 있다.

 

지문의 조건에 의해서 S가 0인 입력일때 정답에서 1을 빼줘야 함에 유의해야 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[50] = {0};
vector<ll> A,B;

ll N,S;
ll ans = 0;

void find(int s, int e, ll sum, int type){
	if(s == e){
		if(type == 1) A.push_back(sum);
		if(type == 2) B.push_back(sum);
		return;
	}
	
	find(s+1, e, sum+arr[s], type);
	find(s+1, e, sum, type);
	return;
}

int main(){
	cin >> N >> S;
	for(int i=0; i<N; i++) cin >> arr[i];
	
	if(N == 1 && arr[0] != S){
		if(arr[0] != S){ cout << 0; return 0; }
		if(arr[0] == S){ cout << 1; return 0; }
	}
	
	find(0,N/2+1,0,1);
	find(N/2+1,N,0,2);
	
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	
	for(int i=0; i<A.size(); i++){
		auto low = lower_bound(B.begin(), B.end(), S-A[i]);
		auto up = upper_bound(B.begin(), B.end(), S-A[i]);
		ans += (ll)(up-low);
	}

	cout << ans - (S==0);
	return 0;
}

 

#4 백준 11967 - 불켜기 ( G2 )

https://blog.koderpark.dev/373

백준 BOJ 11967 - 불켜기

BFS를 정복하기 위한 문제.

BFS 하나만으로 G2를 받아낸 문제이다.

 

한번의 BFS 탐색에서 불을 켜고끄는 light 배열 값의 수정과,

방문했는지 체크하는 vis 배열값의 수정이 동시에 이루어져야 한다.

 

불을 새로 켜게 됨으로써 갈수 있는 경로가 늘어날 수 있기 때문에,

새로 불이 켜진 방 주변에 이미 방문한 적이 있는 방이 있는 경우

새로 불이 켜진 해당 방을 다시 재탐색해야함을 이해한다면

무난하게 해결해낼 수 있다.

 

좌표로 들어오는 x,y의 범위가 100 이하로 작은 경우에는,

x와 y 좌표를 문자열 연산하듯이 하나로 합쳐서

000x000y 등의 형태로 표현된 하나의 숫자로 만들어서 관리해줄 수도 있다.

이렇게 해주는 경우에 pair<int,int> 를 안써도 되서

조금 더 깔끔해지는 경우가 있으니 기억해두면 좋다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> g[1000000];
bool vis[1234567] = {0};
bool light[1234567] = {0};

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int N,M;

int bfs(){
	queue<int> q;
	q.push(1001);
	vis[1001] = true;
	light[1001] = true;
	
	while(!q.empty()){
		int now = q.front();
		q.pop();
		
		for(int nxt : g[now]){
			if(!light[nxt]){
				light[nxt] = true;
				
				for(int i=0; i<4; i++){
					int nnxt = nxt + 1000*dx[i] + dy[i];
					
					int x = nxt/1000;
					int y = nxt%1000;
					if(x==0 || x==N+1 || y==0 || y==N+1) continue;
					
					if(vis[nnxt]) q.push(nnxt);
				}
			}
		}
		
		for(int i=0; i<4; i++){
			int nxt = now + 1000*dx[i] + dy[i];
			
			int x = nxt/1000;
			int y = nxt%1000;
			if(x==0 || x==N+1 || y==0 || y==N+1) continue;
			
			if(light[nxt] && !vis[nxt]){
				q.push(nxt);
				vis[nxt] = 1;
			}
		}
	}
	
	int ans = 0;
	for(int i=0; i<1234567; i++) ans += light[i];
	return ans;
}

int main(){
	int a,b,c,d;
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> a >> b >> c >> d;
		g[a*1000+b].push_back(c*1000+d);
	}
	
	cout << bfs();
	return 0;
}

 

첨언

문제를 꾸준히 쭉쭉 풀다보니

어느새인가 스트릭이 200일을 넘겨서

200일 넘게 문제를 연속 해결해야 받는

<200일의 근면함> 배경화면을 받았다!

 

랜덤디펜스 자체는 지난주와 동일하게 아직도 어려운 편이라

랜덤으로 뽑은 뒤에 풀이가 어느정도 떠오르는 문제들을 해결하고 있다.

하루빨리 안정적인 랜덤디펜스가 가능할정도의 실력을 확보하고 싶다...