2022 하반기 쿠팡 공채 코딩테스트에 응시해보았다!
전형 절차는 위와 같다.
쿠팡은 신기하게도 온라인 코딩테스트 합격자에 한해 포트폴리오를 받는다고 한다.
알고리즘을 중요하게 여기는 쿠팡답다고 생각했다.
주의할 점은, 서류 접수 시기에 탈락한 분들도 일부 존재하는 것으로 확인된다는 점.
접수한 사람들 모두 코딩테스트를 치는 것은 아닌 것 같으니 서류접수를 대충 해선 안될 듯하다.
코딩테스트를 꼭 한번 응시해보고 싶었는데 다행히 나는 코테 응시 자격을 획득할 수 있었다.
서류 접수 란에 이력서를 제출했고, 자기소개서는 별도로 제출하지 않았다.
예전에는 해커랭크에서 진행된 것으로 알고 있는데, 이번에는 프로그래머스에서 진행하는 듯하다.
코딩테스트 환경
- 프로그래머스
- 3시간 알고리즘 4문항
- 사용가능언어: C, C++, Java, Javascript, Kotlin, Python3, Swift
- 이 테스트에서는 외부에서 작성한 코드를 복사하여 붙여넣을 수 없습니다. 코드는 반드시 테스트 자체 코드 에디터에 직접 작성해주세요. (사실상 IDE 사용불가)
- 응시 중 인터넷 및 교재 참고는 불가능합니다.
- 정답 여부 미공개 (예제 테스트케이스만 제공)
- 화면공유 필수
- 모니토앱을 활용한 웹캠 필수
- 신분증 준비 필수
- 감독관에게 책상 검사 맡음
외부 IDE 사용 불가하고, 정답 여부를 안알려준다는 점, 구글링 및 교재 참고 불가한 점을 명심하자.
주관적인 난이도 후기
정답 여부를 알 수 없어 확실하지는 않고, 체감 난이도를 간단하게 적어보도록 하겠다.
| 체감 난이도 | 사용 알고리즘 | |
| 1번 | Silver V | 구현, 시뮬레이션, 수학 |
| 2번 | Silver I | dp, 이분탐색 |
| 3번 | Gold IV | bfs, dfs, 이분탐색 |
| 4번 | Gold V | 백트래킹, 자료구조 |
간단한 후기를 남겨보도록 하겠다. 문제가 된다면 비공개 처리 예정.
1번.
범위가 매우 작기 때문에 단순히 시뮬레이션으로 구현해도 맞는 문제이다.
다만, 배팅 금액이 현재 남은 금액보다 크면 안된다는 예외처리를 조심해야 한다. 다행히 이 부분이 친절하게 테스트케이스로 제공이 돼있기 때문에 이 부분으로 WA를 받는 사람은 거의 없을 듯하다.
비트마스킹 성질을 이용해 조금 더 응용하자면, 사실 배팅에 성공하기만 하면 무조건 100원 이득이다!
배팅에서 쭉 지다가 이길 경우, 100000 ... 0(2) - 011111 ... 1(2) = 1 이라는 성질을 떠올리면 된다.
이렇게 하면 expected[i]==actual[i]의 index가 같은 경우까지 도달 거리를 이용하여 더 빠르게 답을 구할 수 있... 긴 하지만! 쿠팡 코테의 경우 정답여부를 안알려주는데다가, 뒤에 문제가 얼마나 어려울지 예상이 안되는 상황이었다. 그렇기 때문에 이런 기교(?)는 펼치지 않고 확실한 시뮬레이션 코드를 제출했다.
외부 IDE 사용이 불가했기 때문에, 이 문제를 풀면서 #include<bits/stdc++.h>, #define all(v) (v).begin(), (v).end()와 같은 축약 표현 템플릿들을 코드에 작성해놓았다. 프로그래머스 IDE 간에 복붙은 가능하기 때문에, 해당 문제에서 템플릿을 꼼꼼히 짜놓은 후 2번~4번까지 템플릿을 복붙하는 작업을 거쳤다.
2번.
되게 문제가 knapsack dp처럼 생겼다. 하지만, 전혀 그럴 필요가 없는 문제.
knapsack dp로 접근하면 한없이 어려워진다. 단순히 cost를 최대로 해야될 뿐 아니라, 시작일시와 종료일시 사이에 있는 작업들이 겹치지 않게 해야되기 때문이다.
dp식을 현재일자 기준으로 최대로 벌 수 있는 cost로 두면, 탑다운이나 바텀업 dp로 요리조리 풀어주면 된다.
시작일자와 종료일자를 고려하기 위해 해당 작업들을 시간 순으로 정렬한 후, 이분탐색을 이용하여 어느 작업부터 가능한지 찾아주는 작업을 O(logN)에 해도록 했다.
이렇게 한 후, 해당 작업들을 탐색하여 가장 cost가 큰 경우를 dp로 리턴하게 했다.
범위가 작다고 백트래킹 풀이를 떠올릴 확률도 있을 듯한데, O(15!)은 매우 큰 시간복잡도이기 때문에 아마 시간초과가 나는 풀이일 것이다.
다만, 적절히 최적화했다면 문제없을수도? 아마 순서가 상관없고 겹치는지 여부만 잘 체크하는 방식으로 O(2^15 * 상수)로 했다면 문제없을 것 같다.
3번.
개인적으로는 가장 어렵다고 생각되는 문제.
우선 섬이 연결돼있는지는 BFS로 찾으면 된다.
특정 값 이상이면 문제 조건에 만족하는 단조함수꼴을 그리기 때문에, 그리고 L값이 10^9로 매우 크기 때문에 이분탐색이 반드시 필요하다. 이분탐색을 사용하지 않으면 아마 시간초과가 날 것이다.
문제는 특정 섬들의 지역이 그 주위에 더 높은 지역이 있으면 가라앉지 않는다는 점이다.
이 부분때문에 체감난이도가 급증했을 듯.
주위에 더 높은 지역이 있으면 가라앉지 않으므로, 역발상으로 해수면이 외부에서부터 흘러온다고 가정하자. 외부에서 섬이 가라앉는 부분이 있다면, 그 부분들로부터 DFS 탐색을 시작하여 가라앉는 섬들을 찾아주고 더 이상 해수면이 갈 곳이 없으면 멈춰주면 된다. 주의할 점은 DFS 탐색할 때 높이가 자기 자신보다 낮은 섬으로 탐색하는 것이 아닌, 해수면보다 낮거나 같은 상하좌우 연결된 섬들은 모조리 탐색시켜야된다는 점이다. 그렇지 않으면 WA를 받게 된다.
4번.
신기한 체스말 문제.
왜 ps 문제들은 항상 체스판가지고 장난치는걸까...? 🧐
룩나이트는 점프도 가능하기 때문에 파손된 지역이 있어도 이동이 가능하다.
즉, 같은 행 및 열에는 절대 중복해서 체스말을 놓을 수 없다.
또, 나이트 이동영역에도 당연히 말을 놓을 수 없다.
그렇기 때문에 자료구조 set을 이용해서 체스말이 존재하면 해당 행/열에는 말을 놓지 않는 방식으로 진행했고, 최대 x, y축의 크기가 9이기 때문에 백트래킹으로 적절히 전처리하였다.
참고로 시작점을 모든 행 또는 열로 다 세팅해놓을 필요는 없다.
또, 시작점이 특정 행/열에 아예 존재하지 않는 경우가 있을까 걱정할 수 있는데, N개의 룩나이트를 모두 배치해야 하므로 모든 행(또는 열)에는 반드시 체스말이 존재해야 한다.
이 문제의 경우 혹시나 시간초과가 날까봐 N=9, 파손된 구역 한 곳을 임의로 두고 테케를 돌려봤는데 다행히 답이 빠르게 나와서 안심했다. (하지만 정답 여부를 모르니 AC라고 단언할 순 없다...)
정답 여부를 알 수 없는 코테는 항상 피말리는 듯하다.
결과를 알 수 없기 때문.
게다가, 외부 IDE 사용이 불가능해서 디버깅을 못한다는 점이 꽤 힘들었다.
자꾸 3번 문제에서 의도하지 않은 이상한 답을 리턴해버리기 때문에 고생 좀 했다 ㅋㅋ
이후에 다행히 문제점을 발견해서 수정하긴 했지만, 정답 여부를 모르기 때문에 AC인지는 두고봐야될 일.
아무튼 쿠팡 코테도 이렇게 끝났다.
꾸준히 알고리즘 문제풀이를 해야되겠다는 필요성을 느끼는 날이었다 :)
+) 22.11.25.(금) 추가
탈락 메일을 받았다.
여러 가지 이유가 있겠지만, 서류 질 부족 or 코딩테스트 실채점 점수 or 미졸업 (현재 2학년) 세 가지 원인 중에 주된 원인이 포함돼있지 않을까 추측해본다.
앞으로 꾸준히 공부해서 실력을 보완해야겠다 :)
'PS > My Diary (PS, 대회후기)' 카테고리의 다른 글
| [231104] KUPC 2023 참가 후기 (38) | 2023.11.08 |
|---|---|
| [221203] KUPC 2022 출제 및 운영 후기 (16) | 2022.12.03 |
| [221008] 2023 KAKAO BLIND RECRUITMENT 코딩테스트 2차 후기 (16) | 2022.10.08 |
| [221001] 2022 Dev-Matching: 웹 백엔드 개발자(하반기) 데브매칭 코딩 테스트 후기 (2) | 2022.10.01 |
| [220924] 2023 KAKAO BLIND RECRUITMENT 코딩테스트 1차 후기 (25) | 2022.09.24 |