내가 알고리즘 문제풀이를 공부한 방법

기존에도 koosaga님의 글이라던가 남남서님의 블로그에 각종 글들이 있었지만, 자료의 최신화와 내가 겪은 시행착오를 공유하기 위해 작성한다. 특히 첫 번째 링크의 글은 5년이 다 되어가는 글이기 때문에...

내가 스스로 겪고, 공부한 방식에 대해서 방법론 위주로 작성한다.

 

 

solved.ac

 

18년도랑 비교하여 23년 2월 현재 PS 환경에서 가장 크게 바뀐 점은 역시 solved.ac라고 할 수 있을 것 같다.

사실 현재 한국에서 알고리즘 공부를 하는 사람중에 solved.ac를 모르는 사람이 얼마나 될지는 모르겠다. 그만큼 solved.ac는 편리하고, 관리가 잘 되고, 자신의 수준에 맞거나 알고리즘에 맞는 문제를 고를 수 있는 시스템이다.

 

• AC Rating : 소위 말하는 레이팅작이다. 기본적으로 티어 상위 100문제로 레이팅을 매기기 때문에, 자신이 힘들지 않게 풀 수 있는 문제보다 더 어려운 공부를 하기 좋다. 하지만 기본 티어가 높은 알고리즘에만 특화된 공부를 하거나, 아예 자신의 수준에 걸맞지 않는 문제를 붙잡고 있게 될 수도 있다.
• 랜덤 디펜스 : 나는 stonejjun03의 글에서 처음 접했다. 자신이 풀 수 있는 정도 난이도의 문제를 랜덤하게 뽑아서 목표 시간을 가지고 푸는 공부 방식이다. 문제 편식을 막을 수 있고, 정말 다양한 문제를 접하게 되고, 문제를 푸는 속도를 늘릴 수 있다. 모르는 알고리즘을 사용하는 문제라도 태그를 볼 수 있기 때문에, 새로운 알고리즘을 공부하게 되는 계기가 될 수 있다. 자기가 편하게 풀 수 있는 난이도보다 살짝 높은 난이도의 랜덤 디펜스를 하면 기본기를 다지기엔 이보다 좋은 공부 방식이 없다고 생각한다. 10문제 이상의 많은 문제를 빠르게 풀어야 하는 ICPC 준비의 경우, 플래티넘 전체 난이도에서 랜덤 디펜스를 돌면 리저널 수상권도 노릴 수 있을 것이다. 단점이라면, 개인적으로는 다이아 4 이하의 난이도가 한계라고 생각한다. 다이아 4와 다이아 3은 난이도 격차가 꽤나 크고, 그 이후 티어에서는 격차가 더욱 벌어지기 때문이다. (어떤 다이아 문제라도 2시간 내에 풀어낼 수 있다면 이미 CF Rating 3000을 넘겼을 것이다...) 랜덤 디펜스는 결코 쉽지 않으며, 내가 자신있는 난이도의 문제의 난이도를 확장시키기 위해 유용하게 사용될 수 있을 것이다.
• 알고리즘별 공부 : solved.ac에는 알고리즘 태그가 존재하기 때문에, 자기가 연습하고자 하는 알고리즘에 대한 문제를 뽑아서 공부할 수 있다. 더 설명할 필요는 없을 것 같다.

 

solved.ac의 등장으로 알고리즘 공부의 접근성이 정말 크게 개선되었다고 생각한다. 공부할 주제에 맞는 양질의 문제를 쉽게 검색할 수 있고, 자신과 문제의 수준을 수치화해서 직관적으로 알아볼 수 있고, 인터넷 상에 풀이 자료가 없는 문제라도 알고리즘 태그가 있다면 힌트를 얻을 수 있고, 레이팅 시스템으로 공부에 좀 더 자극을 줄 수 있다. 나도 solved.ac를 통해 큰 실력 상승을 이룰 수 있었던 것 같다.

 

 

ICPC

 

ICPC를 준비하는 데에는 사실 위에서 서술하였듯이, 개인 실력에는 랜덤 디펜스가 가장 도움이 된다고 생각한다. 22년도 서울 리저널의 경우 solved.ac 기준 다이아 5, 21년도 기준 다이아 3(이 문제의 경우, 비슷한 문제가 이미 존재하는 문제였다.) 이하의 문제만 빠르게 풀 수 있다면 은상을 수상할 수 있었다. 리저널의 수상권을 가르는 것은 비교적 쉬운, 그리고 상대적으로 많은 문제를 빠르게 풀어내어 페널티를 적게 누적하는 것이 중요하기 때문에, 랜덤 디펜스로 기를 수 있는 능력에 정확하게 부합한다. 예선 통과컷도 마찬가지이다.

 

다이아 하위(다이아 4 이하) 정도를 확실하게 풀어낼 수 있는 팀이라면, 두 가지 선택지가 있다. 첫 번째는 페널티를 줄이는 전략으로, 코드의 정확도를 늘린다던지, 풀이를 내고 코드를 구현하는 속도를 늘린다던지, 선택지는 굉장히 많다. 이를 더 연습하고 싶다면, 랜덤 디펜스를 더 하면 된다.

