[SoftTalk] 알고리즘 공부를 하면서

나는 원래 고등-대학 모두 문과생이었다. 그러나 이과에는 관심이 있었고 곁다리로 조금씩 과목을 듣기도 했다. 그리고는 나중에 뜻한 바 있어 유학을 가게 되어 이과 공부를 하고 왔다. 요새 머신러닝 쪽 실무를 하면서 효율적 코드 작성을 위해 알고리즘과 자료구조 공부를 할 필요가 있다고 생각되어 최근 들어 공부를 시작하였는데, 2개월 정도는 꽤 힘들었지만 지금은 나 스스로도 문제를 이해하고 구상하고 푸는 속도도 빨라지고, 실력이 한차원 높은 궤도에 올랐다는 느낌이 든다. 아직 목표한 수준까지는 갈 길이 멀지만, 그래도 코드를 보는 나의 눈이 많이 달라지고 깊어진 것을 스스로 느낄 때면 알고리즘 공부를 하길 잘했다는 생각이 들어 뿌듯하다. 알고리즘 공부란 무엇일까, 하고 오늘 느낀 점을 간략히 적어보도록 하겠다.

생각

어떤 문제를 접했을 때 이 문제는 무엇을 원하는 것이며, 이를 위해서는 어떻게 풀어야 할지 그 아이디어(idea, 발상)을 생각하는 것이다. 마치 그림을 실제로 그리기 전에 형상을 구상하는 것과 같다. 그러기 위해서는 문제를 추상화해서 결국 이것이 무엇을 궁극적으로 구해야 하는 것인지를 알아내야 한다. 이 과정에서는 밑그림을 그리면서 부분 부분으로 문제를 나누어 그 부분을 나중에 구체적인 코드로 작성해서 해당 기능을 구현해야 한다고 표시해 두게 된다.
이를 위해서는 각 주제마다 대표적 문제와 그 해결방법을 공부한 다음에, 여타 많은 문제를 풀면서 경험치를 쌓는 것이 필요하다고 생각한다. 그런데 이 발상을 위해서는 자료구조나 대표적 알고리즘을 어떻게 알고 적용할 것인지에 대한 이해가 있어야 한다.

구현

구현은 생각한 바를 함수의 올바른 활용법을 통해 정확히 코드로 옮기는 것이라고 하겠다. 사용하는 프로그래밍 언어의 내장함수나 일반적으로 실무에서 많이 쓰이는 외장함수(library)의 사용법을 정확히 숙지하고 있다가 이것을 적재적소에 활용하는 것이 필요하다. 그러려면 평소에 그 구문들에 대해서 숙달해야 하고, 이를 위해서는 언어의 매뉴얼을 읽고 관련된 블로그 글의 예제 등을 구글링을 통해 찾아보고 이해한 다음, 실무에서도 활용해보려고 노력하는 것이 필요하다. 실제로 내가 관련 기능을 활용해보면서 해당 기능을 더욱 자연스럽게 사용할 수 있다.

예를 들어, Python의 sorted 와 sort 에 대해서는 다음처럼 구분해서 알고 있어야 한다.

# a: iterable (list, tuple, str, dict etc.)
a.sort(key=func, reversed=False)   # in-place; returns None
result = sorted(a, key=func, reversed=False)  # returns iterators

여기서 func라고 적은 것은 함수형 프로그래밍의 특성으로서 어떤 함수가 다른 함수의 인수로 들어갈 수 있다는 것을 의미한다. 예를 들어, 저 자리에는 a의 원소들을 받아 어떻게 정렬기준으로 삼을 것인지를 정의한 별도의 함수이름을 넣던지, 아니면 lambda 함수로서 바로 저 func 자리에서 동작하는 함수 내용을 적던지를 결정할 수 있다. 그런데 이런 내용은 간략히 예제를 보는 것 만으로는 능숙히 구현할 수 없다. 대표적인 문제를 풀면서 그 해결을 위한 모범답안을 보고 활용법을 참고하는 것이 유용하다고 생각된다.

암기 vs 이해

문제와 답(코드)을 암기하는 것은 도움이 되지 않으며 또 그렇게 기억을 오래 가져갈 수가 없다. 반면 우리 뇌는 제대로 이해한 것, 그리고 다른 연관지식과 함께 논리적으로 연결이 많이 된 것은 자연히 오래 기억하게 되기 때문에, 문제를 이해하고 풀이의 발상과 각 코드 부분을 조목조목 이해하여 자기 것으로 만드는 것이 필요하다. 하지만 어떤 문제를 풀 때 컴퓨터에 미치는 영향이 같다면 코드가 달리 쓰이더라도 상관없기 때문에, 가장 이상적인 것은, 문제를 자기 힘으로 풀어본 다음 (안되면 해설의 처음부터 조금씩 힌트삼아 보면서) 모범답안과 맞춰보며 결국 같은 이야기를 하고 있는지를 코드를 읽으면서 비교해 보면 될 것이다.

닭 vs 달걀

알고리즘은 각 주제가 스스로 완전하지 않다. 즉, 한 주제를 완전히 이해하기 위해서 다른 부분에 대한 이해가 필요하다. 예를 들어 BST의 탐색에 대한 코드(https://algoship.tistory.com/11)를 짜기 위해서는 재귀에 대해 알아야 한다. 재귀를 알아야 DP를 더 잘 할 수 있다. BST의 문제를 풀다보면 DFS, BFS 기법을 활용하는 것이 나온다. 그리고 두 기법은 스택과 큐를 활용한다. 그런데 해당 기법은 Tree의 상위 집합인 Graph의 문제를 풀 때도 활용된다. DP의 memoization, bottom-up, top-down을 이해하려면 memo table을 만들기 위한 hash (또는 array), 역시 재귀 등을 알아야 한다. 모든 주제가 상호 연관되어 있고 상호 의존적이라 닭이 먼저냐 달걀이 먼저냐를 말할 수가 없다고 생각한다. 마치 가위 바위 보 게임 같기도 하다. 그러므로 한 번에 한 주제를 전부 이해하고 넘어갈 수는 없고 전 주제에 대해 차례로 이해를 깊게 하면서 여러 차례를 보는 동안 전반적 이해도가 높아지는 것 같다.