Algorithm: Greedy Algorithm / Dynamic Programming

**해당 포스트는 지속적 업데이트를 진행할 것입니다. **
**그리디와 다이나믹 프로그래밍 문제들에 대한 링크가 포함될 것입니다. **

본 포스트는 “파이썬 알고리즘 인터뷰”를 기반으로 작성되었습니다. 본 책은 알고리즘 공부에 있어 좋은 평가가 자자하며, 특히 한 줄 씩 뜯어먹을 때 이렇게 맛있는 책이 또 없는 것 같다고 생각합니다. 취업을 위해 알고리즘을 공부하는 현 시점에서 성경과도 같이 말씀 하나 하나가 주옥 같아 잘 때도 머리 맡에 두고 자고 있습니다.

이번에 정리해보고자 하는 내용은 그리디 알고리즘과 다이나믹 프로그래밍입니다. 저의 주관으로, 그리고 알고리즘 애송이의 관점으로 봤을 때 이 두 분야의 문제들을 어려움 없이 풀 수 있어야 알고리즘을 이해하기 시작했다고 간주할 수 있다고 생각합니다. 다른 문제들은 카테고리가 정해져있다고 하더라도 반복이나 여러 전략들로 대체할 수 있는 요소가 있지만, 시험에서 그리디 알고리즘과 다이나믹 프로그래밍이 나오면 그것을 알아차려야 풀 수 있다고 생각하기 때문입니다. 즉, 해당 문제들이 나왔는데, 문제의 풀이 전략이 바로 떠올리지 못한다면 대체할 수 있는 방법이 적어보입니다.

두 분야를 함께 정리하고 싶은 이유는 주관적인 난이도도 있지만, 꽤 유사하기에 계속 헷갈리기 때문입니다. 애송이인 저는 이 문제를 봤을 때 아직도 무섭지만 정리와 많은 문제를 풀어가면서 GA (그리디 알고리즘) / DP (다이나믹 프로그래밍) 포비아를 극복해보겠습니다.

GA (그리디 알고리즘)

그리디 알고리즘이란 정의는 ‘매 순간에 최고의 이익을 얻고 싶어하는 욕심쟁이 기법’이기 때문에 이름과 매칭이 잘 됩니다. 뭔가 반복문을 사용하나 해당 시점의 최대 이익을 추구한다고 생각하면 편하긴 합니다. 해당 기법은 Local optimum을 찾기 위해 노력하기 위해 결과적으로 Global Optimum을 찾지 못할 수도 있습니다. 즉, 매순간 최적해를 찾는 과정이지만 실제 최적해를 구하는 것은 미지수라는 뜻입니다. GA는 ‘최적 부분 구조(Optimal Substructure)’를 띄는 탐욕 선택 속성 문제의 해결법입니다.

최적 부분 구조: 하나의 문제를 부분 문제로 나눈 뒤 결합하여 풀이 예를 들어, 서울에서 대전을 찍고 부산을 가는 경우, (서울 > 부산)의 최적의 경로는 (서울 > 대전) / (대전 > 부산)의 최적의 경로를 구한 뒤 더하는 것과 같은 것입니다. 물론 서울에서 부산으로 바로 가는 경로가 없다는 가정 아래입니다.
탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는다.

대표적인 문제를 통해 해당 문제들이 왜 GA이며, 어떻게 접근해야 하는지 간략하게만 살펴보겠습니다.

동전 바꾸기 문제 1600원을 100 / 500 / 1000원으로 최소의 개수로 나타낸다고 할 때, 액면가가 높은 1000원부터 탐욕적으로 선택하여 10001 + 5001 + 100+1로 풀 수 있습니다. 액면가 순으로 빠르고 해당 시점에서 최고의 선택만을 빠르게 선택한 것입니다. 하지만 해당 문제는 동전들끼리 배수의 관계가 되어야 합니다. 예를 들어, 800원이 동전 리스트에 새로 등장했을 때, 1600원은 1000원부터 계산하는 것이 아니라 800원 짜리 두개를 통해 구성할 수 있으므로 GA를 구성하게 되면 Local Optimum에 빠지게 되는 것입니다.

DP (다이나믹 프로그래밍)

DP는 문제를 각가의 작은 문제로 나누어 해결한 결과를 ‘저장’해두었다가 나중에 큰 문제의 결과와 합해 풀이하는 알고리즘입니다. 그리디 알고리즘은 한번 선택한 것은 무르지 않는 독불장군이기 때문에 굳이 선택한 결정을 기억할 필요가 없기에 기록하지 않지만 DP는 최적해를 구하기 위하여 많은 가능성을 기억해두고자 합니다.

DP는 ‘최적 부분 구조’를 갖는 ‘중복 문제’에 대한 풀이입니다.

중복 문제에 대한 이야기는 대표적인 DP 문제인 피보나치 수 문제를 다루면서 진행하도록 하겠습니다.

‘파이썬 알고리즘 인터뷰’에서는 ‘피보나치=DP’라는 의견을 갖고 있는 것 같습니다. 피보나치에 대한 다양한 접근법이 곧 DP에 대한 다양한 접근법이며 해당 문제가 DP의 정수를 담고 있다고 묘사합니다. 따라서 DP에 대한 문제는 피보나치 하나로 시작하겠습니다.

피보나치 수열이란 다들 잘 아시다시피, 2번째 이전의 수와 1번째 이전의 수를 더해 현재 시점의 수를 만드는 수열입니다. 책에서는 하나의 변수의 값을 업데이트 해나가는 법과 행렬을 활용한 방식 또한 설명하지만, 저는 대표적인 1) 재귀 구조 Brute Force / 2) 메모이제이션 / 3) 타뷸레이션에 대해 정리하겠습니다.

재귀 구조 Brute Force

재귀 구조의 피보나치 수는 0과 1일때만 Return을 진행합니다.
예를 들어, 5번째 피보나치 수는 3인데, n <=1이 성립하지 않으므로 fibonacci(4) + fibonacci(3)으로 표현할 수 있으며 각 요소들은 다시 재귀를 통해 0과 1로 표현될 수 있을 때까지 진행됩니다.

def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

메모이제이션 (하향식)

하향이라는 말은 위에서 아래로 향한다는 뜻이므로, 목표가 수립되면 그것에 필요한 재료를 하나씩 단계를 낮춰가면서 찾는 것입니다. 이는 재귀를 통해 수행합니다.

def fibonacci(n: int) -> int:
    temp = [0 for _ in range(n+1)]
    if n <= 1:
        return n
    
    if temp[n]:
        return temp[n]
    temp[n] = fibonacci(n-1) + fibonacci(n-2)
    return temp[n]  

타뷸레이션 (상향식)

상향이라는 말은 아래에서 위로 향한다는 뜻이므로, 기본 재료를 갖추고 그것을 조합해가며 최종 목표에 다다르는 것입니다. 즉, 1) 재료를 구성 / 2) 목표 지점까지 반복을 하는 것입니다. 이 때 재귀를 사용하지 않고 반복으로 진행하며,, 미리 계산을 해둔 값을 Table화 시키는 Tabulation을 진행한 뒤, 필요한 값을 조각조각 모아서 가져오는 것입니다.

def fibonacci(n: int) -> int:
    temp = [0 for _ in range(n+1)]
    temp[1] = 1
    
    for i in range(2, n+1):
        temp[i] = temp[i-1] + temp[i-2]
    return temp[n]