코뚫린 앙드로이드

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

문제해설

밑의 문제와 동일한 문제입니다( 입력 범위만 살짝 다릅니다 )

2019/10/13 - [알고리즘/BOJ] - [백준BOJ] 2188 축사 배정

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------

#define MAX_N 1001
vector<int> map[MAX_N];

int cow[MAX_N];
int area[MAX_N];
bool visit[MAX_N];

bool fun(int s) {
	visit[s] = true;
	for (int i = 0; i < map[s].size(); i++) {
		if (area[map[s][i]] == -1 || (!visit[area[map[s][i]]] && fun(area[map[s][i]]))) {
			cow[s] = map[s][i];
			area[map[s][i]] = s;
			return true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		int s; cin >> s;
		for (int j = 0; j < s; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(cow, -1, sizeof(cow));
	memset(area, -1, sizeof(area));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (cow[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans++;
		}
	}
	cout << ans << endl;
}

기타

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

문제해설

N의 입력 범위가 작기 때문에, 소를 계속 가능한 위치에 이동시켜주면서 풀어 나가면 됩니다.

또한, 네트워크 플로우의 특성인 어느 소부터 시작하던지, 결국 되는경우는 모두 처리가 되기 때문에,

1번 소부터 N번 소까지 차레대로 처리해주면 됩니다.

k번 소를 원하는 지역에 넣으려고 하는 경우 두가지 케이스가 있습니다

case 1 ) 해당 지역이 비어있는 경우

case 2 ) 다른소가 차지하고 있는 경우

< case 1 >

해당 지역에 k번째 소를 넣어주고

k번째 소가 어느위치에 있는지도 알고 있어야 합니다.

< case 2 >

해당 지역에 있는 소를 y소라고 한다면,

y소를 다른위치로 옮겨야 합니다.

재귀 함수를 사용해서, y소를 다른 지역에 옮길 수 있는지 확인한뒤

(옮긴 후) k번째 소를 해당 지역에 넣어 주면 됩니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------

#define MAX_N 201
vector<int> map[MAX_N];

int cow[MAX_N];
int area[MAX_N];
bool visit[MAX_N];

bool fun(int s) {
	// s번 소는 방문
	visit[s] = true;
	for (int i = 0; i < map[s].size(); i++) {
		// 해당 지역이 비었거나
		// 그렇지 않다면
		// 현재 가려고 하는 위치의 소가 처리 되있지 않고
		// &&
		// 처리 되지 않은소가 다른 지역으로 옮겨갔다면 ( true가 return 된다 )
		if (area[map[s][i]] == -1 || (!visit[area[map[s][i]]] && fun(area[map[s][i]]))) {
			cow[s] = map[s][i];
			area[map[s][i]] = s;
			return true;
		}
	}
	// 소를 현재 위치에서 이사시킬 수 없는 경우
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		int s; cin >> s;
		for (int j = 0; j < s; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(cow, -1, sizeof(cow));
	memset(area, -1, sizeof(area));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		// 1번 소 부터 차례대로 넣는다 ( 플로우 형식이기 때문에 그냥 차례대로 확인해도 상관없다 )
		if (cow[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans++;
		}
	}
	cout << ans << endl;
}

기타

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

문제해설

"라인 스위핑"을 염두에둔 상태에서 문제를 잘 읽으면

조건에 의해 풀 수있는 방법이 떠오르는 문제이다( 저는 상당히 오래걸렸습니다 ㅠ )

위의 빨간박스가 이문제의 핵심이며 라인스위핑을 통해서 답을 구해낼 수 있는 이유라고 할 수 있습니다.

쉽게 생각해서

원의 왼쪽 : 스택의 왼쪽괄호

원의 오른쪽 : 스택의 오른쪽괄호

라고 생각하면 됩니다.

왼쪽괄호가 열렸다는 것은 언젠가 자신보다 오른쪽 좌표에서 오른쪽 괄호가 나타난다는 것을 의미합니다.

스택의 열고 닫기를 하는 와중에 닫는 동작을 할 때에, 중간에 구멍없이 계속 접해왔는지 확인화면 되는 문제입니다.

< 스택 >

class stackItem {
public:
	ll pos; int state;
	stackItem(ll pos, int state) {
		this->pos = pos;
		this->state = state;
	}
}; stack<stackItem> st;

스택에 pos와 state 라는 변수를 두었습니다.

pos : 좌표값을 의미합니다.

state 

초기 괄호를 열였을 경우 : 0

열고나서 끊김없이 계속 접해온경우 : 1

열고나서 끊긴 적이 있는경우 : -1

의 세가지의 경우를 나누었습니다.

여러 케이스를 통해 예시를 들어 보겠습니다

< 예시 1 >

위 처럼 원이 하나만 존재하는 경우는 괄호로 표현시 () 가 됩니다.

위와 같이 stack에 state 0 이 들어가게되고

) 에 의해 pop이 되는경우 ans++ 를 해주게 됩니다.

< 예시 2 >

위와같이 큰원 안에 작은원이 두개가 완전히 접한다고 가정해봅시다

괄호로 표현하면 (()()) 가 될 것입니다. 위 그림이 어떻게 답이 5가 되는지 확인 해봅시다.

위의 왼쪽 괄호 (( 두개를 처리한뒤의 스택의 모습입니다. 물론 pos 정보도 포함하고 있겠죠.

top 에있는 item은 방금 스택에 들어간 item이고

그밑의 item은 push되는 item과 좌표값이 겹치기 때문에 state가 1로 변경된 item입니다.

그다음 ) 가 들어갔을 경우는 ( ) 가 짝이 지어짐으로 pop이 되고, state가 0 이였으므로 ans++를 해주게 됩니다.

똑같이 그다음 ) 가 들어갔을 경우는 ( ) 가 짝이 지어짐으로 pop이 되고, state가 0 이였으므로 ans++를 해주게 됩니다.

마지막의 경우는 state가 1인 상태임으로 답이 2가 나오게 됩니다.

총합 답이 5가 나오게 됩니다.

< 예시 3 >

위의 그림의 경우는 스택의 모양으로는 ( ()() ) 가 될 것입니다. 예시 2과 스택의 구조는 같지만

item의 state를 변경해줌으로써 다른 답이 나오게 됩니다.

아까와 다르게 밑의 item의 state가 -1이 된 모습을 확인할 수 있습니다. 

처리하는 과정은 ( 괄호를 추가하였을때 top 에있는 pos와 현재 pos와 다르다면 

top에있는 item의 state를 -1로 바꾸어 주었습니다.

그후 현재 정보를 push 해주면 됩니다.

이후 부터는 예시2와 같이 처리해주면 답이 4가 나오게 됩니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

bool cmp(pll a, pll b) {
	if (a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}
class stackItem {
public:
	ll pos; int state;
	stackItem(ll pos, int state) {
		this->pos = pos;
		this->state = state;
	}
}; stack<stackItem> st;

vector<pair<ll, int>> vec;


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		ll x, r; cin >> x >> r;
		vec.push_back({ x - r,-1 });
		vec.push_back({ x + r, 1 });
	}
	sort(vec.begin(), vec.end(), cmp);

	ll ans = 0; ll last = 0;
	for (int i = 0; i < vec.size(); i++) {
		if (st.empty()) {
			st.push(stackItem(vec[i].first, 0));
			last = vec[i].first;
		}
		else if (vec[i].second == -1) {
			if (vec[i].first == last) {
				vector<stackItem> vec_tmp;
				stackItem tmp = st.top(); st.pop();
				if (tmp.state != -1) tmp.state = 1;
				st.push(tmp);
				st.push(stackItem(vec[i].first, 0));
			}
			else {
				stackItem tmp = st.top(); st.pop();
				tmp.state = -1;
				st.push(tmp);
				st.push(stackItem(vec[i].first, 0));
				last = vec[i].first;
			}
		}
		else if (vec[i].second == 1) {
			stackItem tmp = st.top(); st.pop();
			if (tmp.state == 1 && last == vec[i].first)
				ans += 2;
			else
				ans++;

			last = vec[i].first;
		}
	}
	cout << ans + 1 << "\n";
}

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

문제해설

입력의 갯수가 30만이 이기 때문에, 전수조사를 할경우 O(N^2)롤 TLE에 걸리게 됩니다.

O(NlgN) 정도의 알고리즘이 필요해 보입니다.

<입력처리>

	// 이름의 길이에 등수를 push_back
	for (int i = 0; i < N; i++) {
		string input; cin >> input;
		vec[input.size()].push_back(i + 1);
	}

입력이 문자열로 들어오지만, 저희가 필요한 정보는 문자열의 길이와 등수뿐 입니다.

<정렬>

이문제의 핵심이라고 할 수 있는 부분입니다.

이름 길이가 같은 친구끼리 묶인 vector에서 정렬을 통해서

이후에, 선형 조사를 하게 되던, lower_bound, upper_bound를 하게되던 정렬을 해야만 

큰 입력에 대해서 시간안에 답을 구할 수 있습니다.

	// i 길이의 이름을 가진 친구들을 등수별로 sort
	for (int i = 0; i < 21; i++) {
		sort(vec[i].begin(), vec[i].end());
	}

<upper_bound>

i 길이의 이름을 가진 친구중에서 j번째 등수기준으로

j + K 번째 등수까지 몇명이 있는지 알기위해서

이분탐색을통해서 알 수 있습니다.

	for (int i = 0; i < 21; i++) {
		// upper_bound를 편의를 위한 push_back
		vec[i].push_back(1e9);
		for (int j = 0; j < vec[i].size()-1; j++) {
			// 자신의 등수보다 K 보다 큰 마지막 친구가 iter로 반환 됩니다.
			auto iter = upper_bound(vec[i].begin(), vec[i].end(), vec[i][j] + K); iter--;
			// 시작 주소를 빼줌으로써 index값을 얻을 수 있고
			auto index = iter - vec[i].begin();
			// 마지막 친구의 index - 현재 index를 해주면 친구의 명수가 나오게 됩니다.
			ans += index - j;
		}
	}

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

vector<int> vec[21];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, K; cin >> N >> K;

	// 이름의 길이에 등수를 push_back
	for (int i = 0; i < N; i++) {
		string input; cin >> input;
		vec[input.size()].push_back(i + 1);
	}

	// i 길이의 이름을 가진 친구들을 등수별로 sort
	for (int i = 0; i < 21; i++) {
		sort(vec[i].begin(), vec[i].end());
	}

	long long ans = 0;
	for (int i = 0; i < 21; i++) {
		// upper_bound를 편의를 위한 push_back
		vec[i].push_back(1e9);
		for (int j = 0; j < vec[i].size()-1; j++) {
			// 자신의 등수보다 K 보다 큰 마지막 친구가 iter로 반환 됩니다.
			auto iter = upper_bound(vec[i].begin(), vec[i].end(), vec[i][j] + K); iter--;
			// 시작 주소를 빼줌으로써 index값을 얻을 수 있고
			auto index = iter - vec[i].begin();
			// 마지막 친구의 index - 현재 index를 해주면 친구의 명수가 나오게 됩니다.
			ans += index - j;
		}
	}
	cout << ans << "\n";
}

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

