SPC 2022 후기

어느덧.. 마지막 SPC이다.

7학기 재학중인 현재, 다음 봄학기에 어떤 심경의 변화가 있어서 휴학을 하지 않는 이상 SPC는 더이상 참가를 할 수 없다...

마지막 SPC인데, 유종의 미를 거둬야겠다!!

..........

라고 생각했지만, 참가신청 이후 넘치는 운영체제 핀토스 프로젝트와 캡스톤디자인 개발을 진행하다보니, 알고리즘의 a자도 공부하지 못했다.

다른 친구들은 잘만 공부하던데.. 사실 어쩌면 변명일지도

ps에 좀 많이 소홀하긴 했다...

 

대회 전날 밤 11시에 친구들의 연락을 받았다. 작년 문제 보니 너무 쉬운데 이거 그냥 참가만 해도 수상컷이라는 연락이었다.

작년 문제셋을 확인해보았다.

1번은 쉬우니까 패스, 2번은 그래프, 3번은 DP... 4번이 냅색? 오 이건 좀 어려운데

그런데 3솔만 해도 수상확정이라니.. 친구들 말대로 정말 해볼만 했다.

부랴부랴 대충 유명한 알고리즘만 구글링해서 하드카피 출력하고 입장!!

 

 

0. 입장 후 환경세팅

알고리즘을 너무 오랜만에 풀어본다는게 느껴졌다. cpp 빠른입출력을 세팅하는데, 헤더로 iostream 대신 cstdio를 선언하고 왜 안되는건지 고민했다... 여기에서 1차 당황. 어쩌면 flag였나!

 

1. 완전한 수열

https://www.acmicpc.net/problem/26090

26090번: 완전한 수열

소수 (prime number)를 보자마자 당황했다. 순간 2018 SPC의 기억이 새록새록 떠올랐다.

당시 빠른 소인수분해를 못해서 수상을 못했었다. 남들 다 풀었는데 나만 못풀어서 자괴감이 엄청 들었었다.

2018 SPC. C번이 빠른 소인수분해를 해야 했는데.. 패널티에 여유가 있었음에도 풀지 못해서 수상을 실패했다.

손을 떨면서 빠른 에라체 하드카피를 찾아서 그대로 복붙을 했다. 예제 넣어보니 통과 되어서 그대로 제출했는데 "틀렸습니다"

문제를 다시 읽어보았다. 아, 최대 2000인 값이 500번 등장 가능하니 100만까지 소수판별을 해야한다.

그래서 단순히 하드카피에서 최대값을 100만으로 바꿔서 돌렸는데 런타임오류. invalid range 접근. 여기서 너무 당황했다.

최대값을 1만으로 세팅하면 돌아가는데, 10만 이상부터는 계속 런타임 오류를 뱉었다. 코드의 잘못일거라고는 생각하지도 않고, visual studio의 stack size가 작게 지정되어있나? 생각부터 들었다. 일단 무지성으로 운영진에 질문해서 stack size 변경 후 재시도. 그래도 여전히 안돌았다. 

그래서 그냥 설마 백준에서는 돌아가나? 하고 제출해 보았다. 당연히 "런타임 에러"

문제의 코드. 26번 줄에서, i*i가 overflow가 나서 j가 신나게 음수를 뱉어주고 있었다. 당시엔 마음만 급해서 코드를 이해조차 못하고 있었다.

여기서 공부를 안한것을 진짜 많이 후회했다. 아니 대회 참가를 진짜 후회했다. 이미 시간은 20분을 넘어가고, 1솔이 넘쳐나는 상황이었다. 

고작 에라체를 할 줄 몰라서 1번문제를 못푼다는 생각에 자괴감이 너무 많이 들었다. 한편으로는 너무 화났다. 왜 하필 마지막 SPC에서 자신없는 소수판별이 나오지? 라는 생각이 들었다. 너무 운이 없었다고 생각했다.

