급하게임개발

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

이 문제는 브루트 포스 문제이다 범위가 500000으로 확정되었기 때문에  특정 범위 안에 있는 수들이 조건이 맞는지만 판별해주면 되는 분제였다 나는 수빈이가 이동하려는 범위의 2배를 채널 선택의 범위로 정하였다.

일단 나는 수빈이가 선택하려는 채널을 기준으로 증가하는 채널과 감소하는 채널 2개를 선택해 2개중에 더 작은 값을 사용하는 방법을 사용하였다

위 그림처럼 변수 psearch와 nsearch를 만들어 

수빈이가 선택한 채널을 기준으로 더큰채널과 더작은 채널 중 증가와 감소로 접근할 수 있는 범위를 찾고 자릿수 입력도 입력수에 포함하기 때문에 +-버튼 클릭수와 채널의 자릿수를 더해서 비교후 더 작은값을 저장해준다.

여기에서 추가로 또 예외처리 해줘야 할게 있는데

수빈이의 채널이 100부터 시작하기에 만약 채널이 100부터 시작했을 때 더 가까울 경우도 생각해주어야 한다.

해당 그림을 통해 구현한 코드는 아래와 같다

#include<iostream>
#include<stdlib.h>
int N,M;
bool arr[10];
int psearch = 1000000;  
int nsearch = 1000000;
int hsearch;
using namespace std;
int solution(int n) {
	if (n < 10) {
		if (!arr[n]) {
			return 1;
		}
	}
	else if (n < 100) {
		if (!arr[n / 10] && !arr[n % 10]) {
			return 2;
		}
	}
	else if (n < 1000) {
		if (!arr[n/100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 3;
		}
	}
	else if (n < 10000) {
		if (!arr[n/1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 4;
		}
	}
	else if (n < 100000) {
		if (!arr[n / 10000] && !arr[n%10000 / 1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 5;
		}
	}
	else if(n<1000000){
		if (!arr[n / 100000] && !arr[n%100000 / 10000] && !arr[n%10000 / 1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 6;
		}
	}
	return false;
}
int main() {
	cin >> N >> M;
	int searchNum1,searchNum2;
	int answer = 0;
	for (int i = 0; i < M; i++) {
		int temp;
		cin >> temp;
		arr[temp] = true;
	}
	searchNum1 = N;
	searchNum2 = N;


	while (true) {
		if (solution(searchNum1) && (searchNum1 >= 0)) {
			psearch = solution(searchNum1) + (N - searchNum1);
			break;
		}
		searchNum1--;
		if (searchNum1 < 0)
			break;
	}

	while (true) {
		if (solution(searchNum2) && (searchNum1 <=1000000)) {
			nsearch = solution(searchNum2) + (searchNum2-N);
			break;
		}
		searchNum2++;
		if (searchNum2 > 1000000)
			break;
	}
	hsearch = abs(N - 100);
	if (psearch > nsearch) {
		answer = nsearch;
	}
	else {
		answer = psearch;
	}

	if (answer > hsearch) {
		answer = hsearch;
	}

	cout << answer;
}

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

이 문제는 쉽다 일단 다익스트라 알고리즘을 사용하고 간선이 양방향이니 양방향으로 설정해 준다

다익스트라로 각지점의 최단거리를 구해준 후 거리를 정렬하여 범위 안에 있는 아이템에 개수를 더해준 누적값을 구해주면 된다

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
#define INT_MAX 2147483647
using namespace std;
int NumOfItem[101];
vector<pair<int, int>> dijkstraV[101];
vector<int> distanceV(101);

void dijkstra(int start) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; // 비용 노드
	pq.push(make_pair(0, start));
	distanceV[start] = 0;
	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraV[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraV[toVertex][i].second;
			if (cost < distanceV[dijkstraV[toVertex][i].first]) {
				distanceV[dijkstraV[toVertex][i].first] = cost;
				pq.push(make_pair(cost, dijkstraV[toVertex][i].first));
			}
		}
	}
}

int getNumOfItem(int idx, int n, int m) {
	int sum=0;
	for (int i = 1; i <= n; i++) {
		if (distanceV[i] <= m) {
			sum += NumOfItem[i];
		}
	}
	return sum;
}


int main() {
	
	int n, m, r;
	int maxItem=0;
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> NumOfItem[i];
	}

	int from, to, cost;
	for (int i = 0; i < r; i++) {
		cin >> from >> to >> cost;
		dijkstraV[from].push_back({ to, cost });
		dijkstraV[to].push_back({ from,cost });
	}

	for (int i = 1; i <= n; i++) {
		distanceV.assign(101, INT_MAX);
		dijkstra(i);
		if(maxItem < getNumOfItem(i, n, m))
			maxItem = getNumOfItem(i, n, m);
	}
	cout << maxItem;
}

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

이 문제는 다익스트라 알고리즘을 그대로 사용하면 풀 수 있는 문제이다. 자세한 풀이 과정은 이전에 내가 올려놓은

https://fastgamedev.tistory.com/49

이 글의 문제와 똑같이 풀고나서 해당 도착지의 값만 출력해주는 문제라 매우 쉬웠다.

#include<iostream>
#include<queue>
#include<vector>
#define INT_MAX 2147483647
using namespace std;
vector<pair<int, int>> djikstraPQ [1001];
vector <int> distanceV(1001);
void dijkstra(int start) {
	priority_queue < pair<int, int>, vector < pair<int, int>>, greater<pair<int, int>>> pq;// front는 cost second 는 index
	pq.push({ 0, start });
	distanceV[start] = 0;
	
	while (!pq.empty()) {
		int costTo = pq.top().first;
		int toIdx = pq.top().second;
		pq.pop();

		if (distanceV[toIdx] < costTo) {
			continue;
		}

		for (int i = 0; i < (int)djikstraPQ[toIdx].size(); i++) {
			// 나랑 연결되어 있는애가 Second 비용이 front
			int cost = djikstraPQ[toIdx][i].second + costTo;
			if (cost < distanceV[djikstraPQ[toIdx][i].first]) {
				distanceV[djikstraPQ[toIdx][i].first] = cost;
				pq.push({ cost, djikstraPQ[toIdx][i].first });
			}
		}
	}
	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M, start, arrive;
	cin >> N >> M;
	int from, to, cost;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> cost;
		djikstraPQ[from].push_back({ to,cost });
	}
	cin >> start >> arrive;
	distanceV.assign(1001,INT_MAX);
	dijkstra(start);

	cout << distanceV[arrive];
}

