Sliding Window, Two Pointers

Sliding Window(슬라이딩 윈도우) 알고리즘은 배열이나 리스트의 일정 범위의 요소를 '창'으로 생각하고, 이 창을 배열이나 리스트의 끝까지 이동시키면서 주어진 문제의 조건에 맞는 최적의 해를 찾는 방식이다. 이 알고리즘은 특히 연속된 데이터에 대해 최대합, 최소값, 평균 등을 효율적으로 계산할 때 유용하다.

 

슬라이딩 윈도우를 구현할 때에는 윈도우의 크기를 결정하고, 배열의 시작 부분에 윈도우를 위치시킨 뒤, 윈도우를 한 칸씩 오른쪽으로 이동시키면서, 윈도우에 포함된 요소들을 이용해 문제를 해결한다.

 

각 이동마다 최적의 해를 찾거나 조건을 만족하는지 검사하고, 필요한 경우 해를 갱신해야 한다.

 

윈도우를 한 번만 순회하므로, 알고리즘의 시간 복잡도는 대체로 O(n)이다. 데이터 스트림과 같이 동적으로 변하는 연속된 데이터에 대해서도 실시간으로 최적의 해를 찾는 데 적합하다.

def max_sum_subarray_of_size_k(arr, k):
    max_sum = 0
    window_sum = sum(arr[:k])  # 초기 윈도우의 합을 계산
    max_sum = window_sum

    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i + k]  # 윈도우를 한 칸씩 오른쪽으로 이동
        max_sum = max(max_sum, window_sum)  # 최대 합 갱신

    return max_sum

arr = [1, 15, 1, 2, 6, 12, 5, 7]
k = 4
print(max_sum_subarray_of_size_k(arr, k))

#출력
#30

 

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 이용하여 문제를 해결하는 방법이다. 주로 정렬된 배열에서 두 요소의 합, 최대값 또는 최소값을 찾거나, 특정 조건을 만족하는 부분 배열을 탐색하는 데 유용하다. 대부분의 경우 선형 시간 안에 해를 찾는다.

 

배열의 시작점에 두 포인터를 위치시킨다. 보통 한 포인터는 배열의 시작점에, 다른 하나는 끝점에 위치시킨다. 주어진 조건에 따라 포인터들을 적절히 이동시키면서 문제의 해를 찾는다.

• 합이 특정 값보다 작을 때는 시작 포인터를 오른쪽으로 이동시켜 합을 증가시킨다.
• 합이 특정 값보다 클 때는 끝 포인터를 왼쪽으로 이동시켜 합을 감소시킨다.

중첩 반복문을 사용하지 않아 시간 복잡도가 O(n^2)에서 O(n)으로 줄어든다.

def two_sum(arr, target):
    left, right = 0, len(arr) - 1  # 초기화

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return None

arr = [1, 2, 3, 4, 5]
target = 9
print(two_sum(arr, target))

# 출력
# (3,4)