SCCC 여름 스터디

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

세번째 스터디 : 그리디 알고리즘 / 분할정복 / 파라메트릭 서치

● 그리디 알고리즘

그리디 알고리즘은

"결정을 할 때 그 순간에 가장 좋은 해답을 선택함으로써 최종적인 해답에 도달하는 알고리즘"

이다.

그렇지만 모든 경우에 대해서 최적해를 보장하지는 않는다. 따라서 그리디 알고리즘은 어떤 문제에서 최적의 해를 보장하는지 증명된 경우에만 사용될 수 있다.

그래서 그리디 알고리즘은

  1. 선정과정 : 현재 상태에서 가장 좋으리라고 생각되는 해답을 찾아서 해답모음에 포함시킨다.
  2. 적정성 점검 : 새로 얻은 해답 모음이 적절한지를 결정한다.
  3. 해답 점검 : 새로 얻은 해답모음이 최적의 해인지를 결정한다.

의 단계로 이루어진다.

전형적인 그리디 문제들로는 다음과 같은 문제들이 있다.

  • 동전 교환 문제
  • Dijkstra Algorithm
  • MST(Minimum Spanning Tree) : Prim, Kruskal
  • 스케쥴링(Scheduling)
  • Knapsack Problem

문제

가장 빨리 돈을 뽑을 수 있는 사람이 제일 먼저 뽑는 것이 결국 총 대기시간을 줄이는 방법이다. 시간 순으로 정렬해서 앞에서부터 더해준 값이 정답이다.

이 문제에서 핵심은 " 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙" 이다. 서류심사 성적 과 면접시험 성적 순 아무 것으로나 정렬한 뒤, 정렬되지 않은 값이 작아지는 순으로 더 이상 뽑지 못할 때까지 사원을 선택하면 된다.

 


● 분할정복

 

문제

분할정복을 연습해 볼 수 있는 가장 간단한 예라고 할 수 있다.

 

 


● 바이너리 서치Binary Search

이분 탐색은 정렬되어있는 수열에서 O(log2의N) 시간만에 원하는 값을 찾아낼 수 있는 방법이다. 우리가 생각하는 방법 안에서 거의 상수에 가까운 방법이라고 볼 수 있다.

파라메트릭 서치Parameteric Search

댓글

댓글 본문
버전 관리
화성인
현재 버전
선택 버전
graphittie 자세히 보기