[알고리즘 트레이닝] 프로그래밍 대회에 나가려고 준비한다면

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - 안티 라크소넨 지음, 조승현.김진현 옮김/인사이트

자동차 운전과 비교한다면 대부분의 사람들은 자동차의 모든 기능을 숙지하지 않습니다. 그냥 내가 당장 운전하는데 필요한 기능만 먼저 확인하게 되죠. 하지만, 자동차 경주를 하는 선수는 일반 운전자와는 다를 겁니다. 최적의 드라이빙 효율을 내기 위해 세밀한 기능에 신경 쓰게 되죠. 같은 자동차를 가지고 일반 운전자와 시합을 하더라도 몇 가지 효율적인 옵션 활용만으로 선수들은 큰 격차를 만들어낼 수 있을 겁니다.

 

이 책에서 알려주고자 하는 내용도 이와 비슷합니다. 프로그래밍 대회 그중에서도 알고리즘을 다루는 대회는 정해진 시간 내에 주어진 과제를 처리해야 합니다. 하나의 주제를 놓고 팀원들과 토론하고 협업하면서 개선해나가는 시스템과는 전혀 다른 환경입니다. 그러기에 그 안에서 가장 높은 성과를 낼 수 있는 옵션을 사용할 수 있어야 하는 것이지요.

 

최근에는 IT 기업에서도 온라인 상에서 프로그래밍 과제로 테스트를 진행하고 있습니다. 외국의 경우는 좀 다를 수 있지만, 한국의 경우에는 이런 트렌드가 점점 커지고 있습니다. 아예 코딩 테스트만 전문적으로 서비스하는 곳도 생겨나고 있고요.

 

...경진 프로그래밍 문제를 풀면 프로그래밍 및 디버깅 기술을 향상시키는 데도 도움이 된다. 일반적으로 제출한 답안이 점수를 받기 위해서는 모든 테스트 케이스를 통과해야 하므로, 버그가 없는 프로그램을 작성하는 능력이 필요하다. 이는 소프트웨어 공학에서 매우 중요한 기술로, IT 회사에서 경진 프로그래밍 경험이 있는 사람을 선호하는 것과 무관하지 않다...

 

카카오 같은 경우에는 작년(2018년) 신입 공채 때 출제되었던 문제에 대한 풀이를 기술 블로그에 올려놓기도 했습니다. 7개의 문제를 5시간 내에 풀어야 하는 과제였습니다.

http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

 

7번까지 문제가 있는데, 5번부터 정답률이 한자리로 떨어집니다. 사실 승부는 이 지점에서 나는 거죠. 4번까지의 문제는 일종의 낚시 같은 거라고 할까요~ 카카오 온라인 코딩 테스트는 그렙에서 제공하는 프로그래머스 플랫폼을 사용하는데, 카카오 CTO 출신이 참여한 회사라 그런지 카카오에서 많은 부분 밀어주고 있는 듯합니다.

http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

 

경진 프로그래밍에서는 주로 C++을 사용합니다. 자바나 파이썬을 사용하는 경우도 있지만, 고등부 이상으로 올라가면 C++을 주로 사용합니다. 현실 세계에서는 자바나 파이썬을 더 많이 사용하는 것처럼 보입니다. TIOBE 인덱스만 보더라도 자바, C, 파이썬 순입니다. 깃허브에 올라와있는 코드의 순위도 마찬가지입니다. 오히려 특정 분야에서는 파이썬이 압도적으로 대세로 보입니다. 다양한 오픈 소스 기반의 확장 라이브러리 덕분이지요.

 

https://www.tiobe.com/tiobe-index/

https://madnight.github.io/githut/

 

하지만, 경진 프로그래밍에서는 제약이 있습니다. 모든 참가자가 같은 조건에서 문제를 풀어야 하기 때문에 내 입맛에 맞는 확장 라이브러리를 설치할 수 없죠. 때문에 표준 라이브러리에 전적으로 의존해야 합니다.

 

...많은 사람이 경진 프로그램을 위한 최고의 언어가 C++라고 말한다. C++를 사용하는 것이 좋은 이유는 C++라는 언어가 매우 효율적이며, 표준 라이브러리에 많은 양의 자료 구조와 알고리즘이 포함되어 있기 때문이다...

 

때문에 이 책에서는 C++ 라이브러리 중심으로 설명하고 여러 가지 팁을 제공하고 있습니다. 그렇다고 C++의 모든 문법을 다 알아야 할 필요는 없습니다. 아주 기본적인 문법만 알고 있다면 이 책을 읽는데 큰 무리는 없습니다. 오히려 수학적인 지식의 부족에 아쉬워하는 부분이 많을 겁니다.

 

