USAMO vs USACO IV

Competitive Programming (CP) 혹은 USACO 공부방법은 외국어를 배우거나, 운동을 배우고 훈련하는 것에 더 가깝다. 머리속에 지식(knowledge)을 쌓는 것보다 직접 작성할 수 있는 기술(skill)을 습득하는 과정이다.

 

여러가지 Blog나 참고 문서들이 있다.

1. USACO Resource page ( link )
2. Crash Course Coding Companion ( link )
3. General Resources for Competitive Programming ( link )
4. Beginner (Bronze/Silver) December Contest Prep ( link )
5. A Way to Practice Competitive Programming : From rating 1000 to 2000 ( link )

먼저, 확인해야 할 것은 CP 는 Coding Competition이 아니라 Problem Solving Competition이라는 것이다. 실제로 문제 해결과정에서 implementation이 필요 없는 것은 아니지만, 전체 문제 풀이를 10이라고 할때 구현이 차지하는 부분은 2~3 정도가 된다고 생각한다. 정확한 문제의 이해가 전체의 1/3은 차지한다. 정확한 문제의 이해는 입력과 출력의 경계를 명확하게 하고, 알고리즘 구현과정에서 주의해야 하는 부분들을 찾을 수 있게 해준다. 예를 들어 문제 풀이 과정중에 덧셈이 있고 그 덧셈값을 어떤 변수에 저장하는 알고리즘을 생각해보자. 이때, 더하는 값들의 범위와 더한 결과 값을 기록하는 변수의 범위는 달라 질 수 있다는 것을 구현하기 전에 정리하는 것이 문제의 이해 과정에 얻어지는 것이라고 할 수 있다. 그 문제 이해를 기반으로 알고 있는 알고리즘에서 구현할 수 있는 것을 문제의 답안으로 할 수  있다. 대부분의 프로그래머들처럼 문제가 생겼을때 검색을 하거나 관련 자료를 찾아서 살펴볼 수 없다. 물론, 그정도의 자료조사나 연구가 필요한 문제는 일반적인 CP의 범위 바깥에 있다. 혹은 배경지식의 부족함으로 더 준비해야 하는 부분이 된다.

 

