[220924] 2023 KAKAO BLIND RECRUITMENT 코딩테스트 1차 후기

https://career.programmers.co.kr/competitions/2759

2023 KAKAO BLIND RECRUITMENT

2023 카카오 코딩테스트에 응시해보았다!

 

카카오는 내가 가고 싶은 기업 중 하나이기도 하고, 카카오 알고리즘 문제들이 꽤나 어렵다는 소문이 자자해 경험삼아 인프라 분야에 접수하여 응시해보았다. (주변 지인분들이 모두 백엔드로 지원했고, 난 아직 졸업예정자가 아니기 때문에 취업이 급하지 않아 경쟁률을 낮춰주기 위해 인프라에 넣은 이유도 있다.)

작년과 몇 가지 다른 점이 있었는데 아래와 같다.

 

• 정확성/효율성이 나누어지지 않았다. 작년에는 정확성만 챙기고 효율성이 터지는 경우는 점수를 절반이라도 챙길 수 있었지만, 이번에는 정확성, 효율성 모두 챙겨야 하는 듯.
• 각 문항 별로 점수가 다르다. 다만, 솔브수 내의 동점자를 가를 때만 쓰인다고 한다  점수 합으로 갈리는 게 맞는 듯하다. 실제로 솔브수가 아닌 점수로 합불이 결정되는 걸 목격했다. 작년엔 문항 별 점수가 없었는데, 이번엔 위 사진처럼 점수가 생긴 모습. 

 

그리고 이건 개인적으로 당황했던 건데, 프로그래머스는 (C++ 기준) #define int long long으로 int를 long long으로 치환해버릴 수가 없었다. 평소에 오버플로우 때문에 int를 long long으로 치환해서 코드를 작성하는데, 프로그래머스에선 컴파일 에러를 띄워준다. 

 

 

 

지문, 풀이코드, 테스트케이스 배포 및 공유는 불가능하기 때문에 간단하게 느낀 점 및 내가 해결한 방법을 포스팅해보겠다.

---

주관적인 난이도 후기

문제	주관적 난이도
1	Bronze I
2	Silver III
3	Silver II
4	Gold V
5	Gold IV
6	Gold I
7	?

---

1번. AC

Tag: 문자열 파싱, 구현

연, 월, 일을 파싱한 다음에, 수가 커지면 적절히 처리해주면 된다.

 

카카오는 앞쪽에서 문자열 파싱 문제를 내는 것을 좋아하기 때문에 이런 류의 문제가 나오지 않을까 예상했는데 예상이 적중해버렸다.

간단하게 파싱 후, 월이 12가 넘어가면 월이 12 이하로 될 때까지 year++를 해주는 작업을 해준다.

그 다음에, 연 월 일을 각각 비교해서 만료가 됐다면 답에 넣어주면 된다.

---

2번. AC

Tag: 그리디, 구현, 우선순위 큐

짧은 거리에 있는 작업을 먼저 처리한다면, 나중에 먼 거리를 처리할 때에도 짧은 거리를 추가로 가야 된다. 따라서 가장 멀리 있는 작업을 먼저 처리해주어야 한다. 또한, 매번 capacity를 꽉 채워서 작업을 해주는 것이 가장 최소거리로 빠르게 작업을 끝낼 수 있다는 그리디적인 특징을 파악해야 한다. 백준 실버4~3 정도에 비슷한 그리디 문제들이 많다. 

 

작업을 처리한 다음에 다시 되돌아와야 하기 때문에 2를 곱해주는 것을 유의하자.

---

3번. AC

Tag: 브루트포스, 백트래킹

카카오 이모티콘 플러스에 최대한 많이 가입시킬 수 있을 때의 경우를 구하는 문제이다.

이모티콘 수가 최대 7개밖에 되지 않고, 할인율을 10%, 20%, 30%, 40% 네 가지로 할 수 있기 때문에 백트래킹으로 4^7가지 경우를 전체 탐색해도 시간초과가 나지 않는다.

그렇기 때문에 전체탐색을 해본 후에 가장 최적의 값을 찾아보는 풀이를 작성하게 됐다.

 

여기서 조금 삽질을 했는데, 이모티콘 구매 비용이 k원을 넘어서면 플러스로 전환한다고 해서 부등호(>)로 처리했는데, k원을 넘어선다는 것은 k원이 됐을 때에도 플러스로 전환하는 거였다... 따라서 부등호를 등호포함조건(>=)으로 바꿔서 AC를 받았다.

---

4번. AC

Tag: DFS, 그래프

슬슬 어려워지는 부분이라 생각한다. 트리 순회 쪽을 공부했다면 유리했을 듯. 

