솔브드 DiamondV 달성 후기

백준을 시작한지, 1년 7개월 지났네요. 드디어 저도 다이아에 달성을 했네요.

solved ac 디스코드 서버에서 최초 승급에 한하여, 축하 알림이 뜨는 것을 모두가 바라는 것 같아요. 저도 솔브드 디스코드 서버에 실버 때 들어가서, 이 기능이 추가 되었으면 좋겠다고 생각을 했었어요. 저 화면을 보면서 다이아를 가는 것을 기대했었지만, 벌써 와버리게 되었네요.

 

 

1. 달성 후기

작년에, 소프트웨어학부로 전과를 하는 시점에 플레5를 달성했었어요. 그 시점에서 새롭게 생긴 목표는, 이제 이것을 전공하기로 결심했으니, 다이아는 한 번 찍어보고 싶다는 것이 첫 번째였고, 작은 대회라도 좋으니, 알고리즘 대회에서 유의미한 등수에 들어서, 상을 한 번 받아보는 게 목표였어요.

첫 번째 목표는 달성했네요. 두 번째를 하기 위해서, 그래도 조금씩 대회를 나가 보고 있지만 쉽지 않은 것 같네요. 작년에 교내 대회와, 올해는 서울대 SCSC 대회, 고려대 맷코컵 번째 목표는 달성했네요. 두 번째를 하기 위해서, 그래도 조금씩 대회를 나가 보고 있지만 쉽지 않은 것 같네요. 작년에 교내 대회와, 올해는 서울대 SCSC 대회, 고려대 맷코컵, 교내대회, ICPC와 고등학교 친구들과 함께 UCPC도 나갔었네요.

결과는 뭐, 고수들이 엄청 많다는 것을 깨닫고 끝났죠. 교내 대회에서는, 약간 장려상 느낌으로 자료구조 책을 하나 받은 게 전부네요. (이미 다 아는 내용이라 그냥 책장에 꽂아만 뒀다.)

 

 

2. 티어는 보장하지 않는다.

티어에만 집중해서, 올리다보니까, 내실이 없다는 것을 깨달았어요. 그리고 진짜 티어는 아무것도 대변해주지 않는 다는 것을 깨달았고요. 저는 주로, 기하학 위주로 풀었기에, 그래프와 dp이런 건 진짜 못 풀어요. 일례로, UCPC에서 bfs가 나왔는데, 갑자기 bfs를 짜는 방법이 기억나지 않아서, 핵심 아이디어와 함께 그 문제를 팀원에게 넘겼던 일도 있었어요.

 

 

가끔, 인터넷을 보면, 백준 다이아 찍으려면 얼마나 걸려요?와 같은 질문이 보여요

 

 

솔브드는 한 번 올리면, (하향 기여를 받지 않는 이상) 자기의 실력이 낮아진다고, 점수가 낮아지지는 않아요. 그리고, 주어진 문제를 무조건 풀어야하는 것이 아닌, 여러 문제들 중에 겨우 100문제의 합 가지고만 점수를 계산해요. 그래서, 풀다가 이 문제는 별로인 거 같으면 버리고 딴 거 풀면 그만이죠.

따라서, 꾸준히 새로운 걸 배우고 더 높은 난이도의 문제를 풀려고 시도하기만 하면, 누구나 가는 거 같아요. 사람마다 진짜 다른 거 같아요. 그냥 브론즈 문제하나만 내고 스트릭만 채우는 사람도 있고, 진짜 진심으로 이거만 해서 6개월도 안 되서 가시는 분들도 있고 말이예요.

 

 

3. 다이아까지 찍으면서 새로 배운 알고리즘들

레이팅은 최근 6개월에 이 정도 올랐네요.

새로 배운 알고리즘으로는,

• 스프라그 그런디 정리 : 특정한 게임 이론 문제를 풀 수 있는 정리예요. 이걸 가장 많이 풀었어요. 플레이상 문제를 25문제나 풀어서 레이팅 높일려고 좀 과하게 풀었죠. (100문제가 레이팅에 반영되는데 25%나 되니까 좀 과하게 풀었네요.)
• 회전하는 캘리퍼스 : 가장 먼 두 점 사이의 거리를 구하는 알고리즘이예요. 볼록껍질의 연장선으로 배웠어요.
• lis, lcs : 골드 하위급인데 아직도 몰랐어서, 기초만 살짝 배웠었어요.
• tsp : 외판원 순회로, 모든 도시를 전부 순회하고 돌아오는 경로를 최소 비용으로 가는 알고리즘이예요. 시간복잡도도 높고, 활용하기가 쉽지 않아서 기본급 알고리즘만 풀었었어요.
• flow, 이분매칭 : 최대유량 문제인데, 다이아까지 가는 마지막 50점에서 이걸 공부했어요. 소스에서 싱크까지 하수관이 연결 되어있다고 칠 때, 그 하수관에 최대 얼마만큼의 물을 흘릴 수 있냐는 문제예요.
• cht(convex hull trick) : 볼록하게 돌아가는 구간의 선들을 찾아요. (이걸 그림없이 어캐 설명할 지 모르겠네요.)
• 삼분탐색 : 이분탐색은 left, right 2개로 위치를 찾았다면, 3분 탐색은 3개를 가지고, 극댓점 또는 극솟점을 찾아요.
• fft : 고속 푸리에 변환

그리고, 이제 각종 다이아 애드혹 문제, 이상한 구현 문제, 상한 원 둘레 구하기 문제, 런전처 문제까지... 이상한 다이아를 몇 개 더 먹고 달성 했네요.

좀 남들과는 다르게 정석적이지 않은, 문제들만 풀었네요. 돌아보니까, 저는 푼 사람 숫자가 두 자리 이하, 또는 한 자리 수 문제면 더 열광적으로 문제를 팠었어요. (다른 사람들이 못 푼 문제를 풀었다는 느낌으로 개인적으로는 기분이 좋았거든요.)

 

4. 앞으로...

문제 푸는 게 참 재미있긴 해요. 하지만, 이제 2학년 2학기에 도달했는데, 아직 아무 개발도 제대로 할 줄 아는 것이 없는 것이 마음에 젤 걸려요. 수업시간에도 백준 아이디어만 떠오르면 수업에 집중도 잘 안 되고 말이예요.

학교 ps동아리도 점점 규모가 줄어드는 거 같고, 알고리즘의 끝은 탈알고라는 말도 있는 거 보면 진짜 개발을 배워야하는데 말이예요. 한 동안은 저점 다지기를 좀 더 하다가 아마 아는 친구들처럼 코드 포스로 넘어가거나, 아니면 다시 또 루비를 향해서 달리지 않을까요?

알고리즘을 그만두고 개발을 본격적으로 배우는 세계선의 저가 더 행복했을려나 잘 모르겠네요. 그래도 힘닿는 데까진 ps를 해보고 싶긴 하네요.