알고리즘잡담

알고리즘을 공부하는 이유

내가 알고리즘 공부를 하는건 그냥 재밌어서다. 처음부터 알고리즘이 재밌던건 아니다. 고등학생때 아무것도 모르면서 오직 열정만으로 게임개발을 했었는데, 3년이라는 짧지않은 시간동안 어느정도 공부하고 프로젝트도 하다보니 뭔가 정체된 느낌을 받았다. 새로운 것을 공부해서 적용해봐도 응용하지는 못한달까. 예를들어 게임개발에서 오브젝트간의 관계가 트리형태기 때문에 재귀적인 계산이 많이 필요했는데, 재귀에 익숙하지 않았던 나는 항상 그런 재귀적인 로직에서 막혔다. 그래서 알고리즘공부를 시작하게 되었다.

적당히 재귀함수에 익숙해지니 풀 수 있는 문제들이 조금씩 생겼다. 풀다보니 재귀가 만능은 아니더라.DP라는것으로 시간복잡도를 줄일 수 있다길래 공부했다. 수많은 참신한 점화식들을 접하며, 문제마다 숨겨져있는 중요한 특징을 찾아내는것의 중요성과 재미를 알게 되었다. 더 하다보니 단순히 몇가지 관찰만을 필요로하는 문제들을 넘어, 몇가지 어려운 알고리즘과 자료구조를 필요로하는 문제들을 만나서 공부했다. 그 알고리즘들에는 과거의 똑똑한 사람들이 가졌던 사고방식이 녹아들어 있고, 이것을 이해하고 적용해보는게 재밌었다. 대략 이런 과정으로 알고리즘에 재미를 느낄 수 있었다. 솔직히 어느정도 수준이상부터는 이걸 대체 어디에 써먹지 싶은 알고리즘도 많긴한데 이거말고 딱히 할것도 없어서 걍 하고있다.

알고리즘을 공부하는 방법

알고리즘을 공부하는 최고의 방법은 나도 모른다. 아직도 부족한게 많지만, 내가 지금까지 공부해왔던 방식을 정리해두면 새롭게 알고리즘을 공부하는 사람들이 방향성 정도는 찾는데 도움이 될까 싶어 적어본다. 나 또한 그동안 공부해왔던 방식을 회고함으로써 앞으로 진행해나갈 방향을 개선하려고 한다.

(알고리즘 시작할때) 너무 어렵고 이해도 잘 안되서 포기하고 싶은 경우

나 또한 그랬고, 주변의 많은 사람들도 그렇다. 사실, 당연한 것이다. 우리가 공부하려는 알고리즘들은, 과거의 천재들이 수많은 시간을 들여 관찰하고 생각하여 만들어진(혹은 찾아낸?) 것이다. 오랜 수학 및 알고리즘 문제풀이 경험을 통한 그들의 직관과 논리력은, 이제 막 공부를 시작하는 우리들과는 전혀 다르기 때문에, 어떤 알고리즘을 보고 한번에 이해가 술술 되는 사람이 있다면 그 사람은 천재임이 틀림없다. 당신이 나와 같은 평범한 사람이라면, 한 알고리즘에 대해 적어도 며칠은 책과 인터넷 자료를 읽어보고, 몇가지 입력에 대해 관찰해보고, 관련 문제를 어떻게 풀 수 있을지 생각해보자. 나는 알고리즘을 엄청 잘하는 사람을 만나면 항상 물어봤다. "알고리즘을 언제부터 얼마나 공부하셨나요?". 그들의 대답은 항상 비슷했다. "초등학생때 학원다니면서 시작했어요", "부모님이 컴퓨터로 게임만하지 말고 이거라도 해보라면서 시키셨어요", "고등학교 친구가 알고리즘을 푸는게 재밌어보여서 같이 풀었어요", "수학올림피아드 하다가 코딩이 더 재밌어서 정보올림피아드를 공부하게 됬어요". 어느 누구도 원래 잘했던 사람은 없었다. 모두 조금씩이라도 최소한 몇년은 꾸준히 공부했던 사람들이었다. 사실 이건 알고리즘뿐만 아니라 다른 모든 분야에서도 크게 틀린말은 아닐 것이다. "투자하는 시간만큼 더 잘하게 된다". 개인마다 속도의 차이는 있겠지만, 적어도 아무것도 공부하지 않는 사람보다는 많은 것을 이해하고 많은 것을 볼 수 있게 된다고 단언할 수 있다. 며칠을 투자했지만 이해가 되지 않으면, 다른 재밌어 보이는 알고리즘을 먼저 공부하거나 그냥 며칠동안 질리도록 놀고 머리를 식힌 다음 다시 공부해보자. 필자는 종만북("알고리즘 문제해결 전략"이라는 책이다)을 적어도 5번 이상 포기했지만, 재충전 한 다음 다시 공부했기 때문에 완독할 수 있었다. 도저히 공부가 안되서 쉴때는 쉬더라도, 꾸준히 하는게 중요한 것 같다.

