sko.kr

알고리즘 - 0. 카데인 알고리즘

algorithmsdynamic-programmingarraysoptimizationkadane
By sko•9/27/2025•1 min read

카데인 알고리즘을 사용할 때

누적 속성을 기반으로 최적의 연속 부분 배열을 찾아야 할 때 카데인 알고리즘을 사용합니다. 최대 합에 가장 일반적으로 사용되지만, 다음과 같이 적응할 수 있습니다:

  • 최대 합 (고전적인 사용 사례)
  • 최대 곱 (음수/0 처리를 위한 수정 포함)
  • 특정 속성을 가진 최장 부분 배열 (예: 합이 k와 같음)
  • 최소 합 (값을 부정하거나 비교를 역전시켜서)
  • 누적 상태를 기반으로 확장 또는 재시작의 지역적 결정을 내릴 수 있는 모든 문제

예제 문제

주식 거래: 일일 주가 변동 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 주어졌을 때, 주식을 보유할 최적의 연속 기간을 찾으세요.

  • 0일차: $2 손실
  • 1일차: $1 이익
  • 2일차: $3 손실
  • ...이하 동일

답: 3일차부터 6일차까지 보유 (부분 배열 [4, -1, 2, 1])하여 총 $6의 이익.

가장 중요한 통찰

모든 부분 배열은 어딘가에서 끝나야 한다 - 각 위치에서 최적의 지역적 결정(확장 vs 재시작)을 내림으로써, 모든 가능한 종점과 그들의 최적 시작점을 확인하여 전역 최대값을 찾는 것이 보장됩니다.

멘탈 노트: 이 알고리즘의 천재성은 "인덱스 i에서 끝나는 최적의 부분 배열"에 초점을 맞추는 데 있습니다. 각 위치에서 필요한 결정은 단 하나: "이전 인덱스에서 끝나는 최적의 부분 배열에 현재 요소를 추가할까, 아니면 새로 시작할까?" 이 간단한 결정이 모든 가능한 부분 배열을 자동으로 탐색합니다.

의사결정 프레임워크

모든 요소에서 하나의 간단한 결정에 직면합니다:

  • 현재 부분 배열을 확장 (가진 것에 추가)
  • 새로운 부분 배열로 재시작 (과거를 버림)

코드

function kadanes(nums: number[]) {
  let globalMax = nums[0];
  let localMax = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const currentNum = nums[i];
    // 의사결정 프레임워크
    const extendSubarray = localMax + currentNum;
    const startNewSubarray = currentNum;
    localMax = Math.max(startNewSubarray, extendSubarray);

    globalMax = Math.max(globalMax, localMax);
  }

  return globalMax;
}

의구심 해소

일반적인 의구심: "알고리즘은 각 위치에서 확장하거나 재시작만 고려합니다. 현재 부분 배열의 처음 몇 개 요소를 제거하면 더 큰 합을 얻을 수 있다면 어떻게 되나요?"

이것은 카데인 알고리즘에 대한 정교한 우려입니다. 구체적인 예제로 이를 해결해 봅시다.

왜 더 나은 부분 배열을 놓칠 수 있다고 생각하는가

배열 [-2, 3, 5, -1, 6]을 고려해보세요. 부분 배열을 추적할 때 다음과 같이 생각할 수 있습니다:

  • "위치 4에서 부분 배열 [3, 5, -1, 6]의 합은 13입니다"
  • "하지만 [-2, 3, 5, -1, 6] 같은 부분 배열이 있고 -2만 제거하고 싶다면 어떻게 되나요?"
  • "알고리즘은 끝에 추가하거나 완전히 재시작만 할 수 있는 것 같습니다 - 시작 부분에서 제거할 수 없나요?"

왜 이 생각이 틀렸는가

핵심 깨달음: 모든 가능한 "부분 삭제"는 이미 이전 위치에서 고려되었습니다!

[-2, 3, 5, -1, 6]을 추적해서 카데인이 이를 어떻게 처리하는지 봅시다:

위치 0: localMax = -2  ([-2])
위치 1: localMax = 3   ([3])         → 비교: -2+3=1 vs 3, 3 선택 (-2를 삭제!)
위치 2: localMax = 8   ([3, 5])      → 비교: 3+5=8 vs 5, 8 선택
위치 3: localMax = 7   ([3, 5, -1])  → 비교: 8+(-1)=7 vs -1, 7 선택
위치 4: localMax = 13  ([3, 5, -1, 6]) → 비교: 7+6=13 vs 6, 13 선택

마법의 순간: 위치 1에서 1을 얻기 위해 확장하는 대신 3으로 재시작하기로 선택했을 때, 자동으로 -2를 삭제했습니다! 알고리즘은 이미 고려하고 최적의 선택을 했습니다.

구체적인 예: 모든 삭제 가능성이 다뤄짐

원하는 부분 배열을 생각해보세요 - 예를 들어 [5, -1, 6] (-2와 3 모두 삭제)을 놓칠까 걱정한다고 가정해봅시다:

  • 첫 번째 요소 [-2] 삭제: 위치 1에서 재시작했을 때 이미 고려됨
  • 첫 두 요소 [-2, 3] 삭제: 위치 2에서 재시작(5) vs 확장(8)을 비교했을 때 이미 고려됨
  • 첫 세 요소 [-2, 3, 5] 삭제: 위치 3에서 재시작(-1) vs 확장(7)을 비교했을 때 이미 고려됨

위치 4에서 끝나는 부분 배열의 모든 가능한 시작점은 각 이전 위치에서 끝나는 최적의 부분 배열을 계산했을 때 이미 평가되었습니다!

왜 지역적 결정이 모든 것을 확인하는 것을 보장하는가

카데인 알고리즘의 훌륭함은 "재시작"이 단순히 새로 시작하는 것을 의미하는 것이 아니라 다음을 의미한다는 것입니다:

  • "이 지점 이전의 모든 것이 내 합을 악화시킨다"
  • "이전 요소들을 포함하는 모든 가능한 부분 배열은 이미 평가되었다"
  • "모든 것을 삭제함으로써, 최적의 선택을 하고 있다"

확장할 때, "최적의 시작점에서 모든 것을 유지하는 것이 여전히 유익하다"고 말하고 있습니다. 재시작할 때, "모든 것을 삭제한다 - 이 지점 이전에서 끝나는 최적의 부분 배열조차도 상황을 악화시킬 것이다"라고 말하고 있습니다.

보장: 모든 부분 배열은 어딘가에서 끝나야 하고, 각 가능한 끝 위치에 대해 최적의 시작을 찾으므로, 모든 가능한 부분 배열을 암시적으로 확인했습니다 - 시작 부분에서 다양한 요소를 삭제하는 모든 것을 포함해서!

← Back to Blog