알고리즘(문제 해결 과정)이란 무엇이고 어떻게 하는 것인가?

저명한 양자  물리학자인 리처드 파인만이 처음 사용했다고 알려진 이 알고리즘은 강력하고 문제 해결에 필수적인 요소들을 모두 담고 있다. 파인만은 이 알고리즘을 이용하여 양자역학의 어려운 문제들을 해결했다고 한다.

1. 칠판에 문제를 적는다.

2. 골똘히 생각한다.

3. 칠판에 답안을 적는다.

반쯤 농담인 말이지만 이 알고리즘에서도 우리가 배울 만한 점이 있다. 그 첫 번째는 바로 문제 해결 과정을 단계 별로 나누었다는 것이다. 

문제 해결 과정을 단계별로 나눈다는 아이디어는 별 것 아닌 것 같지만 굉장히 강력하다. 문제를 해결하기 위해 거쳐 가야 하는 과정들을 세분화함으로써, 어디가 부족하고, 어디를 개선해야 하는지 판단할 수 있게 된다. 

파인만 알고리즘에서 우리가 배울 수 있는 또 다른 교훈은 문제를 적는 단계가 있다는 것이다. 별 의미가 없는 것 같지만, 문제를 다시 적기 위해서는 문제를 읽고 이해한 뒤 자신의 언어를 이용해 재정의해야 하기 때문에 이 단계는 매우 중요하다.

다른 사람들은 문제 해결 과정을 어떻게 나눌까? 문제 해결 연구의 고전인 '어떻게 문제를 풀 것인가' 에서는 문제 해결 과정을 다음과 같이 네 단계로 나눠서 소개한다.

1. 문제를 이해한다.

2. 어떻게 풀지 계획을 세운다.

3. 계획을 수행해서 문제를 해결한다.

4. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

 

1 단계 : 문제를 읽고 이해하기

문제 해결 알고리즘의 첫 번째 단계는 문제를 읽고 이해하는 것이다. 많은 사람들이 이 단계는 당연히 잘할 수 있는 것으로 생각하지만, 이 단계의 중요성은 아무리 강조해도 지나치지 않는다. 

2 단계 : 재정의와 추상화

문제 해결 알고리즘의 두 번째 단계는 자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것이다. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일수록 그 중요성이 커진다.
이 과정에서는 또 하나 중요한 일이 일어나는데 바로 문제의 추상화이다.

추상화란 현실 세계의 개념을 우리가 다루기 쉬운 수학적/전산학적 개념으로 옮겨 표현하는 과정이다. 현실 세계의 개념들은 너무 복잡하기 때문에, 현실 세계를 다루기 위해서는 어느 정도 현실의 본질만을 남겨두고 축약하여 다루기 쉽게 표현해야 한다. 이런 과정을 추상화라고 부르며, 우리에게 익숙한 문제 해결 도구들을 문제에 적용할 수 있는 계기가 된다.

3 단계 : 계획 세우기

문제 해결의 다음 단계는 문제를 어떻게 해결할지 계획을 세우는 것이다. 이 과정에서는 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.

4 단계 : 계획 검증하기

구현을 시작하기 전에 계획을 검증하는 과정을 거쳐야 한다. 이 과정에서는 우리가 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명한다.

5 단계 : 계획 수행하기

위와 같은 과정을 거치고 나서야 프로그램을 작성하는 단계에 들어갈 수 있다. 

 

문제를 풀지 못할 때

어떻게 해도 풀리지 않는 문제에 부딪힌다면 일정 시간이 지나도록 고민해도 답을 찾지 몬한다면 다른 사람의 소스 코드나 풀이를 참조해도 괜찮다. 단, 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반하여 자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이나 접근을 떠올리지 못했는지 살펴봐야 한다.

 

문제 해결 전략

자신이 알고 있는 기술을 직접적으로 사용할 수 있는 단순한 문제의 경우에는 상관 없지만 어려운 문제일수록 다양한 방법을 시도해 보면서 답안을 찾아야 한다. 

- 직관과 체계적인 접근
문제 해결 전략에서 가장 먼저 강조해야 할 것은 문제와 답의 구조에 대한 직관의 중요성이다. 직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작하게 해준다. 

- 체계적인 접근을 위한 질문들
1. "비슷한 문제를 풀어본 적이 있던가?
형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 접근 방법을 사용할 거라고 예측할 수 있다. 
2. "단순한 방법에서 시작할 수 있을까?"
비슷한 문제를 본 적이 없거나, 비슷한 문제의 해법이 적용되지 않는다면 어디서 시작해야할까? 우선 시간과 공간 제약을 생각하지 말고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보자.
3. "내가 문제를 푸는 과정을 수식화 할 수 있을까?"
손으로 한번 나의 생각을 수식화 해본다면 엄청난 도움이 된다.
4. "문제를 단순화할 수 없을까?"
문제의 좀더 쉬운 변형판을 먼저 풀어 본다면 도움이 된다. 단수화된 문제의 해법이 원래 문제의 대한 직관을 제공할 수도 있다.