솔직히 그냥 깔끔히 패배를 인정하고 0solve로 대회장을 나가고 싶었다... 멘탈적으로 많이 흔들려서 다음 문제부터는 못풀것이라고 생각했기 때문이다.

열심히 i와 j를 찍어보다가, B번문제가 뭔지 확인이나 해보기 위해서 다음 문제로 넘어갔다.

 

 

2. DPS

https://www.acmicpc.net/problem/26084

26084번: DPS

이 문제를 읽자마자 멘탈은 가루가 되어 흩어졌다. "경우의 수" 네 글자만 보였다. 이거 무조건 조합이다. 

nCk의 공식은 이미 까먹은지 오래였고, 하드카피로도 가져가지 않았다. 

작년에는 자신있는 알고리즘인 그래프이론이 나왔는데, 어째서 이번엔 제일 쉬운 두문제가 내가 제일 자신없는 수학 분야인건지 너무 원망스러웠다.

 

일단 3가지 알파벳을 조합하는거라서, 경우의 수는 많지 않아서 하나하나 손으로 써보았다.

전부 같은 알파벳인 경우, 전부 다른 알파벳인 경우, 하나만 다른 알파벳인 경우 세가지에 대해 각각 예시를 들어서 공식을 유도했다.

다행이 nCk에서 k는 2 또는 3이었고, 나는 5C2와 5C3의 값을 알고 있었다!!

이 값으로 역으로 공식을 유추해서 nCk = (n!)/((n-k)!k!) 임을 알 수 있었다.. 이거 알아내느라고 황금같은 시간을 쓰다니

그래도 일단 이거라도 맞춰야겠다라는 마음가짐으로 코딩을 시작했는데..

string temp;
cin >> temp;

이 코드가 돌지 않는것이다!! 이 문제는 문자열을 입력받아야 하는데!!!!!

하지만 이미 없어져버린 멘탈 덕분에 정말 아무렇지 않았다. 다른 사람들은 2sol, 3sol을 하고 있는데 나만 0sol로 대회가 끝나겠구나.

결국 그냥 char 배열로 변수를 선언해서 scanf로 받아서 문제를 풀었다. char 배열 다루느라고 너무 노가다를 해서 코드가 굉장히 더럽다.. 어쨌든 문제는 간단해서 1solve 성공. 이게 대회 시작 40분 째였다. 이미 2solve가 수상컷인 상황이었다.

후기를 쓰는 이시점에 알았다... string이 아니라 cstring을 선언했다... 대회 준비도 안하고 날로먹으려던 나에게 내린 벌이었을까

 

3. 현대모비스 소프트웨어 아카데미

https://www.acmicpc.net/problem/26091

26091번: 현대모비스 소프트웨어 아카데미

문제 보자마자 알았다. 아 이건 정렬하고 투포인터 보면 된다.

증명따위 할 시간 없었다. 이미 시간이 너무 늦어서.

44분에 solve를 했다. 금방 풀었다.

하지만 이미 첫 solve가 늦어서 같은 문제를 solve해도 페널티때문에 불리한 상황이었다. 그래서 그냥 포기하고 등수판을 보지 않았다.

 

4. 수학적인 공통 최소 조상

https://www.acmicpc.net/problem/26092

26092번: 수학적인 최소 공통 조상

진짜 너무 슬펐다. 내 눈에는 소인수만 들어왔다. 그렇다. 소인수분해를 하려면 소수를 찾아야했다.. 결국 또 에라체를 써야하는 문제다.

아니 A번을 에라체때문에 못풀고 간신히 2sol을 하고 왔는데 여기서 다시 에라체때문에 막힌다고? 정말 진짜 하늘이 무너진 느낌이었다.

심지어 문제도 간단하다 제일 작은 소인수 찾아서 부모만 계속 찾으면 된다. 

