엘리스 알고리즘 코드 챌린지

https://code-challenge.elice.io/explore

2023년에 시즌1 대회가 있었던것 같은데 참여도 안했고 정보도 없다.

2024년에 열린 시즌2 대회만 정리.

예선은 10일동안 매일 한문제씩 문제가 나오고, 그날 안에 정답을 제출하면 된다.

10일간의 예선이 끝나면, 상위 50명이 오프라인 본선에 진출한다.

본선 상품은 1등 300만원, 2등 맥북 프로 등등.. (어차피 본선에 나갈 생각은 없으니 관심없다..)

이번 대회의 참가 목표는 치킨 기프티콘이다. 아마 10문제 정답자가 그리 많지는 않을거 같고, 그러면 10문제 다 풀기만 하면 당첨 확률이 제법 있을거라는 생각..

그러면 매일 그날 자정 안에 한문제씩만 풀면 되니 그정도는 큰 부담 없이 할수 있으리라 생각했고, 매일 점심시간이나 퇴근 후나 아무때나 잠깐 짬날때 푸는 방식으로 진행했다.

문제를 읽는 순간 최근에 비슷한 문제를 풀었던것 같은 느낌이 들었다. 최근에 풀었던 문제들을 되돌아보며 찾아보니, 마라톤에서 풀었던 '인기가 넘쳐흘러'와 지문만 살짝 바뀐 동일한 문제라는 것을 알수 있었다.

그래서 인기가 넘쳐흘러의 코드를 제출했으나.. 백준에서는 통과되었던 코드가 여기에서는 오답처리가 되었다.. 잠시 디버깅을 거쳐서 원래 코드에서 빼먹었던 조건 체크를 추가해서 제출해서 통과..

일단 풀이는..

문제 불펌 이슈로 크게 화제가 된 다음날 나온 문제이다. 불펌 이슈가 있었으니 적어도 오늘 문제는 오리지널이겠지..

문제 자체는 굉장히 전형적인, 그리드에서의 최단 경로를 찾는 문제이다. 너무 전형적인 문제라서 표절 논란이 나올 여지 자체가 없다.

그리드를 일반적인 그래프로 변환해주기만 하면, 기본적인 최단 경로 알고리즘 (이 경우에는 다익스트라)를 사용해서 최단 경로를 바로 찾을 수 있다.

E가 두개이기 때문에, START → E1 → L → I → C → E2 의 최단 경로와 START → E2 → L → I → C → E1의 최단 경로 중에서 더 짧은 쪽을 답으로 처리하면 된다.

저 경로의 거리를 구하기 위해서는, 6개의 출발점에 대해서 각각 다익스트라를 돌려야 한다 (시작노드, E1, L, I, C, E2).

변환한 그래프에서 노드의 개수는 O(N^2), 엣지의 개수도 O(N^2)이므로, 다익스트라 알고리즘을 돌리는 데에는 O¹⁾이 걸린다.

문제 자체는 직관적인데, 어떻게 하면 예쁘게 짤지를 고민하다가 시간이 좀 걸렸다. 그리드를 가중치 없는 그래프로 변환하는 코드는 전에도 여러번 수정을 거쳐서 작성해놓은 라이브러리가 있었는데, 그리드를 가중치 있는 그래프로 변환할 경우에는 어떻게 라이브러리를 만들어야 예쁠지를 좀 고민하다가 우선은 그냥 어떻게든 돌아가는 코드를 짜서 제출하고, 라이브러리화 시키는 것은 나중에 고민하기로 했다.

오늘이 마지막 날인데, 이전날까지 만점자가 100명이 넘게 있었다. 어떻게든 최종 만점자를 줄이기 위해서는 마지막 기회라서 좀 어려운 문제가 나오지 않을까 예상.

(1)번을 사용하려면, 우선 원소를 추가/삭제할때마다 정렬된 컬렉션을 유지해야 한다. 이거는 tree set 등으로 O(logn)에 가능하다 쳐도, 모든 i에 대해서 확인하려면 O(n)이 걸리는걸 피할수 없다.

