2022 카카오 채용 연계형 인턴십 코딩테스트 회고

카카오 공채와의 인연

2019년 말 처음으로 소프트웨어 개발자가 되고 싶다는 막연함 꿈을 갖게 되었다. 카카오는 어떤 코딩문제로 지원자들을 평가하는지 알고 싶어 지원했던 첫 번째 코딩테스트에서 든 생각은 '이거 어떻게 풀어?'였다.

이후 학교에서 관련 강의를 듣고 알고리즘 기본 개념을 갖춘 상태에서 지원한 2020년 공채에서도 너무나도 당연하게 나는 추풍낙옆처럼 탈락해버렸다. 그때는 '에이, 아직 제대로 공부하지 않아서 그래. 문제도 많이 안풀었잖아. 내년에는 붙겠지.'라는 안일한 생각으로 가볍게 넘겼으며, 안일한 마음에 절실하게 알고리즘을 공부하지 않았다.

2021년 카카오 공채를 볼 당시에는 한창 프로그래머스 데브코스 1기 과정에서 프로젝트를 진행하고 있던 기간이었다. 그 때도 나는 '개발 공부가 바쁘니까...알고리즘은 조금 나중에...'라는 생각으로 또 알고리즘 학습을 미뤘다.

2019년은 호기심으로, 2020년은 안일함으로, 2021년은 자기합리화로 그렇게 삼 년 동안 카카오는 나를 지나쳐갔다. 아니, 내가 카카오를 붙잡지 못했다. 이 정신머리 없는 녀석.

늦었다고 생각할 때가 정말 늦은 것이다

뒤늦게 정신을 차린 나는 2022년 1월 8일부터 부터 5월6일까지 스터디원을 구해 알고리즘 스터디를 진행했다. 이 때는 꽤 커리큘럼도 잘 짰고, 열심히 했기에 실력이 빨리 느는 것이 느껴졌다. 그렇게 2022년 카카오 채용연계형 인턴십에 자신있게 지원했다. 하지만 그 결과는 많이 아쉬웠다.

문제풀이 접근법 복기

결과는 아쉬웠지만, 아쉬운 대로 시험 당일 문제 해결을 위해 내가 어떤 생각을 했는지 기록하려 한다.

문제 풀이 시도 순서는 1,2,5,4,3이었다. 문제들을 빠르게 훑어보면서 내가 풀 만한 문제를 먼저 풀이하기로 결정했다. 1번과 2번은 완벽하게 풀었지만, 5번은 효율성 테스트를 통과하지 못했으며, 3,4번은 테스트 케이스도 통과하지 못했다. 그래도 풀 수 있었던 문제들에 대한 복기를 진행해 보려고 한다.

1번

key, value 쌍을 이용하여 성격유형이 얻은 점수를 조건에 따라 잘 매칭하면 되는 문제였다. 단순한 구현문제였으며, 내가 소비한 풀이시간은 약 15분 정도였다. 이 때까지는 굉장히 기분이 좋았다. 물론 다음 문제부터는 텐션이 급속도로 낮아지고, 심장이 두근거리고, 초조해지기 시작했다.

2번

두 개의 큐 queue1, queue2가 주어졌으며, 각 큐에서 적당히 값을 옮겨서 각 큐 원소들의 합이 같도록 만드는 최소 수행횟수를 리턴하는 문제였다.

이 문제는 간단해보였지만, 실제 문제풀이의 발상은 그리 쉽게 떠오르지 않았다. 문제풀이 발상을 떠올리기 위해 시간을 꽤 많이 사용했던 문제였다.

문제를 풀면서 생각했던 접근법들은 다음과 같았다.

• DFS를 이용한 완전탐색일까? -> 그렇다기엔 기저조건이 불명확한데
• DP일까? -> 이전 수행이 다음 수행에 영향을 주기는 하지만, 이전 수행 값이 최적의 값인지에 대한 보장이 없다.
• 투포인터?....응?