숫자 a를 소인수분해를 하면, a의 소인수분해 중 하나가 가지는 소인수분해는 a의 소인수분해에 포함된다는 것은 well known이다. 따라서 a만 소인수분해를 하면 부모노드를 찾아가는것은 일도 아니다. 대충 소인수분해 하면 소인수의 개수는는 sqrt(n) 안쪽이라서, 시간복잡도도 그 선에서 마무리가 가능하다. 근데 이걸 prime number를 못찾아서 못푼다는게 진짜 화가 날 지경이었다.

스코어보드를 보니, 이미 수상권은 3solve가 다 먹었고 그마저도 대부분이 ABC solve였다. A랑 D가 풀이가 바로 보이는데 에라체를 못돌려서 이걸 수상을 못해? 라는 생각에 너무 괴로웠다. 3solve만 해도 작년엔 수상권이었는데 이번엔 시작한지 1시간만에 3solve가 뚫리다니.... D도 solve가 별로 안나온 탓에 E번문제는 1등만 푼 상황이었다. 여기서 고민 많이했다. 에라체 올인을 하느냐, E번문제를 맛보러 가느냐. 

어짜피 에라체 못풀거같으니 그냥 포기하고 E번문제가 뭔지나 확인하러 갔다.

 

 

5. 고양이 목에 리본달기

https://www.acmicpc.net/problem/26093

26093번: 고양이 목에 리본 달기

보자마자 DP라는 걸 알았고, 식을 어떻게 새워야할지 좀 고민했다.

dp[i][j] 에서 i는 i번째 고양이, j는 j번째 리본을 의미하게 되면, dp[i][j] = max(dp[i-1][0] ~ dp[i-1][k]) + i고양이의 j리본 만족도.

예외는 단 하나다. max(dp[i][0] ~ dp[i][k])의 값이 i-1번째 고양이가 j번째 리본을 고른 경우. 그러면 i-1번째랑 i번째랑 전부 j번째 리본을 고른거라서 연속적인 리본을 선택한 경우이다. 

따라서, i번째 고양이의 만족도의 최대값, 두번째 최대값을 저장해놓고, max(dp[i][0] ~ dp[i][k])의 값이 같은 리본을 고르는 경우에는 두번째 최대값에 현재 만족도를 더해주도록 구현해주면 된다.

깔끔하게 한번에 맞았다. 64분 solve.

 

여기서 스코어보드를 보았다.

이제 수상컷은 4sol에서도 패널티로 갈리는 그림이 보였다. E번을 푼 사람은 나 빼고 단 세명뿐이었다. 그럼에도 불구하고 난 3sol로 스코어보드 저 아래에 보이다니..

진짜 한숨부터 나왔다. 마지막 대회에서 다시한번 에라체에 발목잡혀서 수상실패를 한다는게 너무 만화같았다.

 

일단 멘탈잡고 다시 1번문제로 돌아가서 i와 j를 하나하나 출력해보기 시작했다. 어째서 런타임 오류가 나는지 찾는게 급선무였다.

고통스러웠던 디버깅의 흔적. 오류가 나는 i와 j를 찾으려 애쓴 주석이 보인다.

엄청난 시간을 투자한 끝에 j의 오버플로우가 런타임오류의 원인이었음을 찾았고, 바로 solve가 떴다. 81분 solve. 하지만 제출실패가 3번이라 너무 많은 패널티를 안고 가게 되었다.

 

다시 4번으로 넘어갔다. 부모노드를 찾으려면 소인수분해 해서 그 값을 가지고 어떻게 어떻게 하면 될것같은데.. 처음에 생각한대로 되지가 않아서 다시 생각해서 구현하느라 시간이 좀 걸렸다. 그런데 제출해보니 시간초과가 떴다. 시간복잡도가 절대 시간초과가 뜰 리가 없는데.. 코드를 봐도 도저히 알 수 없었다.

