카데인 알고리즘의 수학적 증명

About this offer

1. 전체 탐색 공간의 분할 (Partitioning) 길이가 $n$인 배열 $A$에서 만들 수 있는 연속 부분 배열의 개수는 총 $\frac{n(n+1)}{2}$개입니다. 이 전체 부분 배열들의 집합을 "어느 인덱스에서 끝나는가?"를 기준으로 $n$개의 서로소 부분집합(Disjoint Sets)으로 나눕니다. $S_0$: 인덱스 $0$에서 끝나는 부분 배열들의 집합 $S_1$: 인덱스 $1$에서 끝나는 부분 배열들의 집합 $\dots$ $S_j$: 인덱스 $j$에서 끝나는 부분 배열들의 집합 ($0 \le j < n$) 모든 연속 부분 배열은 반드시 $0$부터 $n-1$ 중 단 하나의 끝점 을 가지므로, 전체 부분 배열 중 최대합(전역 최적해)은 각 집합의 최댓값들 중 가장 큰 값과 같습니다. $$\text{Global Max} = \max_{0 \le j < n} \Big( \max(S_j) \Big)$$ 2. 점화식의 수학적 유도 (최적 부분 구조) 이제 문제를 "$j$번째 원소로 끝나는 부분 배열 중 최대합 $M[j]$를 어떻게 구할 것인가?"로 좁힐 수 있습니다. 수학적으로 $M[j]$는 다음과 같이 정의됩니다. $$M[j] = \max_{0 \le i \le j} \sum_{k=i}^j A[k]$$ 이 식에서 시작 인덱스 $i$의 경우의 수를 $i = j$인 경우(원소 1개짜리)와 $i < j$인 경우(길이가 2 이상인 경우)로 분리합니다. $$M[j] = \max \left( A[j],; \max_{0 \le i \le j-1} \left( \sum_{k=i}^{j-1} A[k] + A[j] \right) \right)$$ 여기서 $A[j]$는 $i$와 무관한 공통 덧셈 상수이므로 밖으로 묶어낼 수 있습니다. $$M[j] = \max \left( A[j],; \left( \max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k] \right) + A[j] \right)$$ 괄호 안의 $\max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k]$는 정확히 이전 단계의 정의인 $M[j-1]$입니다. 따라서 다음과 같은 전형적인 동적 계획법의 점화식이 도출됩니다. $$M[j] = \max(A[j],; M[j-1] + A[j])$$ 식을 $A[j]$를 기준으로 정리하면 더욱 직관적인 형태가 됩니다. $$M[j] = A[j] + \max(0,; M[j-1])$$ $M[j-1] > 0$이면 : 이전 누적합을 붙이는 것이 이득이므로 $M[j-1] + A[j]$ 선택 $M[j-1] \le 0$이면 : 이전까지의 최적합이 음수이므로, 이전 기록을 버리고 $A[j]$ 단독으로 새로 시작하는 것이 무조건 이득 3. 메모리 최적화 ($O(N) \to O(1)$ 공간) 점화식 $M[j] = \max(A[j], M[j-1] + A[j])$를 보면, $M[j]$를 계산할 때 필요한 이전 값은 오직 직전 값인 $M[j-1]$ 하나뿐 입니다. $M[j-2], M[j-3]$ 등 그 이전의 값들은 알 필요가 없습니다. 따라서 $N$ 크기의 배열 $M[\ ]$을 메모리에 유지할 필요 없이, 단 하나의 변수( currentSum )만 계속 덮어쓰면서 갱신하면 충분하므로 공간 복잡도가 $O(1)$이 됩니다.

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence

49%