2021 카카오 채용연계형 인턴십 for Tech Developers 코딩테스트 후기

평소에 PS를 할 때는 프로그래머스보다 백준 위주로 풀었었다.

그러다 카카오 인턴십을 공고를 보고 과연 어떤 식으로 코딩테스트를 보는지 궁금해졌다.

잘 볼 것이라는 기대는 전혀 없었지만, 어차피 아직 2학년이라 붙어도 인턴십은 못하니

그냥 체험해보자는 느낌으로 가볍게 응시했다.

 

4시간이라는 시간동안 5문제를 풀게되는데, 나의 집중력은 3시간 50분 즈음에서 끝나버렸다.

5문제중에 2문제를 완벽하게 풀고, 한 문제를 테스트케이스 한개 실패해서 못풀고,

나머지 두 문제를 전혀 건들지 못했다.

 

첫번째 문제는 백준 solved.ac 기준 브론즈4~3 정도 난이도로 나올법한

if, else if 를 써서 단순 구현하는 문제였다.

숫자와 숫자의 영어이름이 섞여있는 문자열에서

숫자의 영어이름을 숫자로 바꾸어 최종 정수를 출력하는 문제였다.

간단하게 한번에 풀었지만, 푸는데 생각보다 시간을 많이 썼다.

(10분 정도 쓴 것 같다)

 

두 번째 문제는 백준 solved.ac 기준 실버 3~1 정도 난이도로 예상되는

장애물을 포함한 단순 그래프탐색 문제였다.

나는 BFS를 이중으로 써서 풀었다.

사회적 거리두기를 소재로 한 문제인데, 격자판에서 맨하튼 거리 2 이하로 사람이 있으면

0을 출력하고, 그렇지 않으면 1을 출력한다.

만약 어떤 사람 주변에 가림막이 있으면 거리는 신경쓰지 않아도 되지만,

가림막을 피해서 거리 2이하로 다른 사람과 공기가 닿으면 안된다

이 문제를 풀고 나서 1시간 정도의 시간이 지났던 것 같다.

 

세 번째 문제는 백준 solved.ac 기준 골드 4~2 정도의 난이도로 예상되는 문제로

자료구조 구현 문제였다.

이 문제는 정확성 테스트와 효율성 테스트가 나누어져있었다.

1차원 표에서 데이터를 선택 - 삭제 - 복구 하는 기능을 구현하는 것이다.

처음에는 비효율적인 방법으로 배열의 모든 인덱스를 왔다갔다하면서

데이터를 선택하고, 삭제하고 복구했다.

1시간 정도의 디버깅끝에 정확성 테스트를 통과했다.

 

그 다음 효율성 테스트를 통과하기 위해 자료구조를 고민하다가 이중 연결리스트를 구현했다.

데이터 삭제를 제외하고 이중연결리스트를 사용하자 정확성 테스트를 통과하고

효율성테스트의 테스트 케이스 하나를 시간초과했다.

여기까지 또 1시간이 걸렸다.

 

그래서 데이터 삭제에도 이중연결리스트를 사용해보았다.

그러자 효율성 테스트를 통과했다.

그러나 정확성테스트에서 테스트케이스 하나가 실패로 나왔다.

결국 이건 해결하지 못하고 테스트를 종료했다..

 

네 번째 문제는 최단경로 문제였다.

그래프가 주어지는데, 일부 노드가 trap이다.

트랩 노드를 밟으면 그 노드와 연결된 모든 간선의 방향이 반대로 바뀐다.

이런 그래프 구조에서 시작노드와 끝 노드가 주어질 때 최단 경로를 구하는 문제였다.

 

트랩을 밟으면 간선 방향이 반대로 바뀌는 걸 그대로 구현하고

나머지를 다익스트라나 BFS로 푸는 것을 고민해보았는데

트랩을 밟을때 마다 간선 방향이 바뀌어서 기존 최단 경로 알고리즘을 쓸 수 있을지 확신이 안섰고

이 상태에서 트랩을 밟을 때마다 간선 방향이 바뀌는 것을 시간들여 구현하는 것에 대한 가치를 고민했다.

그래서 이 문제를 읽고 3번 문제 점수 높이기 vs 4번문제 시도 중 고민하다 3번 문제 점수 높이기를 택했다.

 

다섯 번째 문제는 알고리즘 종류가 안 떠올랐다.

이진트리가 주어질 때, 이진트리의 간선을 k-1번 잘리 k개의 그룹으로 만들되

이때 각 그룹 내의 노드 값의 합의 최대값이 최소가 되도록 하는 값을 찾는 문제였던 것 같다.

중급 알고리즘을 공부할 때 얼핏 배웠던 것 같았는데 잘 떠오르지 않아서 그냥 읽고 넘겼다.

---

3번 문제를 처음 읽을 때 이중연결리스트를 못 떠올린 건 아니었다.

1, 2번 문제를 풀면서 맞기만 하면 되겠지 하는 생각으로 비효율적으로 구현했다.

정확성 테스트와 효율성 테스트를 고려하지 않은 접근 방법이었다.

 

만약 처음부터 이중 연결리스트를 구현하는 방향으로 풀었다면 1시간을 아낄 수 있었을 것이다.

그리고 그 시간동안 4번 문제를 조금이라도 풀어서 점수를 조금이라도 더 높일 수 있었을 것이다.

또한 결과적으로 이중연결리스트를 구현했을 때 코드가 더 깔끔하게 나와 디버깅하기도 쉬워보였다.

 

이번 코딩테스트를 통해 내가 자료구조 구현에 약하다는 것을 깨달았다.

(특히 전에 이중 우선순위 큐 구현 문제를 풀 때 굉장히 고생했던 기억이 났다.

힘들게 풀었었는데, 다시 풀어봐도 안풀리는 문제였다.

그때와 달라진 게 없다는 걸 느꼈다.)

 

또한 내가 알던 알고리즘만 계속 쓰는 것이 아닌

새로운 알고리즘을 배우기 위해 노력해야겠다고도 생각했다.

다음에는 5번 문제처럼 어디서 본 유형 같은데,

어떻게 풀어야할지 모르겠다고 느끼는 상황을 만들지 않도록 해야겠다고 느꼈다.

 

---

* 5.14일 추가

코딩테스트 결과가 나왔는데 합격이네요ㅋㅋㅋㅋ

3문제밖에 못풀어서 당연히 칼탈락일 줄 알았는데..

어차피 프로젝트같은 것도 아직 전혀 없어서 지원서에 쓸 내용은 없겠지만 붙어서 너무 신기하네요

알고리즘 공부는 지금 하던대로 하고 프로젝트를 열심히 준비해야겠다는 생각이 들었습니다..