HHyo814
발행일

[ZBF] 6월 5일차 코딩 테스트

코딩테스트

[ZBF] 6월 5일차 코딩 테스트

이 글은 네이버 블로그에 2024년 6월 7일에 올렸던 것을 그대로 옮겨온 것입니다.

슬라이딩 윈도우(Sliding Window) 기법은 배열이나 리스트와 같은 연속된 데이터 구조를 효율적으로 처리하기 위해 사용되는 알고리즘 기법입니다. 이 기법은 고정된 크기의 윈도우를 배열의 시작부터 끝까지 이동시키면서 필요한 계산을 수행합니다. 슬라이딩 윈도우는 다양한 문제에서 유용하게 활용될 수 있습니다.

슬라이딩 윈도우 기법의 개념

슬라이딩 윈도우는 두 개의 포인터(또는 인덱스)를 사용하여 윈도우를 정의합니다. 이 윈도우는 배열 또는 리스트 내에서 특정 크기를 가지며, 이 크기를 유지하면서 배열을 탐색합니다. 윈도우의 시작과 끝을 나타내는 두 포인터는 필요에 따라 이동하면서 윈도우를 슬라이딩(이동)합니다.

슬라이딩 윈도우 기법의 일반적인 사용 사례

1. 부분 배열의 합 구하기:

  • 주어진 배열에서 고정된 크기의 부분 배열의 합을 구할 때 사용됩니다.
  • 예: 크기 k인 모든 부분 배열의 합을 구하는 문제.

2. 최대/최소값 찾기:

  • 부분 배열 내에서 최대값 또는 최소값을 찾을 때 사용됩니다.
  • 예: 주어진 배열에서 크기 k인 모든 부분 배열의 최대값을 구하는 문제.

3. 문자열 처리:

  • 문자열 내에서 고정된 길이의 부분 문자열을 처리할 때 사용됩니다.
  • 예: 특정 조건을 만족하는 가장 긴 부분 문자열을 찾는 문제.

슬라이딩 윈도우 기법의 장점

  • 효율성: 슬라이딩 윈도우 기법은 중복 계산을 피하고, 모든 요소를 한 번씩만 처리하므로 시간 복잡도가 O(n)으로 매우 효율적입니다.
  • 단순성: 구현이 비교적 간단하며, 복잡한 문제를 간단하게 해결할 수 있습니다.

예제 코드

예제 1: 부분 배열의 합 구하기

다음은 크기 k인 모든 부분 배열의 합을 구하는 슬라이딩 윈도우 기법의 예제입니다.

function longestSubstring(s, k) {
    let n = s.length;
    let left = 0, right = 0;
    let maxLength = 0;
    let charCount = {};

    while (right < n) {
        charCount[s[right]] = (charCount[s[right]] || 0) + 1;

        while (Object.keys(charCount).length > k) {
            charCount[s[left]] -= 1;
            if (charCount[s[left]] === 0) {
                delete charCount[s[left]];
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }

    return maxLength;
}

// 테스트
let s = "eceba";
let k = 2;
console.log(longestSubstring(s, k)); // 출력: 3 ("ece")

슬라이딩 윈도우 기법의 적용 방법

  1. 윈도우 크기 결정: 문제에서 요구하는 조건에 따라 윈도우의 크기를 결정합니다.
  2. 윈도우 이동: 배열이나 문자열의 시작부터 끝까지 윈도우를 이동시킵니다.
  3. 조건 검사 및 갱신: 윈도우 내의 요소들을 검사하여 문제에서 요구하는 조건을 만족하는지 확인하고, 필요한 값을 갱신합니다.
  4. 결과 반환: 최종적으로 구한 값을 반환합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/131127

  • 코딩테스트 연습 - 할인 행사 — XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다. 예를 들어, 정현이가 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며, XYZ 마트에서 14일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나...

https://school.programmers.co.kr/learn/courses/30/lessons/64062

  • 코딩테스트 연습 - 징검다리 건너기 — [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리 가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에...
← 글 목록으로