그래서 10자리 이상의 숫자를 아무 입력이나 넣어봤다. 그랬더니 무한루프를 도는 케이스가 존재했다!! 부랴부랴 예외처리를 하고 제출했다. 130분 solve. 

이미 스코어보드는 프리징 된 상태였다. 스코어보드도 이미 어느정도 정리가 된 분위기였다. 5solve에서도 이미 패널티로 수상이 갈리고 있는 상황이었다. 내 패널티를 더해보니 스코어보드가 공개되어도 수상권에 들지 못하는 패널티임이 확실했다. 남은것은 6번문제를 풀어내는 것 뿐이었다.

 

 

6. 더 어려운 스케줄링

https://www.acmicpc.net/problem/26094

26094번: 더 어려운 스케줄링

stack에서 pop과 push를 하는데, 대신 top과 bottom이 바뀌는 쿼리와, 값들을 정렬을 하는 쿼리가 들어온다.

조금 생각을 해보았다. pop/push는 아무렇게나 구현해도 O(1)이다. 

top과 bottom을 바꾸는 쿼리는 stack이나 queue로는 안되고, deque나 vector가 떠올랐다. deque든 vector든 O(1)로 top과 bottom을 바꿀 수 있다.

그런데 정렬.. 정렬을 어떻게 빠르게 하지?

전체를 정렬하면 O(n log n)이다. 따라서 new element만 정렬을 해서 O(log n)에 가깝게 쿼리가 실행되게 튜닝을 해야했다.

정렬을 해주는 자료구조가 뭐가있더라.. priority queue 정도만 떠올랐다. 하지만 pq는 top과 bottom을 뒤집는게 불가능했다. 즉, 정렬은 잘 해주지만 뽑으려는 숫자가 pq에서 정렬된 순서의 역순인 경우 한번에 뽑을 방법을 찾지 못했다. (해설에서는 priority_queue로 구현 가능하다고 하는데 어떤 방식일까..)

그러면 남은 자료구조가 set이나 map밖에 없는데, map은 당연히 아니고 set을 쓰면 되려나.. 했는데 이때의 나는 알고리즘을 풀지 않았기에 파이썬 set에 뇌가 절여져 있었다. set도 중복제거는 되어도 순서가 없으니까~ 하고 넘어갔다. 그런데 당연히 cpp의 set은 이진트리로 아주 잘 정렬을 해주고, 심지어 역순으로도 값을 뽑아낼 수 있다!!! 이걸 까먹다니.. 대회 준비를 안한 탓이다. 심지어 set 사용법 하드카피로 가져갔는데..

시간이 없으니 더이상 아이디어가 떠오르지 않아서 그냥 vector를 이용해서 구현하고, 정렬을 쿼리가 들어올 때 바로 하는것이 아니라, 정렬 할 구간을 가지고 있다가 나중에 해당 구간에 접근 할 필요가 있을 때 정렬을 하도록 하여 최대한 정렬횟수를 줄여보았다.

그러나 그정도의 상수컷으로는 시간초과를 피하지 못하였다...

 

7. 최종 결과

결국 에라체의 늪에 빠져 패널티를 있는대로 다 먹은 나는 5solve중에서도 꼬리를 담당하여 수상을 실패했다.. 정말 대비를 조금만 했더라도 에라체에서 오류를 금방 찾고, cpp set도 수월하게 썼을텐데 굳어져버린 뇌로는 해내지 못하였다. 

A를 못풀었는데 2solve가 넘칠때, BCE 3solve를 했는데 ABC 3solve가 주류일 때 너무 힘들었다. 그래도 다행히 디버깅 노가다 끝에 5solve로 자존심정도는 챙길 수 있었던 대회였던 것 같다. 이제 알고리즘 대회는 더이상 참가하지 않을 듯 한데, 여러모로 아쉬움이 많이 남는 대회이다. 21년에 휴학을 하지 말았어야 했어.. 나도 그래프 잘 풀수 있는데..