취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1111번 문제인 IQ Test이다.
문제는 아래 링크를 확인하자.

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

나올 수 있는 경우의 수를 차근차근 살펴보면 단순하게 풀 수 있는 문제이다.

1) N=1인 경우, 뒤에 나올 수 있는 수열은 무수히 많으므로 A를 출력한다.

2) N=2인 경우

2-1) 두 수가 다른 경우, 뒤에 나올 수 있는 수열은 무수히 많으므로 A를 출력한다.

2-2) 두 수가 같은 경우, 뒤에 나올 수 있는 수열은 단 한가지(같은 수만이 계속 반복)이므로 그 수를 출력한다.

3) N이 3 이상인 경우

수열의 앞 세 수 x, y, z를 입력받는다.

이 수열은 어떤 항이 k였다면 다음 항은 a*k+b로 계산하므로, a*x+b = y와 a*y+b = z의 두 식으로부터 a와 b의 관계식을 구해낼 수 있다. 이 연립방정식의 "정수"인 a와 b가 존재하는지의 여부를 판단할 수 있는가가 이 문제의 핵심으로, a와 b가 존재한다면 남은 항이 위 식을 만족하는지를 구한 a와 b의 값으로 계산하는 것으로 문제를 해결할 수 있다..

특히, 해가 무수히 많이 존재할 경우와 해가 존재하지 않을 경우에 대한 신경써서 해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	if (N == 1) cout << 'A';
	else if (N == 2) {
		int x, y; cin >> x >> y;
		if (x == y) cout << x;
		else cout << 'A';
	}
	else {
		int x, y, z; cin >> x >> y >> z;
		if (x == y) {
			N -= 3;
			if (x != z) {
				cout << 'B';
				return 0;
			}
			while (N--) {
				int next; cin >> next;
				if (next != x) {
					cout << 'B';
					return 0;
				}
			}
			cout << x;
		}
		else {
			if ((z - y) % (y - x) != 0) {
				cout << 'B';
				return 0;
			}
			int a = (z - y) / (y - x);
			int b = y - x * a;
			N -= 3;
			while (N--) {
				int next; cin >> next;
				if (next != a * z + b) {
					cout << 'B';
					return 0;
				}
				z = next;
			}
			cout << a * z + b;
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5397번 문제인 키로거이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 이 문제를 스택 두 개를 이용하여 해결하였다.

문제의 예제 중 첫번째 예제를 다음과 같이 생각해보면 스택 두 개로 문제를 어떻게 해결할 수 있을지 생각해내기 쉬울 것이다.

[): 스택1

(]: 스택2

<: [) 커서 (]

<<: [) 커서 (]

<<B: [B) 커서 (]

<<BP: [BP) 커서 (]

<<BP<: [B) 커서 (P]

<<BP<A: [BA) 커서 (P]

<<BP<A>: [BAP) 커서 (]

<<BP<A>>: [BAP) 커서 (]

<<BP<A>>C: [BAPC) 커서 (]

<<BP<A>>Cd: [BAPCd) 커서 (]

<<BP<A>>Cd-: [BAPC) 커서 (]

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;

stack<char> stkL;
stack<char> stkR;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		string s; cin >> s;
		for (auto x : s) {
			if (x == '<') {
				if (!stkL.empty()) {
					stkR.push(stkL.top());
					stkL.pop();
				}
			}
			else if (x == '>') {
				if (!stkR.empty()) {
					stkL.push(stkR.top());
					stkR.pop();
				}
			}
			else if (x == '-') {
				if (!stkL.empty()) {
					stkL.pop();
				}
			}
			else stkL.push(x);
		}
		while (!stkL.empty()) {
			stkR.push(stkL.top());
			stkL.pop();
		}
		while (!stkR.empty()) {
			cout << stkR.top();
			stkR.pop();
		}

		cout << '\n';
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1666번 문제인 최대 증가 직사각형 집합이다.
문제는 아래 링크를 확인하자.

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

이 문제를 간단히 한 버전, 즉 평면 위에 직사각형이 아닌 점이 찍혀있는 문제는 sweeping을 통한 LIS 풀이가 잘 알려져있다.

이를 간단히 응용하면 세그먼트 트리를 이용한 LIS의 길이 구하기를 응용한 풀이를 똑같이 적용할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef pair<int, int> pt;

multimap<pt, pt> mltmap;
priority_queue<pair<pt, int>> pq;

int seg[262145];

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = max(seg[sI], qVal);
	return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int query(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(query(L, (L + R) / 2, qL, qR, sI * 2), query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		x1 = -x1; x2 = -x2;
		y1++; y2++;
		pt spoint = { x1,y1 }, epoint = { x2,y2 };
		mltmap.insert({ spoint, epoint });
		pq.push({ spoint,0 });
	}

	while (!pq.empty()) {
		pt current = pq.top().first;
		int cnt = pq.top().second;
		pq.pop();
		if (cnt == 0) {
			auto iters = mltmap.equal_range(current);
			for (auto iter = iters.first; iter != iters.second; iter++) {
				pq.push(pair<pt,int> { (*iter).second, query(1,100001,1,current.second - 1,1) + 1 });
			}
		}
		else {
			update(1, 100001, current.second, cnt, 1);
		}
	}

	cout << query(1, 100001, 1, 100001, 1);
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4195번 문제인 친구 네트워크이다.
문제는 아래 링크를 확인하자.

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

이 문제는 입력이 주어지는 각 시점마다 연결된 친구의 수를 구해야한다는 점을 유의하면 map과 disjoint set을 이용하여 간단히 해결할 수 있다.

N가지 친구관계가 주어지면 최대 2N명의 이름이 등장할 수 있다는 점에 유의하자.

아래는 제출한 소스코드이다.

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

map<string, int> dict;
int arr[200000];
int cnt[200000];

int findf(int x) {
	if (x == arr[x]) return x;
	return arr[x] = findf(arr[x]);
}

void solve() {
	dict.clear();
	int N; cin >> N;

	for (int i = 0; i < 2 * N; i++) {
		arr[i] = i;
	}
	
	for (int i = 0; i < 2 * N; i++) {
		cnt[i] = 1;
	}

	int idx = 0;
	while (N--) {
		string s1, s2; cin >> s1 >> s2;
		if (dict.find(s1) == dict.end()) dict.insert({ s1,idx++ });
		if (dict.find(s2) == dict.end()) dict.insert({ s2,idx++ });
		
		int x = findf(dict[s1]), y = findf(dict[s2]);
		if (x != y) {
			cnt[x] += cnt[y];
			arr[y] = x;
		}
		
		cout << cnt[x] << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17131번 문제인 여우가 정보섬에 올라온 이유이다.
문제는 아래 링크를 확인하자.

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

문제의 설명이 기하문제처럼 복잡하게 서술되어 있지만, 결국 구해야하는 것은 간선을 추가하다가 사이클이 생기는 때, 즉 주어지는 두 점이 속한 트리를 disjoint set 자료구조로 하나로 합쳐나가다가 같은 트리 내에 있는 두 점 사이를 이으려는 시도를 하려는 시점을 찾는 것이다. 크루스칼 알고리즘에서 추가하지 않는 간선의 조건이 무엇이었는지를 생각해보자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[500000];

int findf(int x) {
    if (x == arr[x]) return x;
    return arr[x] = findf(arr[x]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        arr[i] = i;
    }

    for (int i = 1; i <= M;i++) {
        int x, y; cin >> x >> y;
        x = findf(x), y = findf(y);
        if (x == y) {
            cout << i;
            return 0;
        }

        arr[y] = x;
    }

    cout << 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17131번 문제인 여우가 정보섬에 올라온 이유이다.
문제는 아래 링크를 확인하자.

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

별 S를 하나 골랐을 때 그 별이 별자리의 가운데 꼭짓점이 될 경우의 수는 (S의 왼쪽 위에 있는 별의 개수 * S의 오른쪽 위에 있는 별의 개수)가 됨을 알 수 있다. 따라서, 위에서부터 아래 방향으로 별을 입력받으며 앞서 들어온 (y가 같지 않은) 왼쪽 별의 개수와 오른쪽 별의 개수를 구간합을 구하는 세그먼트트리를 이용하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll seg[1048577];

void update(int L, int R, int qI) {
	int sI = 1;
	while (L != R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid;
			sI = sI * 2;
		}
		else {
			L = mid + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[sI]++;
}

pair<int, int> pts[200000];
int current = 0;
vector<int> stk;

ll query(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		pts[i] = { -y,x };
	}

	sort(pts, pts + N);

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		int x = pts[i].second + 200001, y = pts[i].first;

		if (!stk.empty() && current != y) {
			while (!stk.empty()) {
				update(1, 400001, stk.back());
				stk.pop_back();
			}
		}

		current = y;
		stk.push_back(x);

		if (x != 1 && x != 400001) {
			ans += query(1, 400001, 1, x - 1, 1) * query(1, 400001, x + 1, 400001, 1);
			ans %= 1000000007;
		}
	}

	cout << ans;
}