이것 저것 &

인적성검사 - 코딩테스트 - 1day 면접 순서로 진행합니다!

인적성검사

인적성검사는 비교적 간단하고 기본적인 유형들로 문제가 구성되어 있습니다. 온라인으로 진행했습니다. 

풀기전에 문제를 풀어보면 좋겠지만, sw직무 분들이 인적성까지 준비하기에는 어려움이 많죠.. ㅠㅠ

저도 이전에 문제를 안 풀어보고 시험을 보았습니다.

그런데도 붙었더라구요! 굉장히 쉬운편이라고 느꼈습니다.

팁은 문제가 여러개인데 유형이 중복되어서 나오더라구요. 그래서 문제를 푸시면서도 쉽게 포기하기보다는 끝까지

어떤 유형에 문제인지 파악하면 좋을거 같습니다.

아래 링크에서 수리와 관련한 유형들은 미리 학습하시면 좋을 것 같습니다.

https://www.youtube.com/watch?v=VMMoPE9wpIU 

코딩테스트

인적성과 함께 코딩테스트도 진행했습니다. 총 3개문제이고 2개는 알고리즘 문제, 1개는 sql 문제입니다.

비교적 쉬운 난이도이고 1시간동안 풀어야 했기 때문에 빠르게 푸는게 관건인 문제들 이었습니다.

문제 유형이나 내용은 비밀....

1day 면접

1 day 면접이라고 하루만에 직무 면접과 임원 면접을 함께 진행했습니다. 

직무면접에서는 기존에 과제로 제출한 ppt를 5분동안 발표하고 질의응답을 함께 진행했습니다.

그리고는 자소서 기반의 전형적인 직무 면접이었습니다.

임원면접에서는 다대다로 진행되었고 기본적인 공통 질문을 통해서 회사에 인재상에 부합하는지 역량을 가지고 있는지 를 평가했습니다. 

굉장히 일정이 빠르게 진행되어서 정신없이 준비했던것 같습니다. 

문제링크: https://www.acmicpc.net/problem/12886

체감 골3 이상이었던 bfs 문제 ㅠㅠ

접근방식

1. dp방식, bfs방식 등이 가능할 것 같았다. 

2. 만만한 bfs로 도전

만약 a, b, c의 총합이 3으로 딱 나눠떨어지지 않는다면 무조건 결과는 0이다. 

1000x1000x1000 배열을 생성하게 되면 메모리 초과이다. 

이때, 총합의 합이 같기 때문에 1000x1000만으로도 a,b,c의 값을 저장할 수 있다는 것을 파악해야 한다.

큐에 들어가는 값은 정렬을 하여서 사용한다.

그 이유는 중복을 방지하기 위함과 런타임에러(OutOfBounds)를 방지하기 위함

문제풀이 

1.  큐를 사용한 bfs 구현

2. y_ar과 x_ar를 통해서 현재 값을 기준으로 탐색해야 하는 값들을 도출

정답코드

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

int visited[1001][1001] = { 0, };
int a, b, c, d = 0;

int bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(a, b));
	visited[a][b] = 1;

	while (!que.empty()) {
		int ca = que.front().first;
		int cb = que.front().second;
		int cc = d - ca - cb;
		que.pop();

		if (ca == cb && ca == cc)
			return 1;

		int n_x[3] = { ca,ca,cb };
		int n_y[3] = { cb,cc,cc };

		for (int i = 0; i < 3; i++) {
			int na = n_x[i];
			int nb = n_y[i];
			if (na < nb)
				nb -= na, na += na;
			else if (na > nb)
				na -= nb, nb += nb;
			else
				continue;
			int nc = d - na - nb;

		
			int ra = min(min(na, nb), nc);
			int rb = max(max(na, nb), nc);

			if (visited[ra][rb] == 0) {
				visited[ra][rb] = 1;
				que.push(make_pair(ra, rb));
			}

		}


	}

	return 0;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> a >> b >> c;
	d = a + b + c;

	if ((a + b + c) % 3 != 0)
		cout << 0 << endl;
	else
		cout << bfs() << endl;
	

	return 0;
}

문제링크: https://www.acmicpc.net/problem/11286

우선순위 큐를 사용하여서 해결하는 문제

접근방식

1.  절댓값에 대한 순서를 우선순위 큐를 활용하여 해결하자!

문제풀이 

1.  pair형태의 우선순위 큐 생성

2. min-heap형태로 구성!

근데, "절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력" 하라는 조건이 있으니 두번째 원소값을 변형 하여서 구현하기

정답코드

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