(2)번을 사용하는 쪽으로 생각하자. 원소 추가/삭제시 카운터를 업뎃하는거는 O(1)이다. 하지만 sum(count[1:x]) 를 구하는 것이 어려울것 같다. 차라리, 카운터가 아니라 카운터의 누적합을 유지하는 것은? 펜윅트리를 쓰면 O(logn)에 업데이트가 가능하다.

실제 예선문제를 풀때에는 여기까지 생각이 미친 다음에, 실제로 m 이라는 원소가 업데이트 되었을 경우, m보다 작은 값들에 대한 카운터의 누적합은 변하지 않으니까, sum(count[1:m]) 만 확인하면 되고, 이것도 펜윅트리로 O(logn)에 쿼리가 되므로 이제는 풀수 있겠다고 생각했다. 그리고 이렇게 구현해서 제출했다가 바로 오답을 한번 먹었다;

그렇다, sum(count[1:m])⇐m 인지 뿐만 아니라 sum(count[1:m+1])⇐m+1, sum(count[1:m+2])⇐m+2, sum(count[1:K])⇐K 를 모두 다 확인해야지 제대로 처리되는데 이것을 간과했다. 반례로는 3 4 3 4 3 4 가 있다.

count의 누적합에 초기값을 주어서 초기화하고, range add 로 갱신, range max 로 쿼리를 하는 레이지 세그트리를 쓰면 O(logn)업뎃, O(logn)쿼리가 가능하다

이제 이대로 구현. 제출해서 통과. 시간복잡도는 O(nlogn)

설마 진짜 레이지 세그가 정해라고? 뭔가 더 쉬운 방법을 놓친것 같기도 했지만 일단 통과했으니 넘어갔다

첫날부터 계속 예선 문제와 유사한 백준 문제가 커뮤니티에 올라오긴 했었다. 하지만, 문제 자체가 충분히 제너럴하기도 하고, 제한이나 이런 부분이 살짝 달랐기 때문에, 그냥 우연한 비슷함 내지는 기존 문제에서 모티베이션을 얻어서 만든 문제 정도로 여기고 넘어가기에 충분했다. 하지만 8일자의 '강림제' 문제에서 표절 논란이 크게 터졌다. 사실 표절이라기 보다도 그냥 무단 도용에 가까운 케이스인데, 단순히 문제가 원하는 솔루션이 동일한 수준을 넘어, 지문도 원 문제와 매우 유사했고 문제에서 주어지는 예제까지도 동일했다. 원 문제는 고등학교 대회에 올라왔던 문제. 그리고 인터넷을 검색하면 이미 코드까지 공개된 풀이도 있었다.

결국 이슈가 커지고, 다음날 엘리스측에서 표절을 인정하고 사과 공지를 올리면서 일단락.

Day 10 에서 정해가 레이지 세그인 꽤 난이도 있는 문제를 출제했지만, 의도한건지는 모르겠지만 제한시간이 너무 여유있게 주어진 나머지 실제로는 꽤나 나이브한 O(n^2logn) 알고리즘도 통과하게 되었다. 그래서, 최종적으로 10문제를 모두 맞춘 참가자의 수는 101명.

원래는 각종 지표를 이용해서 50명을 선별하겠다는 이야기가 있었으나, 내부적으로는 최대한 만점자들은 본선에 모두 초대하는 방향으로 가닥을 잡은것 같았다. 월요일에 만점자들에게 본선 참석여부를 묻는 전화가 왔다. 물론 내게도 왔고, 모두 초대하고 싶으나 장소가 80명까지 들어갈수 있기 때문에 참석 여부를 물어보는 중이라고 했다. 참석하겠다고 한 사람이 80명 이내라면 모두 초대하고, 그렇지 않으면 제출횟수나 여러가지 지표를 이용해서 거를듯..

다음날, 만점자는 전원 본선에 초대한다는 공지가 올라왔다. 전화 돌려서 확인해본 결과, 참석하겠다고 대답한 수가 수용 가능한 인원 이내였나보다.

그리고, 나의 목표였던 치킨 쿠폰도 도착했다. 굳굳