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개가 된다.

 

그렇다면 다음과 같이 도달 가능한 경로가 2가지가 되므로, 문제의 조건에 성립하지 않는다.

즉, 문제에서 주어지는 그래프는 사이클이 없는데, 무방향 그래프이므로 아예 트리라고 부를 수 있다.

결국, 1번을 루트로 하는 트리 구조에서의 탐색을 요구하는 문제로 바뀐다.

 

DP를 왜 쓸까? 중복된 값을 여러번 계산하는 것을 방지하기 위해 사용한다고 들었을 것이다.

그렇지만 이 문제의 경우 방문 순서에 따라 값이 달라지는 경우가 없으므로, 그냥 딱 한번 그래프 탐색을 돌면서 그 역을 지나갈때의 승객 수를 (이 역을 이용하는 승객 수 + 자기 부모의 승객 수) 로 세주면 한 방에 해결된다.