[Code Tree] codetree 나무랄 데 없는 코드트리 식목일 코딩 퀴즈 참가 후기
1. 대회 후기
딱히 이용하고 있지는 않지만, 예전에 한번 둘러본 CODE TREE 사이트에서 식목일 기념 코딩 퀴즈를 개최했다는 메일이 하나 왔다. 내 실력을 점검할 수 있기 때문에 코딩테스트라면 뭐든지 대환영이었던 나에게는 기쁜 소식이었고, 바로 참가했다.
나무 기증 이벤트 기준으로 총 7문제에 시간은 2시간 반이 주어졌다. 이벤트를 신경 쓰지 않는다면 다시 풀어볼 수도 있어서 시간은 사실상 무제한이긴 하다. 이벤트이니 문제가 엄청 어렵지는 않을 거 같아서 시간 내에 올솔브를 목표로 대회에 임했다.
예상했던 것처럼 문제가 엄청 어렵지는 않았고, 개인적으로 느끼기에는 solved 티어 기준 브론즈~골드 문제들이 출제된 것 같다. 또한 난이도 순으로 문제가 배치되어 있었다.
2시간 반 동안 총 다섯 문제를 풀어냈고, 한 문제는 TLE를 받고 못풀었고, 다른 한 문제는 접근 방식을 생각해내지 못했다. 기왕이면 올솔브를 하고 싶었는데 아쉬웠다. TLE를 받은 문제는 나중에 대회 종료 후 다시 풀어서 해결했다.
2. 문제 풀이 및 후기
A. 나무 출력
제출 형식에 메모장이 있으면 그냥 복붙하면 끝인데 없어서 한줄한줄 복사해서 붙여넣어야 했다. 이보다 좀더 쉬운 방법이 있는지, 아니면 다른 언어는 좀더 쉬운지 의문점이 남는다.
B. 나무 심기
정렬해서 제일 큰 음수 두 개, 제일 큰 양수 두 개를 곱하면 가장 큰 수가 나오고… 이런식으로 생각할 수 있다. 그러나 $N\leq 100$이고 시간 제한이 $1000ms$이므로, 그냥 이중 반복문을 돌려서 풀면 된다. 시간복잡도 분석이 중요하다는 것을 다시 한번 느끼게 해준 문제였다.
C. 나무 공격
처음에 브루트포스 형식으로 구현하려 했다. 그런데 더 생각해보니 그냥 각 행의 환경 파괴범 수를 세서, $L\sim R$ 구간의 수를 $-1$해주면 됨을 알게 되었다. 무작정 구현을 시작하는 것이 아니라, 미리 어떻게 풀지 고민하며 최대한 단순화해서 푸는 작업이 중요하다는 교훈을 얻게 해준 문제였다.
D. 나무 수확
브루트포스로 구현하면 시간초과가 나는 것을 계산으로 확인했기 때문에, 이전 문제들보다는 훨씬 까다로운 문제임을 눈치챘다.
백준의 많은 문제를 풀어본 결과, 다음과 같은 나만의 논리를 완성하였다. 실버\sim 골드 난이도의 문제들 중 브루트포스, 그리디 알고리즘, 애드 혹이 통하지 않는 문제가 있다면 다음과 같은 방법들 중 하나를 의심할 수 있다.
- dynamic programmin - 다이나믹 프로그래밍
- binary search - 이분 탐색
- stack or queue - 스택 or 큐
- priority queue - 우선순위 큐
- two pointer - 투 포인터
문제의 형태로 보아 DP가 가장 적절함을 느꼈고, 그렇게 풀어냈다.
$dp[i][j][0] \rightarrow$ 스프링쿨러를 사용하지 않고, $(i,\, j)$까지 도달했을 때 얻을 수 있는 최대 열매 수확량 $dp[i][j][1] \rightarrow$ 스프링쿨러를 한번 놓고, $(i,\, j)$까지 도달했을 때 얻을 수 있는 최대 열매 수확량
E. 나무 조경
$2\leq N \leq 4$이기 때문에 구현 문제임을 알 수 있다. 많이 풀어본 유형이었기 때문에 빠르게 구현해서 성공시킬 수 있을 줄 알았다. 그런데 테스트케이스를 돌려보니 계속 원하는 답이 나오질 않아서 생각보다 많이 헤맸다.
확인해보니, 현재 위치에서 오른쪽이나 아래쪽을 묶을 때, 그 위치가 이미 묶인 곳인지 확인하는 코드를 빼먹었다는 것을 알 수 있었다. 굉장히 많이 풀어봤었던 유형이었음에도 불구하고 이런 실수를 했서 한참동안 못찾았다는 사실에 놀랐다. 아무리 문제에 익숙해도 처음 코딩할때 실수하면, 나중에 문제가 되는 부분을 찾기 정말 힘들다는 것을 느꼈다.
F. 나무 섭지
유령을 피해 탈출하는 문제였다. 대회 시간 내에서는 WA와 TLE를 받고 풀지 못했다.
처음에 DFS를 돌려서 나아가는데 도달할 위치와 모든 유령간의 거리를 계산해서 유령거리<=도달한 시간이면 해당 위치로는 가지 않는 방식으로 코딩을 시도했다. 매 위치마다 모든 유령과의 거리를 반복적으로 계산해야 했기 때문에 오버헤드가 너무 커서 꺼림직했지만, 달리 다른 방법이 생각나질 않아서 그대로 코딩했다.
구현했더니 WA를 받아서 이를 해결하는데도 오래걸렸다. (WA를 왜받았는지 기억을 잃어버렸다…) 그런데 겨우겨우 해결했더니 예상대로 TLE를 받았다. 각 위치에서 가장 가까운 유령을 미리 저장해놓기만 한다면, DFS를 돌릴 때 위치마다 일일이 모든 유령을 확인할 필요가 없어질 텐데, 그 방법이 끝까지 생각나질 않았다.
나중에 대회 종료 후 좀더 생각해보니, 모든 유령을 처음에 queue에 집어넣고 BFS를 돌리면 visited 체크 과정에서 중복작업을 하지 않을 수 있어, 맵 전체를 한번 탐색하는데 그치면서 모든 위치에서 가장 가까운 유령을 알아낼 수 있음을 알게 되었다.
나중에 탐색 방식도 DFS보다 BFS가 구현하면서 예외사항 체크도 편할 거 같아서, 코드를 통채로 갈아엎고 BFS로 바꾸기도 했다. 그리고 결국 해결했다.
유령의 최소 근접 거리를 알아내는데 BFS를 사용하면 된다는 사실을 깨닫기 굉장히 어려웠다. DFS/BFS 문제를 풀면서 BFS라는 방법을 생각해내지 못한 것에 대해서 스스로에게 굉장히 의아함을 느낀 문제였다.
댓글남기기