• 풀이를 봐도 이해가 안되는 경우

  정해가 특정 알고리즘이나 자료구조를 사용해서 모르겠는거라면 해당 알고리즘을 공부하고 다시보면 된다. 그런거 없이 본인이 아는 알고리즘들만 쓰는데도 이해가 안되는거면 본인의 수준보다 상당히 어려운 문제일테고, 보통 해설은 출제자의 눈높이에서 작성되기 때문에 당연하다고 생각되는(읽는입장에서는 전혀 그렇지 않는) 몇가지 논리가 생략됬을 수 있다. 생략된부분이 무엇인지 집중해서 생각해보자. 어느 부분에서 막혔는지 질문하고 도움받는것도 좋겠다. 그래도 잘 모르겠다면 다른문제들을 먼저 공부하고 나중에 다시 보자. 해설에서 생략된건 출제자의 레벨에서는 굳이 언급안해도 될만한 논리이기 때문인데, 이런건 다른문제를 공부하다보면 찾을 수도 있기 때문이다.

• 풀이를 보면 이해가 되는데 안보면 문제를 못풀겠는 경우

  이 경우는 관찰력이 부족하다고 볼 수 있다. 문제가 시키는대로 구현만 하면 풀리거나, 요구하는 알고리즘만 구현해서 풀리는 문제는 많지 않다. 대부분의 문제들은 문제가 제시하는 조건을 토대로 특정한 성질을 관찰해내고 활용해야 문제를 풀 수 있다. 이러한 유용한 성질을 발견하는건 상당히 다양한 방법이 있기 때문에 외워서는 한계가 있다. 관찰력 자체를 길러야 하는데, 이러한 능력을 향상시키는데에 코드포스나 앳코더 문제들이 도움이 될 것이다. 조건들로부터 아이디어를 찾아 푸는문제들이 대부분이기 때문. 다만 가끔은 너무 과해서, 출제를 위해 억지로 조건을 우겨넣어 탄생한 노잼문제나, 모르는사람은 당할수밖에 없는 정수론 문제도 나오는건 주의.

• 올바른 알고리즘은 떠오르는데 문제를 못풀겠는 경우

  이 경우 구현력이 부족하다고 볼 수 있다. 혹은 알고리즘의 전체적인 흐름만 떠올린 상태로 성급하게 코딩하려는 경우일수도 있다. 연습이 답이다.

추천도서

책은 정말 중요하다. 인터넷에 많은 자료가 있지만, 그 자료들이 흩어져 있기 때문에 방향을 읽고 헤매기 쉽다. 책은 저자들의 지식을 한곳에 '체계적으로 모아둔'것이기 때문에 특히 처음공부할때 큰 그림을 보는데 도움이 된다고 생각한다. 그래서 책을 읽고 몇가지 부족한 부분적인 정보들은 인터넷을 통해 공부하길 추천한다. 또한 나는 책을 읽을때 처음에는 큰 그림만 보고, 세부적인 이해는 문제를 풀면서 다시 책을 펼쳐 공부하는 방식으로 완독했다.

• 알고리즘 문제해결전략(구종만)

  전통적인 최고의 알고리즘 책. 다만 최신경향에 비해 오래된 느낌이 있긴 하다. 알문해x 종만북o

• 구체수학(Ronald Graham)

  경진대회보다는 이론적인 부분에서 생각을 정리하는데 도움이 되는 책. 6장 생성함수파트가 인상깊었다. 또한 예전에 확률통계 배울때 관련 표기들이 워낙 생략된게 많아서 복잡했는데, 8장의 이산확률에서 하나하나 짚어준게 도움이 되었다.

• Enumerative Combinatorics(Richard P. Stanley)

  생성함수와 sieve쪽 내용 찍먹추천. 어려움.

• 알고리즘 트레이닝(Antti Laaksonen)

  실제 경진대회에 나오는 고급 기법들이 매우 잘 정리되어있다. 다만 세부적인 설명은 생략된게 많긴 한데, 핵심적인 내용은 다 들어있다. 아래의 책과 이름이 동일해서 구분하기 위해 초록책이라고 부른다.

