Programming Challenges 알고리즘 트레이닝 북

 ACM 문제를 다루고 있는 유명한 책입니다. 원래는 한국정보올림피아드 혹은 국제정보올림피아드 대회를 준비하는 분들이나 공부하실 책이었습니다. 이런 것이 구글이 뜸과 동시에 구글 면접 문제가 뜨면서 동시에 유명해지기 시작했습니다. 비슷한 시기에 비슷한 유형의 4문제짜리 넥슨의 테스트 문제도 같이 유명해졌습니다. 
 이 책은 심화학습용 문제지이지 초보들이 무턱대고 풀 수 있는 문제지가 아니라는 것을 알아야 합니다. 우선 자료구조와 알고리즘 기본 정도는 알고 있어야 합니다.
 
 
자료구조 학습에 관하여...
 이 책에 들어가기 전에 자료구조를 탄탄히 해두는 것이 중요합니다. 자료구조는 많이 알면 알수록 프로그래밍에 도움이 많이되는 관

계로 어떤 책을 사던지 끝까지 정독하는 것이 중요합니다.  저는 대학교 교재가 원서였던 관계로, 서점에 가서 둘러 보다가 자료구조와 C라는 서울대 이석호 교수님이 쓰신 책을 구매하고 정독하였습니다. 이 책은 C소스 대신에 Psuedo Code를 기반으로 하고 있습니다. 이 책의 장점은 그림 설명이 훌륭하고 설명하고 있는 알고리즘과 자료구조의 범위가 넓다는 점입니다. 실제 자료구조를 코딩해봐야 한다면 그리 훌륭한 책이 아닐 수도 있지만 다양한 자료구조 개념을 이해하는 것이 목적이라면 이 책은 꽤 훌륭합니다. 우선 저자가 한국분인 관계로 설명이 번역본에 비하여 이해하기가 쉽습니다. 자료구조는 그 자체만으로도 처음보면 굉장히 머리 아픈데 원서의 영어나 어색한 번역체를 보게 된다면 그 머리 아픔은 배가 된다고 생각합니다. 이 책 다 읽으시면 이석호 교수님께서 집필하신 화일처리론을 추가적으로 한번 훌터보는 것도 좋다고 생각합니다. 화일처리론은 DBMS가 유행하기 이전에 많이 사용하던 파일처리에 대한 내용이 담긴 책으로 External I/O처리에 대한 내용이 있다고 생각하시면 됩니다. 자료구조는 기본적으로 Memory에서의 처리를 담고 있습니다. 보조적인 교재로는 전북대 박순철 교수님께서 만드신 플래쉬 강좌를 추천합니다. 자료구조라는 것이 동작을 먼저 이해해야 하고 동작을 이해하기 위해서는 문자보다는 그림이나 애니메이션을 보는 쪽이 빠르기 때문이며 박교수님의 플래쉬 강좌는 존경받을 가치가 있을 만큼 어느 책보다 쉽게 잘 작성되어 있습니다. 그 외에 한국정보올림피아드 사이트의 기본적인 자료구조에 대한 동영상 강좌도 볼만합니다. 이 정도 자료구조를 봐야 기본적인 자료구조를 아는게 됩니다. 이 기본을 바탕으로 인터넷 검색, External I/O등에서 기존의 자료구조를 응용한 새로운 트리가 나옵니다. 뭐, 쉽게 말해서 해당 상황에 최적화된 새로운 자료구조가 나오게 되는 것입니다.
  
 
자료구조 그 후...
 분명히 STL 이전에는 자료구조를 직접 구현할 수 있는가가 중요 하였습니다. C/C++언어에서 표준화된 자료구조를 지원하지 않았기 때문입니다. 하지만 C 프로그래머가 아닌 이상 STL을 사용하게 되면 자료구조의 구현보다는 현재 상황에서 어떤 자료구조를 사용해야 하는가가 중요합니다. 또 어떻게 응용해야 하는가가 더욱 중요하게 됩니다. 그것이 결국 프로그램의 성능에 영향을 끼치기 때문입니다. 물론, 대량의 데이터를 빠른 시간에 처리할 필요없는 클라이언트 프로그래밍 같은 경우에는 생산성 높고 버그 없는 구조체 쓰는 것이 더욱 좋습니다.
  
 