CP를 준비하는 과정은 Web 페이지를 만들거나 app을 만드는 것과는 방향이 아주 다르다. 이런 개발 과정은 중간중간 확인과 수정이 필요하기도 하고, 기능 구현을 외부에 의존하기도 한다. 실제 개발을 하는 프로그래머에게 제일 많이 하는 조언중 한가지는 이미 만들어져 있는 것을 다시 개발하려고 하지 말라는 것이다. ( Don't invent wheel again) 즉, 이미 기존에 사용할 수 있는 것들을 최대한 활용해서 문제해결에만 집중하라는 것이다. CP에서도 문제 해결에 집중해야 하지만, CP는 제한된 시간안에서 할 수 있는 것만을 대상으로 한다. 그리고, 외부에서 빌려오는 기능은 대부분이 제한되어 있다. Python이나 Java의 확장성이 대부분의 CP에서는 제약 조건이 되고, 언어에서 기본으로 제공하는 라이브러리 기능이외 추가적인 확장 기능은 없다. 

 

시간제한이 없다면, 거의 대부분의 문제는 단순한 Brute Force 를 통해서 답을 구할 수 있다. 시간 제한이 있기 때문에 조금은 효율적인 알고리즘을 적용하는 것이다. Brute force, simple implementation은 CP에서는 중요하고 잘 훈련해야 하는 부분이다. 잘 생각해야 하는 것이 CP는 black box 테스트이다. 어떻게 구현되어 있는가는 제한 조건만 만족한다면 문제가 되지 않는다. 즉, 지금 문제 해결을 위해 필요한 명확한 알고리즘과 그 구현을 익숙하게 구현하는 것을 목표로 공부를 하는 것이다. 너무 많은 자료조사나 공부가 항상 도움이 되는 것은 아니다. 새로운 아이디어, 어렵지만 잘 만들어진 알고리즘이 일반적인 문제해결에는 도움이 될것이다. 하지만, CP에서는 간단하게 할 수 있다면, 간단하게 해결하는 것이 좋다. 확장성을 생각해서 더 범용적이고 잘 정리된 알고리즘을 준비하기 위해서 필요한 시간동안 다음 문제를 고민하는 편이 훨씬 도움이 되고, 문제가 생겼을때 더 빨리 잘못된 부분을 찾아낼 수 있다.

 

그렇지만 CP 준비 과정에서는 알고리즘이나 자료구조에 대해서 공부하는 과정을 배제 할 수는 없다. 그래서, 공부를 한다면 문제 해결에 필요한 수준으로 구현하기 위해 필요한 것까지를 목표로 해야 한다. 많은 알고리즘을 학문적으로 증명하기 위해서는 복잡한 수준의 수학과 논리가 필요하고 그런 부분은 그것을 전공으로 공부하는 대학원에서나 필요한 일이다. CP에서 필요한 수준은 명확한 단계별 논리 흐름과 그때에 어떤 형태로 자료를 다루는가 하는 것이다. 끼워야 할 자리에 레고 모양이 맞으면 끼우면 된다. 레고공장에서 어떻게 블럭이 만들어지는지 알 필요는 없는 것이다.

 

동시에 이렇게 공부를 할 때 주의해야 할 부분도 있다. 즉, 알고리즘에 대한 메타인지와 함께 실제 알고리즘 구현에 대한 메타인지도 필요하다. 즉, I know vs I think I know 를 구분하는 것도 필요하지만, I can implement vs I think I can implement 도 구분히야 한다. 알고리즘이나 자료구조를 알고 있다고 실제로 구현하지 못하면 문제를 풀 수 없다. CP에 대한 훈련은 알고리즘에 대한 지식을 쌓는 것이 아니라, 알고리즘을 구현할 수 있는 능력을 훈련한다고 생각해야 한다.

 

남이 작성한 코드를 읽는 것은 도움이 되지만, 남의 코드를 단순히 외우는 것은 크게 도움이 되지 않는다. 프로그램은 외국어를 배워서 의사소통하는것과 결이 같다. 외국어가 부족해도 손짓이나 표정을 섞어서 의사소통을 할 수 있는 것은 실제로 같은 방법으로 의사소통의 경험이 있어야 가능하고, 동시에 같은 대상에 대해서 논의 할때 가능한 것이다. 또, 다른 사람의 프로그램 코드는 읽는 것을 목표로 해야 하지, 내용을 그냥 옮겨서 문제를 풀었다고 읽은 것이 아니다. 프로그램의 논리구조를 자기의 언어로 설명하는 것을 코드를 읽었다고 해야 한다. 다른 사람의 코드를 읽어서, 자기가 pseudo code로 프로그램을 작성할 수 있어야 코드를 읽고 이해했다고 할 수 있다. 

 

CP에서는 빠른 실패가 도움이 될 수도 있다. 경우에 따라 다르겠지만, 자기가 작성할때 생각하지 못했던 부분을 채점 프로그램이 찾아 줄 수도 있다. 생각하지 못한 입력의 범위나 출력의 범위를 알기 위해서는 빨리 실패하는 것도 좋다. 제출과 채점에 불이익이 없다면, 채점 시스템도 디버깅 툴로 이용할 수 있다. 훈련을 위해서 online judge 프로그램을 사용한다면, 당연히 활용할 수 있는 장점중의 하나이다.

 

2019년 미국 대표중 한명이었던 William Lin 이 CP 에 대해서 설명한 내용은 살펴볼 필요가 있다. ( link )  

 

CP를 훈련하고, USACO를 준비할때 참고하기 위한 리스트이다.  

1. I/O에 주의한다. 항상 특정한 입력과 출력을 할 수 있도록 준비해야 한다. 
2. 문제풀이는 종이에서도 충분히 가능하고 동시에 자기가 생각한 알고리즘의 소요시간이나 메모리에 대해서 분명히 이해하고 적용해야 한다.  
3. 하나의 문제에 일정 시간 이상 사용하지 않는다.  한문제에 1시간이 넘어간다면, 지금 풀 수 없는 문제로 표시하고 다른 문제를 보거나, 다른 사람의 답안을 읽어보는 것도 좋다.
4. 내 프로그램은 내가 검토하지 말자. online judge에서 검증 받을 수 있는 문제들로 연습해서, 시스템의 도움을 받자.
5. 대부분은 현재 내 수준에 합당한 문제들로 연습하지만, 쉬운 문제, 어려운 문제들에도 일정 부분을 배정하자.
6. 한번 풀었던 문제도 입력의 조건이나 출력의 조건이 달라지면 다른 문제가 된다. 문제를 풀고, 확장 가능성을 생각해보자.