티스토리 뷰

Algorithm

문제 해결 전략

박트리 2017. 4. 24. 00:16

** 평소 생각하던 문제 해결 전략들을 적어나갈 생각이다.


1. x좌표와 y좌표를 분리해서 생각하기

x좌표만 있다고 생각하고 문제를 더 쉽게 풀어보고 이후에 y좌표를 추가하면 어떻게 풀 수 있는지 생각하는 접근 방법이다.


2. 순서를 강제하기

주어진 문제가 임의의 순서를 추가 하였을 때 더 쉽게 접근할 수는 없는지 생각해보는 접근이다.

보통 dp문제에서 많이 사용하는 접근 방법이다.


3. 주어진 문제를 반으로 나누기

주어진 문제를 반으로 나누었을 때 왼쪽 범위에서 시작하고 오른쪽 범위에서 끝나는 답을 비교적 구하기 쉬운지 \(O(n)\)

판단하여 분할정복으로 푸는 접근 방법이다.


4. 뒤에서부터 생각하기

보통 앞에서 부터 결정하면 결정하기 난해한 문제들은 뒤에서부터 결정하였을 때 쉽게 풀리는 경우도 있다.


5. 일단 쉬운 알고리즘으로 생각하기

먼저 쉬운 알고리즘으로 접근하여 규칙 또는 최적화가 가능한 부분을 찾고 개선하는 접근 방법이다.


6. 답을 정해놓고 구하는게 더 쉬운지?

임의의 답을 정하고 해당 답이 참인지 거짓인지 판별하는게 더 쉽다면 파라매트릭 서치를 생각해본다.


7. 새로운 공간, 조건, 제약 등을 추가

문제에 없는 새로운 조건이나 제약, 공간등을 추가하고 더 쉬운 문제를 푸는 접근 방법이다.


8. 전처리

알고리즘 중에 미리 계산할 수 있는 부분이 존재하는지 생각해보고 미리 연산하고 저장하고 이용

'Algorithm' 카테고리의 다른 글

복잡도 분석  (0) 2017.04.24
호프크로프트 카프 알고리즘 (Hopcroft-Karp Algorithm)  (0) 2017.04.03
디닉 알고리즘 (Dinic's Algorithm)  (0) 2017.04.03
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함