priority_queue <pair<int, int>> que;
int n = 0;
int num = 0;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--) {
		cin >> num;
		if (num == 0) {
			if (que.size() == 0)
				cout << 0 << "\n";
			else {
				cout <<  que.top().first * que.top().second  << "\n";
				que.pop();
			}
		}
		else {
			if(num > 0)
				que.push(make_pair(-1 * abs(num),-1));
			else
				que.push(make_pair(-1 * abs(num), 1));
		}

	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/15924

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  모든 좌표에서 도달 가능한 좌표를 탐색

이때, dp에 값을 저장해두었다가 같은 좌표를 탐색할때는 곧바로 반환해주는 형태로 구현

정답코드

#include <iostream>

using namespace std;

int n, m;
char arr[3001][3001];
long long dp[3001][3001];
long long result = 0;

long long solved(int y, int x) {
	if (y == n && x == m)
		return 1;

	long long& ret = dp[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (arr[y][x] == 'B') {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else if (arr[y][x] == 'E') {
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
	}

	ret %= 1000000009;

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			result += solved(i, j);

	cout << result % 1000000009 << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/13703

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  높이 수면에 닿는 경우는 항상 배제시켜주고, 

시간이 다 될때 까지 수면에 닿지 않았다면 + 1 을 추가해주는 형태로 진행함

정답코드

#include <iostream>
using namespace std;

long long dp[64 * 2][64];
int n, k;

long long solved(int kk, int nn) {
	
	if (kk == 0)
		return 0;
	if (nn == 0)
		return 1;

	long long& ret = dp[kk][nn];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(kk-1, nn-1);
	ret += solved(kk+1, nn-1);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> k >> n;

	for (int i = 0; i < 64*2; i++)
		for (int j = 0; j < 64; j++)
			dp[i][j] = -1;

	cout << solved(k, n) << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1715

문제 접근에 대해서 이해하면 쉽게 구현한 문제이다.

우선, 그리디한 방식으로 문제를 도출할 수 있다는 것을 이해해야 한다!

접근방식

1. 생각해보면, 항상 작은수를 먼저 처리해주면 최소값이 도출이 된다는 것을 알수 있다.

2. 그렇다면 새로 추가되는 수는 어떻게 관리해주어야 할까? 

새로 수를 넣어줄때 마다 정렬을 해야하나? 

아니다!

그냥 편하게 우선순위 큐를 사용하면 될 일이다. 

자동으로 lgn번의 탐색으로 수를 정렬된 상태로 보관해주기 때문에

해당 문제에 가장 적합한 자료구조이다.

문제풀이 

1.  구현 자체는 너무나도 단순하다.

priority_queue를 사용하여 문제를 해결하자.

정답코드입니다.

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

int n = 0;
priority_queue <int> que;
long long result = 0;

int main() {
	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		que.push(temp * -1);
	}

	while (que.size() != 1) {

		int a = que.top() * -1;
		que.pop();
		int b = que.top() * -1;
		que.pop();

		result += (a + b);

		que.push( (a + b) * -1);


	}

	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1339

간만에 풀어보는 그리디 알고리즘!

접근방식

1. 일반적인 접근방식으로 숫자 자릿수가 큰 경우에 높은 숫자를 배정해주면 될거라고 생각함

ex) accc + bbb일때,

a가 9가 되어야 하지요!

2.  다만 자릿수가 동일한 경우에 우선순위 배정을 신경써주야 한다!

ex) abbb + acdd

이때, a =9 는 당연하고 c와 b 중에서 b에 8을 배정해야 하는 부분!

이부분을 처리하기 위해서, 각 자릿수를 더해주는 형식으로 진행했다.

a = 1000 + 1000 = 2000b = 111 c = 100d = 22

숫자가 더 큰 친구가 높은 우선순위에 속하도록 구현하면 끝!~

문제풀이 

1.  문제 접근 2번에 설명한 것처럼 구현을 진행함

이때, 내림차순으로 정렬을 진행해두어야 함

2. 정렬된 값들을 순서대로 탐색하며 수를 배정해줌으로서 문제 해결

정답코드입니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int arr[26] = { 0, };
int n = 0;
int result = 0;

bool cmp(int& a, int& b) {
	if (a > b)
		return true;
	else
		return false;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;

		int cnt = 1;
		for (int j = temp.size() - 1; j >= 0; j--) {
			arr[temp[j] - 'A'] += cnt;

			cnt *= 10;
		}
	}

	sort(arr, arr + 26, cmp);
	int cnt = 9;
	for (int i = 0; i < 26; i++) {
		if (arr[i] == 0)
			break;

		result += arr[i] * cnt;
		cnt--;
	}

	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/2758

Top-down 방식의 dp로 해결했습니다. 

접근방식

1. 문제를 보면서 일반적인 dfs로는 구현이 불가능한 것을 이해하였고, dp로 구현하기로 함

2.  top-down방식을 통해서 구현

문제풀이 

1.  일반적인 top-down방식으로 구현 

주의점은 숫자 범위때문에 long long으로 선언해야한다는점?

아래는 정답 코드

#include <iostream>
using namespace std;
int t;
int n, m;
long long dp[2001][11];

long long solved(int currentN, int currentM) {

	if (currentN == 1)
		return 1;

	long long& ret = dp[currentM][currentN];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = currentM/2; i >= 1; i--) {
		ret += solved(currentN - 1, i);
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n >> m;

		for (int i = 1; i <= 2000; i++)
			for (int j = 1; j <= 10; j++)
				dp[i][j] = -1;

		long long result = 0;
		for (int i = m; i >= 1; i--)
			result += solved(n, i);

		cout << result  << "\n";

	}


	return 0;
}