2.3 문제 해결 전략
문제 해결 전략에서 가장 중요한 것은 직관 이다. 직관적으로 보았을 때 한번에 답의 얼개가 보인다면 문제를 반쯤 해결한 것이나 마찬가지이다. 하지만, 모든 문제를 이렇게 할 수 있는 것은 아니므로 체계적인 접근 이 필요하다. 막막한 문제에 접근하는 여러 방법들을 알아보자.
1. 비슷한 문제를 풀어본 적이 있던가?
형태가 비슷하거나 관련 문제를 풀어보았다면, 같은 방법을 사용할 거라고 예측할 수 있다. 그러나, 완전히 같은 문제를 만날 가능성은 없기에 문제의 목적을 보고 적절한 접근 방법을 선택할 수 있어야 한다. 이를 위해, 해당 문제가 어떤 문제인지 분류하는 힘을 익히고 우리가 익히는 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 알아가야 한다.
2. 단순한 방법에서 시작할 수 없을까?
이 책에서 많은 연습문제는 "무식하게 풀 수 있을까" 라는 질문으로 풀이가 시작된다. 시·공간의 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보는 것이다. 이는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 방지해준다.
효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문에, 단순한 알고리즘을 구현해두고 여기에서 좀 더 효율적인 자료 구조를 사용하거나, 최적화를 하는 등의 점진적인 개선을 통해 효율적인 알고리즘을 구현해낼 수 있다.
3. 내가 문제를 푸는 과정을 수식화할 수 있을까?
하지만, 위의 점진적인 개선 방식이 만능은 아니며, 처음에 생각한 것과 완전히 다른 새로운 방향에서 접근해야 풀리는 문제들 또한 있다. 이러한 문제를 만났을 때, 문제의 예제 입력을 손으로 직접 공식화해서 해결해보는 것이다. 손으로 문제를 풀어 보는 습관은 어떻게 문제를 풀어야 할지 감을 잡는데도 유용하다. 급할수록 돌아가자.
4. 문제를 단순화할 수 없을까?
문제의 원형을 따르되 좀 더 쉬운 변형판을 먼저 풀어보는 것이다. 제약 조건을 없앨 수도, 변수의 수를 줄일 수도, 다차원을 1차원으로 줄일 수도 있다. 이것의 해법이 원래 문제에 대한 직관을 제공하거나 직접적인 답에 대한 연장선 일 수있다. (책에서의 2차원 격자 -> 1차원 격자 문제를 생각해보자)
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
더 다루기 쉬운 형태로 문제를 변형하는 것이다. 문제의 제약 조건을 분해하는 방법이 있다. 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하는 것이다. 요구 조건들을 수식으로 표현한 뒤 분해하여 다시 합친다.
8. 뒤에서부터 생각해서 풀 수 있을까?
9. 순서를 강제할 수 있을까?
원래 문제에서 순서가 상관 없는 상황이라면, 항상 특정 순서를 따라야 한다고 해도 같은 답일 것이다. 그러므로, 일부러 특정 순서를 따라야 한다는 제약을 추가하여 우리의 사고를 도와준다.
10. 특정 형태의 답만을 고려할 수 있을까?
