엘리스 알고리즘 코드 챌린지, 예선 후기 및 문제 풀이

정보

기간 한정이긴 하지만 사이트에서 문제와 풀이를 공유하고 있기 때문에 적어도 된다고 생각하여 적는다

"오프라인 본선: 외부 IDE, 라이브러리 사용 가능, 인터넷 검색 불가능. 온라인 예선: 제한 없음"이라고 명시한 걸 보면 ide, 라이브러리는 그렇다 치고 인터넷도 모두 써도 된.....다고 해석할 수 있기는 하지만 아무튼 안 될 듯하다.

제출을 누르면 20점*5문제(1, 2, 3일), 10점*10문제(4, 10일), 6.6점*15문제(9일), 5점*20문제(8일), 4점*25문제(5, 6, 7일)에 대해 채점이 이루어진다. "본선 진출자는 2주 동안 10문항을 모두, 공개된 당일 날에 해결한 참여자들 중에 선정되며, 문항 해결은 공개된 문제를 100점으로 해결하는 것을 의미합니다."라고 명시한 것과 25문제까지 있는 걸 보면 보면 별도의 hidden test case는 없는 듯하다.

오프라인 본선 진출자를 선정하는 기준은 5곳에 서로 다르게 써져있어서 알 수가 없다. 가장 접근하기 힘들고 가장 자세한 곳에 따르면 "10문제 당일 올솔+풀이 시간+제출 횟수+추첨" 모두이다. ux가 매우 나쁘다고 생각한다. 4일 째의 문제에 "외부에서 작성한 코드를 복사 및 붙여넣기 시, 정확한 코드 작성 시간 산정이 힘들어 수상 과정에서 불이익이 발생할 수 있습니다. 이는 운영진 측에서 확인이 가능한 사항이므로, 모든 코드는 엘리스 플랫폼 내에서 작성을 부탁드립니다."라는 문구가 추가로 붙었다. 문제 풀기 바빠서 첫 주에는 확인하지 못했는데 구석에 있는 설정을 보면 실습 환경, 에디터 설정, 코드 수정 이력, 실행/제출 이력, 코드 공유 등의 기능이 있고 이 중 코드 수정 이력은 작성하면 3000개 정도의 버전이 생성되는 걸로 보아 모든 수정을 기록하는 듯하다.

리더보드 기준 총 참여자는 2050명이고 10문제 모두 푼 사람은 최소 100명인데 문제 10의 만점자의 시간 간격을 생각하면 많아도 101명으로(대회 종료 이후 유선 상으로 101명임을 공지) 추정된다. 오프라인 본선 진출자는 50명인데(대회 종료 이후 유선 상으로 80명으로 확대함을 공지) 나는 포함이 되었다. 예선 선물은 160개인데 나는 선물을 받지 못했다,

 

소감

1	2	3	4	5	6	7	8	9	10
목표량 (==)	정리 정돈을 좋아하는 k씨 (~=)	문자열 압축 해제 (==)	트리 위의 게임 (~=)	수열 복원 (~=)	빨간 선과 파란 선 (.)	계기판 조작하기 (~=)	강림제 (==)	격자 위의 ELICE (.)	계단 카드 뽑기 (~=)
다음 순열	미정렬 배열의 K번째 원소	.	.	2^n개의 부분 수열의 합에서 원본 수열 복원	.	수 n보다 크면서 숫자 k개를 사용하는 최소 수	.	중간 지점을 거치는 최단 경로	.
실3	실3?	골4	골4?	골5?	골1?	실2?	골1	골3?	골3?
30분	30분	30분	1시간	30분	3시간15분	45분	3시간30분	1시간	1시간30분
웰노운	정렬	스택, 재귀	트리 dp	그리디	다익스트라	브루트포스	냅색, dp	다익스트라	(투 포인터&슬라이딩 윈도우, 파라메트릭 서치&이분 탐색&슬라이딩 윈도우), (누적 합, 정렬, 레이지 세그먼트 트리)

