[210522] 2021 데브 카니발 후기

원티드에서 알고리즘 코딩테스트로 

일정 점수 이상 획득하는 참가자에게 뱃지를 부여하는 이벤트를 개최하였다.

https://www.wanted.co.kr/events/2021_dev_carnival

2021 Dev Carnival : 2021 데브 카니발

단, 뱃지는 2021년 8월 28일까지만 유효하다고 한다. 즉, 군인 신분인 나랑은 상관이 없다는 것..

이번 원티드 데브 카니발에 참가하는 기업이라고 한다. 생각보다 큰 회사들이 많이 보인다.

참가기업에 IT회사로 유명한 대기업들도 꽤 보인다.

따라서 이번 코딩테스트의 난이도는 꽤 높을 것으로 생각하고 응시하였다.

---

주의사항

부정행위 방지 시스템을 통한 운영을 위해 웹캠을 미리 준비해주시기 바랍니다.

• 시험을 시작하면 중간에 멈출 수 없습니다.
• 레퍼런스 사이트를 제외한 인터넷 검색, 외부 메신저 등의 사용은 불가합니다.
• 시험 환경 내 컴파일러 버전 확인 시 레퍼런스 사이트 링크를 확인할 수 있습니다.
• 시험시간 중 응시용 외 전자기기(컴퓨터, 태블릿, 스마트워치, 이어폰 등)는 사용할 수 없습니다.
• 시험 도중 화장실 사용은 불가하오니, 시험 이전에 다녀와 주시기 바랍니다.
• 모의테스트와는 다르게 본 시험에서는 테스트케이스 정답 여부가 표시되지 않고, 문제 정답 여부도 비공개이오니 참고해주시기 바랍니다.
• 외부 IDE (Visual studio, Vscode 등) 사용 가능
• 문제를 푸는 과정에서 종이와 필기구를 이용하는 것은 허용됩니다. 하지만 문제 내용 자체를 기록하는 것은 허용되지 않습니다.

주의사항이 잘 기억이 나지 않아, 필기구를 이용하지 않고 메모장을 이용하여 필기를 하였다.

---

문제 후기

3번 붙잡고 맞왜틀 해결해보려다가, 4번을 제출하지 못했다. 

문제 번호	Solvedac 예상 티어	사용 알고리즘	비고
1	Silver III	queue	요세푸스 문제와 유사함
2	Gold IV	BFS	문제조건 부족
3	Gold I ~ Platinum	bitmask + dp
4	? (골드 상위권 예상)	- (예상 정해: BFS)

---

1번은 백준의 요세푸스 문제와 거의 비슷했다. 다른 점이라면, 반드시 맨 처음 원소부터 push하면 안되고 K번째 원소부터 push해야 된다는 점.

 

처음엔 수학 공식을 세울 수 있어보여서 그렇게 해결해보려 하였으나,

queue를 이용하여 해결하면 무난하게 풀 수 있을 듯 하여

큐를 이용하여 해결하였다. 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 1001;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N, K, a[MAX], M;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> K;
	queue<pair<int, int>> q;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		if (i >= K) {
			q.push({ a[i], i });
		}
	}
	for (int i = 1; i < K; i++) {
		q.push({ a[i], i });
	}
	while (!q.empty()) {
		int n = q.front().first;
		int idx = q.front().second;
		q.pop();
		--n;
		if (!n) {
			cout << idx << " ";
		}
		else
			q.push({ n, idx });
	}
}

---

2번은 문제 조건이 조금 부족했다.

유닛이 도착지점 이외의 장소에서 서로 겹칠 수 있는지의 여부가 주어지지 않았다.

예를 들어 UU. 의 경우, .UU로 1초만에 이동할 수 있다면, 겹칠 수 있는 것이고 나는 이렇게 풀었다.

어차피 둘이 동시에 같은 방향으로 이동하고, 이동할 곳이 이동할 수 있는 곳이라면, 둘이 동시에 이동하므로 둘의 거리를 유지하면서 동시에 이동할 것이라 봤기 때문이다.

 

따라서 그냥 bfs를 구현하였는데, 유닛이 두 마리라서 visit배열을 삼차원으로 두어야 했다. visit[2][MAX][MAX]와 같이 두고 어떤 유닛인지에 따라 visit 여부를 결정지어야 했다. 

 

