어떻게 더 나아지는가? (알고리즘)

https://lukipuki.github.io/contest-wiki/get-better.html

어떻게 더 나아지는가?

너가 서점에 걸어 들어 갈 때, 너는 종종 "7일만에 자바 독학 하기"라는 책을 발견한다. 그 저자들은 프로그래밍이 쉽지 않음에도 쉽다고 너에게 설득하려고 노력한다. Peter Norvig는 내가 매우 추천하는 "10년 동안 프로그래밍 독학하기"라고 불려지는 이 주제에 대한 훌륭한 에세이를 썻었다. 또한 같은 주제에 대해 Abstruse Goose의 만화를 보아라. 나는 Peter에게 동의한다 - 많은 시간과 노력이 필요하다는 것이다. 그러나 너는 여전히 너의 훈련을 가능한한 효과적으로 만들어야만 한다.

프로그래밍 컴페티션을 위한 훈령에 대해 이용할 수 있는 정보가 거의 없다. 그래서 나는 훈련 프로그램을 만드는 것을 결심했었다. 그리고 그것이 쓰여진 첫 번째 것이다. competition programmer일 뿐만 아니라 semi-professional 운동선수로서의 나의 경험에 기반한 것이다.

Training program

Training philosophy
15세의 나이에, 나는 orienteering (숲 속에서 지도와 함께 달리기)에서 경쟁하고 있었다. 나는 많이 훈련했으며, 산에서 1년에 1700km씩 달렸다. 그러고나서 나는 건강 문제를 얻었고 훈련을 완전히 멈추었다. 갑자기 나는 자유시간을 얻었고, 대신에 수학과 프로그래밍 경쟁을 위한 훈련에 시간을 썼다. 나는 실제로 나의 프로그래밍 훈련을 위하 스포츠 훈련 방법의 몇몇을 사용했다.

나는 스포츠와 프로그래밍 경쟁이 많은 공통점이 있다고 생각한다. 스포츠와 유사하게, 너는 오직 훈련과 경쟁의 한 유형을 함으로써  많이 발전하지는 않을 것이다. 훈련은 다양해져야만 하고, 너는 너의 약점에 집중해야만 한다.

축구를 예로 들어보자. 너가 축구 팀의 공격수라고 가정하자. 너는 게임 동안에 득점을 매우잘하지만, 페널티킥이 너의 약점이다. 너는 이전처럼 계속해서 훈련할 수도 있고 훈련 경기 또는 league match에서 기회가 있을 때 일주일에 2-3번 페널티킥을 할 수 도있다. 그러나 매 훈련 후에, 15간 페널티킥을 하는 것이 더 좋지 않겠는가?

똑같은 것이 문제 풀이 능력에도 해당된다. 만약 너가 한 경쟁에서 기하학 문제를 풀지 못하지만, TopCoder practice room에서 너가 연습을 대부분 한다면, 너는 발전하지 못할 것이다. 왜냐하면 TopCoder에는 어떠한 기하학 문제도 없기 떄문이다. 너는 훈련의 다른 방법을 찾을 필요가 있다.

너의 훈련은 또한 다양해져야 한다. 나는 많은 대학교가 ACM ICPC만을 위해 팀으로 훈련하는 것을 알아챘다. KTH에서, 우리는 봄에 개별적으로 훈련하고, 가을에 팀으로 훈련한다. 나는 훈련의 두 가지 유형 모두 다 중요하다고 생각한다. 예를들어, 너는 team training 동안에 dynamic programming 문제를 결코 풀지 못할지도 모른다, 왜냐하면 너의 다른 팀 친구들이 항상 너가 그 문제들을 읽기도 전에 풀 어버릴 수 있기 때문이다. 개인 훈련에서, 너는 그러한 문제들을 풀도록 강요되어질 것이고, 따라서 더 배우게 될 것이다.

우리의 훈련 프로그램은 7개의 training blocks으로 구성된다. 스포츠를 위한 훈련 프로그램들은 종종 너는 1주에 2번 1시간 씩 이것과 저것을 하고, 일주에 한 번 30분씩 저것을 하고 등등을 하라고 말한다. 여기에서 같은 것을 하는 것은 어렵다. 왜냐하면 사람들은 매우 다른 수준에서 시작하기 때문이다. 대신에, 너는 너 자신을 평가해야하고, 너의 약점과 강점을 인식해야하고, 너를 위한 올바른 훈련의 유형을 선택해야만 한다. 너는 경험있는 누군가를 알거나 또는 대학에서 코치를 가질지도 모른다, 그리고 그 사람은 너가 올바른 훈련의 유형을 차즌ㄴ데 도와줄 것이다.

