급하게임개발

이 문제의 경우 기초적인 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로 바꾸고 분할정복을 시행한다. 확실히 회사일을 하다보니 알고리즘 실력은 줄었으나 뭔가를 생각하고 구현을 하는 능력은 올라간거 같다

취준을 준비하는 와중에 시험삼아 넣어본 펄어비스 서류가 덜컥 붙어버렸다. 

현재 일을 하고 있는 상태라서 코테랑 CS준비도 안 되있는데 붙어서 발등에 불이 떨어졌다. 

5월 19일에 발표가 나고 5월 23일에 필기 테스트를 보았다.

비밀 유지 서약서에 의해 자세한 내용은 말할 수 없다. 하지만 펄어비스 테스트를 보고 내가 매우

부족한 사람이라는 것을 인지 했다 붙기 위해 지원한 건 아니지만 막상 떨어짐을 실감하니 코테랑 CS를 내가

노리는 동계 취업시즌 까지 갈고 닦아야함을 인지 했다. 아직 필기 결과는 안나왔지만

보나마나 불합이다.

일단 나의 문제점은 내 코딩실력은 IDE발을 많이 탔다는 것이다

자동완성이 없으면 아무것도 아닌 존재 였다. 일단 STL에 있는 많이 쓰이는 함수들은 외워야 할거같다

reference가 주어지는 시험이면 모르겠는데 펄어비스 필테를 보며 느꼈다.많이 쓰는 함수는 외우자.

둘째 나의 CS지식은 처참하다 포폴이 중요하다고 너무 포폴을 만드는데에만 집중했다.

포폴도 중요하지만 CS지식은 기본이다

셋째, 게임을 좋아하면 많이 쓰이는 수학이나 물리같은건 좀 외워놓자 이거마저 못하면 개발자 실격이다

펄어비스 결과는 보나마나 불합이 확실하지만 내가 어떤 방향으로 공부를 해야할지 알려주는 좋은 경험이었던것

같다. 비록 좋은 결과는 아니더라도 나의 안일함을 일깨워 주는 경험이었다. 앞으로 이렇게 배웠던 걸 더 연마해서 

좋은 게임 개발자가 되어야겠다!!!!!!!

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

이 문제의 경우 생각 보다 쉽게 풀리는 문제일거 같았다 일단은 어차피 탐색할거라면 사전에서 이분탐색이 효율적이라 판단 되어 이분탐색으로 각각의 리스트에 중복되는게 있는 지 없는지를 판단 하려고 하였다

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string DeutBo[500000];
string Bodo[500000];
string Answer[500000];
int binarysearch(string* a, string answer, int low, int high) {
	int mid;
	if (low > high)
		return 0;
	else {
		mid = (low + high) / 2;
		if (answer == a[mid]) {
			return 1;
		}
		else if (answer < a[mid]) 
			return binarysearch(a, answer, low, mid - 1);
		else
			return binarysearch(a, answer, mid + 1, high);
		
	}
}
int main() {
	int N, M;
	int cnt=0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> DeutBo[i];
	}
	sort(DeutBo, DeutBo+N);
	for (int i = 0; i < M; i++) {
		cin >> Bodo[i];
	}
	sort(Bodo, Bodo + M);
	for (int i = 0; i < M; i++) {
		if (binarysearch(DeutBo, Bodo[i], 0, M)) {
			Answer[cnt] = Bodo[i];
			cnt++;
		}
	}
	cout << cnt<<'\n';
	for (int i = 0; i < cnt; i++) {
		cout << Answer[i] << '\n';
	}
}

이문제의 경우 이분탐색의 개념만 알면 풀기 쉬운 문제였다 일다 string객체는 사전적 대소관계를 비교할 수 있으므로

이분 탐색을 통해 지속적으로 비교해주면 되는 문제였다

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/2293

DP는 해도해도 실력이 확실히 점화식을 잘세워야 하는 것 같다 이문제의 경우 점화식이 무조건 필요했는데 사실 문제 이해가 잘 안 갔어서 푸는데 4시간 걸렸다......알고리즘 빨리 풀어야하는데  이문제의 경우는 일단 예시로 나온