이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단  이 문제의 코드는 이렇게 된다

#include <iostream>
#include <queue>
#include <vector>
#define INT_MAX 2147483647
using namespace std;
vector<int> distanceV(20002); //시작점 부터 다른 정점까지의 거리를 저장
vector<bool> visited;
void djikstra(int start, vector<pair<int, int>> dijkstraGraph[]) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 노드 인덱스
	pq.push(make_pair(0, start));
	distanceV[start] = 0;

	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraGraph[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraGraph[toVertex][i].second;
			int nextIndex = dijkstraGraph[toVertex][i].first;
			if (cost < distanceV[nextIndex]) {
				distanceV[nextIndex] = cost;
				pq.push(make_pair(cost, nextIndex));
			}

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge, start;  //vertex는 정점 edge는 간선 start는 시작점을 입력 받는다.
	cin >> vertex >> edge >> start;
	vector<pair<int, int>> dijkstraGraph[20002];//다익스트라 알고리즘의 비용을 저장할 우선순위 큐
	for (int i = 1; i <= edge; i++) {
		int from, to, cost;  //from은 간선사이의 시작점,to는 도착점 , cost는 간선의 비용을 의미
		cin >> from >> to >> cost;
		dijkstraGraph[from].push_back(make_pair(to,cost));
	}
	distanceV.assign(20002, INT_MAX);
	djikstra(start, dijkstraGraph);
	for (int i = 1; i <= vertex; i++) {
		if (distanceV[i] == INT_MAX) {
			cout << "INF"<<endl;
		}
		else {
			cout << distanceV[i] << endl;
		}
	}
}

이 문제의 경우 일단 간선의 방향이 단 방향이다. 일단 이문제의 예시 input에 대한 과정의 그림을 첨부하겠다

