1. 동적 계획법이란?
동적 계획법(Dynamic Programming, DP)은 계산 문제를 해결하기 위한 알고리즘의 하나로, 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 방법입니다. 일반적으로 재귀적 접근을 통해 하위 문제의 결과를 기억하여(메모이제이션 기법) 반복 계산을 방지하여 성능을 개선할 수 있습니다.
동적 계획법은 주로 최적화 문제(solving optimization problems)에 사용되며, 주어진 문제에서 최적의 해를 구하는 데 효과적입니다. 많은 문제들이 동적 계획법으로 해결될 수 있으며, 피보나치 수열, 최장 공통 부분 수열, 최소 편집 거리 문제 등이 그 대표적인 예입니다.
2. 적용 문제: 최대 부분 수열 합
문제 설명: 주어진 정수 배열에서 최대 부분 수열의 합을 구하는 문제입니다. 부분 수열은 배열에서 연속된 원소들을 선택하여 구성됩니다. 예를 들어 배열 [−2,1,−3,4,−1,2,1,−5,4]에서 최대 부분 수열의 합은 6입니다. (이는 [4,−1,2,1]의 합입니다.)
2.1 문제 접근
이 문제는 동적 계획법을 통해 해결할 수 있습니다. 배열의 각 원소를 순회하면서, 현재 원소를 포함하는 최대 합을 계산합니다. 현재 원소가 포함된 경우와 포함되지 않은 경우를 비교하고 더 큰 값을 선택합니다. 이전 원소의 최대 부분 수열 합을 활용하여 현재 원소의 최대 부분 수열 합을 결정합니다.
3. 문제의 풀이 과정
3.1 변수를 정의하자
먼저, 다음과 같은 변수를 정의하겠습니다:
nums: 주어진 정수 배열max_sum: 현재까지의 최대 부분 수열 합current_sum: 현재 위치까지의 부분 수열 합
3.2 점화식 정의
점화식은 다음과 같이 정의할 수 있습니다:
current_sum = max(nums[i], current_sum + nums[i])여기서 nums[i]는 현재 원소입니다. 현재 원소를 포함할 때의 합과 포함하지 않을 때의 합 중 큰 값을 선택하게 됩니다. 그리고 매 시간 max_sum을 갱신합니다.
3.3 초기화 및 반복문 작성
초기화 후 반복문을 작성하여 각 원소를 순회하면서 최대 부분 수열의 합을 구합니다.
def max_sub_array(nums):
max_sum = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum
위 코드에서는 배열의 첫 번째 원소를 초기값으로 설정하고, 두 번째 원소부터 시작하여 max_sub_array를 반복적으로 수행합니다.
3.4 코드 설명
코드를 한 줄씩 살펴보겠습니다:
max_sum = nums[0]: 최대 부분 수열 합을 첫 번째 원소로 초기화합니다.current_sum = nums[0]: 현재 부분 수열 합을 첫 번째 원소로 초기화합니다.for i in range(1, len(nums)):: 배열의 두 번째 원소부터 순회합니다.current_sum = max(nums[i], current_sum + nums[i]): current_sum을 업데이트합니다.max_sum = max(max_sum, current_sum): max_sum을 업데이트합니다.
3.5 실행 결과
print(max_sub_array([-2,1,-3,4,-1,2,1,-5,4])) # 6위 코드를 실행하면 최대 부분 수열의 합 6이 출력됩니다.
4. 동적 계획법의 기법
4.1 메모이제이션과 바텀업 접근
동적 계획법은 보통 두 가지 주요 기법으로 구분됩니다:
- 메모이제이션 (Memoization): 하위 문제의 결과를 저장하여 불필요한 계산을 줄이는 방식입니다. 재귀 호출을 사용하며, 각 함수 호출 시 이미 계산된 결과가 있는지 확인합니다.
- 바텀업(Bottom-Up): 작은 하위 문제부터 차례대로 해결해 나가는 방식입니다. 일반적으로 반복문을 통해 구현되며, 메모리 사용량을 줄일 수 있습니다.
이러한 기법을 활용하여 다양한 문제를 해결할 수 있습니다.
5. 결론
동적 계획법은 다양한 최적화 문제를 해결하는 데 매우 유용한 알고리즘 기법입니다. 이번 강좌에서 설명한 최대 부분 수열 합 문제를 통해 동적 계획법의 기본적인 개념과 문제 해결 방법을 익힐 수 있었습니다. 이는 다양한 알고리즘 문제 해결에 응용될 수 있으며, 코딩테스트에서 자주 출제되는 주제입니다.
추가로, 다양한 문제를 연습하며 동적 계획법에 대한 이해를 깊이 있게 확장해보시길 바랍니다. 이를 통해 알고리즘적 사고력을 향상시키고, 코딩테스트에서 좋은 결과를 얻을 수 있을 것입니다.