2023년 계묘년, 검은 토끼의 해가 밝았습니다.
새해를 맞아 이번에 스터디에서 동적 계획법(Dynamic Programming, DP)에 대해서 공부했습니다.
동적 계획법이라는 것은 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 결과들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘입니다.
이 동적 계획법 알고리즘은 분할 정복 알고리즘과 비슷한 접근 방식을 가지고 있지만 다른 점은 동적 계획법은 중복된 계산을 방지하기 위해 저장된 결과를 메모리에 저장한 후 다음 계산이 필요한 경우 이전에 저장한 값을 사용하여 전체적인 실행 속도를 빠르게 해주는 기술인 메모이제이션(Memoization)을 이용합니다.
만약 피보나치 수열을 재귀적으로 구현하면 동일한 계산을 반복해야 하는 경우가 많습니다. 하지만 이런 문제를 보완할 수 있는 것이 바로 메모이제이션입니다.
fibonacci(n)의 값을 저장하고, 다음 계산에서 필요한 경우는 가져와서 실행하면 되기 때문에 실행 시간이 줄어듭니다.
하지만, 단점은 많은 메모리 공간을 필요로 합니다.
릿코드에 Maximum Product Subarray라는 문제를 풀었습니다.
일단, 이 문제에 대해서 설명하자면 배열 nums가 주어지고 nums에서 부분 배열을 찾아, 그 부분 배열(subarray)의 원소들을 다 곱한 값의 최댓값을 반환하는 문제입니다.
여기서 부분 배열이란 비어있지 않고 연속적인 배열들을 의미합니다. 예를 들어, [1, 3, 5, -4] 에서 부분 배열은 [1], [3], [5], [-4], [1, 3], [3, 5], [5, -4], [1, 3, 5], [3, 5, -4], [1, 3, 5, -4]가 될 수 있습니다. 이 중에서 원소들을 곱했을 때, 최댓값을 반환하면 됩니다.
이중 for문을 이용하여 부분 배열들을 찾아 다 곱하고, 최댓값을 갱신하는 방법으로 구현했는데, 너무 당연하다는 듯이 틀렸습니다.
이것을 어떻게 DP로 이용하여 풀까 고민하다가 답답하여 다른 분들 것을 참고했습니다만 그래도 이해가 가질 않았습니다. 그래서 그룹원 중 한 분이 알기 쉽게 설명해주셔서 이해했습니다.
일단, 음수 * 음수가 양수가 될 수 있는데, 이것이 최댓값이 되는 경우가 있습니다. 그래서 각 원소들을 곱했을 때, 최댓값(max)과 최솟값(min)을 알아야 할 필요가 있습니다.
이제 이 최댓값과 최솟값을 이용하여 경우의 수를 만듭니다. 그 경우의 수로 다음 원소 값과, 다음 원소 값 * max, 다음 원소 값 * min으로 정할 수 있습니다.
왜냐하면, 최댓값과 최솟값을 정하고 그 값이 갱신되고 있다는 가정하에, 최댓값이 양수고, 최솟값이 음수일 경우가 있을 것입니다. 그 다음 원소들 중에 음수를 만나게 되면 지금까지의 최댓값또는 최솟값과 곱하면서 갱신하게 됩니다. 이렇게 갱신하면서 부분 배열을 찾아 최대 곱을 발견할 수 있게됩니다.
코드는 다음과 같고, python으로 작성했습니다.
class Solution(object):
def maxProduct(self, nums):
answer = max_prod = min_prod = nums[0]
for i in nums[1:]:
candidates = [i, i*max_prod, i*min_prod]
max_prod = max(candidates)
min_prod = min(candidates)
answer = max(answer, max_prod)
return answer처음 이 해결 방식을 봤을 때, 어떻게 이런 생각을 해서 해결했을까...? 대단하다고 느꼈습니다. 코드는 간단한데, 이 코드를 구현하기 위해 생각한 방식들은 저에게 쉽지 않았습니다. 다른 분들은 쉽게 생각하실 수 있겠지만 저는 이런 다양한 관점으로 바라보는 시각이 너무 부족한 것 같습니다.
이번 DP 알고리즘을 풀면서 정말 부족하다라는 말도 부족할 정도로 아직 모자라는구나라고 생각했습니다.