이 그림 에서 원으로 되어 있는 그래프는 위에 dijkstra함수에 pq를 그린것이다. 밑에 배열은 distanceV를 그린것이다.

일단 처음 풀이에서

distanceV.assign(20002, INT_MAX);

이 코드를 통해 배열에 큰 값을 다 넣어주었다 이에 처음 벡터에는 INF값만 가득하다 그후 1,0 즉 시작점 1에서 도착지 1로가는 거리는 자기자신이므로 0을 넣어준다 그후 2,2순으로 pq순에서 팝되는 값과 나와 연결되어 있는 다음 인덱스의 값을 더해서 distanceV에 거리를 갱신해 준다. 즉 1이 팝되었을때는 2,3의 거릿값이 갱신된다. 이후 2가팝되었을 때는 3과 4에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.

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

이 문제의 경우 반례를 생각 못해서 틀렸다 기존 코드에서 일반적인 반례는 잘 나왔으나 0 1을 입력했을 때  0 이 나와야 했는데 기존의 코드가 게속 1을 출력했다. 이 부분을 해결하니 해결되었다

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
int visited[100001];
int N, K;

int main() {
	cin >> N >> K;
	queue<int> hs;
	hs.push(N);
	memset(visited, -1, sizeof(visited));
	visited[N] = 0;
	while (true) {
		if (hs.front() == K) {
			break;
		}
		if (hs.front() <= 50000) {
			if (visited[hs.front() * 2] == -1) {
				hs.push(hs.front() * 2);
				visited[hs.front() * 2] = visited[hs.front()];
			}
			else {
				if (visited[hs.front() * 2] > visited[hs.front()]) {
					visited[hs.front() * 2] = visited[hs.front()];
					hs.push(hs.front() * 2);
				}
			}
		}
		if (hs.front() > 0) {
			if (visited[hs.front() - 1] == -1) {
				hs.push(hs.front() - 1);
				visited[hs.front() - 1] = visited[hs.front()] + 1;

			}
			else {
				if (visited[hs.front() - 1] > visited[hs.front()] + 1) {
					visited[hs.front() - 1] = visited[hs.front()] + 1;
					hs.push(hs.front() - 1);
				}
			}
		}
		if (hs.front() < 100000) {
			if (visited[hs.front() + 1] == -1) {
				hs.push(hs.front() + 1);
				visited[hs.front() + 1] = visited[hs.front()] + 1;
			}
			else {
				if (visited[hs.front() + 1] > visited[hs.front()] + 1) {
					visited[hs.front() + 1] = visited[hs.front()] + 1;
					hs.push(hs.front() + 1);
				}
			}
		}
		hs.pop();
	}
	cout << visited[K];
}

일단 이 문제의 경우 완전한 백트래킹이라기 보다 백트래킹과 BFS를 섞어서 해야 한다. 이에 나는 일단 BFS에서 주로 사용하는 큐를 작성하였다. 일단 이문제의 경우 BFS를 위해 그냥 계속 영역을 넓혀주면 된다 단 순서상으로 순간이동 즉 *2 부분을 먼저 해주었다. 그후 나머지 +1,-1 부분에서는 내가 접근하는 방식이 최소 방문횟수로 방문했으면 값을 넣어주고 아니면 무시하도록 작성하였다

이문제는 처음에 bfs로 접근 했다 bfs로 풀었을 때는 각 지점에서 bfs로 확장해나가다가 치킨집이 모든 집을 방문했을 때의 각치킨집의 거리합을 이용해서 최솟값을 도출했으나 시간초과가 발생하였다. 의외로 이 문제는 간단하게 풀리는 문제 였다 그냥 치킨집에서 N개를 뽑아서 얘네들을 집과의 거리를 구해서 집과 치킨의 최소 거리를 저장해준 후 이를 계속 비교해가며 최솟값을 찾는 문제였다. 백트랙킹을 이용한 조합을 사용하여 풀었다.

