급하게임개발

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

이 문제는 전형적인 bfs문제이다 일단 예시로 주어지는 그림부터가 이문제는 bfs로 푸는 것이다라고 알려주고 있다. 이에 이문제는 bfs로 풀어주면 된다 bfs 문제는 queue를 많이 사용한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int arr[1002][1002] = { 0,};
int answer[1002][1002] = {0,};
int startX, startY;
queue <pair<int,int>> bfsq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			int temp;
			cin >> temp;
			arr[i][j] = temp;
			if (temp == 2) {
				startX = i;
				startY = j;
			}
		}
	}
	bfsq.push(make_pair(startX, startY));
	answer[startX][startY] = 0;
	while (!bfsq.empty()) {
		startX = bfsq.front().first;
		startY = bfsq.front().second;
		bfsq.pop();
		if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
			bfsq.push(make_pair(startX, startY + 1));
			answer[startX][ startY + 1] = 1 + answer[startX][startY];
		}
		if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
			bfsq.push(make_pair(startX, startY - 1));
			answer[startX][startY - 1] = 1 + answer[startX][startY];
		}
		if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
			bfsq.push(make_pair(startX+1, startY));
			answer[startX+1][startY] = 1 + answer[startX][startY];
		}
		if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
			bfsq.push(make_pair(startX-1, startY));
			answer[startX-1][startY] = 1 + answer[startX][startY];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (answer[i][j] == 0&& arr[i][j] == 1) {
				cout << -1 << " ";
			}
			else {
				cout << answer[i][j] << " ";
			}
		}
		cout << endl;
	}
}

전체 코드는 이렇게 되고 하나하나 설명을 하도록 하겠다.

bfsq.push(make_pair(startX, startY));
	answer[startX][startY] = 0;
	while (!bfsq.empty()) {
		startX = bfsq.front().first;
		startY = bfsq.front().second;
		bfsq.pop();
		if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
			bfsq.push(make_pair(startX, startY + 1));
			answer[startX][ startY + 1] = 1 + answer[startX][startY];
		}
		if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
			bfsq.push(make_pair(startX, startY - 1));
			answer[startX][startY - 1] = 1 + answer[startX][startY];
		}
		if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
			bfsq.push(make_pair(startX+1, startY));
			answer[startX+1][startY] = 1 + answer[startX][startY];
		}
		if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
			bfsq.push(make_pair(startX-1, startY));
			answer[startX-1][startY] = 1 + answer[startX][startY];
		}
	}

일단 위 코드의 이부분은 pair로 이루어진 큐에서 값을 뽑고 그값을 기준으로 상하좌우의 값을 큐에다가 다시 넣어준다 그후 넣어준큐의 순서에대한 값이 저장되어있는 answer배열에 나의 방문번째수 +1을 넣어서 해준다 즉 내가 2번 layer에 자식이라면 나의 상하좌우는 3번 layer 에 자식이된다

트리로 그리게 되면 이런 구조가 된다. 그후 내가 몇번째 layer에 있는지를 answer배열에 저장해주면 된다.

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

이 문제는 일단 백준상에서 골드 5로 되어있는 문제다 근데 이문제를 보았을 때 느낀게 과연 내가 이 문제가  백트래킹인걸 모르고 풀었을 때 빠르게 정답을 유추 할 수 있었을까? 절대 아니다. 요즘 해당 알고리즘이 주어질 경우에는 그 알고리즘으로 문제를 빠르게 풀지만 내가 어떤 문젠지를 모르면 풀 수 있을 지는 모르겠다. 확실히 실무를 보다보니 머릿속에 생각한 것을 그대로 구현하는 구현능력은 조금 올라갔는데 앞으로도 계속 좋은 일이 있었으면 좋겠

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
char arr[16];
char answer[16];
int cnta;
int cntj;
bool isPassword;
int solution(int level, int beforeindex) {
	if (level == N) {
		cnta = 0;
		cntj = 0;
		isPassword = false;
		for (int i = 0; i < N; i++) {
			if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')
			{
				cnta++;
			}
			else
				cntj++;
			if (cnta > 0 && cntj > 1) {
				isPassword = true;
				break;
			}
		}
		if (isPassword) {
			for (int i = 0; i < N; i++) {
				cout << answer[i];
			}
			cout << endl;
		}
	}
	else {
		for (int i = beforeindex + 1; i <= M; i++) {
			answer[level] = arr[i];
			solution(level + 1, i);
		}
	}
	return 0;

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

}