문제를 풀기 위한 코드가 그리 긴 코드는 아닙니다. 제한된 시간도 있고, 경진 대회에서 사용하는 플랫폼이 그렇게 복잡한 코드를 견디기 위한 플랫폼은 아니기 때문이 아닌가 싶습니다. 앞에서도 이야기했지만, 일부 문제는 비슷한 문제를 풀어본 경험을 가지고 해결할 수 있습니다. 어느 정도 기본 지식만 있다면 해결할 수 있는 수준이지요. 하지만, 실제 우승자를 선별하는 문제는 어떤 공식을 대입해서 해결할 수 있는 것은 아닙니다.

 

...대부분의 프로그래밍 대회 문제는 짧고 간단한 알고리즘으로 풀리지만, 그러한 알고리즘을 떠올리기가 쉽지 않다는 점도 유념해야 한다. 경진 프로그래밍의 본질은 복잡하거나 잘 알려지지 않은 알고리즘을 암기하는 데 있지 않으며, 문제 해결 능력을 기르는 것과 간단한 도구를 이용하여 어려운 문제를 풀어내는 방법을 익히는 데 있다...

 

지금은 잠시 휴식기를 가지고 있는 "문제적 남자"에 등장하는 문제들도 실제 풀이 과정을 보면 복잡한 수학이 등장하는 경우는 거의 없습니다. 문과생들도 충분히 풀 수 있는(방법을 알아낼 수 있다면) 문제들이죠. 다만, 어떻게 풀어내는지가 문제인 것이지요.

 

시중에 나와있는 알고리즘 책이나 교육 과정을 보면 내용이 다 비슷비슷합니다. 정렬 알고리즘을 이해하고 바닥에서 구현하는 것에 초점을 맞추고 있습니다. 하지만, 경진 프로그래밍에서는 표준 라이브러리에 있는 정렬 알고리즘을 어떻게 활용하는지가 좀 더 중요합니다. 물론 이를 적절하게 활용하기 위해서는 해당 알고리즘에 대한 충분한 이해가 필요하겠죠. 그래서 이 책에서는 정렬, 탐색, 그래프 알고리즘을 간단하게 살펴보고 실제 어떤 식으로 활용하는지에 초점을 맞추어 설명하고 있습니다. 

 

책의 구성을 보면 인사이트에서 출판된 "알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우"와 비슷합니다. 목차만 봐서 정확하게는 모르겠지만, 크게 다르지는 않습니다. 다만 저자가 핀란드와 싱가포르라는 차이 정도인데, 접근 방식이 좀 다르지 않을까 싶습니다. 

 

이 책을 읽기 전에는 알고리즘을 충분히 익히고 어느 정도 프로그래밍 능력이 있다면 경진 프로그래밍에서도 충분한 승산이 있지 않을까 싶었는데, 처리 시간이나 메모리 문제로 어려움을 겪을 때가 많습니다. 예를 들어 cout, cin을 사용하는 경우 입력과 출력 때문에 프로그래밍에 병목이 생기면서 시간 초과가 발생하는 경우가 있는데 저자는 아래와 같은 코드를 팁으로 제시합니다.

ios::sync_with_stdio(0); 
cin.tie(0);

사실 저자만 가지고 있는 팁이라기보다는 이쪽 바닥에서는 이미 잘 알려진 팁이더군요. 하지만, 일반적인 프로그래밍 교재에는 저런 내용이 나와있지 않죠. 저자가 2장에서 제시하는 프로그래밍 기법이라는 것은 별것 아닌 것 같지만, 실제 수행 시 실수할 수 있는 부분을 많이 줄여줄 수 있습니다.

 

시간과 관련해서는 3장 효율성에 대한 내용이 유용합니다. 하나의 예제를 가지고 복잡도를 어떻게 줄이고 문제를 빠른 시간 내에 처리할 수 있는지 아이디어를 제공합니다.

 

...알고리즘의 효율성은 경진 프로그래밍의 핵심에 해당한다. 이 장에서는 효율적인 알고리즘을 설계할 때 도움이 되는 도구에 대해 배울 것이다...

 

