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번이 더 어려운 듯...
<총평>
풀리면 쉬워보이고, 안 풀리면 한없이 못 풀 것 같은 문제들이었다.
되게 뭔가... 알고리즘이라기 보단 잔머리를 요구하는 문제들이 많은 느낌?
그동안의 카카오 공채/인턴십과 비교해서 굉장히 이질적인 느낌이 나는 문제들이 많았고, 개인적으로는 좀 풀면서 많이 아쉬웠던 것 같다.
작년보단 컷이 확실히 떨어질 것 같긴 한데... 뭐랄까.... 잘 모르겠다...
