ps:엘리스_알고리즘_코드_챌린지
목차
엘리스 알고리즘 코드 챌린지
- 2023년에 시즌1 대회가 있었던것 같은데 참여도 안했고 정보도 없다.
- 2024년에 열린 시즌2 대회만 정리.
방식 및 상품
- 예선은 10일동안 매일 한문제씩 문제가 나오고, 그날 안에 정답을 제출하면 된다.
- 예선에도 상품을 준다
- 매일 선착순 3명, 추첨 3명에게 스벅 기프티콘
- 10문제 정답자 50명 추첨해서 치킨 기프티콘
- 10일간의 예선이 끝나면, 상위 50명이 오프라인 본선에 진출한다.
- 본선 상품은 1등 300만원, 2등 맥북 프로 등등.. (어차피 본선에 나갈 생각은 없으니 관심없다..)
예선
- 이번 대회의 참가 목표는 치킨 기프티콘이다. 아마 10문제 정답자가 그리 많지는 않을거 같고, 그러면 10문제 다 풀기만 하면 당첨 확률이 제법 있을거라는 생각..
- 매일 주는 스벅 기프티콘은 사실상 포기
- 선착순 3등을 노리기에는, 문제가 공개되는 10시에 바로 문제를 풀어야 하는데 그러기에는 여건이 안됨
- 추첨을 노리기에는, 당첨 확률이 희박할거라 예상
- 그러면 매일 그날 자정 안에 한문제씩만 풀면 되니 그정도는 큰 부담 없이 할수 있으리라 생각했고, 매일 점심시간이나 퇴근 후나 아무때나 잠깐 짬날때 푸는 방식으로 진행했다.
Day 1
Day 8 - 강림제
- 문제를 읽는 순간 최근에 비슷한 문제를 풀었던것 같은 느낌이 들었다. 최근에 풀었던 문제들을 되돌아보며 찾아보니, 마라톤에서 풀었던 '인기가 넘쳐흘러'와 지문만 살짝 바뀐 동일한 문제라는 것을 알수 있었다.
- 그래서 인기가 넘쳐흘러의 코드를 제출했으나.. 백준에서는 통과되었던 코드가 여기에서는 오답처리가 되었다.. 잠시 디버깅을 거쳐서 원래 코드에서 빼먹었던 조건 체크를 추가해서 제출해서 통과..
- 일단 풀이는..
Day 9 - 격자 위의 ELICE
- 문제 불펌 이슈로 크게 화제가 된 다음날 나온 문제이다. 불펌 이슈가 있었으니 적어도 오늘 문제는 오리지널이겠지..
- 문제 자체는 굉장히 전형적인, 그리드에서의 최단 경로를 찾는 문제이다. 너무 전형적인 문제라서 표절 논란이 나올 여지 자체가 없다.
- 그리드를 일반적인 그래프로 변환해주기만 하면, 기본적인 최단 경로 알고리즘 (이 경우에는 다익스트라)를 사용해서 최단 경로를 바로 찾을 수 있다.
- 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)이므로, 다익스트라 알고리즘을 돌리는 데에는 O1)이 걸린다.
- 문제 자체는 직관적인데, 어떻게 하면 예쁘게 짤지를 고민하다가 시간이 좀 걸렸다. 그리드를 가중치 없는 그래프로 변환하는 코드는 전에도 여러번 수정을 거쳐서 작성해놓은 라이브러리가 있었는데, 그리드를 가중치 있는 그래프로 변환할 경우에는 어떻게 라이브러리를 만들어야 예쁠지를 좀 고민하다가 우선은 그냥 어떻게든 돌아가는 코드를 짜서 제출하고, 라이브러리화 시키는 것은 나중에 고민하기로 했다.
- 라이브러리화 시킬때 고민
- 그리드를 가중치 있는 그래프로 변환할 때에는, 가중치를 주는 방식이 딱 정해진건 아닌데 어떻게 해결할지 (boj 4485 참고)
- 이렇게 같은 그래프를 가지고 다익스트라를 여러번 돌릴때에는 implicit 그래프가 아니라 explicit 그래프로 만들어 놓는 것이 더 효율적일수도 있는데 그것을 어떻게 처리할지.
Day 10 - 계단 카드 뽑기
- 오늘이 마지막 날인데, 이전날까지 만점자가 100명이 넘게 있었다. 어떻게든 최종 만점자를 줄이기 위해서는 마지막 기회라서 좀 어려운 문제가 나오지 않을까 예상.
- '조건을 만족하는 부분배열중 가장 길이가 큰 것을 찾는 문제' 에 해당하는데, 이것은 보통 투포인터를 써서 풀리는 유형이 많다.
- 엄밀하게는, 부분배열을 특정 상태값으로 표현할때, (1)어떤 상태가 조건을 만족하는지를 체크하는 연산, (2)부분배열에 원소를 추가할때 상태를 업데이트하는 연산, (3)부분배열에서 원소를 삭제할때 상태를 업데이트하는 연산들을 빠르게 처리할수 있다면, 투포인터가 효율적이다.
- (1),(2),(3)을 처리하는 시간 O(T)라면, 총 O(NT)에 최대 부분배열을 찾을 수 있다.
- 이 문제에서, 주어진 부분배열이 조건을 만족하는지 여부는 체크하는 방법을 생각해보자. 예시를 들어 생각해보면, 1이 두장 이상 있으면 안된다. 1이나 2가 합쳐서 3장 이상 있으면 안된다, … 일반화하면, x이하 숫자가 x개보다 많이 있으면 안되고, 그런 경우가 없으면 조건을 만족시킨다. 이걸 체크하는 방법은 대충 두가지가 떠오른다
- 1) K개의 숫자들을 정렬시킨다. 모든 i에 대해서 a[i]>i 이면 만족한다 (i는 0-indexed)
- 2) K개의 숫자들에 대한 카운터를 만든다. 모든 x⇐K에 대해서, count[0]+count[1]+…+count[x] ⇐ x 이면 만족한다.
- (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 가 있다.
- 작전을 바꾼다. 이것을 모두 체크하는 것을 한번에 처리하기 위해, 식을 이런식으로 변형해보자
- sum(count[1:m])-m ⇐ 0 && sum(count[1:m+1])-(m+1) ⇐ 0 && sum(count[1:m+2])-(m+2) ⇐ 0 ….
- =⇒ max(sum(count[1:m])-m, sum(count[1:m+1])-(m+1), sum(count[1:m+2])-(m+2)) ⇐ 0
- count의 누적합에 초기값을 주어서 초기화하고, range add 로 갱신, range max 로 쿼리를 하는 레이지 세그트리를 쓰면 O(logn)업뎃, O(logn)쿼리가 가능하다
- 이제 이대로 구현. 제출해서 통과. 시간복잡도는 O(nlogn)
- 설마 진짜 레이지 세그가 정해라고? 뭔가 더 쉬운 방법을 놓친것 같기도 했지만 일단 통과했으니 넘어갔다
- 나중에 후기로는, 더욱 나이브한 방법들도 시간 안에 돌아갔다는 이야기를 들었다 (하지만 이건 c언어에나 해당되는 이야기이지 파이썬은 안됐을 것이다)
- 투포인터를 쓰되, K개의 숫자들을 정렬시키고, 모든 i에 대해서 a[i]>i 이면 만족하는지를 체크하는 방법 → 심지어 그냥 정렬된 배열에서 원소 추가/삭제를 O(n)에 처리해서 총 O(n^2)에 한것도 아니고, 추가되는 원소를 매번 정렬을 다시 해서 O(n^2logn)에 돌렸지만 돌아갔다고 한다.
- 투포인터를 쓰지 않고, K를 고정한후, 슬라이딩 윈도우로 해당되는 배열이 있는지 O(n^2)에 찾고, 이분탐색으로 K값을 찾는 방법. 역시 총 O(n^2logn)
문제 무단 도용 논란
- 첫날부터 계속 예선 문제와 유사한 백준 문제가 커뮤니티에 올라오긴 했었다. 하지만, 문제 자체가 충분히 제너럴하기도 하고, 제한이나 이런 부분이 살짝 달랐기 때문에, 그냥 우연한 비슷함 내지는 기존 문제에서 모티베이션을 얻어서 만든 문제 정도로 여기고 넘어가기에 충분했다. 하지만 8일자의 '강림제' 문제에서 표절 논란이 크게 터졌다. 사실 표절이라기 보다도 그냥 무단 도용에 가까운 케이스인데, 단순히 문제가 원하는 솔루션이 동일한 수준을 넘어, 지문도 원 문제와 매우 유사했고 문제에서 주어지는 예제까지도 동일했다. 원 문제는 고등학교 대회에 올라왔던 문제. 그리고 인터넷을 검색하면 이미 코드까지 공개된 풀이도 있었다.
- 결국 이슈가 커지고, 다음날 엘리스측에서 표절을 인정하고 사과 공지를 올리면서 일단락.
예선 이후
- Day 10 에서 정해가 레이지 세그인 꽤 난이도 있는 문제를 출제했지만, 의도한건지는 모르겠지만 제한시간이 너무 여유있게 주어진 나머지 실제로는 꽤나 나이브한 O(n^2logn) 알고리즘도 통과하게 되었다. 그래서, 최종적으로 10문제를 모두 맞춘 참가자의 수는 101명.
- 원래는 각종 지표를 이용해서 50명을 선별하겠다는 이야기가 있었으나, 내부적으로는 최대한 만점자들은 본선에 모두 초대하는 방향으로 가닥을 잡은것 같았다. 월요일에 만점자들에게 본선 참석여부를 묻는 전화가 왔다. 물론 내게도 왔고, 모두 초대하고 싶으나 장소가 80명까지 들어갈수 있기 때문에 참석 여부를 물어보는 중이라고 했다. 참석하겠다고 한 사람이 80명 이내라면 모두 초대하고, 그렇지 않으면 제출횟수나 여러가지 지표를 이용해서 거를듯..
- 다음날, 만점자는 전원 본선에 초대한다는 공지가 올라왔다. 전화 돌려서 확인해본 결과, 참석하겠다고 대답한 수가 수용 가능한 인원 이내였나보다.
- 그리고, 나의 목표였던 치킨 쿠폰도 도착했다. 굳굳
1)
N^2)logN
ps/엘리스_알고리즘_코드_챌린지.txt · 마지막으로 수정됨: 2024/07/24 08:01 저자 teferi
토론