급하게임개발

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/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;
}

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

이 문제는 재시도를 엄청 했다 첫번째 풀이로는 평범하게 사용하는 누적합을 사용해서 풀어보았다. 실버3이라서 확실히 이런 기초적인 코딩을 쓰지는 않았을 거 같지만 일단 해보았다. 당연히 시간초과가 발생했다. 그럼 무슨 알고리즘을 써야할까 알아보다 슬라이딩 윈도우 알고리즘이라는 기억 어딘가에 쳐박아놓은 알고리즘이 생각 났다. 이에 iostream의 cin과 cout을 stdio와 sync까지 끊고 코드를 작성하였음에도 시간초과가 발생했다. 이에 3번째에서는 iostream을 stdio.h 로 바꾸고 실행하니까 정상 적으로 실행 되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;
int N;
int M;
int arr[100001] = { 0, };
int i, j;
int main() {

	int temp1, temp2;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		arr[i] = arr[i] + arr[i - 1];
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &temp1, &temp2);
		printf("%d\n", arr[temp2] - arr[temp1 - 1]);
	}
}

이런 식으로 배열에 누적값을 저장해 줌으로서 범위를 구할 때 2 5를 입력했을 때를 예시로들면 5까지 입력한 값에서 1까지 누적된값을 빼면 2에서5의 누적값이 나온다 기존에 누적시키는 것보다 O(1)의 시간밖에 걸리지 않아 시간초과 가 발생하지 않는다.

최근에 본 코테에서 나온 문제인데 프로그래머스에서 알고리즘 문제를 출제하는 기업들의 단골 기출 문제인 듯 하다 실제로 다른 회사에서도 출제된 사례가 있었다.같이 제공되는 이미지도 많이 겹치는 것 같다.

내적의 개념과 응용을 코테에 녹인 문제 인거 같다. 기억이 잘 안나고 그림도 기억나는데로 그려서 올리겠다

문제 :

한 게임의 캐릭터가 스킬을 사용한다.

해당 캐릭터가 스킬 사용시 스킬의 범위는 부채꼴이다.

해당 부채꼴 범위 안에 적이 있다면, 적은 데미지를 받지만, 범위 밖이라면 데미지를 받지 않는다.

데미지를 받는 적의 수를 Return하세요.

조건1 : 스킬을 사용하는 주체인 게임 캐릭터는 항상 0,0 위치에 있다.

조건2 : 적들은 0,0에 있을 수 없으며, 겹쳐있지 않다.

조건3 : 캐릭터와 일직선상에 적이 2명 이상 겹쳐있어도, 범위 안에만 들어오면 데미지를 받는 것으로 인식한다.

주어지는 값 : 

1. 스킬을 사용하기위해 위치해있는 마우스 좌표 int x,y

2. 스킬의 길이(반지름) int r

3. 각도 int d

4. 적들의 위치 xn, yn이 담긴 int형 2중벡터 vector<vector<int> > target

============================================================================================

이문제의 경우 나는 단계를 2개로 나눠서 풀 것이다. 1번 해당 적이 나를 기준으로 스킬범위 안에 있는가를 먼저 검증한다.

자 이 공식을 사용하면 된다. 어차피 우리는 좌표가 0,0이기 떄문에 실제로 해당 적의 x좌표의 제곱과 y좌표의 제곱을 더한것에 제곱근이 입력된 스킬의 길이보다 작으면 된다. 

또한 게임수학에서 내적은 두 벡터의 각도를 알려준다 이를 이용해 위에서 걸러낸 애들을 2차로 걸러준다. 이 때 우리가 사용할 함수는 acos()이다 이 함수의 경우 안에 내적으로 나온값을 넣어주면 우리가 원하는 각도의 값이 나온다 이를이용해 구현해보도록 하겠다.

자 여기서 빨간 부분을 좌변으로 이항 시켜 보다 그럼 내적을 구하면 벡터의 크기의 곱으로 내적을 나무녀 cos인 값이 나오고 이를 acos에 넣으면 각도인 세타값이 나온다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
double Distance(double x, double y) {
	double distance;
	distance = sqrt(pow(x, 2) + pow(y, 2));
	return distance;
}

double  DotProduct(double x1, double y1, double x2, double y2) {
	return (x1 * x2) + (y1 * y2);
}

double sizeOfVector(double x, double y) {
	double size;
	size= sqrt(pow(x, 2) + pow(y, 2));
	return size;
}
int solution(int x, int y, int r, double d, vector<vector<int>>target) {
	int cnt = 0;
	for (int i = 0; i < target.size(); i++) {
		if (Distance(target[i][0], target[i][1])<=r) {
			if (acos(DotProduct(x, y, target[i][0], target[i][1]) / (sizeOfVector(x, y) * sizeOfVector(target[i][0], target[i][1])))<=d) {
				cnt += 1;
			}
		}
	}
	return cnt;
}
int main() {
	vector<vector<int>> target = { {1,3},{1,1},{4,3},{9,9},{-2,8} };
	cout<<solution(2, 4, 3, 60, target);
}

이를 코드로 작성하면 이렇게 된다.

이번에 모회사 코테를 보는 데 내가 못풀었던 문제에서 중복순열을 2번사용하여 경우의 수를 구하는 브루트포스 방식의 문제가 출제 되었던 거 같다. 내가 생각한게 정답이 아닐 수 도 있지만 적어도 내가 생각한데로 풀기 위해서는 중복순열과 순열을 구현했어야 했다. 하지만 오랫동안 기본적인 알고리즘 조차 손을 놓았어서. 역시 급하게 준비한 코테답게 불합격 메일을 기다리고 있다. 확실히 불합격이 되더라도 코테를 직접 보면서 어떤 식으로 공부해야할지 감이 잡히기 시작했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//중복 순열
int caseNum;
int arr[100000];
bool vectorIndexUsed[100000];
void DuplicatePermutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		DuplicatePermutation(level + 1, caseVector);
	}
}


void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

void Combination(int level, vector<int> caseVector, int beforeIndex) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = beforeIndex; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		Combination(level + 1, caseVector, beforeIndex + 1);
	}
}

int main() {
	cin >> caseNum;
	vector<int> dupPermuTest = { 1,4,5,2 };
	DuplicatePermutation(0, dupPermuTest);
	cout << "====================================="<<endl;
	Permutation(0, dupPermuTest);
	cout << "====================================="<<endl;
	sort(dupPermuTest.begin(), dupPermuTest.end());
	Combination(0, dupPermuTest, 0);
}

일단 기억나는 것은 주어진 벡터에서 몇명을 뽑아야하는 것이었다 이에 나는 중복순열,순열,조합순으로 현재 구현했다.

void DuplicatePermutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		DuplicatePermutation(level + 1, caseVector);
	}
}

중복 순열의 경우 똑같은 걸 여러번 사용해도 되니 굳이 사용했는지 안했는 지 체크할 필요가 없다

void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

순열의 경우 vector에서 순서가 다르면 다른것으로 인정하고 중복은 허하지 않는다

void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

조합은 중복을 허하지도 않고 순서가 달라도 같은 수를 뽑았으면  허용치 않는다.

void duplicateCombination(int level, vector<int> caseVector, int beforeIndex) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = beforeIndex; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		duplicateCombination(level + 1, caseVector, i);
	}
}

중복 조합은 같은 수를 뽑을 수 있고 순서가 존재한다 이에 같은수는 뽑을 수 있지만 순서가 다르고 동일한 요소로 이루어져있는 것은 이전에 뽑은것과 같음으로 허용치 않는다

이 정도 문법은 꼭 기억하도록 하자