문제해설

이 문제의 분류는 "라인스위핑" 입니다.

라인스위핑 알고리즘을 사용하여 중구난방으로 입력된 좌표들을 

어떤 기준에 의해 정렬한뒤에

O(N)으로 처음부터 끝까지 쓰~윽 처리해주시면 됩니다.

기준을 잡는 것에 있어서 여러가지 방법이 있을 수 있습니다.

저는 x축 을 기준으로 정렬한뒤에 현재까지 선을 그은 마지막 위치를 저장하여 처리 했습니다. 

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

typedef pair<int, int> pii;
vector<pii> vec;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		if (b < a) {
			int t = b;
			b = a;
			a = t;
		}
		vec.push_back({ a,b });
	}
	int e = -(1e9+1);
	int ans = 0;
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++) {
		if (e == -(1e9 + 1)) {
			e = vec[i].second;
			ans += e - vec[i].first;
		}

		if (vec[i].first < e) {
			int diff = vec[i].second - e;
			ans += (diff > 0) ? diff : 0;
			e = max(e,vec[i].second);
		}
		else if (vec[i].first >= e) {
			ans += vec[i].second - vec[i].first;
			e = vec[i].second;
		}
	}
	cout << ans << "\n";
}

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

문제해설

이 문제의 아이디어는 설렁설렁 문제를 읽어서는 떠오르기 쉽지 않은 문제입니다.

