2022 KAKAO Tech Internship 코딩테스트 후기

카카오 2022 인턴십 코딩테스트가 5월 7일 14:00 - 17:00 에 진행되었다.

 

시간이 5시간이라 작년보다 어려울 줄 알고 쫄았는데 (??) 생각보다 쉽게 나왔다.

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

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

정말 단순한 구현이라 코멘트는 패스.

Q2
사용된 알고리즘: 투 포인터
예상 난이도 (Solved.ac 기준): S1 ~ G5

어차피 큐는 데이터가 양 끝쪽에서만 들어온다.
첫 번째 배열을 기준으로 생각하면, 맨 앞에서 데이터가 나가고, 맨 뒤로 데이터가 들어온다.

그러니, 두 큐에 담긴 값들을 합치게 되면, 첫 번째 큐에 남게 되는 데이터는 일렬로 배치된다.
일렬로 배치되는 걸 알았으면, 가볍게 투포인터 슥삭하면 끝.

Q3
사용된 알고리즘: DP + (쓸데 없는...) 커팅
예상 난이도 (Soved.ac 기준): G4 ~ G3

알고력을 x, 구현력을 y라고 하면,
DP[x][y] = 현재 알고력이 x이고, 구현력이 y일 때 모든 문제를 풀 수 있는 수준에 도달할 때 까지 걸리는 시간
공부는 cost가 1이고, 필요한 능력치가 0인 문제를 푼다고 해석할 수 있으니, 결과적으로 (처음 주어진 문제의 수) + 2개의 문제 중 문제를 골라푸는 것과 같다.

하지만 c++ 기준 타임 리밋이 너무너무 짧아서, 추가적인 커팅이 필요하다.
만약 알고력이나 구현력 중 하나를 다 채웠다고 가정하자. 이 경우, 다른 하나만 열심히 채우면 되니, 공부를 하는 것 보다 효율이 낮은 task는 아예 건드리지 않고 skip을 하면 효율성이 통과된다.

dp 짜는건 쉬웠는데 커팅에서 좀 애를 먹었다...

Q4
사용된 알고리즘: 이진 탐색 + 그래프 탐색
예상 난이도 (Solved.ac 기준): G4 ~ G3

우리가 찾는 대상을 아무 산봉우리나 오르는데 필요한 최소 insanity 라고 하자.

그러면, 이진 탐색을 통해 해당 값을 찾을 수 있다.

즉, 주어진 가중치 이하의 간선만 방문해서 산봉우리에 오를 수 있는지 확인하는 것을 반복하면, 쉽게 최소 insanity를 구할 수 있다.

그래프 탐색을 진행할 때, 산봉우리에 도달하면 큐에 넣지 않도록 잘 커팅해주면 쉽게 해결할 수 있다.

Q5
사용된 알고리즘: 덱
예상 난이도 (Solved.ac 기준): G3 ~ G2?

숫자를 일일이 옮기면 당연히 터진다!
하지만 덱을 사용하면 조금 여유있게 해결할 수 있다.

먼저, 맨 왼쪽 값과 맨 오른쪽 값을 저장하는 덱을 만들자.
또한, 나머지 값들을 저장하는 덱을 2차원으로 만들자. (C++ 기준, deque<deque<int>*>)

이후 다음과 같이 쿼리를 처리하면 된다.

- ShiftRow
왼쪽 큐와 오른쪽 큐는 데이터를 앞에서 빼고 뒤로 넣으면 된다.
나머지 큐의 경우, 내부 큐를 통째로 빼서 뒤로 넣으면 된다.

- Rotate
왼쪽 큐의 맨 앞의 데이터를 빼서, 나머지 큐의 첫번째 큐의 맨 앞에 넣는다.
나머지 큐의 첫번쨰 큐의 맨 뒤의 데이터를 빼서, 오른쪽 큐의 맨 앞에 넣는다.
아래쪽도 비슷하게 하자.

문제를 풀때, C++ 기준 deque<deque<int>> 로 하면 TLE가 떠서, deque<deque<int>*>로 바꿔서 풀었더니 맞았다.

 

☆추가☆

- 효율성 3개 빼고 다 맞았다고 아깝게 놓쳤다는 사람들이 주변에 한트럭이다. 딱 보니 대놓고 3개 TC로 저격한 것 같더라.

- 생각해보니 이 문제의 정해는 Linked List 같다. C++ deque 시간 커팅 최적화를 해서 뚫린거지, 다른 언어에서 deque을 썼으면 안 될 수도 있다.

 

<총평>
작년에 비해 1시간 늘어나서 좀 쫄았는데 솔직히 작년보단 안 어려웠던 것 같다...