급하게임개발

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

이 문제의 경우  최소 신장  트리 문제중 하나로 일단  최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다
크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다 

이 문제에서는 핵심적으로 4개의로직이 있다.

1. 부모를 찾는 로직

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);

이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다

2. 같은 부모인지 찾는 로직

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;

3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다

void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}

4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서  2번 3번 과정을 반복해준다 그후 연결된 cost중 가장  높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다

	for (int i = 0; i < inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}

전체 코드는 아래와 같다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 0, };

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e;
	long long cost;
	cost = 0;
	int cnt = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}
	cout << cost;
}

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

이 문제의 경우 이진 검색 트리이긴 하지만 나는 굳이 따지자면 분할 정복이라고 봐도 될거 같다. 그 이유는 이문제의 경우

pivot을 기준으로 계속 나눠가면서 트리를 분리해서 출력을 해주어야 한다. 기존에 이진트리가 자신의 인덱스/2가 부모로 배열을 사용하는 것과 달리 특이하게 들어 왔다. 일단 이문제의 풀이는 아래 사진처럼 배열을 나누어야 했다.

#include <iostream>
using namespace std;

int arr[10005];

void post(int start, int end) {
	if (start >= end) return;
	//else if (start == end-1) {
	//	cout << arr[start] << endl;
	//	return;
	//}
	int i;
	for (i = start + 1; i < end; i++)
		if (arr[start] < arr[i]) 
			break;
	post(start + 1, i);
	post(i , end);
	cout << arr[start] << endl;
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int num;
	int idx=0;
	//while (true) {
	//	cin >> num;
	//	if (num == 0) {
	//		break;
	//	}
	//	else {
	//		arr[idx] = num;
	//		idx++;
	//	}
	//}
	while (cin >> num) {
		arr[idx] = num;
		idx++;
	}
	post(0, idx);
}

일단 이 문제는 입력 방식을

	while (cin >> num) {
		arr[idx] = num;
		idx++;
	}

이렇게 작성해 주어야 했는데 그이유는 이문제는 EOF를 통해 입력의 끝을 알기 때문에 우리가 프롬프트창에서 직접 사용자 입력을 해주게 되면 cin 의 기능이 끝나지 않는다 이에 나는 테스트 할때 main함수 부분의 주석을 해제해서 사용했다.

또한 이 문제의 경우 나의 post함수에 주석 부분은 성능을 올리기 위함이지만 가독성으로 볼때는 주석처리를 하는게 맞다.

그 이유는 위에 첨부한 풀이 그림을 보았을 때 원소가 2개남았을 때 무조건 start가 leaf단계이기 때문에 더이상 분할 할 필요가 없기 때문이다 하지만 맨끝에 원소가 하나 남았을 때는 굳이 출력을 해줄 필요가 없다. 이에 나는 원소가 하나 남았다는 것

if (start >= end) return;

을 이런식으로 start  인덱스와 end 인덱스가 같을 때 함수를 return 하여 더 이상 진행되지 않도록 하였다