포화 이진트리에서는 노드의 왼쪽 자식들은 모두 반드시 노드보다 작고, 오른쪽 자식들은 모두 반드시 노드보다 크다.

그렇기 때문에 십진수가 주어지면 이를 이진수로 바꿔준 후에 DFS로 트리 탐색을 해주었다.

루트 노드는 반드시 N(트리의 크기)/2이고, 이 값을 트리의 높이만큼 나눈 값을 왼쪽 자식노드로 갈 때는 빼주고, 오른쪽 자식 노드로 갈 때는 더해주면서 이동하면 된다. 이 역시 포화 이진 트리의 성질이다.

 

탐색된 노드임에도 불구하고 0이거나, 탐색되지 않았는데 1이면 불가능한 경우이다.

---

5번. AC

Tag: 브루트포스, 문자열 파싱, 구현

 

엑셀처럼 표를 병합하거나 분할할 수 있는데, 이를 빡구현하는 문제이다. N이 작기 때문에 DSU (union-find)를 쓰지 않고도 정답을 받을 수 있다. 50 * 50 배열에 문자열 크기는 10 이하이므로 O(N^4)도 통과되기 때문이다.

유니온파인드를 사용하지 않은 풀이를 작성해보겠다.

 

먼저 stringstream으로 공백 기준으로 split을 해주자.

부모 배열을 만들어서 MERGE일 경우 병합된 애들이 r1, c1을 가리킬 수 있도록 부모 배열에 넣어주자.

UNMERGE일 경우는 부모배열로 루트 부모를 찾아 그 값으로 채워주고, 부모에 속한 표들을 다시 자기 자신을 가리키도록 해주자.

UPDATE의 경우 그 값을 직접 변경하면 안된다. 병합되면 자기 자신이 아닌 다른 표를 가리킬 수 있기 때문에 만들어놓은 부모 배열을 이용해서 루트 부모를 업데이트해주도록 하자.

PRINT 역시 부모를 출력하도록 해주어야 한다.

 

빡구현 문제여서 중간에 조금이라도 잘못되면 맞왜틀을 외칠 수 있는데, 바로 내가 그 주인공이었다...

UNMERGE에서 조금 실수를 해서 30분동안 틀린 이유를 찾지 못하고 삽질하다가 예제 테스트 케이스를 이것저것 바꿔보면서 오류를 찾아냈다. 덕분에 수정 후 AC를 받았다.

---

6번. AC

Tag: 다익스트라

이미 방문했던 곳을 다시 방문할 수 있기 때문에 BFS, DFS 등등의 방법을 최적화없이 사용한다면 시간초과 또는 메모리초과를 받는다.

또한, 이동 방향에 따라 가중치가 다르기 때문에 단순 BFS로는 풀기 어렵다.

 

사전 순으로 정렬하면 d, l, r, u이고, 이에 따라 각각 다른 가중치를 두자. 나의 경우는 각각 1,2,3,4로 두었다. 사전 순으로 이동을 해야 하기 때문에 맨앞에 d가 오도록 하는 것이 가장 중요하고, 맨앞에 d가 아닌 다른 값이 온다면 그 값은 맨앞에 d가 오는 모든 값들보다 가중치가 크도록 해주어야 한다. 따라서 가중치에 (K-횟수)를 곱해주도록 했다. 가장 작은 가중치일 경우를 구해주어야 되기 때문에 dijkstra를 떠올렸고, 역추적을 해주기 위해 역추적 배열을 만들어주었다.

 

또한, 이미 방문한 곳도 다시 방문할 수 있으며, 이동에 따른 가중치가 달라지기 때문에 이동횟수를 배열에 저장해두어 3차원 다익스트라로 해주었다.

 

개인적으로 다익스트라를 떠올리는 것이 어렵다고 생각한다. (아니면 다른 방법으로 해도 충분할 듯)

이 문제와 비슷한 난이도라고 생각한다.

https://www.acmicpc.net/problem/24042

24042번: 횡단보도

---

7번. WA

Tag: ?

트리 내에서 이리저리 장난치는 문제인 것 같은데, 6번을 풀고 나니 시간이 30분 정도밖에 남지 않아 해결하지 못했다.

내년에는 올솔을 목표로 도전해보는걸로!

---

결과

6솔이라는 좋은 결과를 받았다.

1시간 30분동안 4솔을 해서 잘하면 올솔도 가능하겠다는 생각이 들었는데, 아직은 실력이 부족한 듯하다.

 

좀 더 수련해서 23년, 24년에는 올솔을 목표로 해야겠다.

 

+) 22.10.04 추가

코테를 치고 10일 정도 후에 합격 메일을 받았다!

연휴가 껴서 결과가 조금 늦게 나온 듯하다.