• 알고리즘 트레이닝(Steven Halim)

  마찬가지로 경진대회를 위한 책인데, 설명도 자세한 편이고 초록책보다 마이너한 주제들도 다룬다. 상위호환 개념은 아닌게, 초록책에 나오는 내용이 이 책에는 없는경우도 있고 그렇다. 최신경향은 초록책이 더 잘 반영하고 있는 느낌. 초록책과 구분하기 위해 파란책이라고 부른다.

• 프로그래밍 콘테스트 챌린징(Takuya Akiba)

  개인적으로 제일 어려운 책이라 생각하고, 선정한 주제와 설명의 퀄리티도 좋다(특히 플로우). 오타가 정말 못 읽을정도로 많은게 옥에티. 프콘챌x 노란책o

대학생활의 끝이 다가오면서

세상에 내가 못푸는 문제가 있으면 안된다는 마인드로 열심히(?) 공부한것도 몇년이 지났다. 종만북으로 알고리즘 시작한게 고2말~고3초쯤이니 연차로만 따지면 6년차인데 뉴비때 허송세월 보낸거 생각하면 6년차라고 인정하긴 싫고 뭐 그렇다. 아무튼 슬슬 ps도 줄여야할 때가 온것 같다. ps에 나름 진심이었기에 진지하게 대학원도 생각해보았지만, 문제푸는게 재밌을뿐 구체적으로 어떤걸 연구하고 싶은지 모르겠어서(이미 풀린문제를 또 푸는건 연구로서 큰 의미는 없으니까...학계SOTA논문을 가끔 보면 ps할 의지가 사라진다 ㅋㅋ) 내 길은 아니라고 생각했다. 무엇보다 실력이 이미 안드로메다로 가있는 어린 영재고 학생들을 보면 ps로 밥벌어먹기는 글렀고🥲. 먹을 수 없으니 신포도라 하는꼴이지만, 취미는 취미일때가 제일 재밌을거라고 생각하며 놓아주기로 했다. ps는 취업하고도 심심하면 자주 할거같은데, cp는 재미없는건 아닌데 몸이 너무 피곤해서 많이 못할것같다. 꼭 알고리즘ps뿐만 아니라 앞으로는 마라톤(휴리스틱)이나 캐글(머신러닝)도 여유가 된다면 시도해보고 싶다. 지금 당장 남는시간은 영어랑 개발을 공부할 예정이다.

슬슬 ps를 접는다는 소리를 했으니 그동안 ps를 하며 이룬건 무엇이 있는지 회고해보았다. 세상 모든문제를 다 풀 수 있는 프로그래밍 초고수가 되기 위해 시작한 ps이지만 여전히 내가 풀 수 없는 문제는 너무나도 많다. 그래도 하나 위안이 되는건 많은 문제들은 해설을 보고 이해하여 내가 직접 코딩할 수 있다는 것이다. 물론 문제를 풀기위해 필요한 아이디어를 찾는것보다, 어떤 아이디어가 문제에 맞는지 확인하고 구현하는게 훨씬 쉽기 때문인거도 맞다(여기서 NP가 떠오르는건 ps후유증인가ㅋㅋ 솔루션을 찾는건 어렵지만 솔루션이 맞는지 검증하는건 상대적으로 쉽다!). 그렇지만 그 아이디어의 이론적 배경이 깊어 그쪽 지식이 없다면 이해하기 힘든 문제들도 많이 있는데, 지금은 배경지식때문에 못읽는 그러한 경우는 거의 없다(-수학빼고-). 그래서 이게 뭘 이뤘다는건지 애매할 수 있지만, 세상 모든 문제를 혼자 해결할 필요는 없다는걸 생각해보면 나의 근자감을 이해할 수 있다. 일을 하다보면 만날 수도 있는 어려운 문제상황에 대해

1. 본인이 직접 해결하거나
2. 논문을 참고하거나
3. 팀원이 해결한걸 이해하고 구현

뭐 대충 이런정도 갈래가 있을것이다. 여기서 모든 문제를 1번으로 해결 할 수 있다면 좋겠지만 현실은 그리 만만하지 않다. 그렇지만 내가 못푸는 문제라도 다른사람이 풀 수 있고, 내가 그 풀이를 듣고 이해할 수 있다면 그 사람과 협업할 수 있다는것이다. 즉, 나 자신의 문제해결력을 올림과 동시에 일종의 커뮤니케이션(협업)능력의 향상을 얻었다는 것이다. 구현&디버깅 실력은 덤, 괴상한 컨벤션에 수렴해버린 코딩스타일은 디버프.(작성중)