이코드의 경우 모음의 개수를 세주는 CNTA 자음의 개수를 세주는 CNTJ라는 변수가 존재 한다 이 변수의 경우 루프를 돌다가 특정 조건을 만족했을 때 바로 루프를 탈출하게 해준다. 즉 최종 4글자 가 모였을 때 이 문자열이 모음이 1개이상 자음이 2개이상이면 더이상 조건을 판단할 필요없으니 루프를 탈출하게 해주는 것이다.

	else {
		for (int i = beforeindex + 1; i <= M; i++) {
			answer[level] = arr[i];
			solution(level + 1, i);
		}
	}

이 부분의 경우는 재귀를 이용해서 백트래킹을 하기 위함인데 정렬되어있는 arr값에서 자기 이전의 index보다 큰 인덱스 부터 시작하기에 무조건 오름차순이 된다.

이 문제의 경우 기초적인 BFS문제 이다 일단 이문제가 원하는 건 경로가 아닌 루트의 갯수를 원하는 것이다. 이에 나는 평균적인 성능을 보장해 주는 BFS를 사용하였다.

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

vector<int> bfsV[1001];
queue<int> bfsQ;
int arr[1001] = { 0, };
int N, M;
int cnt = 0;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		bfsV[temp1].push_back(temp2);
		bfsV[temp2].push_back(temp1);
	}
	for (int i = 1; i <= N; i++) {
		if (arr[i] == 0) {
			bfsQ.push(i);
			arr[i] = cnt;
			cnt++;
			while (!bfsQ.empty()) {
				int temp3;
				temp3 = bfsQ.front();
				bfsQ.pop();
				for (int j = 0; j < bfsV[temp3].size(); j++) {
					if (arr[bfsV[temp3][j]] == 0) {
						bfsQ.push(bfsV[temp3][j]);
						arr[bfsV[temp3][j]] = cnt;
					}
				}
			}
		}
	}
	cout << cnt;
}

이 문제는 너무 쉽다 dp이긴 한데 점화식으로 풀었다고 하기엔 애매하다 1부터 123을 다 더해서 작으면 다시 더한후 그값이 커지면 그 이후로는 계산을 안하면 되겠다는 생각으로 이 문제를 풀었다 이문제는 생각 보다 매우 쉬웠다 설명할것도 없이 코드를 보면 이해가 될것이다

#include <iostream>
#include<queue>
using namespace std;
int T;
queue <int> n;
int answer[12];
int solution(int start,int answerindex) {
	if (start == answerindex) {
		answer[answerindex]++;
	}
	else if (start > answerindex) {
		return 0;
	}
	else {
		solution(start + 1, answerindex);
		solution(start + 2, answerindex);
		solution(start + 3, answerindex);
	}
	return 0;
}
int main() {
	cin >> T;
	int temp;
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int i = 1; i <= T; i++) {
		cin >> temp;
		n.push(temp);
	}
	while (!n.empty()) {
		temp = n.front();
		n.pop();
		solution(0, temp);
		cout << answer[temp] << endl;
	}
}

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

처음에 이문제를 보았을 때 분할 정복을 사용해서 풀면은 될거같다는 느낌을 팍팍 풍기는 그림이 그려져 있었다.

이에 분할정복을 처음 사용 할때 나는 파란종이와 흰종이를 구하는 함수 2개를 만들어서 실행시켰다. 하지만 실행 시키고나니 시간초과가 발생하였다. 이에 시간 초과를 발생시키지 않기 위해서 파란색 종이를 구하면서 하얀색 종이를 구할 수 있도록 작성했다

