[TIL] 11. 9월 알고리즘(Greedy, DP)

탐욕법(Greedy)

Greedy(탐욕법) 이란?

이름 그대로 각 단계에서 지금 당장 좋아보이는 최선의 선택을 하는 알고리즘이다.

해당 알고리즘의 핵심은 매 순간 최적해가 결국 전체 문제의 최적해일 것이다 라는 믿음에 있다.

 

예시

대표적으로 거스름돈 문제가 있다.

예를 들어 500원, 100원, 50원, 10원짜리 동전으로 870원을 거슬러 줘야한다고 생각해보자.

1. 우선 가장 가치가 큰 500원 짜리 먼저 주자(1개 사용, 370원 남음)

2. 남은 돈에서 가장 가치가 큰 100원짜리를 주자(3개 사용, 70원 남음)

3. 다음은 50원(1개 사용, 20원 남음)

4. 마지막으로 10원(2개 사용, 0원 남음)

 

이렇게 가장 가치가 큰 동전을 선택하는 탐욕적인 선택만으로 동전의 개수를 최소화하는 최적의 해를 찾았다.

탐욕법의 장단점

그리디알고리즘을 사용하면 구현이 매우 직관적이고, 한 번의 선택으로 끝나므로 속도가 빠르다는 장점이 있다.

하지만 이 선택이 항상 전체의 최적해를 보장하지는 않는다. 만약 400원짜리 동전이 있다면 그리디 방식으로는 최적해를 찾지 못할 수 도 있다.

 

언제 사용해야하나요?

그리디는 문제의 구조가 단순하고, 순간의 최선이 전체의 최선을 보장하는 특별한 경우에만 사용할 수 있다.

---

동적계획법(DP, Dynamic Programming)

동적계획법이란?

거대한 문제를 잘게 쪼개어 해결하는 분할 정복(Divide and Conquer)과 비슷하지만, 한 가지 중요한 차이가 있다.

DP의 핵심은 memoization(기억하기)이다. 복잡한 문제를 풀다 보면 같은 하위 문제를 반복해서 풀어햐 하는 경우가 있다. DP는 이 하위 문제의 정답을 계산했을 때, 그 결과를 테이블이나 배열 등에 저장해두고 나중에 같은 문제가 나오면 다시 계산하지 않고 저장된 값을 꺼내 쓰는 전략이다.

 

예시

DP의 원리를 가장 잘 보여주는 문제는 피보나치 수열이다. 5번째 피보나치 수를 알려면 4번째와 3번째를 알아야하고, 4번째를 알려면 3번째와 2번째를 알아야한다. 이 과정에서 같은 계산을 여러번 반복하게 된다.

동적 계획법은 처음 3번째를 계산할 때 그 값을 dp[3]과 같은 배열에 저장해둔다. 그리고 다음에 또 3번째 값이 필요하다면 dp[3]에서 값을 바로 가져와 사용하면 된다. 이 차이가 문제의 크기가 커질 수록 엄청난 성능 향상을 가져온다.

 

DP의 장단점

DP는 중복 계산을 획기적으로 줄여주며, 모든 경우를 체계적으로 탐색하므로 항상 최적의 해를 보장한다.

하지만 어떤 하위 문제로 쪼개야 할 지, 어떤 값을 저장해야 할 지 결정하는 '점화식'을 세우는 과정이 어려울 수 있고, 결과를 저장할 추가적인 메모리 공간이 필요하다.

 

언제써야하나요?

DP는 문제의 부분들이 서로 겹치고, 작은 문제의 해답이 큰 문제의 해답을 구성하는 구조일 때 중복 계산을 피해 최적의 해를 찾는  문제일 때 사용하면 된다.

 

이어서

그리디 알고리즘은 정당성이 보장되는 특정 문제에 한해 가장 좋은 해결책이 될 수 있다, 동적 계획법은 조금 복잡하더라도 반드시 최적의 해를 찾아야 하는 문제에서 강력한 힘을 발휘할 수 있다.

결국 어떤 알고리즘을 선택할지는 우리가 해결해야하는 문제에 따라 달려있다.