C++ 코딩테스트 강좌, 슬라이딩 윈도우

C++ 코딩테스트 강좌: 슬라이딩 윈도우

여기에 오신 것을 환영합니다! 이번 강좌에서는 인기 있는 알고리즘 기법인 슬라이딩 윈도우(Sliding Window)에 대해 알아보겠습니다.
슬라이딩 윈도우는 배열이나 문자열과 같은 1차원 데이터 구조에서 부분 수열 또는 부분 배열을 처리할 때 자주 사용됩니다.
복잡도를 효율적으로 줄이고 문제를 해결하는 데 큰 도움을 줄 수 있습니다.
이 글에서는 슬라이딩 윈도우의 개념을 설명하고, 이를 활용한 구체적인 알고리즘 문제를 해결해 보겠습니다.

슬라이딩 윈도우란 무엇인가?

슬라이딩 윈도우 기법은 배열이나 문자열에서 일정한 크기의 윈도우를 설정한 후, 그 윈도우를 왼쪽에서 오른쪽으로 이동시키며 탐색하는 방법입니다.
이 기법은 배열 내의 요소를 효율적으로 탐색하거나 계산할 수 있어, 일반적으로 시간 복잡도를 줄이는 데 큰 장점이 있습니다.
슬라이딩 윈도우는 크게 두 가지 유형으로 나눌 수 있습니다:

고정 크기 윈도우: 윈도우의 크기가 고정된 경우. 예를 들어, K개의 연속된 요소의 합을 구하는 문제.
가변 크기 윈도우: 윈도우의 크기가 가변적인 경우. 예를 들어, 특정 조건을 만족하는 가장 짧은 부분 배열을 찾는 문제.

문제 설명: 최장 부분 문자열

이번에 해결할 문제는 다음과 같습니다:
주어진 문자열에서 중복 없는 가장 긴 부분 문자열의 길이를 찾는 것입니다.
예를 들어, 입력 문자열이 "abcabcbb"일 때, 출력은 3입니다. (최장 부분 문자열은 "abc"이기 때문입니다.)

문제 해결을 위한 접근 방법

슬라이딩 윈도우는 이 문제를 효과적으로 해결하는 데 적합한 전략입니다.
여기에서는 두 가지 포인터를 사용하여 현재 윈도우 내에 중복된 문자가 있는지를 확인하고, 윈도우의 좌우 크기를 조정합니다.
이 접근법에서 사용할 주요 변수는 다음과 같습니다:

left: 윈도우의 시작 인덱스
right: 윈도우의 끝 인덱스
max_length: 가장 긴 부분 문자열의 길이
char_set: 현재 윈도우 내의 문자들을 저장할 집합

알고리즘 단계

왼쪽 포인터 left와 오른쪽 포인터 right를 0으로 초기화합니다.
문자 집합 char_set을 초기화합니다.
오른쪽 포인터 right를 문자열의 마지막까지 이동하며 다음을 수행합니다:

만약 char_set에 s[right]가 이미 있을 경우, 중복이 발생했으므로 왼쪽 포인터 left를 증가시켜 중복을 제거합니다.
중복이 없으면 char_set에 s[right]를 추가합니다.
현재 윈도우의 길이 right - left + 1을 계산하여 최대 길이 max_length와 비교 후 업데이트합니다.
오른쪽 포인터 right를 증가시킵니다.

문자열을 끝까지 탐색한 후 max_length를 반환합니다.

C++ 코드 구현


#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set char_set; // 현재 윈도우 내의 문자 집합
    int left = 0, max_length = 0;

    for (int right = 0; right < s.length(); ++right) {
        // 중복된 문자가 발생할 때까지 왼쪽 포인터를 이동
        while (char_set.find(s[right]) != char_set.end()) {
            char_set.erase(s[left]);
            ++left;
        }
        // 현재 문자 추가
        char_set.insert(s[right]);
        // 최대 길이 갱신
        max_length = max(max_length, right - left + 1);
    }
    return max_length;
}

int main() {
    string s = "abcabcbb";
    cout << "최장 부분 문자열의 길이: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

코드 설명

위 코드에서는 unordered_set를 사용하여 현재 윈도우의 문자를 저장하며, 중복된 문자가 발생할 경우
왼쪽 포인터를 이동하여 중복을 제거합니다. 각 문자를 처리할 때마다 최대 길이를 업데이트합니다.
이 알고리즘은 문자열의 길이를 n이라고 할 때, 시간 복잡도는 O(n)입니다.
두 개의 포인터가 문자열을 한 번만 통과하기 때문입니다.
공간 복잡도는 O(min(n, m)), 여기서 n은 문자열의 길이, m은 문자 집합의 크기입니다.

결론

이번 포스트에서는 슬라이딩 윈도우 기법을 사용하여 최장 부분 문자열 문제를 해결하는 과정을 살펴보았습니다.
슬라이딩 윈도우는 많은 문제를 효율적으로 해결할 수 있는 강력한 도구이며, 이를 통해 알고리즘 문제를 풀 때
더욱 효과적으로 접근할 수 있습니다.
다음 번에도 더 많은 알고리즘 기법과 문제를 다루는 시간을 가지도록 하겠습니다.
독자 여러분의 코딩테스트 준비에 도움이 되었기를 바랍니다!