슬라이딩 윈도우(Sliding Window)는 고정된 크기의 창(Window)을 옆으로 밀면서 데이터를 처리하는 알고리즘 기법입니다. 중복 계산을 줄여 시간 복잡도를 (O(n))으로 최적화하는 데 매우 유용하다.1

또한, 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리하는 방법이다.2

문자열 처리에서 Dictionary<char, int>나 int[] 배열을 활용해 투 포인터(Two Pointers) 방식으로 직접 구현하면 IndexOf보다 훨씬 효율적인 $O(N)$ 성능의 함수를 만들 수 있다.

Substring 사용은 메모리 할당(GC 과부하)이 발생하여 윈도우가 움직일 때마다 Substring을 호출하면 성능이 급격히 떨어진다. 이때 Span<T> 또는 ReadOnlySpan<char>를 사용하면 메모리 복사 없이 문자열의 특정 구간을 가리킬 수 있다.

ReadOnlySpan<char> window = s.AsSpan().Slice(left, right - left + 1);
사용 예제
// 최소 구간 찾기 (Minimum Window Substring)
// 출력: BANC
const string text1 = "ADOBECODEBANC";
ReadOnlySpan<char> minWin = SlidingWindow.GetMinWindow(text1, "ABC");
LogHelper.Debug($"최소 구간 찾기 : {minWin.ToString()}");

// 중복 없는 가장 긴 문자열 길이
// 출력: 3 (abc)
const string text2 = "abcabcbb";
int longLen = SlidingWindow.GetLongestUniqueLength(text2);
LogHelper.Debug($"중복 없는 최장 길이: {longLen}"); 

// 애너그램 위치 찾기
// 출력: 0, 6
const string text3 = "cbaebabacd";
List<int> anagrams = SlidingWindow.FindAnagrams(text3, "abc");
LogHelper.Debug($"애너그램 인덱스: {string.Join(", ", anagrams)}");

// K개 고유 문자 포함 최장 길이
// 출력: 3 (ece)
const string text4 = "eceba";
int kLen = SlidingWindow.GetMaxKUniqueLength(text4, 2);
LogHelper.Debug($"최대 2개 고유문자 최장 길이: {kLen}");
Sliding Window 함수
함수명 핵심 목표 윈도우 크기 핵심 데이터 구조
GetMinWindow 조건 만족하는 최소 길이 가변 (수축 중심) int[] (필요 빈도수)
GetLongestUnique 중복 없는 최대 길이 가변 (확장 중심) int[] (마지막 위치)
FindAnagrams 구성이 일치하는 모든 위치 고정 int[] (고정 빈도수)
GetMaxKUnique 종류가 K개 이하인 최대 길이 가변 (확장 중심) int[] (현재 종류수)

최대 K개의 고유 문자(Unique Characters)를 포함하는 가장 긴 부분 문자열 찾기

예시 (K = 2 일 때) : 문자열 : a a b a c b e

  • [a a] : 고유 문자 1종 (a) - 통과
  • [a a b] : 고유 문자 2종 (a, b) - 통과
  • [a a b a] : 고유 문자 2종 (a, b) - 통과 (현재 최장 길이: 4)
  • [a a b a c] : 고유 문자 3종 (a, b, c) - 실패! (K=2를 초과함)
  • 이제 왼쪽에서 하나씩 뺀다.
  • [a b a c] (3종), [b a c] (3종), [a c] (2종) … 다시 조건을 만족할 때까지 줄인다

결과적으로 위 문자열에서 K=2일 때 가장 긴 구간은 aaba로 길이는 4가 된다.

모든 문자를 포함하는 최소 구간 찾기 (Minimum Window Substring)

  • 데이터 필터링 및 요약
  • 로그 분석: 세 키워드 모두 등작하는 가장 짧은 타임라인 추출
  • 문서 요약: 검색한 키워드들이 모두 포함된 가장 짧은 문장 찾기)
  • Left 최대 수축
