Python 코딩테스트 06: 투포인터와 슬라이딩 윈도우

투포인터와 슬라이딩 윈도우 알고리즘: 개념, 특징, 활용

코딩 테스트에서 배열이나 리스트와 같은 연속된 데이터 구조를 다룰 때, 투포인터(Two Pointer)와 슬라이딩 윈도우(Sliding Window)는 매우 유용한 알고리즘 기법입니다.

이번 포스팅에서는 이 두 가지 기법을 자세히 설명하고, 예제 문제를 통해 어떻게 활용할 수 있는지 알아보겠습니다.

 

투포인터 (Two Pointer)

개념 설명

투포인터는 두 개의 포인터를 사용하여 배열이나 리스트의 특정 구간을 탐색하는 기법입니다.

이 기법은 주로 정렬된 배열에서 특정 조건을 만족하는 부분 배열이나 값을 찾는 데 사용됩니다.

두 포인터는 일반적으로 시작점과 끝점을 나타내며, 조건에 따라 포인터를 이동시키면서 문제를 해결합니다.

 

특징

• 효율성: O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
• 활용도: 정렬된 배열이나 리스트에서 특정 조건을 만족하는 부분 배열을 찾는 문제에 적합합니다.

과정 설명

1. 초기화: 배열의 시작(left)과 끝(right)을 가리키는 두 포인터를 설정합니다.
2. 조건 확인: 두 포인터가 가리키는 값의 합을 계산합니다.
3. 포인터 이동:
   • 합이 목표값(target)과 같으면 인덱스 쌍을 반환합니다.
   • 합이 목표값보다 작으면 left 포인터를 오른쪽으로 이동시킵니다.
   • 합이 목표값보다 크면 right 포인터를 왼쪽으로 이동시킵니다.
4. 반복: 포인터가 교차할 때까지 반복합니다.

 

예시 문제: 두 수의 합 (Two Sum)

문제 설명

정렬된 배열에서 두 수의 합이 특정 값(target)이 되는 인덱스 쌍을 찾아라.

구현

def two_sum(nums, target):
    left, right = 0, len(nums) - 1

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

    return None

# 예시 실행
nums = [1, 2, 3, 4, 6]
target = 6
print(two_sum(nums, target))  # 출력: (1, 3)

 

 

슬라이딩 윈도우 (Sliding Window)

개념 설명

슬라이딩 윈도우는 일정한 크기의 윈도우를 배열이나 리스트 위에서 이동시키며 문제를 해결하는 기법입니다.

이 기법은 주로 연속된 부분 배열에서 최대/최소값, 특정 조건을 만족하는 구간 등을 찾는 데 사용됩니다.

윈도우를 오른쪽으로 한 칸씩 이동시키며 윈도우 내의 값을 업데이트합니다.

특징

• 효율성: O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
• 활용도: 부분 배열이나 구간에서 최대/최소값, 특정 조건을 만족하는 문제에 적합합니다.

과정 설명

1. 초기화: 윈도우의 크기와 위치를 설정합니다.
2. 윈도우 내 값 계산: 현재 윈도우 내의 값을 계산합니다.
3. 최대/최소값 갱신: 현재 값이 최대/최소값 조건을 만족하면 값을 갱신합니다.
4. 윈도우 이동: 윈도우를 오른쪽으로 한 칸씩 이동시키면서 맨 왼쪽 값을 빼줍니다.
5. 반복: 배열 끝까지 순회하며 조건을 만족하는 값을 찾습니다.

 

예시 문제: 최대 부분합 (Maximum Subarray Sum)

문제 설명

연속된 부분 배열의 합 중 최대값을 구하라.

구현

def max_subarray_sum(nums, k):
    max_sum = float('-inf')
    current_sum = 0

    for i in range(len(nums)):
        current_sum += nums[i]
        if i >= k - 1:
            max_sum = max(max_sum, current_sum)
            current_sum -= nums[i - (k - 1)]

    return max_sum

# 예시 실행
nums = [2, 1, 5, 1, 3, 2]
k = 3
print(max_subarray_sum(nums, k))  # 출력: 9 (부분 배열 [5, 1, 3])

 

결론

투포인터와 슬라이딩 윈도우는 배열이나 리스트에서 특정 조건을 만족하는 부분 배열이나 값을 찾을 때 매우 유용한 기법입니다.

두 기법 모두 시간 복잡도를 효율적으로 유지하면서 문제를 해결할 수 있으며, 다양한 문제에 적용할 수 있습니다. 

---

그림 예시

투포인터

예시: 두 수의 합 (target = 6)

배열: [1, 2, 3, 4, 6]

초기 상태:
left -> 1, right -> 6

첫 번째 반복:
left -> 1, right -> 6, current_sum = 1 + 6 = 7 (target보다 큼)
right를 왼쪽으로 이동: left -> 1, right -> 4

두 번째 반복:
left -> 1, right -> 4, current_sum = 1 + 4 = 5 (target보다 작음)
left를 오른쪽으로 이동: left -> 2, right -> 4

세 번째 반복:
left -> 2, right -> 4, current_sum = 2 + 4 = 6 (target과 같음)
결과: (left, right) = (1, 3)

 

슬라이딩 윈도우

예시: 최대 부분합 (k = 3)

배열: [2, 1, 5, 1, 3, 2]

초기 상태:
current_sum = 0, max_sum = -inf

첫 번째 반복 (i = 0):
current_sum += 2, current_sum = 2

두 번째 반복 (i = 1):
current_sum += 1, current_sum = 3

세 번째 반복 (i = 2):
current_sum += 5, current_sum = 8
i >= k - 1이므로:
max_sum = max(max_sum, current_sum) = 8
current_sum -= 2, current_sum = 6

네 번째 반복 (i = 3):
current_sum += 1, current_sum = 7
i >= k - 1이므로:
max_sum = max(max_sum, current_sum) = 8
current_sum -= 1, current_sum = 6

다섯 번째 반복 (i = 4):
current_sum += 3, current_sum = 9
i >= k - 1이므로:
max_sum = max(max_sum, current_sum) = 9
current_sum -= 5, current_sum = 4

여섯 번째 반복 (i = 5):
current_sum += 2, current_sum = 6
i >= k - 1이므로:
max_sum = max(max_sum, current_sum) = 9
current_sum -= 1, current_sum = 5

결과: max_sum = 9

 

이처럼 투포인터와 슬라이딩 윈도우는 배열의 특정 구간에서 조건을 만족하는 값을 찾는 데 매우 유용한 기법입니다.

각각의 알고리즘을 잘 이해하고 활용하면 다양한 문제를 효율적으로 해결할 수 있습니다.