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

2023 카카오 공채 1차 코딩테스트가 09/24 14:00 - 19:00에 진행되었다.

 

오전에 라인 보고 바로 이거 보니까 집중이 안 되어서 생각보다 힘들었다 (?)

스스로 푼 풀이라 실제 정답과 다를 수 있다는 것에 유의...

 

Q1
사용된 알고리즘: 단순 구현
예상 난이도 (Solved.ac 기준): S5

하라는 대로 그대로 하면 된다.

이것저것 구현만 좀 하자.

참고로, 파이썬의 경우 dateutil.relativedelta 라는 치트키가 있는데, 이를 사용하면 날짜 연산이 엄청나게 쉬워진다.

 

Q2

사용된 알고리즘: 그리디, 애드혹

예상 난이도 (Solved.ac 기준): S2 - G3

 

난이도 스펙트럼을 왜 저렇게 했을까? 생각보다 아이디어 떠올리는게 어려울 수도 있을 것 같아서 저렇게 했다...

맨 끝에서부터 앞으로 이동하는게 제일 이동거리를 줄일 수 있다.

 

맨 끝 집부터 순회하면서, 각 집 마다 배달/수거해야 하는 짐의 수를 누적시키고, 만약 cap을 넘어간다면 그때 이동거리를 늘리면서 누적된 짐의 수에 cap을 각각 빼줘야 한다.

 

처음부터 이동하면서 짐을 쌓는게 아니라, 일단 이동했다고 치고 짐부터 수거한다는 아이디어를 가져가야 풀 수 있는 문제.

 

Q3

사용된 알고리즘: 완전탐색

예상 난이도 (Solved.ac 기준): S1

 

각각에 대해, 10% ~ 40%의 할인률을 적용하고, 그냥 각 유저에 대해 테스트를 돌리면 된다.

오히려 2번보다 쉽게 느낀 사람들도 많았을듯.



할인률 설정하는건 재귀로 짜면 뚝딱이다.

 

Q4

사용된 알고리즘: 트리, 분할정복

예상 난이도 (Solved.ac 기준): G5

 

포화 이진트리의 노드의 수는 2^k - 1 개이다.

그러니, 일단 이진수로 바꾸고 난 뒤에 앞에 0을 붙이는 방식으로 저 갯수를 만족하도록 채워주자.

 

끝났으면, 루트노드에서 시작해서...

- 루트노드의 값이 0이라면 왼쪽 서브트리/오른쪽 서브트리의 루트 또한 0이어야 하며,

- 루트노드의 값이 1이라면 왼쪽 서브트리/오른쪽 서브트리의 루트의 값은 뭐가 되던 상관이 없다.

 

이 조건을 만족하는지만 따지면 된다.

 

Q5

사용된 알고리즘: 구현, Union-Find

예상 난이도 (Solved.ac 기준): G2

 

이차원 Union-Find 문제다.

하지만 이차원으로 관리하면 골때리니, 1차원으로 합친 다음에 r * 50 + c로 처리하자. (물론 r과 c 입력 받고 난 뒤엔 1 빼고...)

UPDATE 쿼리를 진행할 땐, 바로 값에 접근하는게 아니라 Union-Find 배열에 접근한 뒤에 그 인덱스를 활용해서 값을 수정해야 한다.

MERGE는 일반적인 Union-Find 로 처리하되, 값을 추가하는 부분에 유의하자.

UNMERGE가 좀 골때리는데, 전체 스캔을 돌리면서 find 를 시도하고, 인덱스가 현재 삭제하려는 인덱스와 같으면 초기화 한다. 물론 값을 복구해야 하니, 미리 값 캡쳐 해놓자!

 

유파인걸 알아도, 생각보다 구현 과정에서 생각할게 많았던 어려운 문제. 난 이게 7번 같다.

 

Q6

사용된 알고리즘: 애드혹, 그리디

예상 난이도 (Solved.ac 기준): G4

 

맨하탄 거리 (두 지점의 x 좌표와 y 좌표 차이의 합) + 2n = k 일때, 이동할 수 있음이 보장된다.

그건 그렇고, 어떻게 이동해야 할까?

사전순으로 이동해야 하니, 아래 -> 왼쪽 -> 오른쪽 -> 위쪽 순으로 배치된다는 점을 기억하자.

 

일단 아래부터 이동하려고 시도하고, 이동할 수 있는지 확인하고 (이동한 다음에 벽 밖으로 나가는지 일단 보고, 이동한 거리에서 k - 1 칸으로 이동할 수 있을지 윗 문단과 같은 방식으로 체크한다.) 이동할 수 있으면 이동하고, 아니면 다음 칸으로 넘어가자.

 

구현은 엄청 짧은데, 생각보다 아이디어 떠올리기 힘들었을 것 같다.

 

Q7

사용된 알고리즘: 트리, 그리디

예상 난이도 (Solved.ac 기준): G3

 

사실, 1/2/3 중 뭐 넣을지 처음엔 고민할 필요가 없다.

어떤 노드의 타겟값이 x, 그 노드에 수를 떨군 횟수를 k라고 한다면, k <= x <= k * 3 안에 들어가면 된다.

 

일단 수를 계속 넣어보면서, 모든 노드가 저 조건을 만족하는 순간 탈출하자. (단, 한 노드라도 x < k 가 된다면, 그냥 -1 띄우고 종료해야 한다.)

그 다음엔? 수 적당히 늘려서 타겟 값 만들면 끝.

솔직히 말해서, 역대 카카오 7번 중에 가장 임팩트가 없었다. 오히려 5번이 더 어려운 듯...

 

<총평>

풀리면 쉬워보이고, 안 풀리면 한없이 못 풀 것 같은 문제들이었다.

되게 뭔가... 알고리즘이라기 보단 잔머리를 요구하는 문제들이 많은 느낌?

 

그동안의 카카오 공채/인턴십과 비교해서 굉장히 이질적인 느낌이 나는 문제들이 많았고, 개인적으로는 좀 풀면서 많이 아쉬웠던 것 같다.

작년보단 컷이 확실히 떨어질 것 같긴 한데... 뭐랄까.... 잘 모르겠다...

 

3시간 8분 컷. 중간에 딴짓만 안 했으면 2시간 30분 정도 걸렸을 것 같다.