본문 바로가기

일상

2020 카카오 신입 개발자 공채 온라인 코딩테스트 후기

해당 코딩 테스트는 2019년 9월 7일인 오늘 오후 2시에서 7시까지 총 5시간 동안 진행되었습니다. 사전에 자신이 면접을 보고 싶은 회사를 선택하였으며, 오프라인 코딩 테스트까지 통과되면 각 회사에 따라 이후 일정이 정해지는 방식으로 운영하는 방식으로 되어 있었습니다.

재작년과 작년에는 군인 신분이라서 참가를 하지 못하였는데, 이번엔 일반인 신분이라 참가가 가능했습니다. 지난 2년 동안과 마찬가지로 총 7문항이 출제 되었으며 언어의 경우에는 C++, Java, Javascript, Kotlin, Python, Swift의 언어가 사용이 가능했습니다. 테스트가 시작하기 전에는 C++로 작성해야지라고 생각을 했었는데 막상 시험에서는 Python만 사용했습니다. 아무래도 문자열 처리 등을 비롯한 기능들이 강력해서 Python을 사용하지 않는게 어려운 것 같습니다.

7문제 중 총 5문제를 풀었습니다.

간략한 풀이 소개

첫 번째 문제는 문자열이 1개 주어졌을 때 이를 특정 알고리즘으로 압축해서 그 길이가 최소가 되는 길이를 출력하는 것이 문제였습니다.

문자열 길이가 길지 않아서 문자열을 자르는 단위를 1개씩 증가시키면서 각각의 경우에 압축된 길이를 계산하고 그 길이들을 비교해서 가장 작은 값을 출력하면 되는 문제입니다.

두 번째 문제는 괄호 문자열이 주어지고 이 문자열을 주어진 조건에 맞게 변형할 수 있는지 여부를 확인하는 문제였습니다.

문제에서 재귀 호출을 하라고 명시가 되어 있어 나와있는 조건 그대로 구현하면 됩니다. 재귀 함수를 구현하는 과정에서 주어진 문자열이 올바른 괄호인지를 확인해야 합니다. 확인하는 방법은 스택을 사용하는 방법이 있고 문자열을 읽어가면서 '('를 만나면 1을 더하고, ')'를 만나면 -1을 더해서 중간에 음수가 되면 올바른 괄호가 아니며 최종 결과가 0이 되면 올바른 괄호가 됩니다.

올바른 괄호인지 확인하는 부분을 제외하면 문제에 나와 있는 그대로 구현하면 됩니다.

세 번째 문제의 경우 자물쇠와 열쇠의 홈과 돌기가 주어졌을 때 열쇠를 회전시키거나 평행이동 시켜서 자물쇠의 홈에 열쇠의 돌기가 모두 들어가고, 자물쇠의 돌기와 열쇠의 돌기가 만나지 않도록 하는 경우가 있는지를 알아보는 문제였습니다.

열쇠를 4번 회전시키고, 각 위치마다 직접 일치하는지 여부를 판단하는 방법이 있을 수 있지만 이렇게 하면 일치여부를 확인할 때 최대 $N^2$ 번($N$은 자물쇠의 한 변의 길이)의 확인이 필요하기 때문에 시간이 초과될 수 있을 것 같아서 비트 연산자를 활용하였습니다.

문제에서 홈은 0으로 되고 돌기는 1로 되어 있기 때문에 자물쇠의 홈에 열쇠의 돌기가 모두 들어가는지 확인하는 방법은 or 연산자(|)를 사용해서 그 값이 $2^{N+1}-1$ 과 같은지 여부를 확인하는 식으로 하면 됩니다. 그리고 돌기가 만나는지 확인하는 방법은 and 연산자(&)를 사용해서 그 값이 0인지 여부를 확인하면 됩니다.

그래서 열쇠를 회전하는 함수와 평행 이동하는 함수를 각각 작성해서 열쇠가 일치하는지 여부를 확인하여 출력하였습니다.

네 번째 문제의 경우 가사 단어들이 주어져 있고, 질의할 단어가 주어져 있는데, 이 때 질의할 단어에는 와일드카드인 ?가 있어서 맨 앞에 연달아 나오던지 혹은 맨 뒤에 연달아 나옵니다. 그래서 질의할 단어와 일치하는 가사 단어들의 개수를 각각 출력하는 문제입니다. 예를 들어 kakaokak??를 질의했을 때 일치하지만 kak?과는 일치하지 않습니다. 이 문제의 경우 다른 문제와 다르게 효율성을 체크하는 부분까지 존재하였습니다.

효율성을 체크하는 부분이 존재하지 않는다면 각각의 경우를 모두 비교해서 값을 출력하면 됩니다. 다만 효율성을 체크하는 부분을 통과하기 위해서는 다른 방법을 사용해야 합니다.