#include <iostream>
#include <vector>
#include <utility>
#define MAX_INT 2147483647
using namespace std;
int N, M;
vector<pair<int, int>> chickenPos;
bool isVisited[50] = { 0, };
vector<pair<int, int>> housePos;
vector<pair<int, int>> selectedChicken;
int minCityDistance=MAX_INT;
void calculateDistance() {
	int distanceOfCity = 0;
	for (int i = 0; i < housePos.size(); i++) {
		int minDistance = MAX_INT;
		for (int j = 0; j < selectedChicken.size(); j++) {
			int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
			if (distance < minDistance) {
				minDistance = distance;
			}
		}
		distanceOfCity += minDistance;
	}
	if (distanceOfCity < minCityDistance) {
		minCityDistance = distanceOfCity;
	}
}
void selectChicken(int idx, int level) {
	if (level == M) {
		calculateDistance();
		return;
	}
	for (int i = idx; i < chickenPos.size(); i++) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			selectedChicken.push_back(chickenPos[i]);
			selectChicken(i , level + 1);
			isVisited[i] = false;
			selectedChicken.pop_back();
		}
	}
}
int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			if (tmp == 2) {
				chickenPos.push_back(make_pair(i, j));
			}
			else if (tmp == 1) {
				housePos.push_back(make_pair(i, j));
			}
		}
	}
	selectChicken(0,0);
	cout << minCityDistance;
}

일단 이 코드의 이 부분 부터 보자

void selectChicken(int idx, int level) {
	if (level == M) {
		calculateDistance();
		return;
	}
	for (int i = idx; i < chickenPos.size(); i++) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			selectedChicken.push_back(chickenPos[i]);
			selectChicken(i , level + 1);
			isVisited[i] = false;
			selectedChicken.pop_back();
		}
	}
}

이 부분은 일단 치킨집의 좌표들이 저장되어있는 chickenPos vectory 에서 치킨을 선택한 후 에 selectedChicken 에 넣어준다 그후 isVisited를 true로 설정해 주어 방문했다고 한 뒤 다쓰고 나면 false로 바꿔주고 selectedchicken 벡터에서 제거해 준다. 그후 level이 M 즉 M개의 치킨집을 뽑았으면 calculate distance 함수를 실행한다.

void calculateDistance() {
	int distanceOfCity = 0;
	for (int i = 0; i < housePos.size(); i++) {
		int minDistance = MAX_INT;
		for (int j = 0; j < selectedChicken.size(); j++) {
			int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
			if (distance < minDistance) {
				minDistance = distance;
			}
		}
		distanceOfCity += minDistance;
	}
	if (distanceOfCity < minCityDistance) {
		minCityDistance = distanceOfCity;
	}
}

이 함수의 로직도 매우 간단하다 아까 이전 함수에서 뽑은 치킨집들이랑 각 집과 의 거리를 구하고 각집마다 치킨집에서 가장 가까운 거리를 minDistance에 저장한다 그후 각집의 치킨집까지의 최솟값을 더한후 이전에 뽑았던 최솟값과 비교를 해서 작은애를 다시 넣어준다.

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 하여 더 이상 진행되지 않도록 하였다

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

이 문제는 중위순회 전위순회 후위순회를 직접 구현해보는 문제였다 문제자체는 그리 어렵지 않았다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <vector>
using namespace std;
int alpha = 65;
//26개의 원소를 0으로 초기화
struct node {
	char left;
	char right;
};
vector<node> v(26);
void preOrder(char node) {
	if (node == '.'-alpha)
		return;

	printf("%c", node + alpha);
	preOrder(v[node].left);
	preOrder(v[node].right);
}
void inOrder(char node) {
	if (node == '.'-alpha)
		return;

	inOrder(v[node].left);
	printf("%c", node + alpha);
	inOrder(v[node].right);
}
void postOrder(char node) {
	if (node == '.'-alpha)
		return;

	postOrder(v[node].left);
	postOrder(v[node].right);
	printf("%c", node + alpha);
}
int main() {
	int N;
	scanf("%d", &N);
	getchar();
	char parent, leftchild, rightchild;
	for (int i = 0; i < N; i++) {
		scanf("%c %c %c", &parent , &leftchild , &rightchild);
		getchar();
		v[parent-alpha].left = leftchild-alpha;
		v[parent-alpha].right = rightchild-alpha;
	}

	preOrder('A'-alpha);
	printf("\n");
	inOrder('A'-alpha);
	printf("\n");
	postOrder('A'-alpha);
	return 0;
}