2021 KOI 2차 후기

문제도 잘 기억이 안나고 잘 풀지도 못해서 후기라고 하기에는 좀 뭐하지만

일기장 느낌으로 써보기로 했다

 

[1. 헬기 착륙장]

DP 문제였다. 

문제를 처음에 제대로 안읽고 풀어서 답이 조금 이상했는데, 고치고나니 답이 어느정도 나왔다.

처음엔 Naive하게 DP 식을 만들려고 했는데, 테스트해보니 역시 메모리 초과가 났다.

약간의 트릭을 통해 메모리를 줄일 수 있는 방법을 구상해냈고, 90점을 받을 수 있었다.

마지막 10점을 받기 위해서는 전처리를 하면 될 것 같다는 생각이 들었지만, 뭔가 끄적여보다가 그렇게 전처리를 하면 안된다는 결론이 나와버렸다...;; 그래서 90점으로 마무리..

 

[2. 그래프 균형 맞추기]

문제를 해석하는데 시간이 조금 걸렸는데, 그래프와 연립 방정식을 섞어놓은 듯한 문제였다.

N=M-1일때는 무조건 해가 무한하게 나오는데, 그게 아닌 경우가 어려웠다.

가우스 소거법을 이용해서 행렬의 Rank를 구할까도 생각해봤지만 분명히 시간 초과가 날 것 같았고..

당연하게도 출제자가 의도한 풀이는 절대 아닐 것 같았다.

결국 N=M-1일 때는 삼분 탐색을 이용해 해결했지만(범위가 생각보다 컸다), 다른 경우는 해결하지 못했다.

사이클을 이용해야 될 것 같다는 생각까지는 떠올렸지만, 이를 구체화시키지 못해 실패..

N=3,M=3인 경우를 포함하여 총 39점을 받았다.

 

[3. 가장 긴 공통 괄호 문자열]

문자열 문제였다. 일단 적어도 겉보기에는 문자열 문제였으니..

문제를 어떻게 풀어야 할지 감을 잡을 수 없었고, A=B인 경우를 해결하고자 하였다. 

올바른 괄호 문자열을 뽑아내고 그 중에서 가장 긴 문자열의 길이를 출력했으나 점수를 받지 못했다.

결국 이 문제에서는 점수를 받지 못했다.

 

[4. 맛집 추천]

트리 문제. 어려워보여서 접근조차 하지 못했다.

아마 HLD같은 알고리즘이 쓰이지 않았을까 싶었는데..

아예 제출을 한번도 하지 않아서 점수를 받지 못했다.

 

 

예선에 비해서 본선 문제는 정말 어렵다는걸 느꼈다.

실제 실력에 비해서는 점수를 조금 더 받은것 같은데..

이번 대회를 통해서 여러 알고리즘들을 대회때도 쓸 수 있는 정도로 공부해야겠다는 생각이 들었다.

그래프 이론이나, 문자열, 트리같은...

슬슬 여러 알고리즘들이 쓰이는 플레랑 다이아 문제들도 연습할 때가 된 것 같다.

적어도 플레를 수월하게 풀 수 있을 정도까지는 실력을 올려야 할텐데..

사실 내신때문에 PS를 할 시간이 있을지는 모르겠다.