우리 학교에서 열린 알고리즘 대회에 나갔어요
작년에도 참가하고 싶었지만 알바를 하고 있었어서 못해서 아쉬웠는데 올해는 다행히 시간이 되었고
새천년관 4층에서 했는데 생각보다 사람이 많이 신청하지는 않아서 편하게 문제를 풀 수 있었다.
가니까 스티커랑 키링?을 받았고 이 스티커는 좀 맘에 들어서 노트북에 붙였다.
문제
문제는 L번까지 총 12개가 있었고, 난이도 순으로 정렬이 되어 있었다.
시간은 3시간, 분명 쉬운 문젠데 긴장해서 그런지 문제를 잘 못 읽어서 틀렸습니다를 너무 받은게 아쉽다.
백준에 문제가 공개가 됐고, A~C는 브론즈, D~E는 실버, F~J는 골드가 달렸다.
나머지는 플레였고, 아무래도 학교 대회에서는 아무도 푼 사람이 없었다.
순서대로 간단히 리뷰를 하면
A번
이 문제와 비슷한 유형의 영어 문제를 얼마전에 풀었는데 그래서 바로 풀 수 있었다.
행이나 열이 같으면 0이고, 아니면 1이라는 것을 알 수 있다.
B번
관찰을 하면 최소 얼룩말의 2배는 있어야 한다.
C번
가장 큰 코끼리를 구하면 쉽게 풀 수 있다.
이렇게 C번까지 풀 때는 좋았는데 이 다음 D, E, F에서 각각 3, 3, 5번씩 틀리는 삽질 때문에
페널티랑 시간을 너무 많이 잡아먹어 버렸다.
D번
길이 N인 A가 주어졌을 때 특정 연산을 통해 길이 2N인 B를 만들 수 있는가 라는 문제였는데
문제를 잘 못 읽고 연산이 가장 뒤에 있는 것을 pop하는 거라고 생각해버렸다.
그래서 stack으로 구현하는데 아무리해도 안되서 다시 읽으니니 그냥 A의 아무 원소를 뒤에 붙일 수 있는 것이었다.
참 안타까웠고, 여기부터 흔들려버리고 말았다.
E번
이것도 악몽에 대해 조금 생각해주면서 풀면 되는 많은 조건 분기 스타일의 구현이었는데 침착하지 못해서
테케를 더 생각하고 짰어야 하는데, 처음이 악몽일 때, 마지막이 악몽일 때 등 케이스를 놓쳐서 계속 틀렸다.
여담으로 백준 문제에는 그림이 없고 나눠준 문제지에만 그림이 있어서.. 그림을 봤다면 더 쉽게 풀었을 것 같다.
F번
이번 대회에서 제일 힘들게 한 문제인데, 또또또 문제 잘못 읽음 이슈가 발생했다.
이게 상하좌우 1칸씩만 큐에 넣는다고 해서 그러면 최대 3개씩 늘어나는구나. 라고 인지를 했는데
알고 보니까 한 면에 전파가 되는 것이었고, 약수 관계로 푸는 문제였다.
그렇게 약 1시간을 여기서 날렸고, 뒤의 문제들을 풀 시간이 없어지고 말았다.
그래도 G, H번을 F번 고민하면서 풀 수 있었기에 그나마 다행이었다.
G번
F번을 풀다가 도저히 안될 것 같아서 이걸 먼저 풀었다.
애드훅? 의 맛이고, 케이스를 몇개 그려보니까 4갠가 8개마다 패턴이 있어서 쉽게 풀 수 있었다.
H번
수식으로 어찌저찌하니 정리가 되서 O(N)으로 해결이 됐다.
I번
뒤에서부터 숫자를 보면서 계속 증식된다는 것은 관찰했는데, 구현을 어떻게 할지 생각을 못했다.
좀 침착하게 디버깅하면서 했으면 풀었을 것 같은데 제일 아쉽다.
J번
스코어보드가 프리즈 되고, 어떤걸 풀 수 있을까 하면서 봤는데 왠지 정렬을 잘 하면 뭔가 풀릴 것 같았다.
Prefix와 Suffix가 생성된 후 섞였음이 보장이 되기 때문에 정렬을 한 다음에 복원이 가능했다.
그 다음은 누적합으로 답을 찍으면 됐고, 구현에서 어려웠던게 map을 통해 복원을 하려고 했어서 꼬인게 있었다.
풀이를 들어보니 좀 더 간단한 방법이 있었지만 궤는 비슷했기에 만족
기적처럼 끝나기 1분 전에 나 혼자만 풀어냈다.
K번
시간이 없어서 못 봤다.
L번
딱 봤을 때 어려워보이긴 했는데 최근 트리 문제를 주구장창 풀고 있어서 혹시? 하는 마음으로 계속 봤다.
한 20분 정도 봐도 시간복잡도가 터지는 상황이 나왔고 다시 J번으로 돌아갔다.
이 때 쓴 시간을 I, J번에 할애했다면 다 맞추지 않았을까 하는 조금의 아쉬움.
끝나고 풀이를 듣는데 내가 생각했던 것이랑 전혀 달라서 더 깊게 건드리지 않았음을 다행이라고 생각했다..
스코어보드
그럼에도 마지막 프리즈 되고서 1분 남기고 푼 J번이 있어 2등을 한 것에 만족한다.
상금 10만원도 좋았고, 열심히 알고리즘을 공부할 에너지를 받을 수 있었다.
대회 후기?
알고리즘 대회는 큰 대회 몇 개를 제외하고는 나갈 수 있는 곳이 별로 없고,
대회 경험이 없다보니까 문제를 보면 좀 긴장되기도 하고, 사고력이 떨어지는 것 같아서
많이 나가보고 싶은데 열리는 대회 수 자체가 너무 적으니 경험을 쌓을 수가 없다고 느껴진다.
CTF도 그렇고 알고리즘 대회도 그렇고 항상 보는 상위권의 닉네임과 본선 컷 언저리에 있는 내 실력
그래도 CTF는 계속 하다보니까 감이라도 생기는데..
이런 상황이었기 때문에 학교에서 열린 대회가 더 재밌게 느껴졌고, 상도 받아서 기분이 좋다.