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가 되는 경우 찾기)
- 연속된 원소들의 곱 찾기 (예: 최대 연속 부분 배열의 곱)
- 특정 조건을 만족하는 최장 부분 배열 찾기
캐터필러 방법은 슬라이딩 윈도우와 유사하며, 연속된 부분 배열을 효과적으로 다룰 때 유용하다.
반응형