사실 정답 여부가 나오지 않아 정답인진 모르겠다. 근데 2번까진 거의 맞지 않을까 싶다. (일부 예외가 발생할 수 있음.)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 51;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
char a[MAX][MAX];
int X1, Y1, X2, Y2, N;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool visit[2][MAX][MAX];
bool flag[2];
int bfs(int x1, int y1, int x2, int y2) {
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push({ {0, 0}, { x1, y1} });
	q.push({ {0, 1}, { x2, y2} });
	visit[0][y1][x1] = true;
	visit[1][y2][x2] = true;
	while (!q.empty()) {
		int time = q.front().first.first;
		int type = q.front().first.second;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();
		if (a[y][x] == 'D') {
			flag[type] = true;
			if (flag[0] && flag[1])
				return time;
			continue;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				if (!visit[type][ny][nx] && a[ny][nx] != 'X') {
					visit[type][ny][nx] = true;
					q.push({ {time + 1 , type}, {nx, ny} });
				}
			}
		}
	}
	return -1;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			a[i][j] = s[j];
			if (a[i][j] == 'X') {
				visit[0][i][j] = true;
				visit[1][i][j] = true;
			}
		}
	}
	cin >> Y1 >> X1 >> Y2 >> X2;
	cout << bfs(X1, Y1, X2, Y2) << "\n";
}

---

3번은 연속된 7일 내에 K일 이상 결근을 하지 않는 경우를 구하는 문제여서 dp인데,

일반적인 dp로 접근한다면 상태에 따라 중복된 메모이제이션이 리턴될 수 있어 문제가 발생한다.

따라서 상태를 저장하는 비트마스크를 이용하여 dp를 하였느데,

그래도 일부 경우가 의도치 않은 메모이제이션이 발생하여 계속 수정해보려다가 실패하였다...

 

아래 코드는 테스트케이스 일부가 맞지 않는 코드이다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 1001;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
ll N, K, d[MAX][1 << 7];
bool visit[MAX];
ll dp(ll cur, ll day) {
	int cnt = 0;
	for (int i = 0; i < 7; i++) {
		if ((day & (1LL << i)))
			cnt++;
	}
	if (cnt >= K)
		return 0;
	if (cur == N)
		return cnt < K ? 1 : 0;
	ll& ret = d[cur][day];
	if (ret != -1)
		return ret;
	ret = dp(cur + 1, day);
	ret += dp(cur + 1, day | (1LL << (cur % 7)));
	return ret % MOD;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> K;
	memset(d, -1, sizeof(d));
	cout << dp(0, 0) << "\n";
}

---

4번은 한번 이동할 때마다 방향이 바뀌는 bfs 문제였다. 

어떤 방부터 입장해야 최대한 많은 방을 탐방할 수 있는지 구하는 문제였는데,

3번에 몰두하다보니 4번은 제대로 해결하지 못했다.

 

범위가 작다보니 아마 bfs로 돌리면 되지 않을까 싶다. 

이 때, 정방향과 역방향을 체크해두어 인접리스트에서 정방향으로 갈지, 역방향으로 갈지 확인을 해야된다는 점,

그리고 정방향 visit 배열과 역방향 visit 배열을 만들어둬야된다는 점에 주의하자.

 

사실 그 이후로는 안해봤다. 그냥 3번 빨리 풀고 4번 풀자는 생각이었다가,

3번을 맞추지 못하고 4시까지 끙끙댔다.

4번을 풀 걸 그랬나... 근데 4번도 꽤 난이도가 있어보인다.

---

풀이가 나오면 좋을텐데 나올지 모르겠다.

제일 궁금한건 3번을 도대체 어떻게 해결하는 것인지이다.

 

이번 대회를 하면서 느낀 점은 역시 그래프탐색, 구현이 중요한 포인트라는 것이다.

앞으로 열심히 해야겠다 ㅎㅎ

 

(21.05.30 추가)

5월 28일에 금손 뱃지를 받았다는 메일이 왔다~

뱃지가 8월에 소멸된다니 ㅠㅠ 군인 신분이라 뱃지의 의미는 없을 듯하다.

사실 금손은 커녕 은손도 못받을 줄 알았는데, 기대치 못한 대회에서 좋은 결과를 받아 기분이 굉장히 좋았다.

 

더 노력해서 더 좋은 실력자가 되고싶다.

 

풀이가 너무 궁금한데... 풀이 없는 건 좀 아쉽다.