2023 KAKAO TECH BLIND RECRUITMENT 1차 후기

9월 24일 오후 2시 ~ 7시까지 5시간동안 1차 코딩테스트를 봤습니다.

 

문제는 총 7문제였고, 6문제를 해결하였습니다.

 

 

1번. 구현

모든 달이 28일로 되어 있어서 [31일, 28일, 31일, ...] 이런 노가다 없이 년-월-일을 전부 일로 변환하여 풀었습니다.

---

2번. 그리디

생각해보면 한 번 왔다갔다할 때마다 최대로 배송하고, 최대로 수거할 수 있음이 보장되어 있습니다.

그래서 한 번 왔다갔다할 때 max(가장 멀리 배송해야 하는 곳, 가장 멀리 수거하는 곳)만큼 더해주는 일을 반복하면 됩니다.

---

3번. 브루트포스, 백트래킹

이모티콘 할인율이 0%, 10%, 20%, 30%, 40%이므로 하나의 이모티콘에 5가지의 경우의 수를 적용할 수 있습니다.

그래서 이모티콘의 개수를 k개라고 하면 5^k가지의 경우의 수를 모두 확인해주면 됩니다.

파이썬의 경우 재귀 함수로 문제를 풀려고 하면 데이터 1개가 시간 초과로 나와서 for문으로 다시 풀었네요. 제가 코드를 이상하게 짰을지도 모르겠어요.

---

4번. 트리에 대한 이해, 재귀

완전 이진 포화 트리를 만들어야 하므로 트리 노드의 수를 2^n - 1개로 만들어야 합니다.

그래서 numbers에 있는 요소를 하나 받으면 이진수로 바꾸고 길이가 2^n - 1이 되도록 맨 앞에 0을 여러 개 붙이면 됩니다.

이러면 완전 이진 포화 트리가 나오는데, 완전 이진 포화 트리의 특징은 서브트리의 노드 개수가 무조건 홀수임을 보장합니다. 그래서 tree[len(tree)//2]로 쉽게 루트노드 접근이 가능합니다.

이런 상태에서 루트 노드가 1이거나, 루트노드가 0인데 자식노드의 값도 전부 0 으로 이루어졌으면 해당 숫자로 완전 이진 포화 트리를 만들 수 있고, 루트 노드가 0인데 자식 노드중에 하나라도 1이 있으면 완전 이진 포화 트리를 만들 수 없습니다.

---

5번. 구현

유니온 파인드 + 완전 탐색 + 구현

유니온 파인드는 문제 지문에 대놓고 쓰라고 말하고 있어서 유형 찾는데는 시간이 얼마 안걸렸는데, 어떻게 구현을 해야할지 생각하는 것에서 시간이 너무 오래 걸렸습니다.

---

6번. 그리디

알파벳을 사전순으로 정렬하면 d, l, r, u가 나옵니다.

1) 최대한 밑으로 이동한다 (d)

2) 최대한 왼쪽으로 이동한다 (l)

3) 이후 오른쪽 ↔ 왼쪽 왔다갔다한다 (rl)

4) 이후 위 ↔ 아래 왔다갔다한다 (ud)

5) 이제 목적지로 이동하는데, 오른쪽부터 이동한다 (r)

6) 목적지로 이동하는데, 위로만 이동한다 (u)

7) 목적지 도착

이렇게 풀면 됩니다.

 

 

이번에 2차까지 열심히 준비해서 면접도 보고 싶었는데, 2차가 ICPC 예선전이랑 일정이 겹쳐서 너무 아쉽네요