2019년 8월 진행

기본적으로 어떤 내용들을 살펴봐야 하는지 자료조사를 진행했다.

 

Competition Programming 은 제한된 환경에서 효과적인 알고리즘을 구현하는 시합이라고 할 수 있다. 메모리, 시간의 제한이 있고, 대부분의 알고리즘이나 자료구조는 직접 구현하거나 언어에서 지원하는 기본적인 내용만을 사용해야 한다. 아마도 이런 이유에서 C++이 제일 선호되는 언어인지도 모른다. Java 혹은 Pascal 도 가능하고, IOI 2019 경우(https://ioi2019.az/en-content-26.html)에는 Ruby, Python 도 제공됐다. 요구되는 코딩 수준이 복잡하고 어려운 기능이 아니기 때문에, 언어에 대한 아주 깊은 수준의 이해나 공부는 필요하지 않다고 생각했다. 그래서, USACO 19-20 season이 시작되는 12월 전까지 기본적인 학습과 다른 연습들을 해보려고 한다.  

이것을 위해서 자료를 찾고, 몇개 기사들을 읽고, 실제 문제를 살펴봤다. 그리고, 진행방향을 정리했다.  

먼저, 사용할 언어는 C++로 했다. 나중에 C++17이 적용된다고 해도, 새롭게 사용할 수 있는 기능들이 꼭 필요한 문제는 없을 것이라고 생각해서, 아래의 책 3권을 골랐다.

• 입문용: C++ in One Hour a Day, Sams Teach Yourself, 8th
• 참고용: C++ Primer, 5th
• 참고용: The C++ Programming Language, 4th

참고용 책 2권은 너무 많은 내용을 다루기 때문에 처음 입문용으로는 좀 분량이 많다. 1000 페이지가 넘어가는 책은 읽는 책이 아니라 찾아보는 사전같은 책이라고 생각한다. 혹시, C++을 더 능숙하게 다루는 프로그래머의 진로를 생각한다면 자세히 읽어봐야 겠지만, 그것은 여기에서 생각하는 범위 밖에 있는 것이다. C++ 컴파일러는 IOI 2019 에 나와있는 virtual box image에서 진행하려고 했는데, 컴퓨터 사양이 부족해서 cygwin g++ 로 구축했다. 손에 익숙하기는 vi 가 익숙하지만, 나중에 다른 사람들에게 설명하려고 생각하면 IDE를 골라야 한다고 생각해서 CodeBlock으로 연습중이다. 

 그 다음은 알고리즘, 자료구조에 관련된 공부 방법이다. "Introduction to Algorithms" 같은 온라인 강의를 찾을 수 있다. IOI 에서 요구하는 수준의 알고리즘만을 대상으로 생각하면, 수업 전체를 들을 필요까지는 없을 것 같다. 다 들을 수 있으면 좋겠지만, 일단 IOI Syllabus에 나온 것들을 중심으로 필요한 내용들을 들어보려고 생각한다.

마지막으로는 Competition Programming 준비이다. 관련된 책들이 여러가지 있겠지만, 아래같은 책들을 찾을 수 있었다.

 

• Programming Challenges: The Programming Contest Training Manual by Steven S Skiena, Miguel A. Revilla
• Competitive Programming, 3rd Edition by Steven Halim
• Competitive Programmer’s Handbook by Antti Laaksonen
• Guide to Competitive Programming: Learning and Improving Algorithms Through Contests by Antti Laaksonen

책들은 알고리즘과 그것을 적용하기 위한 연습문제들로 구성되어 있고, "Guide to Competitive Programming: Learning and Improving Algorithms Through Contests"이 가장 최근에 나왔고 온라인 참고자료들도 있어서 이 책으로 선정했다. 같은 저자가 작성한 "Competitive Programmer's Handbook" 은 온라인에 공개된 책으로 바로 내용을 확인 할 수 있다. 

 

지금 현재는 Teaching Yourself, lesson 12를 살펴보고 있다. 하루에 한시간정도 책을 읽고 코드를 살펴보고 있는데 생각처럼 빨리 넘길 수는 없다.