여기서 Trie 자료 구조를 사용하면 해당 문제를 해결할 수 있습니다. 와일드 카드가 중간에 등장하지도 않고 맨 앞 혹은 맨 뒤에 연달아서 등장하기 때문에 결국 접두사를 만들어서 길이가 일치하는 경우의 개수를 세도록 하면 됩니다.

주의할 점은 문자열의 길이가 너무 길기 때문에 재귀 함수로 사용할 경우 재귀 깊이 에러가 발생하게 되므로 반복문으로 구현을 해야 합니다.

또한 앞쪽에 ?가 나타나는 경우는 문자열을 뒤집어서 동일한 방식으로 사용하면 됩니다.

다섯 번째 문제는 특정한 조건에 따라 입력된 명령을 실행하고 조건을 만족하지 않으면 해당 명령을 무시하며, 모든 명령을 실행한 결과를 반환하는 문제입니다. 이 문제의 경우에도 2번째 문제와 마찬가지로 주어진 내용을 구현할 수 있는지 여부를 물어보는 문제였습니다.

주어진 조건 그대로 구현을 하면 되나 해당 조건이 약간 복잡해서 각 경우를 잘 나누어서 구현해야 합니다. 시간이 부족해서 완성을 하지 못했던 점이 아쉬웠습니다.

여섯 번째 문제는 원형의 벽이 있고, 이 벽에 약한 위치가 표시되어 있으며 사람들이 움직일 수 있는 거리가 주어졌을 때 최소 몇 명만 있으면 약한 위치를 모두 확인할 수 있는지를 묻는 문제였습니다.

이 문제의 경우 기준을 어떻게 잡을 것인지가 중요합니다. 따로 기준을 잡지 않고 완전 탐색을 하게 되면 중복이 되는 경우도 발생하게 되고 그로 인해서 시간 초과가 발생하게 됩니다.

물론 여러 가지 풀이 방법이 있겠지만 저는 가장 많이 이동하는 사람이 출발하는 점을 설정하고, 각 사람은 반시계 방향으로 이동한다고 제약조건을 주고 탐색을 하는 방식으로 진행하였습니다. 이렇게 하면 중복 되는 경우가 없이 나올 수 있는 모든 경우를 확인할 수 있어서 모두 확인할 수 있는 경우의 사람수를 각각 계산해서 가장 작은 값을 반환하도록 하였습니다.

마지막으로 7번 문제는 미로가 주어져 있고 1X2의 드론이 있을 때 해당 드론을 움직이거나 회전하게 해서 주어진 목적지로 최소 시간이 걸리도록 도착하게 하는 문제였습니다. 이 문제는 BFS로 탐색을 하면 될 것 같기는 한데, 직접 구현을 해보지는 못하였습니다. 일반적인 미로 찾기와 비교했을 때 크기가 1X2라는 점과 회전이 있다는 점에서 약간 복잡할 것 같습니다.

후기

문제를 풀면서 자잘한 실수들이 많아서 해당 실수를 바로 잡는데 시간이 오래 걸려서 쉬운 5번 문제를 놓친 것이 아쉬웠습니다.

실수한 내용을 보면 3번 문제를 푸는 과정에서 열쇠 회전을 구현할 때 1을 더 빼주어야 하는데 그러지 않았다는 점, 열쇠가 이동할 수 있는 범위를 잘못 설정했었던 점이 있었고, 6번 문제를 푸는 과정에서 탐색을 할 때 조건을 잘못 설정해서 일부 경우를 빼먹어서 해당 경우를 찾는데 시간이 오래 걸렸던 점 등이 있었습니다.

요즘 알고리즘 문제를 풀지 못했다보니 구현하기 전 아이디어를 생각해내는 과정이 오래 걸린 부분도 아쉬웠습니다.

나중에 카카오 기술 블로그에 문제가 공개가 되면 제가 풀었던 문제에 대한 풀이 영상을 찍어 올리도록 하겠습니다.

  • KSH 2019.09.08 12:46 댓글주소 수정/삭제 댓글쓰기

    수고 하셧습니다 ‘-‘
    저 같은 경우 5,7 번 문제 풀었는데 둘다 조건이 엄청 많습니다. 5번 같은 경우 그냥 문제 조건들을 잘 읽어서 구현 하면 되는데, 7번은 bfs 만으론 시간 초과 메모리 초과가 나더라구요. 그래서 전 a* 로 해결 했습니다

  • KSY 2019.09.08 15:30 댓글주소 수정/삭제 댓글쓰기

    7번 문제 bfs + 4차원 방문배열 이용해서 풀었습니다.
    같은 상태로 방문하는 경우만 가지 치면 무난히 패스하더라구요

  • 비밀댓글입니다

    • 네 Python3를 사용하였으며 모든 효율성 테스크까지 통과하였습니다.

      재귀 부분을 반복문으로 변경하고, Trie 자료 구조를 구현할 때 매칭되는 개수를 저장하였습니다. 그래서 불필요하게 아래쪽 원소를 탐색하는 것을 방지하였습니다.

  • 비밀댓글입니다