30 핵심 알고리즘 :Ep-07:카데인 알고리즘

Source: Dev.to

Overview

많은 시스템이 실패하는 이유는 모멘텀이 부족해서가 아니라, 모멘텀을 버리지 않으려 하기 때문이다.
Kadane’s Algorithm은 겉보기엔 어려운 질문에 답한다: 계속 진행하는 것이 재시작보다 비용이 더 많이 드는 순간은 언제인가?

이 알고리즘은 배열에만 국한되지 않는다. 시간에 따라 성과를 추적한다고 생각해 보라: 어떤 구간은 긍정적인 기여를 하고, 다른 구간은 부정적인 기여를 한다. 순진한 접근법은 가능한 모든 구간을 독립적으로 평가해 데이터 어딘가에 최적의 결과가 있기를 기대한다. 이렇게 하면 작동하지만, 모든 과거를 기억할 필요는 없다. 때로는 과거를 더 이상 이어가지 않는 것이 최선의 선택이다.

Core Idea

Kadane’s Algorithm은 엄격한 규칙을 만든다:

과거가 현재에 해를 끼친다면, 과거를 버려라.

각 단계마다 알고리즘은 현재 시퀀스를 확장하는 것이 유리한지, 아니면 새로 시작하는 것이 더 나은 결과를 낼지를 결정한다. 이 판단은 전역적인 비교가 아니라 지역적인 판단이다.

Algorithm

best = float('-inf')
current = 0

for value in sequence:
    current = max(value, current + value)
    best = max(best, current)

• **current**는 현재 위치에서 끝나는 최상의 합을 보관한다.
• **best**는 지금까지 본 전체 최대값을 기록한다.

부분 배열에 대한 기억은 없으며, 각 단계는 하나의 질문만 한다: “내가 가진 것을 유지하는 것이 아직도 도움이 되는가?”

Why It Works

Kadane의 관찰은 단순하지만 강력하다:

누적 합이 음수가 되면, 뒤따르는 어떤 값의 가치도 감소시킬 뿐이다.

따라서 알고리즘은 부정적인 접두사를 버리는 것을 주저하지 않는다. 이러한 리셋 의지는 과거 결정을 다시 검토하지 않아도 최적해를 유지하게 만든다.

Applications Beyond Arrays

동일한 논리는 시스템이 잡음 속에서 의미 있는 연속을 감지해야 할 때 어디서든 나타난다, 예를 들어:

• 성과 연속 streaks
• 금융 손익 기간
• 신호 처리 피크

각 경우에 목표는 연속성을 보존하는 것이 아니라 가장 유익한 연속 구간을 찾아내는 것이다.

Limitations

Kadane’s는 재시작 비용이 낮다고 가정한다. 상태를 리셋하는 데 비용이 많이 들거나, 과거가 장기적인 의존성을 가지고 있다면 알고리즘의 논리가 무너질 수 있다. 다음과 같은 상황에서 한계가 있다:

• 다차원 제약
• 지연된 페널티
• 복구 비용이 중요한 시스템

Trade‑offs

Kadane’s는 결단력은 있지만 조심성은 부족하다. 완전성을 포기하고 즉시성을 선택한다:

• 장점: 선형 시간(O(n))과 상수 메모리(O(1))로 문제에 대한 최적 결과를 제공한다.
• 단점: 모든 가능한 구간을 탐색하지 않는다; 점진적으로 구축될 수 있는 구간만 고려한다.

Takeaway

Kadane’s Algorithm은 단순히 최대 부분 배열을 찾는 것이 아니라 과거의 노력이 더 이상 자산이 되지 않을 때를 인식하고, 즉시 포기할 수 있는 규율을 의미한다. 이 원칙은 시스템이 실제 모멘텀과 누적된 저항을 구분해야 하는 모든 곳에 나타나며, 그래서 Kadane’s는 단순한 트릭이 아니라 핵심 알고리즘으로 남아 있다.