0Pricing
Coding Interview Prep · 강의

투 포인터를 이용한 가변 윈도

조건을 만족할 때까지 늘리고 줄입니다

투 포인터를 이용한 가변 윈도은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

윈도가 늘었다 줄어들 때

일부 문제에서는 윈도의 길이를 고정하지 않습니다. 대신 합이 제한 아래에 있도록 하는 것처럼 조건을 만족하기 위해 윈도가 늘었다 줄어듭니다.

두 포인터, 하나의 윈도

윈도의 양 끝을 나타내는 두 인덱스 왼쪽과 오른쪽을 유지합니다. 오른쪽 포인터가 확장하는 동안 왼쪽 포인터는 뒤따르다가 필요할 때 윈도를 줄입니다.

left = 0
window = 0

오른쪽으로 확장하기

모든 요소를 따라 오른쪽으로 이동하며 각 요소를 윈도에 포함합니다. 합에 새 값을 더하는 것처럼 누적 상태를 갱신하십시오.

for right in range(n):
    window += a[right]

필요할 때 줄이기

윈도가 규칙을 위반하는 동안 왼쪽을 오른쪽으로 이동하고 해당 요소를 제거합니다. 이렇게 하면 되돌아가지 않고 조건을 복구할 수 있습니다.

    while window > limit:
        window -= a[left]
        left += 1

유효한 윈도 읽기

내부 반복이 끝나면 왼쪽부터 오른쪽까지의 윈도가 유효합니다. 윈도의 길이는 오른쪽에서 왼쪽을 뺀 값에 1을 더한 값이므로 바로 사용할 수 있습니다.

    length = right - left + 1

최선의 결과 기록하기

이 유효한 윈도로 답을 갱신합니다. 보통은 지금까지 본 윈도 중 가장 긴 윈도를 기록합니다. 아무것도 놓치지 않도록 매 반복마다 수행하십시오.

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

선형 시간인 이유

각 포인터는 앞으로만 이동하며 절대 뒤로 가지 않습니다. 왼쪽과 오른쪽 포인터의 이동 횟수를 합쳐도 최대 n번이므로 전체 탐색은 O(n)입니다.

단조성 요구 사항

윈도를 확장할수록 조건을 만족하기가 더 어려워지는 경우에 이 방법이 작동합니다. 이러한 단조성 덕분에 왼쪽 포인터를 되돌리지 않아도 됩니다.

최장과 최단 비교

가장 짧은 유효한 윈도를 구하려면 규칙이 여전히 성립하는 동안 줄이고, 줄이기 전에 기록하십시오. 포인터의 작동 방식은 동일합니다.

    while window >= target:
        best = min(best, right - left + 1)
        window -= a[left]
        left += 1

빈 윈도 주의하기

줄이는 과정에서 윈도가 비어 버릴 수 있다면 왼쪽이 오른쪽을 지나가는 상황을 방지하십시오. 또한 반환하기 전에 실제로 답을 찾았는지도 확인하십시오.

패턴 알아보기

요소에 대한 조건을 만족하는 연속된 구간 중 가장 길거나 짧은 구간을 요구하는 문제라면 가변 윈도를 떠올리십시오.

빠른 확인

크기가 n인 배열에서 두 포인터를 사용하는 가변 윈도를 실행합니다.

정리

요소를 포함하도록 오른쪽을 확장하고, 규칙이 깨지는 동안 왼쪽을 줄인 다음 각 유효한 윈도를 기록하십시오. 앞으로만 이동하는 포인터 덕분에 O(n)에 처리할 수 있습니다. ✅

자주 묻는 질문

“투 포인터를 이용한 가변 윈도” 강의는 무료인가요?

네 — “투 포인터를 이용한 가변 윈도” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“투 포인터를 이용한 가변 윈도”에서 뭘 배우나요?

조건을 만족할 때까지 늘리고 줄입니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

“투 포인터를 이용한 가변 윈도” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 고정 크기 윈도 합
  2. 투 포인터를 이용한 가변 윈도
  3. 반복 없는 가장 긴 부분 문자열
  4. 규칙을 만족하는 윈도 개수 세기
← Coding Interview Prep(으)로 돌아가기