public static ReadOnlySpan<char> GetMinWindow(string s, string t)
{
    if (string.IsNullOrWhiteSpace(s) || string.IsNullOrWhiteSpace(t))
    {
        return ReadOnlySpan<char>.Empty;
    }

    try
    {
        int[] targetMap = new int[128];

        foreach (char c in t)
        {
            targetMap[c]++;
        }

        int[] windowMap = new int[128];
        int left = 0, count = 0, minLen = int.MaxValue, startIndex = 0;
        int required = t.Distinct().Count();

        for (int right = 0; right < s.Length; right++)
        {
            char rChar = s[right];
            windowMap[rChar]++;

            if (targetMap[rChar] > 0 && windowMap[rChar] == targetMap[rChar])
            {
                count++;
            }

            while (count == required)
            {
                if (right - left + 1 < minLen)
                {
                    minLen = right - left + 1;
                    startIndex = left;
                }

                char lChar = s[left];

                if (targetMap[lChar] > 0 && windowMap[lChar] == targetMap[lChar])
                {
                    count--;
                }

                windowMap[lChar]--;
                left++;
            }
        }

        return minLen == int.MaxValue
            ? ReadOnlySpan<char>.Empty
            : s.AsSpan().Slice(startIndex, minLen);
    }
    catch (Exception ex)
    {
        LogHelper.Error($"GetMinWindow Error : {ex.Message}");
        return ReadOnlySpan<char>.Empty;
    }
}

중복 문자가 없는 가장 긴 부분 문자열 (Longest Substring Without Repeating)

  • 고유성 검사 및 패턴 인식
  • 보안 인증: 일회용 비밀번호(OTP)나 난수 생성기에서 문자가 겹치지 않고 연속해서 나올 수 있는 최대 성능 측정
  • 데이터 압축: 반복되지 않는 문자열 구간을 찾아 효율적인 압축 사전을 만들 때
  • 중복 발생 시 포인터 점프
public static int GetLongestUniqueLength(string s)
{
    if (string.IsNullOrWhiteSpace(s))
    {
        return 0;
    }

    try
    {
        int[] lastSeen = new int[128];
        Array.Fill(lastSeen, -1);
        int maxLength = 0, left = 0;

        for (int right = 0; right < s.Length; right++)
        {
            if (lastSeen[s[right]] >= left)
            {
                left = lastSeen[s[right]] + 1;
            }

            lastSeen[s[right]] = right;
            maxLength = Math.Max(maxLength, right - left + 1);
        }

        return maxLength;
    }
    catch (Exception ex)
    {
        LogHelper.Error($"GetLongestUniqueLength Error : {ex.Message}");
        return 0;
    }
}

애너그램 시작 위치 모두 찾기 (Find All Anagrams)

  • 패턴 매칭 및 암호 해석
  • 유전자 분석: DNA 염기 서열(ATGC)에서 순서는 다르지만 구성 성분이 같은 특정 유전자 마커를 찾을 때
  • 철자 검사기: 사용자가 입력한 단어의 철자를 조합해서 만들 수 있는 단어가 본문에 어디어디 숨어있는지 찾을 때
  • 대상(p.Length)으로 고정
public static List<int> FindAnagrams(string s, string p)
{
    List<int> indices = [];

    if (s.Length < p.Length)
    {
        return indices;
    }

    try
    {
        int[] pCount = new int[128];
        int[] sCount = new int[128];

        foreach (char c in p)
        {
            pCount[c]++;
        }

        for (int i = 0; i < s.Length; i++)
        {
            sCount[s[i]]++;

            if (i >= p.Length)
            {
                sCount[s[i - p.Length]]--;
            }

            if (i < p.Length - 1)
            {
                continue;
            }

            if (AreCountsEqual(pCount, sCount))
            {
                indices.Add(i - p.Length + 1);
            }
        }

        return indices;
    }
    catch (Exception ex)
    {
        LogHelper.Error($"FindAnagrams Error : {ex.Message}");
        return indices;
    }

    // Span을 이용한 빈도 배열 비교
    bool AreCountsEqual(int[] a, int[] b)
    {
        return a.AsSpan().SequenceEqual(b.AsSpan());
    }
}

