최대 부분합 문제를 풀 때 쓰이는 알고리즘으로 선형시간 O(n)에 최대 부분합을 찾아내는 알고리즘이다. 동적으로 움직이는 점화식을 이용하여 동적계획법 알고리즘이라고도 한다.
A라는 정수 배열 { -1, 3, 4, -5} 이 주어졌을때 합이 최대가 되는 부분을 구하려면 가장 쉽게는 O(n^2) 탐색으로 모든 값을 탐색하는 방법도 있지만 굉장히 비효율적이다. 따라서 선형시간내에 탐색할 알고리즘으로 Kadane 알고리즘을 사용할 수 있다. 이 문제는 아래의 점화식과 같이 표현할 수 있다.
sumSubMax[i] = max(0, sumSubMax[i-1]) + A[i]
sumSubMax의 i 번째 값은 sumSubMax[i-1] 의 값이 음수일 경우 제외하고 0으로, 음수가 아닐경우는 보존하고 A[i] 값을 더하는 식으로 표현될 수 있다.
이 동적계획법 방식은 다양한 알고리즘 문제에 적용되어 효율적으로 사용할 수 있으니 기억해두는게 좋다.
'Algorithm' 카테고리의 다른 글
| [Codility] Dominator (0) | 2019.06.24 |
|---|---|
| [Codility] StoneWall (0) | 2019.06.18 |
| [Codility] Nesting (0) | 2019.06.18 |
| [Codility] Brackets (0) | 2019.06.18 |
| [Codility] Fish (0) | 2019.06.18 |
Denken_Y
coding 블로그