[2021-02-03 추가] 풀이 영상 업로드합니다. 코드와 슬라이드 파일은 여기서 확인 가능합니다.

------

제 코드를 함께 남기고 싶지만 코딩테스트 진행중에 문의를 해보니 프로그래머스를 통해 공식적으로 문제가 공개되기 전에는 문제를 제외하고 자신의 정답 코드만 업로드하는 것도 허락하지 않는다는 답변을 받아서 자세한 풀이와 코드는 공식적으로 문제가 공개된 이후에 업로드할 수 있겠습니다.

대신 저작권을 침해하지 않는 선에서 총평을 해보면 일단 카카오의 코딩테스트는 확실히 굉장히 넓은 범주에서 출제되고 구현의 난이도가 상당함은 물론 요구하는 지식 또한 일부 문제는 학부 알고리즘 수업만으로 커버가 안됩니다. 물론 그렇다고 해도 어디까지나 코딩테스트이니 꾸준하게 PS 분야를 공부했다면, 구체적으로는 코드포스 기준 블루 상위권(대략 1800+)이면 그럭저럭 올솔브를 하거나 한 문제정도 삐끗할 것 같습니다.

하지만 알고리즘을 이전에 공부한 적이 없거나, 공부를 했더라도 삼성 A형 느낌의 시뮬레이션 문제만 계속 풀어보셨다면 이번 시험이 굉장히 어려웠을 것 같습니다. 지금 노베이스라고 칠 때 이정도 난이도의 코딩테스트에서 간신히 턱걸이로 통과를 해내는 수준을 넘어서서 합격을 장담할 수 있는 정도의 실력을 가지려면 뛰어난 재능을 가진게 아닌 이상 6개월 정도는 필요해보입니다.

또한 문자열 처리를 할 땐 python이 편한데 전반적으로 시간이 타이트할 것 같은 문제도 있어 C++이 필요할 것 같아보이는 문제도 몇 개 있었습니다(첨언하자면 정해로 풀었으면 python으로 짜든 C++로 짜든 통과될테지만 비효율적으로 구현했을 때 python로는 시간초과가 발생하지만 C++로는 통과되는 요행을 바랄 수 있습니다).

이제 문제를 한 번 짚어보겠습니다. 아래의 난이도는 백준 온라인 저지의 문제 티어를 참고해 제가 뇌피셜로 붙인 난이도입니다.

1번

알고리즘 분류 : 문자열, 구현

난이도 : B1-S4

곧이곧대로 구현을 하면 되는 문제였습니다. 웬만하면 파이썬으로 푸는게 정신건강에 이로워보입니다.

2번

알고리즘 분류 : 정렬, 브루트 포스

난이도 : S2-G5

구현 방법은 여러가지이지만 가능한 모든 조합을 만들어내고 C++ map 혹은 python의 dict 등을 이용해 개수를 세는 방식이 무난해보입니다. 구현 방향을 잘못 잡으면 코드가 산으로 갈 것 같습니다.

3번

알고리즘 분류 : 이분 탐색

난이도 : S2-G5

정확성은 아마 그냥 곧이곧대로 구현하면 받을 수 있을 것 같고 효율성은 미리 정보를 리스트에 다 담아둔 후에 쿼리가 들어올 때 마다 이분 탐색을 수행하는 방법으로 구현할 때 통과될 수 있습니다. 정보를 리스트에 담을 때 "적당한 처리"를 미리 해두면 매 쿼리마다 여러 리스트를 볼 필요 없이 한 개의 리스트만 보면 됩니다. PS 공부 경험이 많지 않다면 이 "적당한 처리"를 떠올리기가 힘들지 않았을까 싶습니다.

4번

알고리즘 분류 : 플로이드 or 다익스트라

난이도 : G5-G4

그래프 최단거리 문제를 조금만 풀어봤다면 문제의 풀이를 거의 보자마자 알 수 있고 그렇지 않더라도 플로이드 알고리즘 or 다익스트라 알고리즘을 알고 있었다면 코딩 테스트 시간 내에는 풀이를 유추해낼만 할 것 같습니다.

플로이드 알고리즘 혹은 다익스트라 알고리즘 3번으로 문제를 해결할 수 있고 n이 작기 때문에 마음 편하게 플로이드 알고리즘으로 구현을 하는게 나아보입니다. 중급(?) 알고리즘이 쓰여서 난이도는 G5-G4로 두었지만 플로이드 or 다익스트라를 안다는 가정 하에 2번, 3번보다 구현이 더 쉬웠습니다.

5번

알고리즘 분류 : 투 포인터

난이도 : G2

2017년 카카오 블라인드 채용 1차에 비슷한 문제가 있는데 그 문제에서 난이도를 엄청 뻥튀기해두었습니다. 구현 난이도도 그럭저럭 높았기 때문에 투 포인터를 몰랐다면 아예 손을 못댔을 것이고 이 문제가 투 포인터로 해결 가능한 문제임을 알았다고 해도 많이 짜보지 않았다면 구현에 실패했을 가능성이 높아 보입니다.

6번

알고리즘 분류 : BFS, 시뮬레이션, 브루트 포스, DP

난이도 : G3

삼성 A형같은 느낌의 문제였습니다. 푸는 법은 가양각색이겠지만 저는 미리 카드를 지워갈 순서를 정해두고 해당 순서대로 카드를 지울 때 필요한 조작 횟수를 계산했습니다. A형 유형을 많이 풀어보신 분은 알겠지만 이런 유형의 문제에서 전수조사를 하는 대신 자신이 보기에 좋아보이는 방법으로(ex : 가장 가까운 카드부터 방문하기) 구현을 하면 아마 틀릴 것입니다.

7번

알고리즘 분류 : 트리 DP

난이도 : G2

제가 알기로는 카카오에서 트리 DP를 낸 적이 없던 것 같은데 처음으로 나왔네요. 학부 알고리즘에서 트리 DP를 다루지는 않을거라 기존에 알고리즘을 공부한 사람이 아니었다면 이 문제를 풀어낼 수 있는 가능성이 거의 없었습니다. 다만 전형적인 트리 DP 문제이고 구현이 복잡하지는 않아서 푸는 입장에서는 편했습니다.

선수 지식이 어느정도였냐에 따라 생각은 다 다르겠지만 제 생각에 문제의 난이도 순은 1 < 2 < 3 < 6 < 4 < 7 < 5 이고 알고리즘 지식이 부족했다면 1, 2, 3(정확성만), 6 까지가 최선일 것 같습니다.

카카오 신입개발자 블라인드 채용이 독보적으로 어려운 편이니 오늘 코딩테스트를 잘 못치셨다고 해도 너무 실망하지 마시고 계속 정진합시다..!!