최대 K개의 고유 문자를 포함하는 가장 긴 구간

  • 자원 제한 조건에서의 최대 효율 탐색
  • 스트리밍 최적화: “서로 다른 화질(Resolution) 종류를 최대 2개까지만 유지하면서 끊김 없이 보낼 수 있는 가장 긴 시간대” 계산.
  • 마케팅: 고객의 구매 이력에서 “최대 3종류의 카테고리 물건만 사면서 가장 길게 이어진 쇼핑 세션”을 분석하여 고객 성향 파악.
  • 윈도우 내부의 ‘종류(Count)’
public static int GetMaxKUniqueLength(string s, int k)
{
    if (string.IsNullOrWhiteSpace(s) || k == 0)
    {
        return 0;
    }

    int[] counts = new int[128];
    int left = 0, distinctCount = 0, maxLen = 0;

    for (int right = 0; right < s.Length; right++)
    {
        if (counts[s[right]] == 0)
        {
            distinctCount++;
        }

        counts[s[right]]++;

        while (distinctCount > k)
        {
            counts[s[left]]--;
            if (counts[s[left]] == 0) distinctCount--;
            left++;
        }

        maxLen = Math.Max(maxLen, right - left + 1);
    }

    return maxLen;
}
Rust, windows() 예제

Rust는 C#과 달리 표준 라이브러리의 slice 유니티에 windows()라는 메서드가 내장되어 있다. C#과 의 가장 큰 차이점은 Rust의 windows()는 데이터를 복사하지 않고 참조(Reference)만 넘겨준다는 점이다.

fn main() {
    let words = vec!["A", "B", "C", "D", "E"];

    // 크기가 3인 창(Window)을 만들어서 한 칸씩 이동
    for window in words.windows(3) {
        // window는 순서로 참조, ["A", "B", "C"], ["B", "C", "D"]
        println!("{:?}", window);
    }
}

인접한 요소 비교하기

fn main() {
    let prices = vec![100, 150, 120, 200, 180];

    // 크기가 2인 윈도우를 사용해 가격 변동 분석
    for w in prices.windows(2) {
        let diff = w[1] - w[0];
        let status = if diff > 0 { "상승" } else { "하락" };
        println!("{} -> {}: {} ({})", w[0], w[1], diff.abs(), status);
    }
}

애너그램 : C#과 비교해서 코드가 간결 함.

fn find_anagrams(s: &str, p: &str) -> Vec<usize> {
    let mut result = Vec::new();
    let p_len = p.len();
    let s_bytes = s.as_bytes();
    
    // 정렬된 target (비교용)
    let mut p_sorted = p.as_bytes().to_vec();
    p_sorted.sort();

    // windows(p_len)을 사용해 슬라이딩 윈도우 자동 생성
    for (i, window) in s_bytes.windows(p_len).enumerate() {
        let mut temp = window.to_vec();
        temp.sort();
        if temp == p_sorted {
            result.add(i);
        }
    }
    result
}

Rust의 내장 windows(n)는 윈도우 크기가 n으로 고정된 경우에만 사용할 수 있다. &str에서 바로 사용할 수 없고 바이트 단위나 유니코드 스칼라(chars()) 단위로 변환 후 사용해야 한다.

슬라이딩 윈도우 vs 투 포인터3

구분 슬라이딩 윈도우 투 포인터
윈도우 크기 고정됨 (K) 가변적임 (조건에 따라 변화)
주요 목적 연속된 구간의 합/평균 최적화 구간 내 특정 조건을 만족하는 쌍 찾기

Reference

  1. “윈도잉(windowing) 기법을 적용한 고성능 표 컴포넌트 개발기”, <NAVER D2>, 2025.07.24, https://d2.naver.com/helloworld/1450243, 2026.05.02.
  2. “슬라이딩윈도우 알고리즘(feat.Javascript)”, <endmoseung>, 2022.10.12, https://velog.io/@endmoseung/슬라이딩윈도우-알고리즘feat.Javascript, 2016.05.02.
  3. “단순화된 슬라이딩 윈도우 기법”, <Linkedin>, 2024.10.24, https://kr.linkedin.com/pulse/sliding-window-technique-simplified-c-rishabh-singh-1b3te, 2026.05.02.