[알고리즘 #5] Problem Solving Paradigms(2)

Greedy Algorithms

: 매 과정마다 현재 상태에서 최적의 해를 만드는 것을 선택해 나가는 방법

- Greedy Algorithm 동작하기 위해서는 다음 두가지 조건을 만족해야 한다.

1. Local optimum 의 존재

2. 이것을 greedy 한 방법으로 global optimal solution 에 도달 가능하다는 것을 증명가능해야함

 

그리디 알고리즘 예시 : 크루스칼, 다익스트라, Huffman code , 스케줄링

 

입력 사이즈가 커서 다른 방법이 통하지 않을 것처럼 보이면 greedy 를 우선적으로 고려해볼 만하다.

문제에서 greedy algorithm 을 사용할 수 있는지 애매한 경우 보통 입력 데이터를 sorting 하면 문제가 해결되는지 여부로 어느 정도 파악 가능하다.

 

ex) Uva 410_ Station Balance

 

ex) Uva 10382_ Watering Grass

 

ex_ Uva 10718 _ Bit Mask

 

Dynamic Programming

Recursion + Memoization 

단순 테이블 채우기가 아닌 memoization 이용해 recursion 을 효율저긍로 수행하는 기법

 

1. 문제를 정확하게 정의하기

2. 정의된 문제에 대한 subproblem 을 생각한 뒤 이를 이용해 recurrence relation 을 세우기

 

3. Memoization 이용하여 recurrence relation 계산

- 중간 결과물을 저장할 data structure 고르기 : 보통 n차원 array

- subproblem 들 간의 dependency 확인

- dependency  에 기반하여 subproblem 의 답을 구하는 순서를 정하기 

 

ex) Uva 11450 _ Wedding Shopping

 

 

ex) Uva_ 10003 _ Cutting Sticks

 

 

ex) Uva 10755 _ Garbage Heap