PS를 접근할 때에는 문제 해결 과정을 단계별로 나누는 것이 중요하다.

리처드 파인만은 아래와 같은 알고리즘을 사용하여 대부분의 양자역학 문제들을 해결했다고 알려져 있다.

1. 칠판에 문제를 적는다.
2. 골똘히 생각한다.
3. 칠판에 답안을 적는다.

...

농담이다.

하지만 이와 같이 문제 해결의 단계를 나누어 접근하는 습관은 중요하다.

아래는 종만북에 소개된 PS과정 6단계 이다.

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법을 찾는다.

1. 문제를 읽고 이해한다.

문제를 잘못 읽어 문제를 풀지 못하는 일은 초급자부터 챔피언까지 저지르는 실수 중 하나이다.
조급한 마음에 입출력 예제만을 훑어보고 성급하게 유추하는 실수를 저지르지 말자.

문제가 원하는 것,
입출력의 형식,
문제의 제약조건

지문에서 문제와 상관 없는 것들은 걸러내고,
문제와 연관된 모든 것은 꼼꼼하게 파악하라.

2. 재정의와 추상화

문제에서 주어진 개념을 자신이 다루기 쉬운 개념으로 풀어쓰는 것이다. 그리고 이 과정에서 '추상화'가 필연적으로 일어난다.
문제에서 제시되는 무언가를 '배열의 요소'로 추상화하는가와 '그래프의 정점/노드'로 추상화하는가에 따라서 문제의 해법과 효율성이 달라질 것이다.

3. 계획 세우기

문제를 추상화 했다면, 추상화된 개념을 어떻게 해결할지 계획을 세우는 것이다. 어려운 문제일수록, 또 잘못된 추상화로 잘못된 접근을 했다면, 이 과정에서 오랜 시간을 쏟게 될 것이다.

4. 계획 검증하기

계획을 세웠다고 해서 무작정 키보드를 잡지 않는다.
해당 계획이 알고리즘의 요구 조건을 정확히 수행하는지를 증명하고, 시간 복잡도와 공간 복잡도가 문제의 제한 내의 들 수 있는지를 파악한다.

5. 계획 수행하기

계획의 검증을 완료했다면, 구현을 진행한다.
뛰어난 알고리즘 계획이라도 구현 단계에서 오류가 발생하면 작동하지 않을 것이다.
구현 단계에서 좋은 프로그램을 작성하기 위해 집중하라.

6. 회고하기

문제를 풀었다면/또 틀렸다면, 회고하라.

문제를 풀면서 어떠한 기술을 썼는지 회고하라.
더 나은 기술은 없었는지 회고하라.
오답이 나왔다면 단순한 실수일 지라도 회고하라.
다른 사람의 코드를 보면서 회고하라.

문제를 풀지 못할 때에

한 문제에 너무 오랜 시간을 쏟지 않는다. 가령 1시간을 고민한다는 원칙이 있다면 그 원칙을 지켜라.
단, 다른 사람의 문제 해답을 보았다고 하더라도 회고와 복기가 동반되어야 한다. 다른 사람은 풀었는데 왜 나는 못풀었는지, 나의 접근법이 어디에서 잘못되었는지를 항상 살펴봐야 한다. 이러한 경험이 쌓이고 쌓이면, 그들의 접근법을 나도 할 수 잇게 된다.

문제를 체계적으로 접근하는 법

여러 문제를 풀고 복기할수록 직관이 늘어난다. 문제를 분석하자마자 어떻게 접근할지 떠오른다.

하지만 직관이 부족한 경우, 직관적으로 떠오르지 않는 경우 아래와 같이 단계적으로 접근한다.

1. 비슷한 문제를 푼 경험이 있는가? - 가령 경우의 수를 계산하는 문제는 십중팔구 다이나믹 프로그래밍 문제일 것이다. 다이나믹 프로그래밍을 풀었던 기억들을 되짚으며 어떠한 문제들을 풀었고 어떻게 접근할 수 있는지 떠올려보라

2. 단순한 방법에서 시작할 수 있을까? - 비슷한 문제를 풀어본 경험이 없다면, 단순무식하게 풀 수 있을까를 생각해본다. 의외로 많은 문제들이 단순한 접근을 요구하는 경우가 많다. 이러한 문제에 복잡한 접근을 하는 것은 낭비일 수 있다. 단순한 접근을 계획한 이후, 개선할 점이 있는지 검증해도 늦지 않다. 단순한 접근에 단순한 개선을 해도 다이나믹 프로그래밍 기법이 되기도 한다.

3. 문제를 단순화할 수 있을까? - 겉보기에 복잡한 문제도 단순화할 수 있다. 가령 2차원 문제가 정렬을 하면 1차원 문제가 되고, 크기 비교 문제가 되기도 한다.

4. 그림으로 그려볼 수 있을까? - 가령 두 문자열을 비교하는 문제는 가로, 세로 축을 갖는 그림으로 그리면 더 쉽게 풀리곤 한다.

5. 수식으로 표현할 수 있을까? - 복잡한 문제를 하나의 수식으로 표현할 수 있다면, 수학적 조작을 하는 알고리즘을 구현하여 문제를 풀 수 있다.

6. 문제를 분해할 수 있을까? - 복잡한 문제를 다루기 쉬운 문제들로 분해한다. 가령 복잡한 제약 조건을 가진 문제를, 단순한 제약 조건을 가진 여러개의 문제로 나누는 것이다. '기사는 A일수도 있고 B일수도 있는데 해당 기사가 진실인지 판별하라'는 문제는 '기사가 A && B이면 진실이다'와 같이 나눌 수 있고, A제약조건과 B제약조건을 각기 다른 함수로 풀면 된다.

7. 뒤에서 부터 문제를 풀 수 있을까? - 순서가 정해진 문제에서, 순서를 반대로 접근해보는 것이다.

8. 순서를 강제할 수 있을까? - 이번엔 순서가 없는 문제에서, 순서를 강제하며 접근해보는 것이다.

9. 답의 형태를 변형할 수 있을까? - 가령 평면 위에 여러개의 원이 있고, 특정 지점에서 이 원을 모두 덮는 최소 크기의 원을 구한다고 해보자. 현실이라면 원을 캠퍼스로 그려가며 확인할 수 있지만, 프로그램으로 구현하는 것은 쉽지 않을 것이다. 이를 '특정 지점과, 각 원에서 특점 지점으로부터 가장 먼 지점'으로 정규화하면 문제를 풀 수 있다.