문제 해결을 시작하며

※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음.

 

문제 해결의 과정

1. 문제를 읽고 이해하기

문제가 원하는 바를 공격적으로 완전히 이해하기.

사소한 제약 조건들 놓치지 않기.

2. 재정의와 추상화

재정의: 요구사항의 이해를 위해 자신의 쉬운 언어, 개념으로 풀어 쓰기.

추상화: 복잡한 문제의 본질만 남겨두고 축약, 다루기 쉽게 표현하기.

3. 계획 세우기

해결 방식을 결정, 사용 할 알고리즘과 자료구조를 선택하기.

4. 계획 검증하기

어떤 경우에도 요구 조건을 정확히 수행하는가?

시간, 메모리가 제약 조건에 부합하는가?

5. 계획 수행하기

6. 회고하기

해결 과정을 돌이켜 보기. (효율성, 간결성, 직관성 등.)

코드와 경험을 기록하기. (접근 방식, 해결의 실마리, 오답의 원인.)

못 푼 경우 자신의 접근 방법이 왜 성공하지 못 했는지 생각하기.

문제 해결 전략 - 체계적으로 접근하기

1. 비슷한 문제를 푼 경험을 떠올려 보기

2. 무식하게(단순하게) 풀 수 있을지 생각하기

단순한 문제를 복잡하게 생각해 어렵게 푸는 실수를 예방하기.

(간단하고 느린 알고리즘으로도 충분히 해결 가능하다면 오히려 좋아.)

단순한 알고리즘, 효율적인 자료 구조, 중복 계산 개선 등의 최적화를 적용.

3. 문제 해결 과정을 수식화, 간단한 예제 입력을 손으로 직접 해결해 보기

4. 문제를 단순화할 수 있을지 생각하기

제약 조건을 없애거나 계산의 양을 줄여보기. 이를 통해 원래의 문제를 해결하는

직관을 제공하거나 직접 이용할 수도 있다.

5. 그림으로 그릴 수 있을지 생각하기

정수 쌍을 다루는 문제를 2차원 평면좌표 혹은 직선 상 구간으로 그려 보기.

6. 거꾸로 생각해 보기

사다리 게임을 예로 들면, 어떤 사다리가 원하는 결과일지 구하지 말고 원하는

결과로부터 거슬러 올라갈 수 있다.

7. 순서를 강제해 보기

게임판에 블록을 놓는 순서를 구할 때 순서를 강제해 보는 등 문제의 순서를

강제하면 경우의 수가 줄어들 수 있다.