TIL 52일차_알고리즘: 탐욕알고리즘과 동적계획법

알고리즘 ... 😭
하루이틀만에 머릿속에 너무많이 입력한 것 같다... 정리하자.

탐욕 알고리즘 (Greedy Algorithm)

여러 경우 중, 그 '순간' 에 최적이라고 생각하는 것을 선택해 나가는 방식.
'순간'이라고 정의하는 선택은 Local하게는 최적이지만,
그 선택이 계속되어 Global하게 해답을 만들었을 때, 그것이 최적이라는 보장은 없다.

Greedy Algorithm이 최적의 결과를 보장하기위해서는,
Greedy Choice Property 와 Optimal substructure라는 두 가지 속성을 만족해야한다.

• Greedy Choice Property : subproblem의 해답이 다음 subproblem에 영향이 가지 않는다는 독립적인 연산 속성
• Optimal Substructure : 문제 전체의 최적해(Global Optimal)이 Subproblem에서도 최적해가 된다는 속성

쉽게 말하면, Greedy Algorithm은 매 순간마다 최적의 수를 계산한다 했으므로,
각 순간은 독립적이며 그 결과가 어느 순간에도 영향을 끼치지 않는다는 속성과
매 순간마다 구한 최적의 수가 전체 문제에 대한 최적해와 같아야된다는 속성을 가져야 최적의 결과를 보장한다.

그렇다면, Greedy Algorithm이 저 위의 두 속성을 만족하지 않는다면 안좋은 것일까?

NO!!
탐욕알고리즘이 최적해를 보장하지는 않지만,
근사 알고리즘으로 사용이 가능하며, 대부분의 경우 계산 속도가 빠르기때문에 실용적으로 사용이 가능하다.
최적해를 보장하지는 않지만, 최적해에 가까운 값을 사용함으로써,
어느정도의 Loss를 감안하고 빠른 실행시간을 얻을 수 있다.

동적계획법 (Dynamic Programming)

모든 경우의 수를 따져본 후, 이를 조합해 최적의 해법을 찾는 방식
동적계획법은 재귀와 밀접하게 연결되어 있다.

보통, 모든 경우의 수를 따져보며 중간 계산 결과를 저장해두고, 다음 계산에 써먹는 방식으로 진행해나간다.
DP는 모든 경우의 수를 따져보기 때문에 그만큼 계산하는데 오랜 시간이 걸린다는 단점이 있다.
즉, DP와 Greedy Algorithm는 하위 문제를 해결했을때 원래 문제를 해결할 수 있는 속성은 동일하지만,
DP는 Time Complexity가 더 높지만 그 결과의 신뢰도는 높다고 할 수 있다.

예시

두 방법으로 가장 작은 값을 찾아보자.

1. 탐욕 알고리즘: 시작점에서 7<10 이므로 7선택 --> 12<15 이므로 12선택
2. 동적 계획법: 시작점에서 모든 경우를 살핀다. --> 재귀와 메모이제이션으로 살핀 뒤 최적의 값 10선택 - 5선택

참고: RAINBOW-LAB, SK_MOUSE 개발일기