너는 모든 training blocks들을 해야만 하지만, 다른 블럭들을 하는데 소비되는 시간은 사람마다 다를 것이다.

Learning algorithms and data structures
사람들이 프로그래밍 컴페티션에서 나아지려고 노력할 때, 그들은 처음에 알고리즘과 자료구조를 배운다. 트레이닝 프로그램의 모든 부분 중에서, 이것이 가장 많이 발전되어진 것이다. 그 주제에 대해 셀 수 없는 책들과, 튜토리얼, 그리고 대학 강의들이 있다.

나는 너가 Introduction to Algorithms를 읽기를 추천한다. 또한 Topcoder에 훌륭한 알고리즘 튜토리얼들이 있다. 알고리즘 수업에 대해서, 너는 너의 대학교를 확인하거나 온라인 강의를 찾을 수도 있다. 만약 너가 KTG에 있다면, Algoritmer, datastruckture och komplexitet and Problemlosning och progarmmering under press를 가능한한 들어라. ~~~

그러나, 이것은 좋은 프로그래머가 되는 것은 작은 일부일 뿐이다. 내 의견으로는 그것은 조금 과장되었다. 너는 많은 알고리즘을 알지 않고도 멀리 나아갈 수 있고, 이 훈련의 다른 블럭들이 너에게 더 도움이 될지도 모른다.

왜 내가 생각하기에 너가 너무 많이 공부해선 안되는지를 비유를 들어 설명할 것이다. 너가 산악 자전거를 고르려고 결심했다고 가정하자. 하지만 너는 결코 전에 자전거를 안타봤다. 너는 웹을 검색하기 시작하고, 유튜브 비디오들을 보고, 너는 심지어 산악 자전거에 대한 150-page 책을 산다. 공부한 지 두 달 후에, 너는 이제 시도할 시간이라고 결심한다. 너는 너가 읽고, 비디오에서 본 모든 것을 기억하려고 노력하고, 압도당한다. 너는 너 자신에게 화가난다. 왜냐하면 그렇게 열심히 공부를 한 후에도  너무 자주 넘어지기 때문이다. 너는 마지막에 실제로 자전가를 포기할 지도 모른다.

이게 너에게 어처구니 없게 들리는가? 이제 위의 자전거를 프로그래밍으로 바꾸어라. 물론 자전거 타는 것과 프로그래밍은 같지 않지만, 모든 이용가능한 정보를 흡수하려고 하는 것은 종종 해가 더 많다. 대신에, 너는 문제들을 풀려고 노력해야하고 그러한 방식으로 알고리즘을 배우려고 해야한다. 너느 또한 언제 어떻게 알고리즘들이 실제로 사용되는지를 볼 것이다. 인간은 행동하여 배우고, 우리는 어떤 것을 배우기 위해서 실수할 필요가 있다. 만약 너가 결코 실패하지 않는다면, 너는 결코 배우지 못한다. 너는 이 챕터에서 나중에 실패에 대한 것을 더 많이 읽을 수 있다.

이러한 생각들은 꽤 연구에 의해 지지받는다. 가이드를 얻ㄱ기전에, 너 스스로 문제들에 부딪히는 것을 시작하는 것이 더 좋다고 판명이 됐다. 예시로, 한 알고리즘 수업에서, 너는 자료구조 또는 시간 복잡도에 대한 정보 없이, 가중치가 없는 그래프에서 최단 경로 알고리즘을 프로그래밍 하라고 요청받을 수 있다. 너는 아마도 Bfreadth-first-search와 유사한 어떤 것을 생각해 낼 것이지만, 너는 큐와 시간 복잡도를 이전에 들어본 적이 없기 때문에, 너의 알고리즘은 더 느려질 것이다. 다음 강의에서, 그 선생님은 큐를 구현하는 것을 포함한 한 솔루션을 보여줄 것이고, 그는 너에게 너의 프로그램의 시간 복잡도를 어떻게 측정하는지에 대해 말할 것이다. 교육의 이러한 방식은 다른 방식으로 하는 것보다 더 효과적이다 - 처음에 현재 이론적인 지식을 보여주고 나중에 문제 풀게하는 것보다.