#include <iostream>
using namespace std;
int N;
int bCnt;
int wCnt;
int arr[128][128];
int bSolution(int x, int y , int size) {
	if (size == 0) {
		return 0;
	}
	int check=0;
	for (int i = x; i < x+size; i++) {
		for (int j = y; j < y+size; j++) {
			if (arr[i][j] != 1) {
				check = 1;
				break;
			}
		}
		if (check == 1)
			break;
	}
	if (check == 1) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (arr[i][j] != 0) {
					check = 2;
					break;
				}
			}
			if (check == 2)
				break;
		}

	}
	if (check == 0) {
		bCnt++;
	}
	else if (check == 1) {
		wCnt++;
	}
	else {
		bSolution(x, y, size / 2);
		bSolution(x, y + size / 2, size / 2);
		bSolution(x + size / 2, y, size / 2);
		bSolution(x + size / 2, y + size / 2, size / 2);
	}
	return 0;
}

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

	bSolution(0, 0, N);
	cout << wCnt<<endl;
	cout << bCnt << endl;
}

위에 코드를 보면 check라는 변수가 존재 한다 나는 check가 0일 때는 파란색종이의 갯수를 구하다 check가 1로바뀌면 흰종이를 check가 2로 해당영역이 파란종이도 흰종이도 아닌것이라고 파악했다 이경우 분할을 통해 다시 색종이의 갯수를 구한다.

	for (int i = x; i < x+size; i++) {
		for (int j = y; j < y+size; j++) {
			if (arr[i][j] != 1) {
				check = 1;
				break;
			}
		}
		if (check == 1)
			break;
	}

이부분은 해당영역에 0이 하나라도 있으면 break 한다 그럼 일단 파란종이는 아니다

	if (check == 1) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (arr[i][j] != 0) {
					check = 2;
					break;
				}
			}
			if (check == 2)
				break;
		}

	}

이부분은 일단 파란종이가 아니니 흰종이인지 검사한다 이부분에서 0이 하나라도 발견되면 흰종이가 아니니 이제 모드를 check2로 바꾸고 분할정복을 시행한다. 확실히 회사일을 하다보니 알고리즘 실력은 줄었으나 뭔가를 생각하고 구현을 하는 능력은 올라간거 같다

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

이 문제는 한동안 다른프로젝트를 진행하다가 다시 알고리즘을 풀면서 우선순위 큐에 대해 공부해야할 필요성이 있을거 같아 풀기 시작한 문제이다 이 문제의 경우 처음에 이중 우선순위 큐라는 자료구조를 직접 클래스로 작성할 까 생각하다가 메모리제한과 시간제한이 여유로운 것을 보고 최대값 우선순위 큐와 최솟값 우선순위 큐를 2개를 사용하여 풀면 될 것 같은 생각을 했다 이에 그렇게 구현 하여 작성했

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pqMin;
priority_queue<int, vector<int>> pqMax;
map<int, int>cnt;
void insertpq(int n) {
	pqMax.push(n);
	pqMin.push(n);
	cnt[n]++;
}
void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

int main() {

	int T, n, k;
	char mode;
	cin >> T;
	for (int i = 0; i < T; i++) {
		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

		cnt.clear();

		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> mode >> n;
			if (mode == 'I') {
				insertpq(n);
			}
			else {
				if (n == 1)
					deleteMax();
				else
					deleteMin();
				while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
					pqMax.pop();
				}
				while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
					pqMin.pop();
				}
			}
		}
		if (pqMax.empty() || pqMin.empty()) {
			cout << "EMPTY\n";
		}
		else cout << pqMax.top() << " " << pqMin.top() << '\n';
	}
	return 0;
}

이문제의 경우 가장 중요한건  최솟값 우선순위 큐와 최댓값 우선순위 큐를 계속 동기화를 시켜줘야 한다 즉 최댓값 우선순위 큐에서 삭제한 데이터는 후에 최솟값 우선순위 큐에서도 삭제를 해줘야한다. 또한 이 문제의 경우 여러개의 테스트 케이스를 한번에 입력함으로 각각의 테스트 케이스 마다 우선순위 큐를 초기화 시켜줘야한다 이에

		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

이 부분을 작성해서 매 테스트 케이스 마다 초기화 시켜주었다 그후 2번째로 중요한 부분은

void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

이 두 부분이다 이 두부부느이 경우 각자의 우선순위 큐에서 데이터를 지울때 일차적으로 데이터를 동기화 시켜주기 위함이다 만약 어느 한쪽에서의 값을 지웠을 경우 cnt의 값이 0이되있을 것이므로 반대쪽에 큐에서 cnt가 0인 부분들을 pop해줄수 있게 하기위해서다 

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

