02) 문제 해결 개관 - 문제 해결 전략

◇ 직관과 체계적인 접근

문제 해결 전략에서 문제와 답의 구조에 대한 *직관을 강조해야 한다.

* 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다.

 

◇ 체계적인 접근을 위한 질문들

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

이전에 사용했던 방법과 비슷한 접근 방법을 사용할 것이라 예측할 수 있다.

문제를 분류하는 방법을 익히고, 각 알고리즘들이 어떤 경우에 사용될 수 있는지 체계적으로 공부해야 한다.

즉, 그 동작 과정과 원리를 완전히 이해하고 있어야 한다.

 

◆ 단순한 방법에서 시작할 수 있을까?

일단 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보는 것도 괜찮다.

=> 어렵게 푸는 실수를 예방!

 

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

번뜩이는 영감이 필요한 문제를 만났을 때에는 손으로 여러 간단한 입력을 해결해보는 것.

자신이 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘을 만드는 것.

 

손으로 문제를 풀어보는 습관은 곧 어떻게 문제를 해결할지 감을 만들어낼 때도 유용하다!

=> 프로그램을 작성하기 전에 알고리즘에 간과한 점이 없는지 미리 확인할 수 있기 때문.

 

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

주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어보는 것.

쉽게 변형하는 방법: 문제의 제약조건을 없애거나, 변수의 수를 줄이고나, 다차원 문제를 1차원으로 줄이는 등!

 

◆ 그림으로 그려볼 수 있을까?

많은 사람들의 사고 체계는 숫자의 나열보다 기하학적 도형을 더 직관적으로 받아들이기 때문.

 

◆ 수식으로 표현할 수 있을까?

평문으로 쓰여있는 문제를 수식으로 표현하는 것도 도움이 되는 경우가 있다.

수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제 해결의 열쇠가 될 수 있기 때문이다.

 

◆ 문제를 분해할 수 있을까?

더 다루기 쉬운 형태로 문제를 변형하는 것.

문제 제약 조건을 분해하는 방법! 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문.

 

◆ 뒤에서부터 생각해서 문제를 풀 수 있을까?

문제에 내재된 순서를 바꿔보는 것.

예를 들면 사다리타기가 있다. 꽝이 아니라 당첨이 되고 싶을 때, 당첨 구간에서부터 위로 올라가는 편이 더 찾기 쉬운 것처럼!

 

◆ 순서를 강제할 수 있을까?

순서가 없는 문제에 순서를 강제해서 문제를 푸는 방법.

순서 강제 기법은 경우의 수를 셀 때도 유용. 특정 조건을 만족하는 답의 수를 세는 문제 등.

 

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

정규화 기법: 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법.

이 방법을 사용하기 위해서는  어떤 답이 주어지더라도 이것을 특정한 형태의 답으로 바꿀 수 있는 변형 과정을 찾아야 한다.