Improving your problem solving ability
이것은 우리의 프로그램에서 가장 어려운 구역이다. 우리의 궁극적인 목적은 여기에서 너의 지능을 증가시키는 것이다. 너는 지능은 꽤 상속받는 것이고 변할 수 없다고 들었을지도 모르지만, 사실은, 너는 그것을 조금 증가시킬 수 있다 (그리고 아마도 게을러지면 감소시킬 것이다). 슬프게도 이 주제에 대해 이용가능한 많은 정보가 없다.

너가 나의 TopCoder 레이팅 그래프를 볼 떄, 너는 2006년과 2007년 둘다에서, 내가 어느정도 발전했지만, 2007년에 더 한 것을 볼 것이다. 2006년 대부분 동안 나는 1900-2100점을 얻었지만, 2007년에는 2300점까지 이동했다. 2006년의 상반기에서, 잠시동안 어떤 발전을 하지 않은 후에, 나는 내가 최대치로 올라갔다고 생각했다. 그리고 2000 2100이 나의 영원한 점수일 것이다.

아마도 너는 내가 2007년에 더 훈련했다고 생각하지만, 그것은 사실이 아니다. 2007년에
나는 한 회사에서 1주일에 2일씩 일하기 시작했고, 나의 학사 논문을 썼었고, 나는 여전히 Slovak Olympiad를 공부하고 도와주고 있었고, ultimate frisbee semi-professionally를 시작하고 있었고 마지막이지만 중요한, 나는 또한 좀더 사회적으로 활발 했었다. 나는 정말 프로그래밍 훈련을 위한 더 적은 시간을 가졌었다.

양을 증가시키는 대신에, 나는 훈련의 질을 증가시켰다. 나는 더 어려운 문제들을 풀기 시작했었다. 너가 많은 쉬운 문제들을 풀 때, 너는 빠르게 type하고 실수하지 않은 것을 배울지 모르지만, 너는 너의 뇌를 많이 시험하지 않는다. 반면에, 너는 너 자신에게도 너무 많이 도전시키지 않는다. 왜냐하면 만약 문제가 너무 어렵다면 좌절스럽기 떄문이다. 심리학자는 이 현상을 proximal development의 zone이라고 부른다.

나는 다음의 furniture metaphor를 사용하여 문제 풀이에 대해 생각하는 것을 좋아한다. 너가 집을 가지고 있고, 너가 2층에 놓고 싶은 큰 테이블을 샀다고 상상하자. 만약 그 문과 계단이 너무 작다면, 너는 그 테이블을  분해해야만 할 것이고 심지어는 아마도 자를 수도 있을 것이다. 더 작은 조각들을 2층에 옮겨놓은 후에, 너는 그것을 다시 조립하지만, 시간이 많이 걸린다. 더 큰 문과 계단을 가지면 더 좋지 않을까?

너는 문제를 풀려고 할 때, 너는 그 문제를 house에 있는 그 table처럼 비슷한 방식으로 너의 뇌에 맞추려고 한다. 만약 문제가 너무 복잡하다면, 너는 그것을 더 작은 조각을 분해해야할지도 모르고, 그것들을 처음에 풀고, 그러고나서 그 조각들을 전체 솔루션을 위해 다시 조립할지도 모른다. 너가 너의 지능을 증가시킴에 따라, 너의 뇌는 더 커진다, 그래서 너는 그것들을 분해하지 않고 너의 뇌에 더더욱 어려운 문제들을 맞출 수 있따.

나머지 질문은 어떻게 너의 comfort zone밖의 문제들을 찾는가이다. (또는 너가 좋아한다면 Zone of proximal development에서) 너는 다른 것을 생각해낼지도 모르지만, 여기에 대충 내가 한 것이 있다. 나는 많은 아름다운 문제들을 가진 SPOJ judge를 좋아한다. 각 문제에 대해서, 너는 많은 사람들이 그것을 해결한 것을 볼 수 있다. 초기에, 나는 150-200명의 사람들에 의해 풀어진 문제들을 열었고, 몇 달 동안 이것을 했다. 내가 이게 쉽다고 느껴졌을 때, 나는 잠시동안 100-150명이 푼 것을 했다. 등등 너는 또한 TopCoder에서 같은 것을 시험삼아 할지도 모른다. 처음에 Division 2 Easy로 시작하고, 그런 다음에 Div1 문제들로 넘어가라. 너가 문제 푸는데 어려움이 있을 떄, 좀 더 경험있는 친구나, 코치, 또는 포럼에서 물어보도록 해라. 사람들이 기꺼이 너에게 솔루션을 가지고 도와줄 수 많은 온라인 커뮤니티들이 있다.

~~~