[삼성코테] 24년 하반기 삼성전자 3급 공채 코딩테스트 후기(오전)

 오늘 동탄DS에듀센터에서 삼성 3급 공채 코딩테스트를 보고 왔다!(직무는 비밀이다)

https://naver.me/5wmPuRrY

DS 에듀센터 동탄 : 네이버

 

 이곳이 나에게는 익숙한 장소였는데, 사실 DS에듀센터는 삼성전자 대학생 대외활동인 "삼성전자 샤이닝스타"의 활동 중 하나로 방문했기 때문이다! 옛날이나 지금이나 아주 시설이 좋았다.

 

 시험장에 들어가서 가장 놀랐던 점은, 모니터가 무려 34인치 삼성 커브드 오디세이 였다.. 100만원 이상의 값을 자랑하는 모니터인데, 이게 시험장 자리마다 있었다는게 놀랍다. 이걸로 게임하면 얼마나 재밌을까.. 덕분에 널찍한 화면에서 마치 더블모니터를 쓰는 것처럼 왼쪽에는 문제 띄우고 오른쪽에는 Visual Studio IDE 띄워서 쉽게 코딩할 수 있었다.

 

 문제는 저작권 서약때문에 자세히는 알려줄 수 없다. 나중에 코드트리에 올라올 것이니 참고하면 될 것 같다.(자세한 문제가 나오면 글을 수정하겠다.) 하지만 한 마디만 하자면 지금까지 나온 기출문제보다 "훨씬" 어려웠다. 1번이 플레티넘4~5 수준의 빡구현이 나오고, 2번은 간단해보이지만 시간초과가 나기 쉬운 문제이므로 적절한 아키텍쳐 구상이 필요한 문제이다.

 

 음..그래도 하나의 힌트를 주자면, 백준 삼성 역량테스트 문제집에서 어려운 구현 문제에 속하는 "큐빙" 문제를 풀어보면 도움이 될 것 같다. 

 

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

 

 삼성 역량테스트 문제집중 가장 "복잡한" 구현량을 자랑하는 문제인데, 이번 1번 문제도 그렇게 나와버렸다.. 이렇게 고여버리면 내년 코딩테스트는 어떤 수준일지 감도 안잡힌다. 이번에 꼭 합격해야하는 이유 중 하나이다. 내년에도 빡구현하고싶지않다 ㅠㅠ

 

1번을 푸는데만 3시간 반이 걸려서, 2번은 그냥 포기했다. 부디 이번엔 합격해서 최종면접까지 가고싶다.

 

 +추가

 

10월 14일자로 코드트리에 문제가 올라왔다! 실제 시험문제가 아니라 코드트리에서 제공하는 문제임을 명심하고 1번만 풀어보자.

 

https://www.codetree.ai/training-field/frequent-problems/problems/escape-unknown-space/description?page=1&pageSize=5

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 1. 한번도 겪어보지 못했던 "3차원" BFS

 

 

 이 문제가 신선한 점은, 일단 "미지의 공간"의 바닥으로 향해야 한다는 점이다. 그러기 위해서는, 미지의 공간에서  하나의 탈출구까지의 "최단 거리"를 구해야 하고, 그 의미는 BFS를 해야한다는 것이다.(여기까지는 그동안의 문제들과 유사하다.)

 

 그러나 심각한 점은, 미지의 공간이 큐브 형태의 3차원이라는 것이다! 그렇다면 즉, 우리는 3차원 정육면체 평면에 대하여 BFS를 적용해야 한다. 필자는 지금까지 많은 백준, 프로그래머스, 코드트리 문제를 풀어왔지만, 3차원 BFS를 하는 문제는 난생 처음이다. 정말 신선한 문제라고 할 수 있다. 우선 예제의 그림을 그려가며 천천히 진행해보자.

 

 

 정육면체의 윗면에서 출구로 이동해야 하는데, 이렇게 되면 윗면에서 "이탈" 했다면 다른 면의 맵으로 이동할 수 있어야 한다. 따라서 정육면체 전개도를 다음과 같이 그려보면 조금더 쉽게 문제풀이를 할 수 있다.

 

 이제 슬슬 어떻게 문제를 풀어야할지 짐작이 온다. 바로 한 면의 "맵"에서 이탈했을 때, 다른 쪽의 맵으로 이동하면서 BFS를 하도록 구성하는, 즉 3차원 형태의 배열과, 3차원(map, y, x) 형태의 queue를 설정해야 한다는 것이다. BFS부분만 생각하면 다음과 같다.

 

typedef struct cube {
	int mp, y, x;
}Cube;

bool is_out(int ny, int nx, int _size) {
	if (ny < 0 || ny >= _size || nx < 0 || nx >= _size) return true;
	return false;
}

int m;
pii man; // 윗면 남자의 y,x 좌표
const int dy[] = { 0, 0, 1, -1 }; // 동서남북
const int dx[] = { 1, -1, 0, 0 };
int cube_land[5][24][24];

Cube next_map(int mp, int y, int x) {
	// ???
}

