알고리즘 문제 해결 전략들을 정리해 보았다
문제 해결 전략
1) 비슷한 문제를 풀어본 적이 있던가?
-
형태가 비슷하거나 관련된 문제를 해결했을 때의 알고리즘을 응용한다.
-
문제의 유형을 구분하고, 알고리즘을 어느 문제에 사용할 수 있는지 공부한다.
2) 단순한 방법에서 시작할 수 있을까?
-
시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 본다.
-
좀 더 효율적인 자료구조를 사용하거나, 계산 과정에서 중복된 부분을 제거하는 등의 최적화를 적용해서 알고리즘을 개선한다.
3) 문제를 푸는 과정을 수식화할 수 있을까?
- 손으로 문제를 풀어 보면서 생각해 본다.
4) 문제를 단순화할 수 없을까?
- 문제를 쉽게 변형(제약 조건 없애기, 변수의 수 줄이기, 차원 줄이기 등)하여 풀어 본다.
5) 그림으로 그려볼 수 있을까?
6) 수식으로 표현할 수 있을까?
- 평문으로 쓰여 있는 문제를 수식으로 표현해 본다.
7) 문제를 분해할 수 있을까?
- 다루기 쉬운 형태로 문제를 분해해 본다.
8) 뒤에서부터 생각해서 문제를 풀 수 있을까?
- 문제에 내재된 순서를 바꿔서 풀어 본다.
9) 순서를 강제할 수 있을까?
- 순서가 없는 문제에 순서를 강제해서 문제를 풀어 본다.
10) 특정 형태의 답만을 고려할 수 있을까?
- 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 후, 각 그룹의 대표들만을 고려해 본다.
11) 특정 영역의 넓이를 계산하는 문제(겹치는 영역 등)는 배열으로 쉽게 풀 수 있다.
출처
[프로그래밍 대회에서 배는 알고리즘 문제 해결 전략] - 구종만, 인사이트