후기
2023년 카카오 공채 1차 코딩테스트를 쳐보았다. 결과는 1~6번까지 6솔브 했다.
2020~2022 공채 기출들과 2023년 코테와의 차이점을 보자면,
1. 그리디스러운 문제들이 많이 출제되었다.
문제 모양새는 어떠한 알고리즘을 요구하는 것 같지만서도, 잘 생각해보면 그 알고리즘이 필요없는 문제가 있었다. 4번은 트리탐색을 해야할 것 같지만 안해도 되고, 5번은 dsu를 써야할 것 같지만 안써도 되고, 6번은 BFS나 Dijkstra를 써야할 것 같지만 안써도 되었다. 시간복잡도를 줄이는 방안으로 알고리즘을 쓰는 것이 중요함을 다시금 깨닫게 해준 코테였다.
2. 2번이 꽤 어려웠다.
여태까지 코딩테스트는 1,2,3번이 쉬운 문제에 속했으나, 올해 2번은 평소 2번과는 꽤 달랐다. 당황한 사람들이 많았을 것 같고, 2번의 난이도가 이번 코테 전체 난이도를 높인 느낌이 있다.
3. 정확성/효율성이 나눠지는 문제가 없었다.
이 덕분에 합격선이 4솔 아니면 5솔로 딱 떨어질텐데, 개인적으로는 Programming 분야는 4솔브이상이라면 합격일 것이라고 예상한다.
문제 풀이
1번, 3번, 4번, 6번, 2번, 5번 순으로 풀었다. 원래 모든 문제를 읽고 푸는걸 좋아했고, 어떤 문제를 풀면서 다른 문제의 아이디어가 생각날 때가 많았어서 좀 뒤죽박죽 풀었다.
1번. 구현 (+16min)
한 달에 28일인 달력에서 날짜가 넘어갈 때마다 년, 월, 일 계산을 잘 해줘야 하는 문제. 년도 제한이 크지 않아 하루씩 계산해도 된다. 전형적인 1번 문제.
2번. 그리디 (+235min)
최적의 방안은 한 번 갔다올 때마다 지급이나 수거가 필요한 가장 멀리 떨어진 곳에서부터 capacity만큼 택배를 주고, 박스를 수거하는 것이다. 이 점을 증명하는 것이 쉽지도 않고, 택배 지급과 수거가 따로 이루어지는데 항상 가능한지가 의문이 들 수 있지만, 언제나 가능하다는 것을 직접 시뮬레이션하다보면 알 수 있다. 난이도가 꽤 높다.
3번. 브루트포스, 구현 (+46min)
할인율 선택지가 4개라는 점과, 이모티콘 개수가 최대 m = 7개인 점을 이용해 완전탐색으로 구현이 가능하다. 가능한 모든 조합 개수 $4^m$을 계산하고 4씩 나눈 나머지로 할인율을 정해두면 완전탐색이 된다. 코테에 나오는 전형적인 유형이기 때문에 쉽게 풀었을 것이다.
4번. 트리, 비트마스킹 (+107min)
전위탐색으로 번호가 붙여진 포화이진트리들이 있을 때, 어떠한 수를 주면 그 수에 맞는 트리가 있는지 묻는 문제이다. 전위탐색으로 매겨진 포화이진트리 번호에서 이 성질을 관찰했다면 쉽게 풀 수 있다.
- 번호가 홀수인 노드는 리프노드(자식이 없는 노드)이고, 리프노드는 번호가 홀수이다.
- 번호를 $m \times 2^n (m은 홀수, n \geq 1)$로 표현했을 때, 자식노드 2개의 번호는 $m \times 2^n-2^{n-1}$, $m \times 2^n+2^{n-1}$ 이다.
- 트리임이 성립하려면 부모, 자식 관계에 있는 노드를 탐색하면서 부모가 0, 자식이 1인 경우가 하나도 없으면 된다.
이 성질들을 알아냈다면 트리탐색을 할 필요가 없고, 비트연산(shift, and)만으로 가능성을 판단할 수 있다.
5번. 구현, 파싱 (+291min)
DSU를 써야하는지 아닌지 고민을 하다가, 쓸 필요가 없을 것 같음을 깨닫고 종료 거의 직전에 푼 문제이다. 일단 표 제한이 50*50이기 때문에 꽤 할만해보였다. 먼저 50*50 정수배열을 하나 더 만들어 관리했는데, 각 좌표가 $(i,j)$일 때 $i*50+j$로 계산해 모두 다르게 표현했고, merge가 됐다면 같은 수로 표현한다. 알기로 명령어 종류가 4개였는데, 그림으로 표현해보자. 모든 쿼리는 50*50에 할 수 있고, 쿼리 개수까지 곱해도 얼마 안됐던 것 같다.
1) UPDATE 문자 문자
string 50*50 배열에서 관리하는 string을 바꾸면 된다.
2) UPDATE 좌표 문자
(merge된 것도 같이 update) 따로 만든 정수배열에서 같은 숫자라면 같이 update해준다.
3) MERGE 좌표 좌표
따로 관리하는 배열의 값이 각각 X, Y라면 Y를 X로 모두 바꾸고, string 배열에서도 바꿔주면 된다.
4) UNMERGE 좌표
따로 관리하는 배열의 값이 X인 것들을 모두 초기상태로 되돌려주고 string 배열도 조건에 맞게 한다.
6번. 그리디 (+158min)
이 문제 역시 처음에 BFS를 써야겠다고 생각해 코드를 열심히 짜다가, 이건 아님을 깨닫고 고쳤다. 먼저 사전순 순서인 d, l, r, u를 실행할 수 있는대로 실행하는 것이 목표다. 이동할 때마다 목표지점까지의 최단거리 $ |x_i-x_j|+|y_i-y_j| $를 계산하고, 이 값과 앞으로 이동해야하는 횟수를 비교해 d, l, r, u로 가도 되는지(가도 제한횟수 안에 목표까지 도달할 수 있는지)를 각각 판단해 이동했다. 생각보다 어렵지는 않았다.