[종만북] 02. 문제 해결 개관

02. 문제 해결 개관

2.2 문제 해결 과정

 1. 문제를 읽고 이해하기

모든 참가자들이 겪는 실수는 바로 잘못 읽는 실수이다. 문제가 원하는 바를 완전히 이해하는 과정이 필요하다. 사소한 제약 조건을 잘못 이해하면 풀 수 없게 되는 문제들이 흔하기 때문.

2. 재정의와 추상화

 문제의 추상화 : 현실 세계의 개념을 우리가 다루기 쉬운 수학적 / 전산학적 개념으로 옮겨 표현하는 것이다.  현실의 본질만을 남겨두고 축약하여 쉽게 표현한다. 어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 필수적인 과정이다.

3. 계획 세우기

2.3 절에서 해결 계획을 수립할 때 사용할 수 있는 여러 전략들에 대해 설명한다.

4. 계획 검증하기

 우리가 세운 알고리즘이 모든 경우에 만족하는지 증명해야한다. 4장과 5장에서 전략들을 다룬다.

5. 계획 수행하기

 3장에서 다룬다.

6. 회고하기

 장기적으로 가장 큰 영향을 미치는 단계가 바로 회고입니다.
끊임없이 자신이 이 추상적인 문제 해결 기술들을 어떻게 사용하고 있는지를 돌아보고 개선해야 합니다.

 코드와 함께 자신의 경험을 기록으로 남긴다.

• 문제의 간단한 해법
• 어떤 방식으로 접근했는지
• 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지
• 오답 원인
• 다른 사람의 코드를 보고 비교

※ 문제를 풀지 못할 때

일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 풀이를 참조한다는 원칙을 세우고 이를 지킨는 것이 좋습니다.

 

 나는 90분 안에 풀리지 않는 문제는 풀이를 참조하여 꼭 복기한다는 규칙을 세웠다.

---

2.3 문제 해결 전략

문제 해결 전략에서 가장 중요한 것은 직관 이다. 직관적으로 보았을 때 한번에 답의 얼개가 보인다면 문제를 반쯤 해결한 것이나 마찬가지이다. 하지만, 모든 문제를 이렇게 할 수 있는 것은 아니므로 체계적인 접근 이 필요하다. 막막한 문제에 접근하는 여러 방법들을 알아보자.

 

1. 비슷한 문제를 풀어본 적이 있던가?

  형태가 비슷하거나 관련 문제를 풀어보았다면, 같은 방법을 사용할 거라고 예측할 수 있다. 그러나, 완전히 같은 문제를 만날 가능성은 없기에 문제의 목적을 보고 적절한 접근 방법을 선택할  수 있어야 한다. 이를 위해, 해당 문제가 어떤 문제인지 분류하는 힘을 익히고 우리가 익히는 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 알아가야 한다.

2. 단순한 방법에서 시작할 수 없을까?

 이 책에서 많은 연습문제는 "무식하게 풀 수 있을까" 라는 질문으로 풀이가 시작된다. 시·공간의 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보는 것이다. 이는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 방지해준다. 

 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문에, 단순한 알고리즘을 구현해두고 여기에서 좀 더 효율적인 자료 구조를 사용하거나, 최적화를 하는 등의 점진적인 개선을 통해 효율적인 알고리즘을 구현해낼 수 있다.

3. 내가 문제를 푸는 과정을 수식화할 수 있을까?

 하지만, 위의 점진적인 개선 방식이 만능은 아니며, 처음에 생각한 것과 완전히 다른 새로운 방향에서 접근해야 풀리는 문제들 또한 있다. 이러한 문제를 만났을 때, 문제의 예제 입력을 손으로 직접 공식화해서 해결해보는 것이다. 손으로 문제를 풀어 보는 습관은 어떻게 문제를 풀어야 할지 감을 잡는데도 유용하다. 급할수록 돌아가자.

4. 문제를 단순화할 수 없을까?

 문제의 원형을 따르되 좀 더 쉬운 변형판을 먼저 풀어보는 것이다. 제약 조건을 없앨 수도, 변수의 수를 줄일 수도, 다차원을 1차원으로 줄일 수도 있다. 이것의 해법이 원래 문제에 대한 직관을 제공하거나 직접적인 답에 대한 연장선 일 수있다. (책에서의 2차원 격자 -> 1차원 격자 문제를 생각해보자)

5. 그림으로 그려볼 수 있을까?

 

6. 수식으로 표현할 수 있을까? 

 

7. 문제를 분해할 수 있을까?

 더 다루기 쉬운 형태로 문제를 변형하는 것이다. 문제의 제약 조건을 분해하는 방법이 있다. 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하는 것이다. 요구 조건들을 수식으로 표현한 뒤 분해하여 다시 합친다.

8. 뒤에서부터 생각해서 풀 수 있을까?

 

9. 순서를 강제할 수 있을까?

 원래 문제에서 순서가 상관 없는 상황이라면, 항상 특정 순서를 따라야 한다고 해도 같은 답일 것이다. 그러므로, 일부러 특정 순서를 따라야 한다는 제약을 추가하여 우리의 사고를 도와준다.

10. 특정 형태의 답만을 고려할 수 있을까?