5월 알고리즘

일주일에 다이아를 다섯 문제씩 풀겠다는 다짐을 했다.

이 다짐을 어느 정도 지켰다.

 

마지막 주는 두 문제 밖에 풀지 못해서 아쉽지만, 6월 첫째주는 다시 6문제를 풀면서 달리고 있다.

 

현재 해결한 다이아는 98문제이다. 다이아 문제 짬을 좀 늘려보겠다는 생각으로 시작했는데, 금방 100문제에 다다라서 기분이 좋다.

더불어, 플래티넘 5~3은 각각 95문제 이상 해결한 것으로 보인다.

 

일단, 5월 동안 해결한 다이아 문제들을 나열해 보겠다.

• 13514번: 트리와 쿼리 5
• 13546번: 수열과 쿼리 4
• 13545번: 수열과 쿼리 0
• 14504번: 수열과 쿼리 18
• 17410번: 수열과 쿼리 1.5
• 19525번: Rectangle-free Grid
• 31055번: A Graph Problem
• 23798번: 올바른 괄호 문자열
• 13550번: 수열과 쿼리 7
• 16264번: Array Study
• 9877번: Ski Course Rating
• 13557번: 수열과 쿼리 10
• 26296번: Dihotomna Dioba
• 18590번: Snowy Smile
• 1557번: 제곱 ㄴㄴ
• 8464번: Non-Squarefree Numbers
• 16074번: Mountaineers
• 13055번: K-Inversions
• 11385번: 씽크스몰
• 30485번: Journey of the Robber
• 31626번: Gift Exchange
• 22350번: 맛집 추천
• 18438번: LCS 5

일단 일주일에 다섯 문제를 어떻게든 맞춰야겠다는 생각을 해서, 재미없는 수열과 쿼리 문제들과 비슷한 문제 쌍들을 많이 풀었다.

그들을 추리고 남은 재밌는 문제들은 생각보다 몇 개 없다. 스포 없는 후기.

• Rectangle-free Grid: 3시간 고민해서 해결한 문제다. 그냥 문제에서 풍기는 그대로 아이디어 원툴 애드혹 문제다.
• A Graph Problem: 자료구조를 연습하기 좋은 문제다. 이걸 얼마나 잘 푸는지에서 자료구조를 잘 이해하고 있는지가 드러난다.
• 올바른 괄호 문자열: 괄호열과 관련된 간단한 문제다. 해당 개념의 심화 문제로 적절해 보여 동아리 강의에 연습 문제로 제공했다.
• Ski Course Rating: 크루스칼의 공과 동일한 문제다. 해당 테크닉을 연습할 수 있는 문제, 딱 그 정도다.
• 제곱 ㄴㄴ: 고평가된 문제다.
• 씽크스몰: 정밀도가 문제라면 자릿수를 반으로 쪼개서 FFT를 하자!
• Journey of the Robber: 그냥 푼다면 트쿼5다. 하지만 쿼리를 루트씩 묶어서 O(1) LCA를 돌린다면? 흥미롭다. O(log N) LCA는 TLE를 받으니 주의.
• Gift Exchange: 심플한 아이디어와 간단한 풀이이지만,, 어렵다. 이런 문제는 어떻게 만드는 것인가.
• 맛집 추천: 머리가 터지기는 하나, 해당 테크닉을 적용하는 것은 감탄을 자아낸다. 어떻게 이게 되지?

 

작년 KOI~NYPC 시즌 때만큼 머리를 많이 쓰지 않는 요즘인 것 같다.

이상한 수열과 쿼리를 푸는 것은 물렸다.

하나를 풀어도 좋은걸 풀어야겠다.

 

그냥 일주일에 어떤 OI 세트 한 두 개를 다 푼다던가 하는 식으로 하는게 나을 것 같다.

더불어 방학에도 어떻게 연습해나갈지 고민해보려고 한다.