문제는 요약하자면 위와 같다. 난이도는 골1~실3 수준이다. 다익스트라가 지나치게 많은 2번, dp가 지나치게 적은 2번 나온 게 특이한데 제출진은 문제 6을 솔루션처럼 다익스트라가 아니라 bfs+dp로 판단했을지도 모르겠다. 문제 6의 솔루션이 bfs인 건 그렇다 치고 문제 10의 시간 제한이 지나치게 널널해 레이지 세그가 아닌 정렬, 누적 합으로 풀려서 꽤나 쉬워졌다.

문제의 핵심적인 퀄리티는 만족한다. 왜냐하면 이미 검증된 문제들을 표절했기 때문이다. 꾸준히 제기되던 표절 논란이 문제 8에서 수면 위로 올라왔고 사과 공지가 올라왔다.

문제의 부차적인 퀄리티는 만족하지 않는다. 수 차례의 지문 수정, 문제 3의 솔루션의 오버플로우 혹은 지문의 출력값 제한 미기재, 문제 4의 지문의 말의 개수 미기재, 문제 5의 솔루션의 더티 코드와 비효율성, 문제 6의 솔루션의 더티 코드와 비효율성, 문제 8의 파이썬 솔루션의 더티 코드와 C와 자바 솔루션의 다소 비효율성, 문제 10의 솔루션의 더티 코드 등의 문제가 있다.

진행은 만족하지 않는다. 무수히 많은 오류가 있었다. 또한 맨 처음에 썼듯이 가장 중요한 유의 사항과 가장 중요한 본선 진출 규정이 명확하지 않은데 대회 종료 시점에서도 마찬가지이다.

나에 대해서는 약간 만족한다. 그럭저럭 잘 푼 것 같다. 하지만 지문을 이해하는 데에 시간이 너무 오래 걸린 점, 어렵긴 하지만 문제 6과 8을 더 빨리 풀지 못한 점, 본선 진출 규정은 애매하지만 10시부터 바로 풀지 않은 점, 본선 진출 규정은 애매하지만 100점 이후에도 다시 제출을 한 점, 본선 진출 규정은 애매하지만 조금 더 집중해서 풀지 않은 점 등이 아쉽다.

 

문제들

1일.

강의는 시간 복잡도이다. 빅오와 최악의 경우가 동일하다고 설명하는 오개념이 있다.

강의와 문제는 약간 연관이 있다. O(n!) 대신 O(n)을 써야 한다.