4장 이후에 나오는 내용은 알고리즘 관련 서적이나 수학 관련 서적에서 기본적인 내용을 다루고 있는 내용입니다. 책을 읽다가 낯선 이야기가 나온다면 체크해놓고 다른 책을 찾아보는 것도 좋을 것 같습니다. 아무래도 이 책에서는 살짝 다루고 넘어가면서 이런 알고리즘을 이렇게 활용할 수 있다 정도라서 깊게 내용을 다루지는 않습니다.

 

예를 들어 "다익스트라 알고리즘"같은 경우에는 검색해보면 이 책을 포함해 28건의 IT 관련 서적이 검색됩니다 (네이버 책 검색 기준). 독특하게 취업 카테고리에도 책이 있길래 찾아보니 삼성 소프트웨어 역량 테스트 수험서였습니다. 

 

하지만, 12장 고급 그래프 알고리즘에 등장하는 "해밀턴 경로"는 최근 출간된 IT 분야 책 중에서는 이 책에서만 다루는 내용입니다. 다른 책은 "이산 수학", "그래프 수학" 같은 타이틀이 걸려있더군요.

 

IOI 출제 요강(The International Olympiad in Informatics Syllabus)을 보면 다루는 범위가 결코 적지는 않습니다. 이 책에서 다 다루지 못하는 내용도 있을 겁니다. 번역서 제목은 "입문 가이드"지만, 결코 입문서는 아닌 것 같습니다. 물론, 프로그래밍은 어느 정도 알지만, 이런 대회에 참여해보지 못한 분들에게는 입문 가이드로서의 역할을 하겠지만, 그렇게까지 친절한 책은 아닙니다. 오히려 이 책의 목적은 저자가 밝히고 있듯이 온라인 게시판이나 블로그를 통해 공유되는 기법들을 정리하고 검증한 것이 아닌가 싶습니다. 구글 검색을 통해 다양한 정보를 얻을 수 있지만, 간혹 정답이 아닌 것을 정답인 것처럼 올려놓은 경우가 많거든요. 특히 정답이 공개되지 않은(물론 코드에 정답이 있는 건 아니지만) 경우에는 자신만의 풀이를 올려놓는데, 그 자체에 오류가 숨어있는 경우가 있어서, 경험이 없다면 그걸 정답으로 받아들일 수도 있습니다. 때문에 이 책에 담긴 저자의 노력에 감사할만한 일입니다.

 

"알고리즘 행성 여행"의 저자 제바스티안 슈틸러는 "알고리즘은 게으름이 예술로 표현된 것이다", "짧고, 간단하고, 무장해제한 것처럼 있는 그대로 모든 것을 내보이는 알고리즘은 모두 한 편의 시 같다"라고 했습니다. 게으름이 예술로 표현되었다는 이야기가 정말 따악 와 닿더군요. 시를 창작하는 것처럼 결과를 보면 누구나 할 수 있는 것처럼 보이지만, 한 편의 시를 창작하기 위해 얼마나 많은 고민이 담겨있는지 생각한다면 알고리즘도 마찬가지가 아닌가 싶습니다.

 

물론, 앞으로 레이싱 따위에 참가할 일은 없어라고 생각한다면 모르겠지만, 세상 일은 모르는 거니깐, 공식적인 대회에 나가지 않더라도 취미로 테스트 경진 대회에 참여해보는 것도 좋을 겁니다. 누군가 취미로 시를 쓰는 것처럼 알고리즘을 고민해보는 것은 어떨까요?

 

Photo by  Darren Nunis  on  Unsplash

"알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우"과 비교해보면 경진 프로그래밍에 대한 이야기는 "알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우"에서 더 많이 다루고 있습니다 (물론 목차만 보았을때). 그리고 이 책에서는 효율성, 정렬과 탐색, 동적 계획법, 알고리즘 설계 기법, 구간 질의, 트리 알고리즘을 좀 더 상세하게 다루고 있고 "알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우"에서는 실제 문제를 중심으로 해설을 8장, 9장에서 다루고 있습니다.

 

일단 책 두께 자체가 달라서 절대적인 비교는 애매하긴 합니다. 책 두께로 본다면 이 책을 가이드라고 하는 것이 좀 더 적절할 수 있겠네요 ^^ 아래 링크에서 몇 가지 책을 비교해보았습니다. 대충 비슷한 챕터를 비교한 것이라 절대적인 비교는 되지 않을 것 같습니다.

 

https://docs.google.com/spreadsheets/d/1JPTGIJiGxIK4mpamaw4JTIuznI0TuVhDfLQMZe-Wa84/edit?usp=sharing

경진 프로그래밍 가이드 비교