2021 카카오커머스 백엔드 개발자 공개채용 1차 코딩테스트 후기
어... 아무래도 코딩테스트에 썩 적합하지 않은 언어들만 가능해서 그런지 (데이터 분석 분야를 제외하면, FE - JS, BE, Android, iOS - Java, (일부 Kotlin) iOS - Swfit) 난이도 자체는 어렵게 나오지 않았다.
덕분에 25분컷...
다만 기존 카카오 코딩테스트와 달리 채점 결과를 보여주지 않기 때문에, 함정 문제가 있었다는 것은 주의해야 할 것 같았다.
#1
Topic: 카운팅 정렬을 약~~~간 변형한 값 담기
예상 난이도 (Solved.ac 기준): S5 ~ S4
상품을 바꾸는거에 초점을 맞추지 말고, 자기가 원하는걸 못 받는 사람들에 포커스를 맞춰보자.
바꾸는건 자기들 알아서 할테고, 어떻게든 열심히 바꾸면 존재하는 선에선 잘 바꿀 수 있을 것이다.
즉, 주어진 물건의 수와 사람들이 갖고 있는 물건의 수의 차를 구하면 끝나는 문제다.
따라서 물건의 번호가 1~100000이니 100001 크기의 배열을 만들어주고, (0번부터 시작하니까 하나 늘려주면 좋다...) 각 인덱스에 대응하는 값을 "그 번호가 붙은 물건의 갯수"라고 생각하면 쉽게 해결 가능하다.
#2
Topic: 백트래킹, 브루트포스
예상 난이도 (Solved.ac 기준): S4 ~ S3
(주의: 예시를 하나만 줘서 "그냥 부품 수 많은 것 부터 그리디로 처리하면 안될까?" 싶을 수도 있지만, 그러면 큰일남!!! needs: [[1, 0, 1], [1, 0, 1], [1, 0, 1], [1, 0, 1], [1, 0, 1], [0, 1, 0]], r = 1이면?)
부품의 수는 최대 15개이다.
모든 경우를 탐색하기 위해 가장 최악의 경우를 살펴본다면, 15C7 = 6,435고, 물건의 최대 갯수는 1,000개이므로 그냥 모든 경우를 탐색해도 시간적으로 여유롭다는 것을 깨달을 수 있을 것이다.
#3
Topic: 그래프 탐색
예상 난이도 (Solved.ac 기준): G5 ~ G4
DP로 풀려고 접근할 수도 있을 것 같은 문제다.
근데 문제를 꼼꼼~~~히 읽어보자. "서로 다른 두 역 사이의 이동 경로는 딱 한가지" 라고 적혀있는데, 이게 무슨 의미인지 간파하는게 중요한 문제다.
결론만 말하면, 그래프 탐색 딱 한번 하면 끝난다. 감으로 푼 분도 계시겠지만, 이유를 한 번 알아보자.
빨간점에서 시작해서 다른 빨간점으로 가려고 한다. 그런데 문제에서는 "서로 다른 두 역 사이의 이동 경로는 딱 한가지"라고 이야기 하고 있다.
만약 그래프에 사이클이 있으면 어떻게 될까?
어차피 모든 점에서 테스트를 해야하므로, 사이클 내부에 저 두점이 포함되어 있다고 가정하자.
그렇다면 다음과 같이 도달 가능한 경로가 2가지가 되므로, 문제의 조건에 성립하지 않는다.
즉, 문제에서 주어지는 그래프는 사이클이 없는데, 무방향 그래프이므로 아예 트리라고 부를 수 있다.
결국, 1번을 루트로 하는 트리 구조에서의 탐색을 요구하는 문제로 바뀐다.
DP를 왜 쓸까? 중복된 값을 여러번 계산하는 것을 방지하기 위해 사용한다고 들었을 것이다.
그렇지만 이 문제의 경우 방문 순서에 따라 값이 달라지는 경우가 없으므로, 그냥 딱 한번 그래프 탐색을 돌면서 그 역을 지나갈때의 승객 수를 (이 역을 이용하는 승객 수 + 자기 부모의 승객 수) 로 세주면 한 방에 해결된다.