[알고리즘] 동적 계획법(dynamic programming) - 2

오늘은 동적 계획법 제 2 단계를 시작하겠습니다!

지난번에는 메모이제이션을 통해서 입력 값이 계산되었다면, 바로 그 값을 반환하는 것을 배웠습니다.

이번에는 입력값을 어떻게하면 걸러낼 수 있을지에 대해서 한번 살펴보겠습니다.

만약, 앞에 해결한 부분의 조각들의 결과들이 뒤에 미해결된 부분 조각들에 영향을 주지 않는 문제가 있다고 합시다.

(대표적으로, 수열에서 점차적으로 증가하는 부분집합의 가장 긴 개수를 찾는 LIS(longest increasing subsequence가 있습니다.)

그렇다면, 이 문제의 답은 

(0~0번 까지의 답) or (0~1번 까지의 답) or (1~2번 까지의 답) 등등... + (3~5번 까지의 답) 으로 나눠서 구할 수 있습니다.

(현재의 답 + solve(3,5) 의 형식으로 나타날 것입니다.)

이처럼, 지금까지 어떤 경로로 부분 문제에 도달했더라도 남은 부분 문제는 항상 최적으로 풀어도 상관 없는 경우를 '최적 부분 구조'라고 합니다. 그리고, 이 부분을 구하는 것이 바로 동적 계획법에서 아주 중요한 요소입니다!

보통, 배열에서는 부분을 나누기 위해서 '시작 인덱스'를 변경하는 방식을 사용합니다. 배열을 새로 만들어서 넘겨주는 것 보다는 원래 있던 배열의 시작 인덱스만 알려주는 것이 그 배열의 부분 집합을 넘겨주는데 훨씬 효과적이기 때문입니다!

다만, 어떤 경우에는 더 작은 문제의 최적해만으로 전체 문제의 최적해를 구할 수 없는 경우가 있습니다.

예를 들어, 서울 - 부산 까지의 통행료가 3만원이 넘지 않는 경우의 최적 경로를 찾고싶다는 경우를 생각해봅시다.

서울 - 대전 까지 가는 경로 A와 대전 - 부산까지 가는 경로 B, C가 있습니다.

경로 B : 통행료 1 만원, 시간 2 시간

경로 C : 통행료 2 만원, 시간 1 시간

경로 A의 가격에 따라서 B와 C를 결정하는 조건이 달라집니다. 

예를 들면, 경로 A의 가격이 5천원이라면, 경로 C를 선택하는 것이 맞습니다.

하지만, 경로 A의 가격이 1만 5천원이라면 경로 C를 선택할 수 없게 됩니다.

따라서, 이러한 경우에는 부분 문제의 정의에 지금까지 지불한 통행료에 대한 정보를 추가시키는 작업이 필요합니다. 

이러한 정보가 많을수록 메모이제이션을 해도 중복이 많이 일어나지 않기 때문에 최적화의 효율은 떨어집니다.

그럼 지금까지 배운것을 토대로 최적화 문제 동적 계획법을 할때의 순서를 대략적으로 알아봅시다.

1. 완전 탐색 알고리즘 방법 생각합니다.

2. 최적 부분 문제를 구할 수 있는지 부분 문제 정의를 생각합니다.

3. 최대한 문제가 중복이 될 수 있도록 재귀 호출 입력 이전에 꼭 필요한 정보만 넘깁니다.

4. 입력이 배열이나 문자열인경우 적절하게 부분 문제를 만들 수 있도록 합니다. (위에서 처럼 배열의 부분을 인덱스를 활용하여 넘기도록 합시다!)

5. 메모이제이션을 이용합니다.

오늘의 동적 계획법은 여기까지 입니다!