두 번째는, 남은 시간동안 어떻게든 한 문제를 더 풀어내어 문제수를 올리는 전략이다. 후술하겠지만 올림피아드와 성질이 비슷하기 때문에, 비슷한 식으로 공부를 하면 된다.

ICPC는 팀 대회이기 때문에, 개인 실력도 물론 중요하지만 팀의 협동 능력을 중요하게 본다. 특히 팀의 전략이 굉장히 중요하기 때문에, 높은 성적을 노린다면 꼭 전략과 역할 분담을 잘 짜고 팀 연습을 최대한 많이 해 보자. 팀 연습은 오프라인과 온라인, 1컴퓨터 연습과 3컴퓨터 연습이 정말 엄청나게 느낌이 다르기에, 최대한 리저널의 규칙에 맞추어서 실전과 같이 팀 연습에 임하는 것이 좋다.

 

팀 연습에 필요한 셋의 경우, 처음에 언급한 koosaga님의 글에 자세히 적혀 있기 때문에 따로 서술하지 않겠다. 좋은 ICPC 셋은 지금이나 그때나 비슷한 것 같다.

개인적인 의견이지만, 나는 일본 쪽 셋을 정말 좋아한다. 혼자 5시간 잡고 돌기에도 재밌고, 팀 연습 하기에도 좋고, 문제 난이도도 적당하다. 한국 리저널도 물론 좋지만, 이 쪽은 국내 대회다 보니 팀원 모두가 한 문제도 모르기는 힘들기에 이걸 가지고 팀 연습을 할 수 있을까?라고 하면 잘 모르겠다. 적어도 내가 21년도에 이뤘던 팀은 한국 리저널로 팀 연습을 할 수 없었다...

 

 

Olympiad

 

사실 나는 올림피아드에서 그다지 좋은 성적을 거두지 못했다. KOI 고등부에서는 은상 한번과 장려상 한번밖에 타지 못했고, 계절학교에서는 괜찮은 성적을 냈지만 결국 IOI 국가대표로 선발되지는 못하였다. 그러나, 내 실패의 경험을 되돌아보며, 그리고 현재진행형으로 공부하고 있는 방법을 바탕으로 '이렇게 공부했으면 좋았을텐데'라는 글을 작성해 본다.

• 문제 셋 돌기 : 실제 대회처럼, 적당한 문제 셋을 잡아서 5시간 동안 풀어보는 방식이다. 실제 대회와 같은 시간을 사용하여 실전 감각을 기를 수 있다. 또한, 시간과 풀 문제를 정해서 풀기 때문에 정한 시간 동안은 풀 수 있는 문제가 더 이상 없더라도 풀이에 대해 고민을 계속 해보는 것이 좋은데, 이를 통해 여러 방향에서 접근하며 풀이를 생각하는 능력을 기를 수 있다. 보통은 알고리즘이 편향되어 출제되는 경우는 잘 없기 때문에 랜덤하게 문제를 뽑는 효과를 내기도 한다. 물론, 셋을 잘못 고르면 5시간동안 고통을 받다 끝날 수도 있다.... 또한 중요한 점은, 업솔빙을 꼭 하고 넘어가야 한다. 스스로 생각하지 못한다면 풀이를 확인해서라도 확실히 풀고, 구현까지 끝마치고 넘어가는 것이 중요하다.
• 어려운 문제 풀어보기 : 자력으로 풀 수 있는 문제의 한계선에 걸친 정도의 문제를 몇시간, 심하면 며칠이던 간에 붙잡고 풀어 보는 것은, 풀이를 보고 풀더라도 좋은 공부 방식이다. 특히 자료구조 문제들은 쉬운 문제가 어려운 문제의 하위호환인 경우가 많기 때문에 효과적이다. 레이팅작의 굴레에 빠져들지 않도록 주의하자.
• IOI 계절학교 : 국내에서 올림피아드를 공부하기 위한 최고의 경로이다. 중학교 2학년부터 고등학교 2학년까지 3월에 서류를 신청할 수 있으며, 이외에는 KOI 2차 대회 상위 입상자들에게도 메일로 기회가 온다. 2주 동안 반쯤 강제 반쯤 자진하여 감금당해서 문제만 풀게 되며, 매주마다 선발고사처럼 진행되는 모의고사가 시행된다. 또한, 겨울학교 마지막 날에 1차 선발고사를, 이후 시행되는 2차 선발고사를 통해 IOI 국가대표(처음반 학생의 경우 계속반 진급의 기회)를 선발한다. 처음반의 경우 매일 오전 알고리즘 수업과 오후 실습, 저녁 실습 문제 풀이와 업솔빙을 진행한다. 계속반의 경우 매일 OI 셋을 돌며 풀이와 토론 및 업솔빙을 진행한다. 문제와 교수진, 코치진의 수준과 퀄리티가 굉장히 높으며, 실습에 성실히 참가한다면 비약적인 실력 성장을 이룰 수 있을 것이다. 나 또한 17/19년도 여름학교와 18/20년도 겨울학교에 학생으로 참가했고, 21/22/23년도 겨울학교와 21년도 여름학교에 코치로 참가했다. 코로나 이전 오프라인 계절학교에 비해 최근 온라인 계절학교는 학생들의 참여도나 몰입도가 낮아서 아쉽다. 하루빨리 다시 오프라인으로 전환되기를 바란다.