2022 그렙 개발자 채용 챌린지 후기
지원 분야는 "웹백엔드 프로젝트 기반 학습 콘텐츠 제작자" 였다.
"알고리즘 & 코딩테스트 문제 출제자" 분야도 있었지만 내가 아직 그 정도의 실력이 아니라 생각하여 지원하지는 않았다.
무려 4시간이나 주어지는 코딩테스트였다. 알고리즘 4문제 + SQL 2문제가 나왔다.
최근 본 코딩 테스트 중에 가장 문제 퀄리티가 좋은 것 같았다.
최종 결과는 4/6 문제를 2시간 남기고 풀었다. 알고리즘 문제는 다 맞췄다!
문제
1번 문제는 전광판 구현이었다. 여러 풀이가 있을 수 있지만 나는 덱을 이용하여 풀었다. 전광판의 이동은 popleft()와 append()로 구현이 가능했다. 숫자도 작아서 특별한 구현 없이 돌리는 것 만으로도 통과가 가능했다. 다만 문제 조건을 잘 안 읽고 제출했다가 한번 틀렸다.
2번 문제는 딱 봐도 DP 문제였다. 하지만 내가 제일 약한 부분이 DP라서 DP말고 다른 풀이를 이용해보기로 했다. 자세히 보니 문제의 조건이 매우 작아 다른 풀이로도 풀릴 것 같았다. 그래서 백트래킹으로 풀었는데 여기에 해당 위치기준 최솟값인가만 더해주면 그게 DP였다. 끝나고 보니 약간 아쉬운 풀이였다. 그렇지만 시간은 넉넉하게 통과해서 당시에는 그냥 넘어갔다.
3번 문제는 문자열 / 구현 문제였다. 맨 처음 보자마자 시간복잡도 따위는 생각하지도 않았다. 보통 이런 문제들은 구현만 제대로 했다면 시간 초과는 발생하지 않을 것이라 생각했기 때문에 수많은 중첩의 for문을 짜다가 꼬여서 때려치고 다시 적고의 반복이 시작되었다. 그렇게 처음으로 구현한 코드를 제출해보니 6000ms를 찍더니 40점에 걸치고 말았다. 이게 아닌가 싶어서 KMP 알고리즘 짜논 것도 가져와서 해보고 KMP 알고리즘에서 pi 구하는 과정에 힌트가 있지 않을까? 했다가 시간이 더 오래걸리길래 코드 싹다 지우고 4번문제로 넘어갔었다. 4번 문제 풀고 난이도 순으로 배치 되어 있다면 3번은 절대 고급 알고리즘이 들어가지 않는다라고 생각하고 최적화에 신경써서 완전탐색을 돌렸다. 사소한 차이임에도 하나는 통과되었고 하나는 70점이 나왔다. 생각보다 구현력이 중요한 문제였던 것 같다.
4번 문제는 백준의 N-Queen 문제랑 비슷한데 이것이 다른 형태의 판에서 일어나는 것이었다. 움직이는 것만 보면 룩이 아니라 퀸인데 룩이라 해서 조금 웃긴 문제였다. 크기와 개수가 그리 많지 않았으므로 맨 처음에는 점화식을 찾는 것을 생각 했었다. 하지만 DP에 약하니 DP는 넘기고 구현해서 풀어보려 했다. 진짜 한 10분 동안 생각만 했었다. 코드 한줄도 적지 못하고.. 가로줄 세로줄 방문처리가 아닌 대각선 방문처리를 이용한 백트래킹으로 풀어보려 했고, 중요한 것은 어떤 위치가 어떤 대각선을 처리하는 지를 구현하는 것이었다. bfs를 통해서 판을 구현해주었고, 1부터 끝까지 단순 백트래킹을 돌렸다. 솔직히 맞출 줄 몰랐다. 시간복잡도를 낭비하지는 않았지만 그렇게 최적화를 하지도 않았는데 풀려서 조금 놀랐던 문제였던 것 같다.
느낀 점
DP에 너무 약하다. 실버 수준의 DP는 어찌어찌 할 수 있는데 골드 난이도의 DP 혹은 체감상 그런 경우 쭈글이가 되어버린다. 다른 문제면 그나마 괜찮은데 DP는 손도 안가서 더욱 문제인 것 같다.
최근 엄청 많은 알고리즘을 공부하였고 코딩 테스트에서는 풀 일 없을 그런 알고리즘도 많이 공부하였다. 3번 문제에서 KMP를 떠올린 것은 오버킬이었던 것 같다.
생각보다 시간이 오래 걸린 것 같다. 알고리즘 4문제 풀기까지 2시간이나 걸렸는데 3번 삽질만 안했어도 1시간 반이면 충분 했을 것 같다.
내일부턴 진짜로 SQL 공부할 것이다. 그리고 JS도!