note title

알고리즘 문제 접근 방식

알고리즘 문제를 풀다 보면 어떻게 접근해야 할지 몰라서 포기한 경우가 한 두 번이 아니다. 뭔가 말은 하는데 이해도 잘 되지 않고, 이해가 되더라도 어떻게 구현을 해야 할 지 모른 적 말이다.

우리는 문제를 보면 3가지 단계를 통해서 문제를 이해한다.

위 3가지의 흐름을 가지고 문제를 푸는데, 우리의 알고리즘 코딩 테스트의 경우에는 5가지 단계가 될 것으로 보인다.

이 5가지의 단계는 어떻게 접근해야 할까

알고리즘 테스트는 대부분 한 장의 종이 혹은 아무것도 없는 환경에서 풀이를 요청한다. 그 말인 즉, 문제 자체의 이해를 머리 속으로 구현해야 하며, 노팅을 하더라도 주석으로 처리해야 한다는 것이다. 그러기에 우리는 반복을 통해서 이를 습관화 해야 한다.

문제 이해

문제를 우선 이해해야 한다. 문제가 나한테 무엇을 물어보는지, 주의 점이 무엇인지 알아봐야 한다.
이 단계에서는 문제의 흐름, 규칙까지 병렬적으로 생각하지 말자. 필자는 머리가 썩 좋지 않아 여기서 너무 시간을 소비하기에 문제는 문제로 이해하는 것이다.

알고리즘 문제의 경우 입력을 어떻게 할 것인지 문제 하단에 나오는 경우가 많다. 숫자를 받는지, 문자를 받는지 혹은 리스트 형태로 받는지 등등을 확인해야 한다.

대부분은 자연 수 $N$ 을 받는 경우가 대부분인데, 입력에 대한 공식처럼 사용되는 코드가 있기도 하다. 이를 활용해서 입력 유형에 맞게 작성한다.

실제 답안으로 제출되어야 할 출력 유형도 확인해야 한다. 대부분은 str로 이루어진 문자열을 출력하게 되니, 조건에 맞게 작성하면 되겠다.

이 부분이 우리의 핵심이다. 문제를 보았을 때, 이 문제가 나에게 어떤 알고리즘으로 문제를 풀어라 를 캐치 해야 한다. 여러 문제를 풀어보고 공통적인 문제에 대한 방법론을 이해하면 좋겠다.

해당 규칙을 파악했다면, sample data가 출력될 때 어떤 규칙으로 움직이는지 글로서, 여기선 주석으로서 작성해두자. 적지 않으면, 까먹는다.

Python의 특징이기도 하고, 알고리즘 테스트의 특징이기도 한, “코드는 위에서 아래로 순서대로 흐른다” 를 지켜야 한다. 내가 찾은 규칙이 무엇인지, 해당 규칙에 대한 흐름이 어떤 지를 주석으로 작성해서 그에 맞게 코드를 작성한다.

총 5가지의 방향으로 알고리즘 문제를 접근한다면 복잡한 머리 속을 어느 정도의 체계를 부여할 수 있을 것 같다. 물론, 여러 알고리즘 이론과 문제를 풀어봐야 알겠지만 지금부터 차근차근 노력해야 앞으로 결실을 맺을 수 있을 것으로 보인다.