● 그리디 알고리즘
그리디 알고리즘은
"결정을 할 때 그 순간에 가장 좋은 해답을 선택함으로써 최종적인 해답에 도달하는 알고리즘"
이다.
그렇지만 모든 경우에 대해서 최적해를 보장하지는 않는다. 따라서 그리디 알고리즘은 어떤 문제에서 최적의 해를 보장하는지 증명된 경우에만 사용될 수 있다.
그래서 그리디 알고리즘은
- 선정과정 : 현재 상태에서 가장 좋으리라고 생각되는 해답을 찾아서 해답모음에 포함시킨다.
- 적정성 점검 : 새로 얻은 해답 모음이 적절한지를 결정한다.
- 해답 점검 : 새로 얻은 해답모음이 최적의 해인지를 결정한다.
의 단계로 이루어진다.
전형적인 그리디 문제들로는 다음과 같은 문제들이 있다.
- 동전 교환 문제
- Dijkstra Algorithm
- MST(Minimum Spanning Tree) : Prim, Kruskal
- 스케쥴링(Scheduling)
- Knapsack Problem
문제
가장 빨리 돈을 뽑을 수 있는 사람이 제일 먼저 뽑는 것이 결국 총 대기시간을 줄이는 방법이다. 시간 순으로 정렬해서 앞에서부터 더해준 값이 정답이다.
이 문제에서 핵심은 " 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙" 이다. 서류심사 성적 과 면접시험 성적 순 아무 것으로나 정렬한 뒤, 정렬되지 않은 값이 작아지는 순으로 더 이상 뽑지 못할 때까지 사원을 선택하면 된다.
● 분할정복
문제
분할정복을 연습해 볼 수 있는 가장 간단한 예라고 할 수 있다.
● 바이너리 서치Binary Search
이분 탐색은 정렬되어있는 수열에서 O(log2의N) 시간만에 원하는 값을 찾아낼 수 있는 방법이다. 우리가 생각하는 방법 안에서 거의 상수에 가까운 방법이라고 볼 수 있다.
● 파라메트릭 서치Parameteric Search