이 문제는 disjoint-set 및 union-find 알고리즘을 사용한다는 것 까지는 쉽게 알 수 있습니다.

그러나 union-find 의연산횟수가 적은 이유는

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return par[x] = find(par[x]);
}

위 처럼, find를 할때에 union의 root를 부모로 설정해주기 때문입니다.

그러나,

이문제에서는 자신의 바로 윗부모와의 엣지를 삭제하는 쿼리가 들어옵니다.

위의 코드가 전혀 쓸모없는 코드가 되어버리고

저코드를 활용한다하더라도

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return find(par[x]);
}

위 처럼, 딱봐도 TL이 걸릴 것 같은 코드정도로 밖에 쓰지 못할 것입니다.

union-find의 특성을 그대로 활용하기 위해서

쿼리를 뒤에서부터 처리해주는 방법을 선택할 수 있습니다.

제일 뒤에서부터 시작하기 때문에, 아무런 연결이 없는상태로 시작해서

삭제되는 쿼리를 만나면 union을 시켜주는 형태로 문제를 풀어 나가면 됩니다.

전체코드

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

class Input {
public:
	int tag, x, y, par;
	Input() {};
	Input(int tag, int x, int y) {
		this->tag = tag;
		this->x = x;
		this->y = y;
	}
	Input(int tag, int x) {
		this->tag = tag;
		this->x = x;
	}
};