투포인터가 내게는 적절한 접근법으로 다가왔다. 종이에 그림을 그려보면서 큐1과 큐2를 붙여놓고 최적의 투포인터 위치를 계산해보았다. 다행히 접근법이 맞는 듯 했다.

큐1+큐2, 큐2+큐1의 두 가지 경우에서 투 포인터 알고리즘을 적용하여 right와 left의 차를 구했고, 두 값 중 작은 값을 답으로 채택했다.

내 알고리즘에서 right 포인터는 뒤에 붙은 큐에서 dequeue를 하는 횟수를 의미했고, left 포인터는 앞에 붙은 큐에서 dequeue를 하는 횟수였다.

3번

못 풀고 넘겼다. 접근법이 도저히 생각이 나지 않았다. 다른 후기들에서는 DP로 풀 수 있다고 한다.

4번

첫 시도에서 시간이 오래 걸릴 것 같아 5번을 먼저 풀어보고 다시 돌아오기로 했다. 5번을 어느 정도 풀이 하고 돌아와서 보니 그래프 알고리즘 문제같았다.

내가 그간 공부했던 그래프 알고리즘은

• 다익스트라
• 플로이드 워셜
• 크루스칼
  이렇게 세 가지였지만, 학습 당시 어려워서 어영부영 확인하고 추가 학습을 통해 보완하지 않았기에 너무나도 헤맸다. 결국 문제는 풀지 못하고 남은 한 시간 반의 시간을 다 써버리고 말았다. 다른 후기들을 찾아보니, 다익스트라로도 해결할 수 있고, 크루스칼 알고리즘을 통해서
  최소 신장트리를 찾은 다음 DFS를 통해 탐색하는 방식으로도 풀 수 있다고 한다.

5번

행과 열의 길이가 최대 50,000인 N*N 행렬이 첫 번째 입력으로 주어지고, 명령어 배열이 두 번째 입력으로 주어졌다. 명령어에는 rotate와 shift 가 있었다.

• rotate 명령: 명령바깥쪽 열과 행만을 시계방향으로 한 칸 돌리기
• shift 명령: 맨 밑의 행을 맨 위로 옮기기

클래스를 이용하여 구현하였고, 정합성 체크는 약 40분의 시간을 들여 통과할 수 있었다.

문제는 내 로직이 효율성 체크를 꽤 많이 통과를 못했다는 점이었다. 3번과 4번을 거의 포기하다시피 했기 때문에, 이 문제는 만점을 맞고 싶어 시간을 많이 소비했다.

내가 작성한 기존의 rotate 로직은 매 호출마다 최대 200,000번의 값 할당이 이루어졌다. 정말 비효율적인 로직이다. 그래서 "만약 동일한 rotate 명령이 연속적으로 등장한다면, 모아서 한 번에 처리한다면" 효율성을 개선할 수 있을 것이라 판단하였다.

또한 기존의 shift로직 또한 연속적인 shift명령을 받아서 수행하는 로직으로 수정하였다.

그 결과 2개의 효율성 케이스를 제외하고 모두 통과하였다.

느낀 점

준비되어 있지 않으면 언제든 허를 찔릴 수 있음

이번 시험은 약 4개월 동안의 알고리즘 스터디를 통해서 알고리즘 실력이 많이 향상되었음을 확인 할 수 있었다.

하지만, 학습 당시에 어려워서 겉핥기로만 확인하고 넘어갔었던 그래프 이론들

• 최단거리 알고리즘
• 최소신장 트리 알고리즘
  관련 문제들이 언제라도 내가 방심하고 있는 사이에 출제되어 나를 당황시킬 수 있음을 깨달았다.

인턴십 프로그램에 합격하지 못할 것 같다는 불안함과 아쉬움보다는, 그 동안 알고리즘 스터디를 하면서 왜 부족한 부분을 눈 가리고 아웅 하면서 보충하지 않았던 자책감이 컸다.

앞으로 더 해야 할 것이 무엇인지 알았으니, 이제는 미루지 말고, 다음에 보자 카카오.