이 문제는 내가 지금 까지 DP배열을 1차원 배열로 만드는데 익숙 해져서 그런지 2차원 배열로 설정 하는 것을 생각을 못해서 어려운 문제 였다. 이 문제의 경우 나는 이렇게 생각 해주었다.

일단 나는 이문제를 1번 아이템 부터 4번아이템을 넣어준다고 가졍하였다 이문제에서 0은 어떠한 아이템도 안 넣었다고 생각해서 0이자 무게가 0이라고 생각을 했다 이렇게 생각하지 않으면 너무 헷갈렸다 그래서 1번을 넣었을 때 무게가 6이고 7인 경우에는 1을 넣었기 때문에 1의 무게인 13을 넣었다. 1을 넣었을 때 무게가 1,2,3,4 일 수는 없으니 1을 넣지 않았다는 표시이자 안 넣었고 무게도 0이니 0으로 한다. 2번아이템을 넣었을 때 도 마찬가지 무게가 1,2,일 때는 2번을 넣었을 때

무게가 4로 초과되니 0으로 표시한다 그후 무게가 4랑 5일때는 

나의 이전 단계인 1을 넣었을 때의 무게들 중 나를 안넣었다고 가정한 무게 + 나의 무게를 했을 때와 이전단계의 무게들과 비교하여 더큰 값을 넣어준다. 이것을  dp로 표현 하면

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); 

예시로 dp[2][6]은 dp[1][2]+v[2] 과 dp[1][6]일 때를 비교한다 이 의미는 1을 먼저 넣을 안넣을 지 결정하는 상태에서 무게가 2일때+나의 더했을 때의 가치와 1을 넣을 안넣을지 결정했을 무게가 6인 경우를 비교하여 더 큰 값을 선택한다.

쉽게 설명하자면

1을 넣을지 말지 결정했을 때  특정 무게를 맞춘다고 가정했을 때 나의 무게를 더해서 그 무게를 맞춘다고 가정한 값과 이전 단계에서 그 무게를 달성했을 때의 값을 비교하여 큰값을 선택해 주는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[101][100001];//가방 물건의 번호,내가방의 무게
int W[101];
int V[101];
int main() {
	int maxItemNum;
	int maxItemWeight;
	cin >> maxItemNum >> maxItemWeight;

	for(int i=1; i<=maxItemNum; i++){
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= maxItemNum; i++) {
		for (int j = 1; j <= maxItemWeight; j++) {
			if (j - W[i]>=0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[maxItemNum][maxItemWeight];
}

그래서 이러한 점화식으로 이문제를 풀면 전체 식이 이렇게 된다. 1차원으로 dp를 세우는 거 뿐만 아니라 다차원의dp 도 세우는 방법을 연습해야 할거 같다.

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

이러한 문제류는 이제 dfs든 bfs로 풀기 쉬워졌다 이문제의 경우 자신을 기준으로 상하좌우로만 이동 할 수있기때문에 깊이우선 탐색으로 풀어 보았다 이문제는 어차피 단지의 개수를 세야 하기때문에 모든점을 한번에 다방문하면서 개수를 셀수 있는 dfs를 사용하였다. 이문제의 핵심 부분은

	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);

이부분이다 나를 기준으로 내 상하좌우중 방문한적이 없는 애들이 없으면 방문한다 그후 이함수 부분을 재귀적으로 호출하기 때문에 내 다음애들이 없으면 다시 부모로 돌아가서 다음거를 탐색한다 즉 재귀함수로 dfs를 구현한것이다

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int map[26][26];
bool visited[26][26];
int countnum = 0;
int danjicount = 0;
vector<int> answer;
void dfs(int i, int j) {
	countnum++;
	visited[i][j] = true;
	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);
}
int main() {
	int N;
	string temp;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> temp;
		for (int j = 0; j <N; j++) {
			map[i][j + 1] = temp[j]-'0';
		}
	} 

	for (int i = 1; i <= N; i++) {	
		for (int j = 1; j <= N; j++) {
			countnum = 0;
			if (visited[i][j] || map[i][j]==0)
				continue;
			dfs(i, j);
			danjicount++;
			if(countnum)
				answer.push_back(countnum);
		}
	}
	
	sort(answer.begin(), answer.end());
	cout << danjicount << '\n';
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

}