int par[200001];
int origin[200001];
vector<string> ans;
vector<Input> input;

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return par[x] = find(par[x]);
}

void make_set(int x, int p) {
	x = find(x);
	p = find(p);
	par[x] = p;
	//cout << x << "의부모 : " << par[x] << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, Q;
	cin >> N >> Q;
	par[1] = 1;
	for (int i = 2; i <= N; i++) {
		cin >> origin[i];
		par[i] = i;
	}


	for (int i = 0; i < N + Q - 1; i++) {
		int tag;  cin >> tag;
		if (tag) {
			int x, y; cin >> x >> y;
			input.push_back(Input(1, x, y));
		}
		else {
			int x; cin >> x;
			input.push_back(Input(0, x));
		}
	}

	vector <string> ans;
	for (int i = N + Q - 2; i >= 0; i--) {
		if (input[i].tag) {
			int x = input[i].x;
			int y = input[i].y;
			if (find(x) == find(y)) ans.push_back("YES");
			else ans.push_back("NO");
		}
		else {
			int x = input[i].x;
			make_set(x, origin[x]);
		}
	}

	for (int i = Q - 1; i >= 0; i--) {
		cout << ans[i] << "\n";
	}
}

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

문제해설

H와 W의 입력자체가 1000까지 들어오지만, N이 10^7까지 들어오기 때문에,

일반적인 시뮬레이션으로는 해결 할 수없어 보입니다.

총 N번 산책을 했을 때, 어떤 교차점에대해서 몇번 지나게 되는가를 미리 계산하면 됩니다.

(1,1) 정점은 N번 산책을 할 경우 N번 지나게 될 것입니다.

(1,2)는 대략적으로 N/2

(2,1)도 대략적으로 N/2

...

이런식으로 dp 테이블을 생성해 나아가면 됩니다.

< 예시 >

W = 1, H = 1 인 케이스에서 N 이 주어졌다고 생각해봅시다.

N번 산책동안 1,1를 N번 지나게됨으로

N번 산책일때 오른쪽으로 가는가, 왼쪽으로 가는가만 계산하면 될텐데

첫 입력에서 (오른쪽)이 주어졌다면

짝수번 방문할 경우는 (2,1)

홀수번 방문할 경우는(1,2)

에 도착하게됩니다.