을 기준으로 하면 동전의 갯수 만큼의 경우의 수를 생각 해주어야 했다

맨처음 첫번째 동전인 1원만으로 1원 부터 10원 까지 만들 수 있는 경우의 수를 dp 에 채워 준다 그 후

2원 부분의 행을 채워 줘야한다 2원 부분의 행은 무조건 해당 단계에서 2원만을 사용해서 그 해당 수를 만들어 주는 경우의 수다 이부분에서는 5원에 대한 생각은 해주지 않습니다 2원의 행은 2원과 1원 부분만을 이용해서 그 해당 원수를 만드는 것 입니다

이에 이렇게 쭉 구하면서 5원 부분까지 가면 10월을 만들 때 딱 5원을 추가하여 10원을 만드는 경우의 수는 5원으로 5원을 만든 경우의수와 1원과 2원으로 만든 5원의 경우의 수와 1원으로만 만든 5원의 경우의 수를 더하여 4가지가 나온다 이렇게 생각을 하게 되면 이문제의 dp를 추정 할 수 있습니다 하지만 위에거를 그대로 사용하여 2차원 배열을 사용하게 되면 4mb를 초과하는 사태가 발생하여 틀렸습니다가 생겼습니다 이에 우리는 위에 식을 이용해 점화식을 더간단한 점화식을 만들어야합니다.

점화식을 세울때 우리가 봐야할 부분은 합계입니다  2원에서의 합계를 보시지요 자 기존에 1원에서 만 만들었던 값에서 자기자신을 뺀 부분에서의 값을 더해줌으로서 지금 원을 만드는데 2원을 넣었다고 가정했을 때의 경우의 수를 더해주게 됩니다.

각 2원의 행을 예시로 봅시다 2원의 행은 지금 계속 표를 보면 0원에서 2원

dp[2] += dp [0]   2

dp[3] += dp [1]   2

dp[4] += dp [2]   3

즉 dp[2] 의경우 1원으로 만든 경우의 수 + 0원의 경우의 수가 됩니다 이유는 0원에서 2원을 고름으로서 2원을 만들 것이기 때문입니다 이에

dp 배열의 합계 부분들은 이런식으로 값이 바뀌게 됩니다.

즉 먼저 하나의 코인으로 해당 값을 만든 다고 가정하고 그 경우의 수에서 나의 동전값을 뺏을 때의 경우의 수를 더해줘야 합니다 

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

이 문제는 앞으로 보나 뒤로 보나 분할 정복을 쓸거 같은 문제였다 처음에는 배열의 값을 분할정복을 이용해서 넣어주려했으나 이문제의 배열만큼의 크기를 선언하려면은 이문제의 메모리 제한을 넘는 배열이 생성 된다 이에 이문제는 소속 해 있는 행과 렬을 계산 해주면서 푸는 문제가 되겠다.

#include <iostream>
#include <cmath>
using namespace std;
int n, r, c;
int ans;
void solution(int row , int col , int size) {
	if (r == row && c == col) {
		cout << ans;
		return;
	}
	if (r >= row && r < row + size && c >= col && c < col +size)
	{
		solution(row, col, size / 2);//1사분면
		solution(row, col + size/2, size / 2); //2사분면
		solution(row + size/2, col, size / 2); // 3사분면
		solution(row + size / 2, col + size / 2, size / 2); //4사분면
	}
	else {
		ans += size * size;
	}
}
int main() {
	cin >> n >> r >> c;
	solution(0, 0, pow(2,n));
}

이 문제의 설명을 하자면

일단 초기값을 입력 받았을때 size의 크기의 col이 0~7 row가 0~7에 있는지 확인한다 그후 n과 r이 있는 사분면을 만났을 때 그 4분면을 4개로 쪼갠후 자신의 값이 포함되어 있는 4분면 쪽으로 들어가 답이 나올 때 까지 쪼개면서 결국에는 size가 1이 될 때까지 4분면의 4분면...을 찾아 들어간다 만약 4분면에 포함이 안되면 그 4분면의 크기만큼 ans값에 더해준다. 왜냐면 그만큼의 크기를 뛰어넘은것으로 생각되기 때문이다 

이에 이렇게 풀면 분할정복으로 이문제를 풀 수 있다