항해99 19일차 [ 그리디 알고리즘/ 동적 프로그래밍]

19일차

그리디 알고리즘

그리디는 탐욕스러운, 욕심이 많은 이라는 의미를 가지고 있는 단어이다.
그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황의 답에 도달하는 방식을 말한다. 하지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장이 없다.

따라서 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들일때 그리디 알고리즘을 적용할 수 있다.

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 어떤 조건을 가지고 있을까?
1. greedy choice property : 현재 선택이 이 후의 선택에 영향을 주지 않는다.
2. optimal substructure : 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함
이 이외에도 그리디 알고리즘은 근사 알고리즘을 사용하는 경우가 있다.

동적 알고리즘

: 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. '다이나믹'이라는 단어는 이 기법과 아무런 상관이 없다.

Divide and Conquer(분할 정복)과 다른점은?

작은 문제가 중복이 있는지 없는 지의 차이가 있다.

Dynamic Programming의 조건❔

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같다.