W = 2, H = 2인 케이스에서 N이 주어졌다고 생각해봅시다.

N이만약 짝수라면

dp[1][1] = N번

dp[2][1] = dp[1][1]/2

dp[1][2] = dp[1][1]/2

dp[2][2] = dp[1][2]/2 + dp[2][1]/2

가 될 것입니다. 

위의 같은케이스에서 N이홀 수라면 

처음 입력에 따라서 오른쪽이나 아래쪽에 1이 더큰 숫자가 들어가게 될 것입니다.

 DP 테이블을 완성한뒤에

mod2 연산을 하게 되었을때 dp 테이블에 남은 숫자가 곧

방향을 알려줄 것이고

DFS를 통해 결과를 구 할 수 있습니다.

전체코드

#include <iostream>
using namespace std;

int arr[1001][1001];
int dp[1001][1001];
int R, C, N;
pair<int, int> ans;

void DFS(int r, int c) {
	if (r >= R || c >= C) {
		ans = { r,c };
		return;
	}
	if (arr[r][c] == 1) {
		if (dp[r][c] == 1) 
			DFS(r, c + 1);
		else 
			DFS(r + 1, c);
	}
	else {
		if (dp[r][c] == 1)
			DFS(r+1, c);
		else 
			DFS(r, c+1);
	}
}


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> R >> C >> N;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> arr[i][j];
		}
	}

	dp[0][0] = N;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (arr[i][j] == 1) {
				dp[i+1][j] += dp[i][j] / 2;
				dp[i][j+1] += (dp[i][j] % 2 == 0) ? dp[i][j] / 2 : dp[i][j] / 2 + 1;
			}
			else {
				dp[i+1][j] += (dp[i][j] % 2 == 0) ? dp[i][j] / 2 : dp[i][j] / 2 + 1;
				dp[i][j + 1] += dp[i][j] / 2;
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			dp[i][j] %= 2;
		}
	}
	DFS(0, 0);
	cout << ++ans.first  << " " << ++ans.second << "\n";
}

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

문제해설

이 문제는 "라인스위핑(line sweeping)" 알고리즘을 사용하여 해결 할 수 있습니다.

어떤 축을 기준으로 정렬한뒤에, 확인하는 경우의수를 대폭 줄일 수 있습니다.

많은 다른 블로그들은 lower_bound 없이 반복문으로 O(N)으로 풀으셨는데

lower_bound를 사용 하여 O(NlgN) 으로 풀었습니다.

풀이는 다음과 같습니다.

사대를 x축 정렬

동물들도 x축 정렬

정렬된 동물들을 처음부터 끝까지 탐색하는데

해당 동물이 사냥될 수 있는지 체크하기 위해서

해당 동물과 가장 오른쪽에서 가까운(x축기준) 사대

해당 동물과 가장 왼쪽에서 가까운(x축기준) 사대

를 찾아서 거리를 구해주면 됩니다.

lower_bound의 예외처리를 쉽게 하기 위해서 밑과 같은 사전처리를 해주었습니다.

	sands.push_back(-MAX);
	sands.push_back(MAX);

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
vector<ll> sands;
vector<pair<ll, ll> > ani;

ll getDist(ll x, ll x1, ll y1) {
	return abs(x - x1) + y1;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int M, N, L; cin >> M >> N >> L;
	ll MAX = 1000000001;
	for (int i = 0; i < M; i++) {
		ll x; cin >> x;
		sands.push_back(x);
	}
	for (int i = 0; i < N; i++) {
		ll x, y; cin >> x >> y;
		ani.push_back({ x,y });
	}
	sands.push_back(-MAX);
	sands.push_back(MAX);
	sort(sands.begin(), sands.end());
	sort(ani.begin(), ani.end());
	int ans = 0;
	for (int i = 0; i < ani.size(); i++) {
		ll x = ani[i].first;
		ll y = ani[i].second;
		auto left = lower_bound(sands.begin(), sands.end(), x);
		auto right = left - 1;
		if (min(getDist(*right, x, y), getDist(*left, x, y)) <= L) ans++;
	}
	cout << ans;
}