문제는 목표량(다음 순열, https://www.acmicpc.net/problem/10972, 실3, 웰노운과 C 내장함수를 빼고 생각하면 실1?, 풀이 30분)이고 백준 문제와 동일하다. 주어진 수에 숫자가 중복되었다면 다음 순열이 여러 개가 있을 수 있는데 이 문제에서는 커야 한다고 조건이 주어졌으므로 코드를 짤 때 등호에 신경써야한다.

풀이는 웰노운 알고리즘을 쓰면 된다.

 

2일.

강의는 유클리드 호제법, 소수 판별, 에라토스테네스의 체이다.

강의와 문제는 연관이 없다.

문제는 정리 정돈을 좋아하는 k씨(링크 없음, 정해 실3?, 내 풀이 실2?, 풀이 30분)이고 "주어진 배열의 임의의 구간 속 k번째 작은 수를 출력하라"이다. 프로그래머스 "k번째수"가 범위가 조금 더 작긴 하지만 사실상 동일하고 백준의 문제들은 범위가 너무 커서 비슷한 문제가 없는 듯하다.

풀이는 나는 배열의 원소의 값이 -199~199라고 굳이 명시한 것이 힌트라고 생각해 방법 3을 사용했지만, 방법 1이 정해이고 내가 시간복잡도를 잘못 계산했던 것보다 훨씬 짧은 O(6.5e7)로 아슬아슬하게 통과한다. 조금 더 쉽게 생각하거나 일단 제출을 하면서 proof-by-ac 해야 될 것 같다. https://www.geeksforgeeks.org/kth-smallest-largest-element-in-unsorted-array의 방법 1. 쿼리q*(슬라이싱n+정렬nlogn+인덱싱1), 방법 2. 쿼리q*(슬라이싱n*최대힙우선순위큐logk), 방법 3. 쿼리q*(슬라이싱n+계수정렬num_range)이다. 그외에도 버블정렬, 선택정렬 등을 통해 쿼리q*(배열n*첫수부터k수까지정렬k), 퀵셀렉트 평균 쿼리q*(분할정복n), 최악 쿼리q*(분할정복n^2), 백준 2243의 세그먼트트리 쿼리q*(배열만들기n+k + 수정과탐색logn), 백준 7469의 머지소트+세그먼트트리가 있다.

 

3일.

강의는 문자열 알고리즘(회문, 올바른 괄호 문자열), 분할정복과 백트래킹이다.

강의와 문제는 큰 연관이 있다. 올바른 괄호 문자열에서 했듯이 스택을 쓰거나, 백트래킹과 재귀를 쓰면 된다.

문제는 문자열 압축 해제(압축, https://www.acmicpc.net/problem/1662, 골4, 실2?, 당일 오후 3시 기준 맞힌 사람 2400명, 풀이 30분)이고 백준 문제와 동일하다.

풀이는 나는 스택을 사용하였다.

 

4일.

강의는 재귀와 정렬(삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬, 힙 정렬)이다.

강의와 문제는 작은 연관이 있다. dfs, 즉 재귀를 쓰면 된다.

문제는 트리 위의 게임(트리 게임, https://www.acmicpc.net/problem/30893, 골4, 당일 오후 2시 기준 맞힌 사람 100명, 이해 30분&풀이 30분)이고 백준의 문제가 방문 가능 여부 판별인 것과는 살짝 다르게 "방문 시마다 해당 정점의 숫자만큼 점수를 얻는데 선공의 점수>=후공의 점수 여부를 판별하라"이다. 게임 이론에는 꽤 익숙한데 백준에 비해 문제 조건이 다소 생략되어있어서 문제와 예제를 이해하는 데에만 30분이 걸렸다. 1개의 말을 공동으로 쓰는 거고 게임 종료 조건이 충족되면 즉시 종료된다.

풀이는 트리 dp를 쓰면 된다. dp[parent] = max(-dp[child] + vertex[parent])이다.

 

5일

강의는 DFS이다.

강의와 문제는 작은 연관이 있다. 재귀를 쓰면 된다.

문제는 수열 복원(링크 없음, 골5?, 풀이 30분)이고 "길이 n 수열의 부분수열의 개수는 2^n인데 이러한 부분수열의 합이 2^n개 주어지는데 이로부터 길이 n의 원래의 수열을 복원하라"이다. a[i]>=1이라는 조건이 있는데 이게 없으면 어떻게 풀지 모르겠다.

풀이는 그리디 알고리즘에 재귀 혹은 반복문을 쓰면 된다. 이하는 https://leeingyun96.tistory.com/36을 참고하라.

 

6일

강의는 BFS, 다익스트라이다.

강의와 문제는 큰 연관이 있다. 다익스트라를 쓰면 된다.

문제는 빨간 선과 파란 선(링크 없음, 골1?, 풀이 3시간15분)이고 "정점의 개수 N이 주어지고 0 혹은 1을 원소로 갖는 길이 N-1의 배열 colors가 주어진다. 차례마다 2개의 서로 연결되지 않은 정점 u와 v를 고른 뒤, u가 포함된 연결 요소 내의 모든 정점들로부터 v가 포함된 연결 요소 내의 모든 정점들에 간선을 잇는다. 이때 2<=N<=30이고 간선의 색은 0이면 빨간 색, 1이면 파란 색이고 k번째 차례에는 colors[k]를 사용해야 한다. 이때 사용한 빨간 간선의 개수의 최솟값을 출력하라."이다.

풀이는 다익스트라를 쓰면 된다. 이하는 https://leeingyun96.tistory.com/37을 참고하라.

 

7일

강의는 다이나믹 프로그래밍이다.

강의와 문제는 연관이 없다.

문제는 계기판 조작하기(링크 없음, 실2?, 풀이 45분)이고 "정수 N(1<=N<=1e7)보다 크면서 숫자를 K개(1<=K<=10) 사용하는 수 중 최솟값을 출력하라."이다. 예를 들어 수 1232에는 숫자 3개가 쓰였으니 K=3이다.

풀이는 브루트포스를 쓰면 된다.
브루트포스로 느리더라도 답을 찾을 수 있는 것은 자명하고 이를 바탕으로 낮은 N, K의 랜덤한 입력을 상대로 답을 찾은 뒤 나의 풀이의 답과 비교하려고 하였다. 그리디를 먼저 떠올렸으나 그럴싸한 규칙을 찾을 수 없었고 dp 역시 그럴싸한 규칙을 찾을 수 없었다.

def sol(N, K):
    if len(str(N)) < K:
        return '1023456789'[:K]
    return bruteforce(N, K)

다양한 입력을 대상으로 답을 뽑아 규칙을 찾아내려 노력했는데, N의 길이보다 K가 클 때는 위와 같은 답이 출력되는 것을 찾을 수 있었고 정당화 역시 쉽게 떠올릴 수 있었다. K가 클 때는 이렇게 한 번에 처리 가능하니 K가 낮을 때만 브루트포스로 처리한다. N이 더 크다면 정수(https://www.acmicpc.net/problem/1040, 플2, 맞힌 사람 400명)와 사실상 동일하다.

 

8일

강의는 다이나믹 프로그래밍이다. 전날의 영상과 동일하다.

강의와 문제는 큰 관련이 있다. dp를 사용하면 된다.

문제는 강림제(인기가 넘쳐흘러, https://www.acmicpc.net/problem/17258, 플4였는데 골1로 내려감, 골1?, 당일 저녁 기준 맞힌 사람 170명, 풀이 3시간30분)이고 백준 문제와 동일하다.

풀이는 dp를 쓰면 된다. 이하는 https://leeingyun96.tistory.com/38을 참고하라.

 

9일

강의는 서로소 집합과 유니온 파인드이다.

강의와 문제는 연관이 없다.

문제는 격자 위의 ELICE(링크 없음, 골3?, 풀이 1시간)이고 "엘리스는 N*N(3<=N<=1000) 크기의 격자 모양의 미로에 갖혔다. 엘리스는 현재 (1,1)에 위치해있다. 미로 속의 글자 ELICE를 순서대로 모으면 미로를 탈출할 수 있다. 모든 격자에는 양의 정수가 쓰여있고 5칸에는 추가로 글자가 놓여있다. 엘리스는 상하좌우로 1칸 이동할 수 있다. 엘리스가 어떤 칸에서 다른 칸으로 이동할 때 두 칸 위에 쓰인 정수의 합만큼의 시간이 걸린다. 엘리스가 미로를 탈출하는 데에 걸리는 최소 시간은?"이다.

풀이는 중간 지점을 거치는 다익스트라를 쓰면 된다.
편의상 첫 번째 E를 대문자 E, 두 번째 e를 소문자 e라고 하자. 엘리스가 탈출할 수 있는 방법은 시작점->E->L->I->C->e와 시작점->e->L->I->C->E 이렇게 둘뿐이다. 각 화살표의 가중치는 시작점, E, L, I, C, e 총 6개를 시작으로 하는 다익스트라를 돌린 뒤 다음 점을 도착지로 하는 경로의 길이를 찾으면 알 수 있다. 다익스트라의 시간 복잡도는 O(ElogE + ElogE) = O(2*4e6*log(4e6)) = O(2*4e6*(2+20)) = O(1.56e8)이고 이런 다익스트라를 6번 돌리는데, 시간 제한이 7초니 아슬아슬하게 통과할 수 있다.

 

10일

강의는 없다.

강의와 문제는 연관이 없다.

문제는 계단 카드 뽑기(링크 없음, 골3?, 풀이 1시간30분)이고 아래와 같다.

풀이는 (투 포인터&슬라이딩 윈도우, 파라메트릭 서치, 이분 탐색, 슬라이딩 윈도우) 중 하나와 (누적 합, 정렬, 레이지 세그먼트 트리) 중 하나를 쓰면 된다. 이하는 https://leeingyun96.tistory.com/39을 참고하라.