Code/Codility

15. 캐터필러 방법 (Caterpillar Method) Codility Lesson 한국어 정리본 (JavaScript ver.)

haeunkim.on 2025. 3. 2. 16:30

1. 캐터필러 방법이란?

캐터필러 방법은 연속된 부분 배열(슬라이스)에서 특정 조건을 만족하는 경우를 찾는 효율적인 방법 이다. 보통 O(n) 시간 복잡도로 최적화할 수 있다.


2. O(n) 시간 복잡도의 캐터필러 방법

JavaScript 코드:

function caterpillarMethod(A, s) {
    let n = A.length, front = 0, sum = 0;
    for (let back = 0; back < n; back++) {
        while (front < n && sum + A[front] <= s) {
            sum += A[front];
            front++;
        }
        if (sum === s) return true;
        sum -= A[back];
    }
    return false;
}

이 방법을 사용하면 O(n) 시간 복잡도로 특정 조건을 만족하는 부분 배열을 찾을 수 있다.


3. 캐터필러 방법의 활용

이 알고리즘은 다음과 같은 문제에 적용할 수 있다:

  • 연속 부분 배열의 합 찾기 (예: 연속된 숫자의 합이 특정 값 s가 되는 경우 찾기)
  • 연속된 원소들의 곱 찾기 (예: 최대 연속 부분 배열의 곱)
  • 특정 조건을 만족하는 최장 부분 배열 찾기

캐터필러 방법은 슬라이딩 윈도우와 유사하며, 연속된 부분 배열을 효과적으로 다룰 때 유용하다.

반응형