2024년에도 어김없이 한국정보올림피아드가 열렸습니다. 올해 고3인지라 인생 최후의 KOI 참가가 되겠네요.
1차대회는 은상을 받았습니다. 전체 13등이라는데 이 정도면 그냥 금상 주면 안되나 싶습니다.
나중에 금상 커트라인을 확인해 봤는데 제 점수랑 10점도 차이가 안 나더군요. 가엾은 스스로를 위로하면서 2차대회에 참가 신청을 넣었습니다.
2차대회는 알고리즘 실기 문제로 4문제, 쉬는 시간 없이 4시간 30분 (13:30 ~ 18:00) 동안 진행되었습니다.
$$ \bf{근데\ 얘는\ 왜\ 이런\ 선택을\ 한\ 걸까요.} $$
저는 2022년에 알고리즘 대회 참여를 본격적으로 시작해 모든 KOI를 온라인으로 쳤습니다. 늘상 그랬듯이 아무렇게나 꽂은 책들과 대충 적당히 걸어둔 옷들을 감독관께 소개시켜드리고 한 15분 멍 때리고 있으니 대회가 시작했습니다.
작년 1번 문제가 예년에 비해, 나아가 전 고등부 1번을 통틀어서도 상당히 쉬웠습니다. 아마도 이 기조를 이어 올해도 1번 문제만큼은 쉬울 것이라 예상했습니다.
1번 문제 :: 가로등을 읽었습니다. 1차원 배열 위에서 각 칸마다 가장 가까운 가로등까지의 거리를 작은 순서대로 적당한 개수만큼 출력하는 문제입니다.
가로등마다 투 포인터를 하듯이 양쪽으로 칸을 밀어주면서 양쪽이 다 옆 가로등과 겹치면 그 가로등을 뽑아버리면 되겠다 싶었습니다. O((N+K) lg N) 근처에 작동할 겁니다. std::set 대신 연결 리스트로 가로등을 관리하면 선형에도 짤 수 있는데 제곱 미만이면 시간복잡도가 아주 큰 영향을 미치는 문제는 아니라서 뭐…
그대로 구현해서 맞았습니다. (AC 100 00:08)
시작이 좋습니다. 2번 문제를 열었습니다.
아… 부분문자열?
3번 문제를 열었습니다.