엘리스 알고리즘 코드 챌린지, 예선 10일 차 문제

강의는 없다.

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

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

풀이는 (투 포인터&슬라이딩 윈도우, 파라메트릭 서치&이분 탐색&슬라이딩 윈도우) 중 하나와 (누적 합, 정렬, 레이지 세그먼트 트리) 중 하나를 쓰면 된다.
풀이 및 발상을 나열하자면 아래와 같다.
1. 문제 잘못 읽고 단순한 세그먼트 트리?
2. 모노톤 스택?
3. 매개 변수 탐색?
4. dp? 이렇게 1, 2, 3, 4 모두 고민을 해봤는데 풀이를 찾을 수 없었다.
5. "Ai = 3이 4개 있다고 하자. 이들이 배치될 수 있는 곳은 1, 2, 3 세 곳뿐인데 한 개는 무조건 배치될 수 없다. 따라서 i>=cnt[i] for all i=1..k라면 올바른 부분 배열이다."라는 그럴싸한 풀이를 생각할 수 있었다. 122333 같은 반례에서 이전에 배치된 장소를 계산을 못 하기 때문에 틀린 풀이긴 하다.
6. 5번을 구현하기 위해 cnt 배열을 떠올렸고 계수 배열은 슬라이딩 윈도우, 투 포인터를 돌려서 배열이 변화하더라도 변화 한 개는 O(1)로 처리할 수 있다. 또한 올바른 배열이라면 길이를 +1, 틀린 배열이라면 시작을 +=1 해도 정답을 찾을 수 있고 이 방식으로는 정확히 n개의(O(N)) 부분 배열만 탐색하게 된다. 따라서 O(N)이다. 틀린 배열이라서 시작을 옮길 때 길이를 1로 초기화하지 않고 그대로 유지하는 이유는 어차피 최대 k를 찾는 게 목표기 때문에 낮은 길이에 대해 판별할 필요가 없기 때문이다.
7. 풀이: (투 포인터, 슬라이딩 윈도우), (누적 합).
배열을 만들어내는 건 동일하다. 5번 풀이의 오류를 찾아냈고 문제 그 자체를 다른 표현으로 옮길 뿐이라 오류가 없을 다른 식을 찾고자 했다. k=4가 되기 위해서는 sum(cnt[4:])>=1이어야만 한다. 그 후에는 sum(cnt[3])>=2이어야만 한다. 왜냐하면 3 이상이어야 3을 배치할 수 있고 이미 1개는 4에 배치되었기 때문에 그것도 감안해줘야 하기 때문이다. 그 후에는 3, 2, 1 .... 이렇게 하면 sum(cnt[x:])>=k-x+1 for all x=1..k가 된다. 이건 거꾸로 말하면 sum(cnt[:x])<=x-1 for all x=1..k가 된다. 투 포인터와 슬라이딩 윈도우로 배열을 만든 뒤(O(N)) 그 배열 내에서 x=1..k 순회를 돌며(O(L, 단 L=해당배열의길이)) 누적 합으로 cnt를 합쳐주며 판별하면 된다. 나는 이렇게 풀었고 아래로는 내가 안 될 거라 짐작했던 방식 혹은 몰랐던 방식이다. 판별식의 변환과 슬라이딩 윈도우 발상이 어려운 것이지 코드는 쉬우므로 생략한다. O(N^2).
8. 풀이: (투 포인터, 슬라이딩 윈도우), (정렬).
배열을 만들어내는 건 동일하다. 그 배열 내에서 정렬을 한 후 arr[i]>=i for all i=0..k-1을 순회하며(O(L)) 판별하면 된다. 정렬은 배열의 끝에 추가 후 빠른 정렬&이분 탐색 후 중도삭제(O(LlogL)&O(logL+L)) 혹은 기정렬 배열을 이분 탐색 후 배열 내 삽입&삭제(O(logL+L)) 혹은 계수 배열 형태를 수정(O(1)) 등을 하면 된다. 가장 느린 경우 O(N^2logN)이고 가장 빠른 경우이자 7번과 동일한 경우는 O(N^2)이다.
9. 풀이: (투 포인터, 슬라이딩 윈도우), (레이지 세그먼트 트리).
배열을 만들어내는 건 동일하다. 판별식 sum(cnt[:x])<=x-1 for all x=1..k은 곧 sum(cnt[:x]) - x + 1 <= 0 for all x=1..k이다. 좌항을 P[x]라 하면 곧 P[x] <= 0 for all x=1..k이다. 곧 max(P[x] for all x=1..k) <= 0이다. 이는 세그먼트 트리의 구간 최댓값 쿼리와(O(logN)) 동일하다. 배열이 달라져서 cnt[y]가 변화했다고 하자. 이 변화가 영향을 미치는 것은 cnt[:y+1], cnt[:y+2] ... 이다. 이는 곧 P[y+1]...이고 세그먼트 트리의 레이지 프로파게이션과 구간 업데이트를 통해(O(logN)) 계산할 수 있다. O(NlogN).
10. 풀이: (파라메트릭 서치, 이분 탐색, 슬라이딩 윈도우), (레이지 세그먼트 트리).
판별은 동일하다. 최대의 k를 찾는 최적화 문제이니 결정 문제로 발상을 바꿔서 생각해보자. 이분 탐색(logN)을 쓰면 된다. 길이 k를 갖는 배열은 슬라이딩 윈도우를(O(N)) 통해 cnt 배열을 만들고 수정할 수 있다. O(Nlog^2N).
이외에도 (파라메트릭 서치, 이분 탐색, 슬라이딩 윈도우), (누적 합)과 (파라메트릭 서치, 이분 탐색, 슬라이딩 윈도우), (정렬)도 있다.
솔루션은 (파라메트릭 서치, 이분 탐색, 슬라이딩 윈도우), (레이지 세그먼트 트리) 같기는 한데 가독성이 심히 나쁘고 파이썬, C, 자바의 솔루션이 다 달라서 읽을 수가 없다.
이번 문제는 시간 제한이 5초이고 테스트 케이스도 약하고 엘리스의 컴퓨터가 성능이 좋은 듯해서 O(NlogN)이 아닌 다른 풀이도 통과해서 조금 더 쉽다. 순열(https://www.acmicpc.net/problem/8330, 플2, 맞힌 사람 30명) 문제는 배열을 만드는 아이디어는 필요 없고 P 배열을 조작하는 아이디어만 있는데도 시간 제한이 1초라서 O(NlogN) 풀이를 아마도 강제해서인지 난이도는 플2이다. 엘리스도 시간 제한을 줄인다면 다5까지 될 수 있지 않을까 싶다.

다시 난도가 상승했다. 현재까지 만점자 중 50번째로 빨리 푼 사람이 13:07분, 100번째로 빨리 푼 사람이 23:35분에 풀었다. 대충 추세를 보면 당일 내에 푼 사람은 100명 정도가 될 듯하다. 의도한 것인지는 모르겠는데 레이지 세그에 비해서는 시간 제한이 넉넉해 풀기가 쉬워서 만점자가 많았고 그럼에도 불구하고 중도 포기자가 있는 것인지 쉬운 정도에 비해서는 만점자가 적었다.