당신과 이야기하세요 시리즈 #2-파이썬 튜토리얼-php.cn

소개

오늘은 다양한 알고리즘 문제를 해결하는 데 사용되는 개념에 대한 개요를 시작하겠습니다. 특정 개념을 이해하면 어떤 각도에서 잠재적인 솔루션을 생각해야 할지 직관할 수 있습니다.

다양하지만 개념이 너무 많지는 않습니다. 오늘은 슬라이딩 윈도우 컨셉에 여러분의 관심을 투자해보겠습니다.

슬라이딩 윈도우

Talk with You Series #2

미닫이창의 개념은 언뜻 보기보다 좀 더 복잡합니다. 실제 사례를 통해 이를 보여드리겠습니다. 지금은 이동해야 하는 창이 있다는 개념적 아이디어를 염두에 두세요. 바로 예시부터 시작해보겠습니다.

정수 배열과 사전 정의된 하위 배열 크기가 있다고 가정합니다. 다른 값 중에서 값의 합이 최대가 되는 하위 배열(창이라고도 함)을 찾으라는 요청을 받습니다.

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

로그인 후 복사

아주 간단해 보입니다.
(1) 크기 2의 슬라이딩 창
(2) 하위 배열 2개
(3) 각각의 합을 세어보세요
(4) 그들 사이의 최대값을 찾으세요

실천해 보겠습니다.

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum

로그인 후 복사

글쎄, 우리는 슬라이딩 윈도우 개념을 효율적으로 사용한 것 같습니다. 실제로는 정확하지 않습니다. 솔루션의 시간 복잡도를 이해함으로써 이에 대한 "증거"를 얻을 수 있습니다.

복잡도는 O(l)*O(w)입니다. 여기서 l은 배열의 창 수이고 w는 창의 요소 수입니다. 즉, l개 창을 순회해야 하며 각 l번째 창에 대해 w개 요소의 합을 계산해야 합니다.

여기서 의문스러운 점은 무엇인가요? 질문에 답하기 위한 반복을 개념적으로 묘사해 보겠습니다.

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|

로그인 후 복사

답은 배열을 슬라이딩하더라도 각 반복마다 이전 반복에서 이미 계산된 k-1개 요소를 "다시 계산"해야 한다는 것입니다.

기본적으로 이 통찰력은 우리에게 다음과 같은 질문을 하도록 제안합니다.

"이전 단계의 계산을 활용할 수 있는 방법이 있나요?"

답은 '그렇다'입니다. 창 요소 뒤에 첫 번째 요소와 다음 요소를 더하고 빼면 창 요소의 합을 얻을 수 있습니다. 이 아이디어를 코드에 넣어보겠습니다.

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

로그인 후 복사

여기서 길이와 크기의 하위 배열을 구성한 시점에서 창 합계에서 첫 번째 요소를 빼기 시작하여 이전 단계의 계산을 재사용할 수 있다는 것을 알 수 있습니다.

이제 우리는 슬라이딩 윈도우의 개념을 효율적으로 활용했다고 말할 수 있지만 시간 복잡도를 확인하는 증거는 O(l*w)에서 O(l)로 감소했습니다. 여기서 l은 우리가 사용할 윈도우의 양입니다. 슬라이드.

제가 강조하고 싶은 주요 아이디어인 슬라이딩 윈도우 개념은 단순히 반복 가능한 항목을 특정 크기의 창으로 분할하는 것이 아닙니다.

몇 가지 문제를 제시하겠습니다. 여기서는 슬라이딩 창 개념과 관련된 문제를 감지하는 방법과 창 자체로 수행할 수 있는 작업이 정확히 무엇인지 알아볼 것입니다.

문제 개요

여기서는 개념에 대해서만 이야기하고 있으므로 "창 안에서 숫자를 세는 방법"은 건너뛰겠습니다.

첫 번째 문제

주어진 배열에서 크기가 K인 모든 인접한 하위 배열의 평균을 구합니다.

미닫이창 ? - 연속 하위 배열은 첫 번째 키워드입니다. 즉, 연속 하위 배열을 나타내는 창을 처리해야 한다는 의미입니다.
미닫이창의 크기를 아시나요? - 네, K, 창문의 크기를 알아냈는데, 그 길이는 K의 길이여야 합니다.
슬라이딩 윈도우 내에서는 구체적으로 무엇을 관리/점검해야 하나요? - 평균을 구해 보세요...

좋습니다. 이제 접근 방식을 다음과 같이 정의할 수 있습니다. 크기가 K인 창을 사용하여 입력 배열을 반복합니다. 각 반복에서 창의 평균을 계산합니다...

두 번째 문제

양수 배열과 양수 K가 주어지면 크기 K인 인접한 하위 배열의 최대 합을 구합니다.

미닫이창 ? - 다시 연속 하위 배열, 첫 번째 키워드는 연속 하위 배열을 나타내는 창을 처리해야 함을 의미합니다.
미닫이창의 크기를 아시나요? - 네, K, 창문의 크기를 알아냈는데, 그 길이는 K의 길이여야 합니다.
슬라이딩 윈도우 내에서는 구체적으로 무엇을 관리/점검해야 하나요? - .. 합계 ...

이제: 크기가 K인 창으로 입력 배열을 탐색합니다. 각 반복에서 창의 합을 계산합니다...

3번 문제

양수 배열과 양수 S가 주어졌을 때 합이 S보다 크거나 같은 가장 작은 연속 하위 배열의 길이를 찾습니다.

미닫이창 ? - 다시 연속 하위 배열, 첫 번째 키워드는 연속 하위 배열을 나타내는 창을 처리해야 함을 의미합니다.
미닫이창의 크기를 아시나요? - 아니, 사실은 우리가 알아내야 해.
슬라이딩 윈도우 내에서는 구체적으로 무엇을 관리/점검해야 하나요? - ... 합계는 >= S ...

이제 접근 방식을 다음과 같이 정의할 수 있습니다. "먼저 입력 배열을 반복하고 조건을 충족하는 첫 번째 창을 구성합니다(합계는 >=에서 S까지). 완료되면 창을 이동하고 창을 관리합니다. 시작과 끝..."

문제 4

주어진 문자열에서 K개 이하의 고유 문자를 포함하는 가장 긴 부분 문자열의 길이를 찾습니다.

미닫이창 ? - 가장 긴 하위 문자열, 첫 번째 키워드는 하위 문자열을 나타내는 창을 처리해야 함을 의미합니다.
미닫이창의 크기를 아시나요? - 아니, 우리가 알아내야 해.
슬라이딩 윈도우 내에서는 구체적으로 무엇을 관리/점검해야 하나요? - ... 고유한 문자의 양 ...

여기서의 접근 방식은 좀 더 복잡하므로 여기서는 생략하겠습니다.

5번 문제

각 정수가 과일나무를 나타내는 정수 배열이 주어지면 두 개의 바구니가 주어지며, 목표는 각 바구니에 최대 개수의 과일을 넣는 것입니다. 유일한 제한은 각 바구니에 한 종류의 과일만 담을 수 있다는 것입니다.
어떤 트리로든 시작할 수 있지만 일단 시작한 후에는 트리를 건너뛸 수 없습니다. 선택할 수 없을 때까지 각 나무에서 하나의 과일을 따게 됩니다. 즉, 세 번째 과일 유형에서 따야 할 때 중지합니다.
두 바구니에 담긴 최대 과일 수를 반환하는 함수를 작성하세요.

그렇게 명확하지는 않은 것 같습니다. 먼저 조건을 단순화해 보겠습니다.