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

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가 되는 경우 찾기)
• 연속된 원소들의 곱 찾기 (예: 최대 연속 부분 배열의 곱)
• 특정 조건을 만족하는 최장 부분 배열 찾기

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