드디어... 백준 다이아 5 달성!

최근에 계절학기 관련된 일 등등 처리하느라 못 쓰다가 다시 글을 쓰게되었습니다.

 

제 블로그를 보면 알다시피 11월 초부터는 알고리즘 및 PS 관련 글을 많이 올리지 않기 시작했습니다. 뭔가 PS 관련되어 계속 공부는 하고 있는데, 그렇게 가시적으로 실력이 느는 것 같지도 않고 왠지 '내가 너무 여기에만 몰두하는 건가?'라는 생각도 들었기 때문입니다. 또한, 제 실력을 어느정도 평가 가능한 대회들도 올해는 더 이상 없어져서 흥미도 좀 떨어지기도 했습니다. 그래서 한동안 스트릭 유지를 위해서만 하루에 브론즈 5 몇 문제만 건들고, 시간이 된다면 백준 대회 찍먹해보고, 그런식으로 스트릭 유지만 하자는 마인드로 공부를 하고 있었습니다.

 

그러다가 제가 생각이 바뀌게 된 것은 12월이나 새해쯤에 solved.ac에서 굿즈 샵을 연다는 것을 기억해내었을 때였습니다. 왜인지, 그때 뭔가 '다이아 뱃지달린 키링을 사고 싶다...!'라는 생각이 들었고, 그래서 다이아 5를 달성하기 위해서 시간날 때마다 문제들을 풀어보았습니다.(이러면서도 어느정도 손도 땔 수 있다면 좋겠다는 생각도 있었습니다.)

 

원래라면은 제 목표는 '실력을 증진시켜서 대회 등등에서 좋은 지표를 얻는다' 이런 마인드였지만, 현재 목표가 '키링을 얻기 위해서 다이아 5를 찍는다'가 되었는 이상 제가 요새 푼 문제들은 제가 원래 주로 풀었던 문제들과 다른 양상을 보였습니다. 원래 제가 주로 푼 문제들은 내가 이미 알고 있는 지식들 및 알고리즘만을 활용해서 풀 수 있으나 상당한 사고력을 필요로 하는 문제들 위주로만 풀었는데, 현재 제가 티어작을 목표로 하고 있는 이상은 제가 모르는 알고리즘이지만 공부하고 이에 대한 기본 문제 및 약간의 응용하는 문제들을 위주로 풀었습니다. 또한, 제가 일부로 솔루션을 대략 알지만 귀찮아서 풀지 않았거나 어느정도 티어가 올라가면 풀려고 했던 문제들도 그냥 가능하면 다 풀어보았습니다. 그렇게 계속 티어작을 하던 도중 어느덧 딱 1점만 남기게 되었습니다.

딱 1점...이 남았네요...

진짜로 다이아5로 들어가기전에 딱 1점이 남았는데 저는 뭔가 좀 의미가 있는 문제를 풀어서 1점을 채우고 싶었습니다. 그래서 여러 생각을 해보았습니다. 'CHT 찍먹을 해볼까? 아니면 HLD? 퍼시스턴트 세그먼트 트리도 재밌어 보이는데? 아니 내가 아직 이해하지 못한 Mo's부터?' 이런 생각들을 하다가 최근에 공부했던 '인접행렬의 거듭제곱을 활용하여 길이가 K인 Path의 개수를 구할 수 있다'가 떠올랐고 이를 활용해서 BOJ 1533의 솔루션이 갑자기 떠올랐습니다. 그래서 자력솔로 다이아 5를 가는 것도 나름 의미있을 것이라 생각하고 이를 풀어보았습니다.

그래프를 다시 모델링하는게 생각한 것 보다는 좀 더 고민을 해야했으나, 결국엔 정답을 얻어냈습니다!

 

코드를 바로 짜보고 정답이겠지라는 생각과 기대감과 같이 제출해보았으나, WA가 떠서 좀 실망스러웠습니다. 하지만, 그래프를 좀 더 효율적이게 리모델링을 하는 아이디어를 결국엔 도출해서 풀어냈습니다. 그리고 다시 solved.ac로 들어가보니...

다이아 5 달성!

Diamond V라는 문구가 보였습니다. 이렇게 다이아 5를 달게 되었습니다.

 

이번에 다이아 5를 달면서 티어작도 해보았는데, 제가 원래 풀던 방식과 많이 달랐어서 여러 생각이 들었습니다. 일단 장점으로는 티어작을 하느라 여러 알고리즘들을 찍먹하여 대충 어떤 알고리즘인지도 알 수 있으면서, 제가 시도해볼려고 했던 네트워크 플로우도 공부해볼 수 있었습니다. 이러한 점들은 장점이지만, 각 알고리즘 별로 기본 문제들만 풀어서 그런지 뭔가 내실이 엄청 단단해지거나 실력이 매우 향상되었다는 생각은 들지 않았습니다. 이제 PS 내에서의 제 다음 목표는 이런 내실을 채워나가는 것 + 코드포스 퍼플 달성이 될 것 같습니다. 다음에는 올해 한 해 동안 PS 공부과정 및 기록들에 관하여 서술해볼 예정입니다. (아마 그 전에 다이아 달성하게 된 BOJ 1533을 다룰 수도 있을 것 같긴 합니다...?)