알고리즘
 저 대학시절에는 자료구조 만이 중시되었던거 같은데 근래에는 알고리즘 강좌가 더욱 유명해지는 듯 합니다. 기본적인 것은 한국정보올림피아드 사이트의 고급알고리즘강좌를 보시면 됩니다. 뭐, 기본적인 것만 설명하고 있습니다. 알고리즘은 공부 분량 자체는 자료구조보다 적습니다. 자료구조가 메모리의 구조를 어떻게 효율적으로 가져가는 가에 중점을 두고 있다면 알고리즘은 문제를 전산학적으로 어떻게 효율적으로 풀어나갈 것인가에 중점을 두고 있습니다. BITComputer와 방통대 동영상 강의를 들으면서 기초를 잡고 문제를 풀면서 알아 나간거 같은데 기억이 대략 가물가물 합니다. 그래프 이론의 DFS, BFS, Merge Sort등 알고리즘의  기본은 자료구조에서도 배우는 것들이라 그리 크게 시간이 걸리지는 않았던거 같습니다. 알고리즘의 기본적인 것은 분할정복법, 탐욕알고리즘, 동적계획법, 퇴각검색법(Back Tracking), 분기한정법 등이 있으며 자료구조는 적당한 수준 정도만 알면 됩니다. 참고로 자료구조의 이해없이 알고리즘은 시작할 수 없습니다. 그 외에 추가적인 상황에 따른 다양한 알고리즘이란 것들이 있는데 Programming Challenges를 보면서 필요한 것들만 찾아서 공부하여도 될 듯 합니다. 이런 추가적인 알고리즘은 상황에 따라 쓰면 문제를 빠르고 효율적으로 풀 수 있는 장점이 있습니다. 물론, 현업에서는 문제만 풀면 되기 때문에 몰라도 큰 문제가 되지는 않습니다. 하지만 구글같이 처리 속도가 중요한 SW를 개발하는 회사에서는 굉장히 중요하게 생각합니다. 그것은 알고리즘이라는 것 자체가 해당 문제를 가장 빠르고 효율적으로 처리하는 증명된 방법이기 때문입니다.
  
  
Programming Challenges 알고리즘 트레이닝 북
  이렇게 지루할 정도로 자료구조와 알고리즘를 공부하신 후에 이 책을 보시는 것이 좋습니다. 이 책의 번역은 훌륭한 편이나 책의 설명은 번역체+집필양으로 인하여 이해하기 거의 불가능하기 때문입니다. 뭐, 번역체로 어색하게 표현한 자료구조의 요약집 같다고 할 수 있습니다. 더욱이 그림 설명이 너무 적어 자료구조 특성상 개념잡기가 너무 힘듭니다.
 문제를 풀기 위하여 필요한 기본적인 것은 자료구조, 알고리즘 그리고 수학입니다. 수학중에서는 그래도 난이도가 낮은 부분을 담고 있지만 쓰지 않던 것을 써야하는 입장에서는 쉽지 않아 보입니다. 14장 중 5장이 수학에 관한 부분입니다. 그 중에 상당수가 프로그래밍 능력보다는 수학 풀이능력을 요구합니다. 프로그래밍은 그냥 해당 풀이를 프로그램화하는 정도인 듯 보입니다.
 그 외에는 자료구조와 알고리즘의 내용을 담고 있습니다. 색칠문제와 같은 기본적이지만 본인과 같은 사람에게는 조금은 독특한 알고리즘 문제를 제외한다면 무난히 풀 수 있는 정도 입니다. 솔직히 말하여 이 책 중에 수학과 관련된 부분은 풀지 않아도 해당 분야를 하지 않는다면 대회에 나갈 이유 없는 저와 같은 프로그램머에게는 별 문제 없을 듯 보입니다. 하지만 자료구조와 알고리즘에 관련된 부분은 반드시 봐두어야 한다고 생각합니다.
 이 책의 문제는 상당수가 SW의 핵심 알고리즘으로 확장해도 손색없을 만한 내용들을 문제로 담고 있습니다. 개인적으로 이런 문제 1~2시간 만에 푸는 괴물들은 테트리스 정도는 몇 시간 만에 만들 수 있지 않을까 생각합니다. 저는 이 책 보는데 6개월 걸렸습니다. 많은 시간은 수학 공부와 앨고리즘 공부에 할애하였습니다.
 본격적으로 이 책에서 문제를 보는 시간을 한 법 계산하여 보겠습니다. 수학과 알고리즘, 자료구조를 아는 상태라고 가정하였을 때 {풀이시간} =  문제 읽기 +  문제 인식 및 정의 + 풀이 아이디어 생각(적용 알고리즘 선택) + {코딩 + 검증(ACM Robot)}으로 나누어 집니다. 흔히들 가장 많은 시간이 필요한 것이 풀이 아이디어 생각일 듯 보이지만 상당 부분의 문제는 문제 인식 및 정의에 대부분의 시간을 소요하는 듯 합니다. 즉, 어떻게 보면 문제를 얼마나 명확히 하는가가 가장 중요한 듯 보입니다. 개인적으로는 코딩 및 검증은 한 1x문제만 한 듯 보입니다. 너무 시간이 걸려서 이기도 하고 코딩 경험이 이미 몇 십만 라인의 코딩을 짜본 본인에게는 크게 득이될게 없다고 생각해서 입니다. 물론 검증도 중요하지만 검증이라는 것 자체가 생각지 못한 케이스를 찾아 버그를 수정하는 것이 주 목적인 관계로 그것도 크게 득이될 게 없다고 생각해서 코딩과 같이 하지 않았습니다.
 이 책을 읽어 보시려고 한다면 반드시 자료구조, 앨고리즘을 깊이 한 뒤에 하시기를 바랍니다. 참고로 이 책의 설명으로 공부하실 생각은 하지 않으시는 것이 좋을 듯 합니다. 그리고 자료구조는 균형트리 전까지는 하셔야 합니다.
 마지막으로 본인은 이 책을 보면서 하도 하드하게 문제 인식에 노력을 했기 때문에 문제를 보고 정의 하는 능력이 굉장히 좋아진 듯 보입니다. 게임을 할 때 몬스터의 움직임을 보면서 저 움직임이 어떻게 정의되었을 까가 보일 정도로...