2022 KAKAO 블라인드 채용 1차 코딩테스트 후기

 

2022 카카오 블라인드 채용 1차 코딩테스트에 참가했다. 

 

정확히 2시간 30분 소모했고, 그중 절반을 7번에 쏟아부었다.

구현과 완전 탐색 문제가 조금 많기도 하고, 6번이 웰논이라 개인적으로 지난여름 인턴십 코딩테스트 문제가 조금 더 괜찮았고 난이도도 높은 느낌이다. 작년 블라인드를 경험해보지도 못했고, 너무 블라인드 코테에 대한 악명을 많이 들어서인지 기대만큼은 아니었다. 

문제나 코드를 업로드할 수 없어 간단하게 과정이나 풀이만 설명하겠다. 

 

1.

유형 : 구현 / 문자열 / set 

예상 난이도 : Silver V ~ Silver IV

 

제한이 작고 간선이 중복될 수 있으므로, set배열을 선언해 각 문자열마다 자신에게 들어오는 문자열을 넣어주었다. 

 

2. 

유형 : 문자열 / sqrt(n) 소수 판별

예상 난이도 : Silver V ~ Silver IV

 

문자열을 바꾼 후 소수가 몇 개 존재하는지를 판별하면 된다. 만들어진 수에서 0을 기준으로 모두 분리했을 때 각 수 별로 소수인지 체크하면 된다. 제한이 작기 때문에 2 ~ sqrt(n)까지 직접 나눠보는 소수 판별법을 사용해도 충분하다.  

 

3. 

유형 : 문자열 / 파싱 / map

예상 난이도 : Silver IV ~ Silver III

 

코테에서 매우 자주 나오는 것 같은, 시간이 주어지는 문자열 파싱 문제이다. IN인 경우엔 map에 시간을 저장하고, OUT인 경우엔 map에 저장된 시간과의 차를 이용하여 더해준다. 

 

4. 

유형 : 완전 탐색 & 백트래킹

예상 난이도 : Silver III ~ Silver II

 

다른 사람들의 풀이를 들으니 비트마스킹을 쓴 사람이 많은 것 같다.

사실 n이 최대 10이므로 모든 경우를 고려해도 $_{11}H_{10} = _{20}C_{10}$, 대략 20만 가지의 경우밖에 나오지 않는다. 따라서 완전 탐색과 백트래킹을 이용해서 화살을 쏘는 모든 경우를 다 구한다. 

현재 경우가 답이 되는지를 판단하는 시간까지 고려하면 대충 200만 ~ 600만 번의 연산이 필요하다. 

 

5. 

유형 : 완전 탐색 & 백트래킹

예상 난이도 : Gold V ~ Gold IV

 

완탐의 연속이다. 이 문제 또한 비트마스킹, bfs 등 다양한 풀이가 나왔는데, 마찬가지로 제한이 매우 작아서 완전 탐색으로도 충분히 해결 가능하다. 

방문할 수 있는 점들은 지금까지 방문한 점들의 자식 정점이면서 아직 방문하지 않은 정점이다. 이 중 양이 잡아먹히지 않으면서 갈 수 있는 모든 경우를 다 고려한다. 새로운 점을 방문한다면 추가로 방문할 수 있는 점은 최대 2개씩만 늘어나기 때문에 시간 내에 충분히 돌아간다.

 

6. 

유형 : 누적 합

예상 난이도 : Gold III ~ Gold II

 

웰논 문제임을 풀이 시간으로 증명하고 있다. 1 ~ 7번 문제 중에서 가장 시간이 적게 걸렸다.

2차원에서 어떤 직사각형 범위의 칸에 값을 더해주는 쿼리는 직사각형의 네 꼭짓점 부분에만 연산을 해준 후 마지막에 한번 훑어서 완성할 수 있다. 

정확히는 (x1, y1) ~ (x2, y2)에 값을 더해줄 때, (x1, y1)은 더해주고 (x1, y2+1) & (x2+1, y1)은 빼주고 (x2+1, y2+1)에 더해준 다음 왼쪽 위부터 오른쪽 아래로 누적합을 계산해주면 된다. 

자세한 설명은 https://hellogaon.tistory.com/75 의 I. 색종이와 쿼리의 풀이 1단계에 잘 나와있다.  

 

7. 

유형 : 게임이론 / 재귀

예상 난이도 : Platinum V ~ Platinum IV

 

게임이론이 코테에 나올 줄은 몰랐다.... 문제를 잘못 이해해서 푸는데 꽤 오랜 시간이 걸렸다. 

A를 기준으로 이기는 경우는 최대한 빠르게, 지는 경우엔 최대한 느리게 끝나야 하므로 pair를 반환하는 재귀를 사용했다. first는 최소, second는 최대가 되도록 유지했다.