SWMaestro 14기 합격 회고

 기술 포스트는 영어 위주로 작성하려 했으나, 이후 기수들이나 후배들에게 조금이나마 도움이 될 수 있을까 싶어 합격 회고는 한글로 작성한다.

 

SWMaestro는 BOB와 함께 신입생 때부터 선배들에게 들어왔던 인재 양성 과정이다. 저번 기수의 지원기간에는 알고리즘 능력도, 프로젝트의 질도 턱없이 모자랐기에 지원서를 쓰던 도중 14기를 기약했던 기억이 난다. 올해는 프로젝트를 숙지하고 면접을 견고하게 준비하면 합격하기에 최적의 시기라고 생각했다.

 

1차 코딩 테스트

Programmers에서 2시간동안 시험을 치뤘는데, 서버가 터진건지 1차는 무효가 됐다. 알고리즘 4문제 + SQL 1문제 구성이었다.

 

간단한 문제 유형과 백준 예상 티어, C++ pseudocode 를 적어본다.

 

1번 : 그냥 단순구현 (실2)

맨 위에서 쏟아지는 눈이 index 별 정해진 양의 값을 초과하면 밑으로 흘러내린다. 각 index에 최종적으로 남은 눈의 벡터를 리턴하면 된다.

snow : 처음 흘러내리는 눈
max : 구간별 최대 눈
now : 구간별 현재 눈

for(int i=0; i<now.size(); i++){
        now[i] += snow;
        if(now[i] > max[i]){
            snow = now[i] - max[i];
            now[i] = max[i];
        }
        else snow = 0;
    }

2번 : 빡구현 (골2)

좌표평면 위의 선분들이 주어지는데, 만들어지는 십자가 (중점 기준 좌우상하의 길이가 모두 같은) 중 가장 큰 것을 출력하는 문제였다. 선분이 끝나는 지점에서 다른 선분과 교차하면 안된다.

평면의 크기가 작아 모든 점을 Brute Force해도 무방했으나, DP + BFS로 Optimization이 가능할 듯 하긴 하다.

vector<vector<int>> lines : 좌표평면의 선분. 0,1,2,3 인덱스는 각각 시작점과 끝점의 x, y
int arr[51][51][4] : 좌표평면의 점 + 상하좌우 이어지는 선이 있는지

for(auto i : lines){
	X축 평행인지, Y축 평행인지 처리
    선분에 있는 점들로 arr boolean 값 갱신
}

모든 점 완전탐색

for(int i = 0; i < 51; i++){
	for(int k = 0; k < 51; k++){
    	4방향 BFS
        끝나면 max값 갱신
    }
}

3번 : 백트래킹 / 조합 구현 (골3)

도미노들이 늘여져 있다. 도미노가 쓰러지면 그 도미노의 위치 + 도미노의 길이 보다 적은 도미노들은 모두 쓰러진다. 이 중 n 개를 골라 쓰러지는 개수를 최소로 하려 한다.

원래는 백트래킹이나 메모이제이션을 생각하여 풀이했겠지만, 도미노의 최대 개수가 20개여서 20C10의 값을 계산한 후 그냥 next_permutation으로 구현했다.

point : 도미노 위치
    length : 도미노 길이
    n : 없애는 도미노 개수

    vector<int>v : next_permutation 위해
    for(int i=0; i<n; i++){
        v.push_back(0);
    }
    for(int i=0; i<point.size()-n; i++){
        v.push_back(1);
    }

    do{
        for(int i=v.size()-1; i>=0; i--){
            if(v[i]){
                point.erase(point.begin() + i);
            }
        }
        그냥 쓰러지는 개수 구현 , min 값 갱신
    }while(next_permutation(all(v)));

4번 : DFS (플5?)

A~D를 가질 수 있는 젓가락 쌍들이 있는데, 양옆의 젓가락을 하나씩 골라 바꿔 모든 젓가락의 쌍들을 맞춰야 한다. 최소 이동수

