단순한 문제는 직관적으로 해결할 수 있지만 어려운 문제일수록 다양한 방법을 시도해 보며 답을 찾아야 합니다. 아래는 답을 찾는 일반적인 전략들입니다.

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

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

비슷한 문제를 떠올리면 쉽게 해결할 수 있는 문제들이 있습니다. 비슷한 문제를 떠올리려면 많은 문제를 풀어봐야 합니다.

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

문제를 보고 우선은 무식하게 푸는 방법인 완전탐색으로 접근해봅니다. 만약 좀더 효율적인 알고리즘이 필요하다면 단순하게 접근한 상태에서 생각하면 더 수월하게 생각할 수 있습니다. 예를 들면 동적 계획법은 완전탐색을 기반으로 합니다.

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

재정의와 추상화의 중요성은 문제해결기법의 단계에서 언급했습니다.

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

문제를 좀더 쉬운 변형판으로 풀어보는 것입니다. 예를 들어 2차원을 1차원으로 바꾸는 것이 있습니다.

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

재정의와 추상화의 중요성을 알고 있다면 이 방법 또한 해볼만한 가치가 있다는 것을 알 수 있습니다.

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

재정의와 추상화의 중요성을 알고 있다면 이 방법 또한 해볼만한 가치가 있다는 것을 알 수 있습니다.

문제를 분해할 수 있을까?

예를 들어 제약 조건을 분해하는 방법이 있습니다. 이 방법은 문제에 주어진 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문에 이 변형은 종종 유용합니다.

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

예를 들어 사다리 게임이 있습니다.

순서를 강제할 수 있을까?

순서를 강제해도 답이 달라지지 않는 문제에 적용할 수 있습니다.

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

순서를 강제하는 기법의 연장선인 정규화 기법이 있습니다. 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법입니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)