알고리즘 1: 슬라이딩 윈도우 (Sliding Window)

✅ 개념 요약

• 고정 크기 또는 가변 크기의 “창(window)”을 배열 위에서 왼→오 방향으로 이동하며 처리
• 시간복잡도 O(n)으로 반복 연산 최소화

---

💡 문제: 가장 긴 1의 연속 구간 (최대 K번 0을 1로 바꾸기)

0과 1로 이루어진 배열 nums가 주어진다. 최대 k번 0을 1로 바꿀 수 있을 때,
1로만 이루어진 가장 긴 연속 부분 배열의 길이를 구하라.

python

 

Input: nums = [1,1,0,0,1,1,1,0], k = 2  
Output: 7

---

✅ 풀이 (슬라이딩 윈도우)

python

 

def longest_ones(nums, k):
    left = 0
    max_len = 0
    zero_count = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

🧪 핵심 포인트

• 0의 개수가 k를 초과하면 left 이동
• 매 스텝마다 유효한 윈도우 길이 갱신