알고리즘 공부 후기

300솔 달성!

방학때만 거의 200문제를 푼 것 같다.

선린에 입학하고 1년동안 알고리즘 공부를 어떻게 했는지 적어볼까 한다. 제대로 한 기간은 얼마 되지 않지만, 요즘 들어 점점 실력이 늘고 있는게 보여 뿌듯하다.

 

2021 12월 - 백준을 처음 알게 됨

그전에도 알고리즘이 뭔지는 알고 있었지만, 공부해본적은 한번도 없었다. 앱 개발을 포트폴리오로 제출해서, 선린 특별전형에 합격했고, 그 이후 신입생 단톡방에서 백준을 처음 알게 되었다. 처음 봤을 때 재밌어보여서 몇번 끄적이다 귀찮아서 그만두었던 기억이 난다. 이분탐색을 이때 배웠다. 

 

2022 7월 - 선린 천하제일 코딩 대회에 나가다

뭔가 재밌어보여서 친구들과 함께 참가했다. 나 - 브론즈 5, 친구1 - 언랭, 친구2 - 실버5 조합으로 나간 대회였다. 그 당시 나는 파이썬으로 입출력을 받을 줄도 몰라 예선에서 공식 문서를 1시간동안 뒤졌다(...). 결국 포기하고 c로 제출한 기억이 아직도 난다. 예선에서는 브론즈 2문제를 풀게 되었다.

 

이 당시 나는 아무런 알고리즘을 몰랐다. 그래서 본선에는 입출력을 받는 방법을 외우고 갔었다.

19명중에 11등을 한 사진이다.

당시 내가 3문제를 풀고 팀원들은 각자 한 문제를 계속 잡고 있었는데, 한명은 그 대회에서 가장 어려운 문제를 잡았고, 다른 한명은 파라매트릭 서치를 알아야 풀 수 있는 문제를 잡고 있었다(이 친구는 그 당시 언랭이었다). 결국 나 빼고 아무도 문제를 못풀었다. 당시 푼 문제는 실버5, 실버4, 실버4로, 지문을 읽을 줄 알면 풀 수 있는 쉬운 문제였다.

 

이때 생각보다 문제를 푸는 것이 재밌다는걸 깨달았다. 그래서 아는 친구 중 알고리즘 연구반에 있는 친구에게 부탁해서, 알고리즘 연구반에 들어가게 되었다.

 

2022 7월 ~ 8월 - 알고리즘 연구반에 들어가다

사실 여기서부터 뭔가 잘못됨을 느꼈어야 했다. 아는거는 기초 정수론 밖에 없던 내가 처음 들었던 수업은 세그먼트 트리 였다. 코드를 복붙하는 수준에 지나지 않았고, 레이지 세그를 배울 때 부턴 모니터에 수업을 틀어놓고 잠을 잤다. 정수론과 대수학이 생각보다 흥미로워서, 이 때 알아도 쓸모없는 수학 지식을 많이 습득하게 되었다. 그 당시 푼 문제를 보면 전부 다 수학 문제 or 그리디였다. 

 

2022 8월 ~ 11월 (이 기간에는 알고리즘을 안했다)

 

2022 12월 - 본격적으로 알고리즘 공부를 시작하다

이때 기초적인 자료구조와 알고리즘을 공부하기 시작했다. 그 후, 다이나믹 프로그래밍이 너무나 어렵게 느껴져서, dp문제만 계속 풀었던 기억이 난다. 12월 말까지는 열심히 하다 방학이 시작하니 귀찮아져서 때려치고 애니를 봤다. 이때즘부터 백합에 빠진 것 같다.

봇치가 내 백합 입문작이었다

그러다 친구가 1월에 usaco라는 것이 있다는 것을 알려줘서, 재밌어보여서 참가해보았다. usaco 문제는 상당히 재밌었다. 문제가 쉽다고 생각해서 2문제를 풀고 프로세카를 2시간 정도 하였는데, 남은 1 문제가 풀리지 않아서 당황하다 대회 시간 30분 정도를 남기고 ac를 받았다. 브론즈 만점을 받으면 바로 실버를 풀 수 있었는데, 그 날에 학원이 없었어서 바로 실버를 풀러 갔다. 2번 문제를 봤는데, dp + 그래프 문제였다. 보자마자 문제의 아이디어가 떠올랐고, 구현하고 제출하니 당연히 틀렸다. 3시간동안 디버깅하다보니 새로운 아이디어가 생각났고, 또 몇번의 디버깅 후 대회가 끝나기 5초(!!!)전에 AC를 받을 수 있었다. 그때를 생각해보면 심장이 엄청 빨리 뛰었었다. 문제를 맞추고 너무 기뻐 거실로 달려가서 아버지한테 엄청 자랑했다.

 

그 당시 푼 문제는 내가 생각해도 어려운 문제였고, 현재 그 문제는 백준에서 골1 ~ 플5 사이를 왔다갔다 하고 있다. 내가 대회에서 고난이도의 문제를 풀었다는 사실에 엄청난 자신감이 들었다. 이때부터 알고리즘 공부를 엄청 열심히 했다. 1달동안 거의 100문제를 풀었다.

1월 후반 부터 스트릭이 빨개진다.

기초 자료구조, 그래프, dp, 그리디, 세그먼트 트리, 다익스트라, 오일러 투어 테크닉 등 다양한 알고리즘을 배우고 그 응용 문제를 풀었다. 1월의 자신감을 가지고 문제를 푸니, 전보다 훨씬 잘 풀렸고, 공부를 하다보니 점점 풀리는 문제의 난이도가 올라가기 시작했다. 

 

그리고 어제 (2월 27일), 나는 두번째 usaco 실버를 풀게 되었다. 그동안 연습한 것도 있고, 자신이 있었다. 결국 1시간 30분만에 2솔을 성공했지만, 마지막 남은 한 문제는 풀지 못했다. 아직 usaco가 끝나지 않아서 자세한건 말 못하지만, 못풀만했다고 생각한다. 실력이 는게 눈에 보여서 너무 행복하다.

 

전에 인스타에 올린 글에서도 말했지만, 알고리즘은 나한테 엄청 특별한 의미를 지닌다. 지금까지 무언가에 열정을 가지고 열심히 해본적이 없는 인생이었는데, 최근 한달간 엄청난 열정을 가지고 노력했다고 생각한다. 앞으로도 계속됐으면 좋겠다.