void cube_bfs() {
	int cube_visited[5][24][24]; // {0,1,2,3,4} <- 위 동 서 남 북
	memset(cube_visited, -1, sizeof(cube_visited));
	queue<Cube> q; // {mp, y, x}
	cube_visited[0][man.first][man.second] = 0;
	q.push({ 0, man.first, man.second });
	while (q.size()) {
		Cube a = q.front(); q.pop();
		int mp = a.mp, y = a.y, x = a.x;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i], nx = x + dx[i];
			if (is_out(ny, nx, m)) {
				Cube next_a = next_map(mp, ny, nx);
				int nmp = next_a.mp, ny = next_a.y, nx = next_a.x;
                		if (nmp == -1) continue;
				if (cube_land[nmp][ny][nx] || cube_visited[nmp][ny][nx] == -1) continue;
				cube_visited[nmp][ny][nx] = cube_visited[mp][y][x] + 1;
				q.push({ nmp, ny, nx });
			}
			else {
				if (cube_land[mp][ny][nx] || cube_visited[mp][ny][nx] == -1) continue;
				cube_visited[mp][ny][nx] = cube_visited[mp][y][x] + 1;
				q.push({ mp,ny,nx });
			}
		}
	}
}

 

 여기에서 next_map 함수만 완성시켜주면 3차원 BFS 완성이다. 위 그림을 다시 한 번 보자.

 

 여기에서 차근차근 생각해보자. 편의상 위, 동, 서, 남, 북 그래프라고 표현하겠다.

 

1. 위쪽 그래프에서
   1. y<0이 되었을 때 : 북쪽 그래프의 위쪽(y==0)
   2. y>=m이 되었을 때 : 남쪽 그래프의 위쪽
   3. x<0이 되었을 때 : 서쪽 그래프의 위쪽
   4. x>=m이 되었을 때 : 동쪽 그래프의 위쪽
2. 남쪽 그래프에서
   1. y<0일 때 : 위쪽 그래프의 아래쪽(y == m-1)
   2. y>=m일 때 : 못 감(exit)
   3. x<0일 때 : 서쪽 그래프의 오른쪽(x == m-1)
   4. x>=m일 때 : 동쪽 그래프의 서쪽(x == 0)

 나머지 3, 4, 5번의 경우는 생략한다. 즉 위, 동, 서, 남, 북 그래프에서 이탈하였을 때 다음 그래프로 적절히 이동하도록 해주는 코드를   "노가다"로 작성해주면 되는 것이다.

 

 그럼 이에 해당하는 로직을 작성해보자. 작성하다보면 규칙성이 보인다.

Cube next_map(int mp, int y, int x) {
	int nmp = -1, ny = -1, nx = -1;
	if (mp == 0) { // 위쪽 그래프
		if (y < 0) { // 북쪽 그래프의 위쪽
			nmp = 4; ny = 0; nx = m - 1 - x;
		}
		if (y >= m) { // 남쪽 그래프의 위쪽
			nmp = 3; ny = 0; nx = x;
		}
		if (x < 0) { // 서쪽 그래프의 위쪽
			nmp = 2; ny = 0; nx = y;
		}
		if (x >= m) { // 동쪽 그래프의 위쪽
			nmp = 1; ny = 0; nx = m - 1 - y;
		}
	}
	if (mp == 1) { // 동쪽 그래프
		if (y < 0) { // 위쪽 그래프의 오른쪽
			nmp = 0; ny = m - 1 - x; nx = m - 1;
		}
		if (y >= m) { // 못 감.
			nmp = -1;
		}
		if (x < 0) { // 남쪽 그래프의 오른쪽
			nmp = 3; ny = y; nx = m - 1;
		}
		if (x >= m) { // 북쪽 그래프의 왼쪽
			nmp = 4; ny = y; nx = 0;
		}
	}
	if (mp == 2) { // 서쪽 그래프
		if (y < 0) { // 위쪽 그래프의 왼쪽
			nmp = 0; ny = x; nx = 0;
		}
		if (y >= m) { // 못 감.
			nmp = -1;
		}
		if (x < 0) { // 북쪽 그래프의 오른쪽
			nmp = 4; ny = y; nx = m - 1;
		}
		if (x >= m) { // 남쪽 그래프의 왼쪽
			nmp = 3; ny = y; nx = 0;
		}
	}
	if (mp == 3) { // 남쪽 그래프
		if (y < 0) { // 위쪽 그래프의 아래쪽
			nmp = 0; ny = m - 1; nx = x;
		}
		if (y >= m) { // 못 감.
			nmp = -1;
		}
		if (x < 0) { // 서쪽 그래프의 오른쪽
			nmp = 2; ny = y; nx = m - 1;
		}
		if (x >= m) { // 동쪽 그래프의 왼쪽
			nmp = 1; ny = y; nx = 0;
		}
	}
	if (mp == 4) { // 북쪽 그래프
		if (y < 0) { // 위쪽 그래프의 위쪽
			nmp = 0; ny = 0; nx = m - 1 - x;
		}
		if (y >= m) { // 못 감.
			nmp = -1;
		}
		if (x < 0) { // 동쪽 그래프의 오른쪽
			nmp = 1; ny = y; nx = m - 1;
		}
		if (x >= m) { // 서쪽 그래프의 왼쪽
			nmp = 2; ny = y; nx = 0;
		}
	}
	return { nmp, ny, nx };
}

 

 여기까지 풀었다면 "난생 처음 보는" 3차원 BFS를 푸는 것에 성공했다. 이제 남은 것은 탈출구를 2차원 LAND와 연결하고 무사히 탈출하는 경로를 찾아주면 된다. 이는 간단한 2차원 BFS로 구할 수 있다. 이후 코드는 생략하겠다.