Ad-Hoc인가 싶어 종이에 조합을 써보면 끄적이다 끝났는데 나중에 생각해보니 DFS였던 것 같다. 근데 풀이가 생각이 안나니 어차피 못풀었을 것 같다. 헤맸던 느낌이 예전 ICPC의 Jars에서 머리 박았던 때가 생각났다.

 

5번 SQL

SQL쪽은 알고 있던 것에 더해 딱히 준비한게 없었다. String parsing 등을 사용해야 했던 문제인 것 같은데 아무튼 어려워서 바로 넘겼다.

 

2차 코딩테스트

똑같은 방식으로 진행되었으며, 서버 폭파는 없었다.

1번 : 구현 (실4)

화살표들이 늘여져있고 양방향인지, 좌우 단뱡향인지와 길이를 구하면 된다. 

s : 화살표 String

for(int i=0; i<s.size(); i++){
	if(s[i]=='<'){
    	int tmp = 0;
        for(int k=i+1; k<s.size(); k++){
        	if(s[k]=='-'){
            	tmp++;
            }
            else vector.push(~)
            break;
            ~
        }
    }
    else ~ '-', '>' 처리
}

2번 : DP (골1)

이동하며 연료를 소모하는데, 중간 지점들의 주유소에서 1초에 x[i]만큼 연료를 충전할 수 있다. 목적지까지 가는 최소시간.

엣지케이스 처리를 못해 부분점수를 받았다. 개인적으로 이후 나올 다익 + DP인 4번문제보다 애를 먹었던 문제이다.

vector<int>v : 구간당 1초에 충전 가능한 연료량
a : 현재 연료량
pair<int,int> dp[50] : <도달한 시간, 연료량> memoization

dp[0] = {0, a};
for(int i=0; i<v.size(); i++){
	if(i에 도달 가능){
    	dp 갱신
    }
}
// 한 지점에서 필요량보다 많이 충전하는 케이스 처리 필요

3번 : Queue (골4)

회전문을 통해 들어오는 사람들을 반대편으로 내보낸다. 사람이 들어간 시점 이후 x만큼 회전문이 움직이며, 회전 중 사람이 들어와도 회전량이 갱신되지 않는다. 회전문에 남아있는 사람들 return.

queue<pair<int, int>> q; // <남은 회전수, 시간>
    vector<int> v; // <들어가는 시간
    bool check, int left; // 회전중인지, 남은 회전수

    for (auto i : v) {
        if (check) {
            남은 회전 시키기 로직
            회전 남을시 ~
            check, left 갱신
        }
    }

4번 : Dijkstra + DP (플5)

전형적인 다익스트라 최단거리 이동 문제인데, 이동하는 사람이 자차가 있다. 주차장이 있는 곳에는 차를 세울 수 있으나, 없으면 택시를 타야 하고, 가는 비용이 X3이 된다. 해당 지역에 주차를 했을시 / 주변에 주차를 했을시를 배열로 동적 관리해줘야 한다. 그래프는 Floyd-Warshall 로도 가능할듯 싶다.

    bool arr[50]; // 주차 가능 여부
    vector<pair<int, int>>v[50]; // 간선 방향, 길이

    priority_queue<pair<int, int>>pq;
    거리 초기세팅
    while (!pq.empty()) {
        다익스트라 구현
            if (pq.front().second) {
                주차 가능시 처리 + memoization
            }
            else
                주차 불가능시 처리
    }

5번 SQL

Union 사용하여 테이블 출력하는 쉬운 문제였음

 

1 / 2 차 코딩테스트 모두 구현이 쉽지 않고 시간이 빡빡한 느낌이었다. 대충 2솔정도가 컷인듯 하다. 취준 코테를 준비하며 필수 유형들이 학습이 되어 있으면 코테 통과는 쉬울 듯 하다. 멘토님께 듣기로는 2차 코테에서 대부분의 연수생이 1,5번만 풀고 나머지는 틀렸다고 한다. 코테에 대한 면접 질문은 이후 서술

 

심층면접