취미로 코딩하기

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

이번에 볼 문제는 백준 1021번 문제인 회전하는 큐이다.
문제는 아래 링크를 확인하자.

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

2번 연산과 3번 연산은 단순히 서로 반대방향으로 큐를 회전시킨다.

한편, 연산을 최소 횟수로 쓰려면 수를 하나 뽑고 다음 수를 뽑을 때까지 한가지 연산만을 한다는 점을 생각하자.

따라서, 문제를 해결하기 위해 2번 연산을 사용하여 목표한 숫자를 뽑을 수 있을 때까지 큐를 회전시키는 횟수 cnt를 구하고, 반대로 회전시킬 때 필요한 횟수를 cnt를 이용하여 계산한 다음 둘 중 작은 값을 누적하면 답을 구할 수 있다.

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

#include <iostream>
#include <queue>
using namespace std;

queue<int> que;

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

	int N, M; cin >> N >> M;

	for (int i = 1; i <= N; i++) que.push(i);

	int ans = 0;
	while (M--) {
		int x; cin >> x;
		int cnt = 0;
		while (x != que.front()) {
			cnt++;
			que.push(que.front());
			que.pop();
		}
		ans += min(cnt, (int)que.size() - cnt);
		que.pop();
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 1912번 문제인 연속합이다.
문제는 아래 링크를 확인하자.

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

이 문제는 Maximum Subarray Problem을 해결하는 문제이다. 이 문제를 해결하는 알고리즘으로 Kadane의 알고리즘이 잘 알려져있다.

이 문제에 대한 자세한 정보는 다음 링크를 참고하자:

en.wikipedia.org/wiki/Maximum_subarray_problem

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

#include <iostream>
using namespace std;

int arr[100000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	int ans = -1000000001, psum = 0;
	int L = 0, R = 0;
	while (R < N) {
		psum += arr[R++];
		if (psum > ans) ans = psum;
		while (psum < 0) {
			psum -= arr[L++];
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 9184번 문제인 신나는 함수 실행이다.
문제는 아래 링크를 확인하자.

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

이 문제는 메모이제이션(memoization)의 중요성을 알 수 있는 문제이다.

주어진 함수는 새로 호출하는 함수의 세 입력값의 합이 strict하게 감소하므로 유한한 횟수를 호출하면 계산이 끝날 것임을 알 수 있다.

문제에서 주어진 함수구현은 재귀적으로 함수를 호출하지만, 메모이제이션을 하지 않아 같은 계산을 매우 여러번 반복하게 된다. 이미 한번 계산했던 함수의 값을 저장해 보관하면 이러한 반복계산을 줄일 수 있다. 아래의 코드에서 이와 같은 역할을 하는 부분은 func 함수의 if (visited) 부분과, 계산값을 dp배열에 저장하는 부분이다..

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

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

bool visited[21][21][21];
ll dp[21][21][21];

ll func(int a, int b, int c) {
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return func(20, 20, 20);
    
    if (visited[a][b][c]) return dp[a][b][c];
    visited[a][b][c] = 1;
    
    if (a < b && b < c) return dp[a][b][c] = func(a, b, c - 1) + func(a, b - 1, c - 1) - func(a, b - 1, c);
    return dp[a][b][c] = func(a - 1, b, c) + func(a - 1, b - 1, c) + func(a - 1, b, c - 1) - func(a - 1, b - 1, c - 1);
}

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

    int x, y, z; cin >> x >> y >> z;
    while (!((x == -1 && y == -1 && z == -1))) {
        cout << "w(" << x << ", " << y << ", " << z << ") = " << func(x, y, z) << '\n';
        cin >> x >> y >> z;
    }
}

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

이번에 볼 문제는 백준 2188번 문제인 축사 배정이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2188

문제에서 주어진 상황은 "소들의 집합"과 "축사의 집합" 두 종류의 노드에 대하여 소들끼리와 축사끼리는 연결된 간선이 없고 오직 소들과 축사 사이에만 연결된 간선(소가 선호하는 축사)이 있는 이분그래프로 나타낼 수 있다.

가장 많은 (소와 축사의 쌍)을 중복 없이 뽑아야 하는 문제이므로, 이 그래프의 maximum bipartite matching(최대 이분매칭)을 계산하는 것으로 이 문제를 해결할 수 있다.

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

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

vector<int> G[201];
int visited[201];
int matching[201];

int bimatching(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		else if (bimatching(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int S; cin >> S;
		while (S--) {
			int x; cin >> x;
			G[i].push_back(x);
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ans += bimatching(i);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 1197번 문제인 최소 스패닝 트리이다.
문제는 아래 링크를 확인하자.

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

이 문제는 주어진 그래프에서 MST(Minimum Spanning Tree: 최소신장트리)의 간선의 가중치의 합을 구하는 문제이다.

글쓴이는 Kruskal(크루스칼) 알고리즘을 이용하려 이 문제를 해결하였다.

아래의 구현에서, 배열 arr은 각 꼭짓점의 disjoint set(자료구조)을 나타내고, findf는 disjoint set에서 각 꼭짓점을 대표하는 꼭짓점이 무엇인지를 돌려주는 함수이다.

에지를 가중치순으로 정렬하고, 그 에지가 잇는 양 끝점이 연결되어있는가의 여부를 disjoint set을 통해 확인한 다음 연결되어있지 않다면 이 간선을 이용해 연결하는 것으로 Kruskal 알고리즘을 구현할 수 있다.

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

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

int arr[10001];

vector<pair<int, pair<int, int>>> edges;

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

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

	int V, E; cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		arr[i] = i;
	}

	while (E--) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ c,{a,b} });
	}

	sort(edges.begin(), edges.end());

	int ans = 0;
	for (auto edge : edges) {
		int x = findf(edge.second.first), y = findf(edge.second.second);
		if (x == y) continue;
		ans += edge.first;
		arr[y] = x;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 2628번 문제인 종이자르기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2628

가장 큰 종이의 크기는 (잘린 가로간격의 최댓값) * (잘린 세로간격의 최댓값)으로 계산될 수 있다는 점을 발견하면 문제를 간단히 해결할 수 있다.

종이의 가로를 나누는 점선은 세로점선이고, 종이의 세로를 나누는 점선은 가로점선이라는 점을 헷갈리지 말자.

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

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

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

	int garo, sero; cin >> sero >> garo;
	vector<int> garocut = { 0,garo };
	vector<int> serocut = { 0,sero };

	int N; cin >> N;
	while (N--) {
		bool x; int y; cin >> x >> y;
		if (x) serocut.push_back(y);
		else garocut.push_back(y);
	}

	sort(garocut.begin(), garocut.end());
	sort(serocut.begin(), serocut.end());

	garo = (int) garocut.size();
	sero = (int) serocut.size();
	
	int maxgaro = 0;
	int maxsero = 0;
	for (int i = 1; i < garo; i++) {
		int temp = garocut[i] - garocut[i - 1];
		if (temp > maxgaro) maxgaro = temp;
	}
	for (int i = 1; i < sero; i++) {
		int temp = serocut[i] - serocut[i - 1];
		if (temp > maxsero) maxsero = temp;
	}

	cout << maxgaro * maxsero;
}