문제 해결의 절차(Algorithm)에 대하여
: 문제를 해결하는 데에 있어서 문제를 해결만하면 장땡(?)이라는 접근보다는 옛날에 비문학 지문을 풀 때도 일정한 스텝이 있듯이 알고리즘 문제를 풀 때에도 일정한 스텝을 정해놓고 푸는 것이 좋을 것 같고, 그 부분에 대해서 포스팅을 해보고자 한다.
문제 해결의 절차
1) 문제를 정확히 이해한다.
: 실제로 내가 요즘 알고리즘 문제를 풀면서 실수를 하는 부분을 보면, 지문에 나온 조건을 제대로 파악하지 못했다던지, 문제에서 요구하는 것을 B라고 생각했지만, A였다던지의 실수가 많았다. 사실 문제 자체가 해결방법에 대한 힌트이므로 반드시 제대로 파악하고 넘어가자
2) 문제를 해결하는 알고리즘을 개발한다(설계 단계)
: 말그대로 문제를 해결하는 방법을 개발하는 단계로 '어떻게 풀지' 즉, 어떻게 문제에서 요구하는 것을 가능하게 할지를 고민하는 단계이다. 이 때, 가장 첫 번 째로 고민해봐야할 것은 '탐색공간'이다. 탐색공간은 우리가 문제를 해결하기 위해 고려해봐야할 모든 경우의 수의 범위를 말한다. 그리고 우리가 이러한 탐색 공간을 고려한 뒤에 가장 먼저 생각해봐야할 솔루션은 '완전탐색(brute-force)' 방법이다. 앞서 말한 탐색 공간에 해당하는 모든 경우의 수에 대해서 탐색을 하는 방법으로 문제를 해결하는 것이다.
3) 설계한 혹은 생각한 알고리즘이 맞는지 수학적으로 증명해야한다. 즉, 왜 되는지에 대해서 설명할 수 있어야한다.
4) 그 다음에는 시간복잡도에 대한 고려가 필요하다. 그리고 이러한 시간복잡도를 계산하는 단계에서 2,3번에 고려해본 알고리즘으로 이 문제를 풀 수 있을지를 고려해보고, 만약에 풀 수 없다면, 즉, 완전탐색법으로 풀 수 없는 문제라면 다른 솔루션을 생각해내야한다. 그러한 다른 솔루션에는 아래와 같은 종류가 있다.
문제 해결의 접근법- 완전탐색법(가장 기초가 되는 것)
- 분할 정복법(divide & conquer)
- 동적 계획법(dynamic programming)
- 탐욕법(Greedy Algorithm)
- 그래프 알고리즘(Graph Algorithm)
5) 그리고 이 5번에 와서야 코드 구현이 시작된다. 이 때, 코드 구현 단계에서도 바로 코딩을 하는 것이 아니라 수도코드(Pseudo Code)를 먼저 작성하는 것이 좋다. 항상 기억해야할 것은 디버깅 없이 한번에 코딩한 뒤에 한번에 정답을 맞추는 것이다. 생각해보면 디버깅을 여러번 하는 것 자체가 이미 문제에 대한 잘못된 접근을 하고 있던 경우가 많았다. 여러 테스트 케이스중 2개가 통과못했다는 것은 말그대로 그 문제를 틀린 것이다. 따라서, 앞의 1-4단계에서 시간을 오래 쓰더라도 코딩을 한 뒤에는 문제를 한번에 맞추는 습관을 들이자(즉, 한번에 정답 코드를 작성하는 습관을 들이자). 코딩 단계에서는 생각을 깊게하는 단계가 아닌, 이미 깊게 생각하는 것을 옮기는 작업을 하는 단계로 생각하자.
