지난 11월 12일 LG CNS 에서 진행한 코드몬스터 채용연계형 대회에 참가한 후기입니다.
이 대회를 통해 예선과 본선을 거쳐 최종면접만으로 취직이 가능하고, 무려 2년까지도 유예기간으로 기다려주겠다는 다른 곳에서는 볼 수 없는 혜택이 주어집니다.
얼마전 카카오 기술면접에서 쓴맛을 본 입장에서, 또 졸업까지 1년 이상 남아있는 입장에서 정말 매력적인 조건이 아닐 수 없습니다.
현재 글은 본선의 후기가 아닌 예선후기입니다.
예선 전반에 관하여
문제는 4문제, 시간은 3시간이 주어졌습니다.
특이하게도 시간복잡도를 주요 평가대상으로 여기지는 않는 것으로 보입니다.
4문제 모두 동일하게 시간제한이 10초로 되어있었습니다.
문제내용 상 10초가 필요할 만큼 범위가 넓거나 시간복잡도가 크지도 않았습니다.
문제의 전반적인 느낌은 다른 대회들보다 브루트포스를 중심으로 풀어나가야 한다는 것이었습니다.
제 경우에는 4문제 모두 예제 테스트케이스는 통과했지만, 전체 테스트케이스 채점결과는 공개되지 않았기 때문에 실제로 얼마나 맞추었는지는 알 수 없었습니다.
그래도 예선은 통과했으니 어느 정도는 맞춘 것 같습니다.
문제의 내용은 공개하지 못하게 되어있기 때문에 간략한 설명으로만 갈음하도록 하겠습니다.
또한 제대로 맞추었는지 확인도 불가능했기에 난이도 표기는 하지 않았습니다.
1번문제
구슬을 배치하는 문제였습니다.
배치에 대한 우선순위 조건이 몇가지 주어졌습니다.
처음에는 그리디 문제라고 생각해서 규칙을 발견하기 위해 시간을 썼습니다만..
시간제한이 10초에다가 문제 조건의 범위가 매우 작다는 것을 뒤늦게 확인했습니다.
그래서 next_permutation 을 활용한 조합을 이용하여 브루트포스로 문제를 해결했습니다.
2번문제
다수의 멀티탭에서 전력제한에 맞게 전자기기를 제거하는 문제였습니다.
멀티탭의 연결구조는 트리구조로 생각할 수 있었습니다.
먼저, 자식노드에서부터 부모노드로 올라가며 멀티탭에 걸리는 부하를 계산했습니다.
이후 제거할 기기 개수 계산도 비슷하게 자식노드에서 부모노드로 올라갔고, 다만 최대값으로 갱신하며 계산했습니다.
3번문제
부분문자열 연속매칭 시 최소길이의 최대값을 구하는 문제였습니다.
unordered_set 을 이용하여 레퍼런스 문자열의 모든 subsequence 를 해싱해둔 후에, DP로 처리하여 계산했습니다.
그리고 항상 고민되는 부분이지만, unordered_set 과 set 에서 고민을 많이 했습니다.
일반적으로 unordered_set이 set보다 빠른 것으로 알려져 있지만, 코드포스에서 문제를 풀면서 알게 된 것은 set 이 더 빠른 경우도 많다는 것입니다.
더 자세히 공부해야할 것 같지만, 일단은 C++ STL 의 set 은 문자열 길이가 길어지면 해싱함수가 더 복잡해지는 것으로 알고 있고, 개수가 많아져 해시충돌이 빈번해지면 레드블랙트리로 구성된 set이 더 효율적으로 작동한다고 알고 있습니다.
당시에는 그냥 unordered_set 을 이용했지만 어느 것을 사용하는게 맞았는지 아직도 잘 모르겠습니다..
4번문제
루트노드에 따라 부모자식역전현상 횟수를 구하는 문제였습니다.
"부모-자식" 관계를 배열로 저장해두었고, 루트노드에서 BFS 돌려서 역전 횟수를 계산했습니다.
본선일정
본선은 11월 26일 마곡에 위치한 LG 사이언스파크에서 오프라인으로 진행된다고 합니다.
대회 오프라인 참가가 처음이기도 하고, 본선 참가 축하 상품을 지급한다고 하는데 어떤 것일지 기대됩니다.
본선에서는 테스트케이스 통과여부 정도는 알 수 있게 해주면 좋을 것 같습니다.
