on my way
Python 코딩테스트 06: 투포인터와 슬라이딩 윈도우 본문
투포인터와 슬라이딩 윈도우 알고리즘: 개념, 특징, 활용
코딩 테스트에서 배열이나 리스트와 같은 연속된 데이터 구조를 다룰 때, 투포인터(Two Pointer)와 슬라이딩 윈도우(Sliding Window)는 매우 유용한 알고리즘 기법입니다.
이번 포스팅에서는 이 두 가지 기법을 자세히 설명하고, 예제 문제를 통해 어떻게 활용할 수 있는지 알아보겠습니다.
투포인터 (Two Pointer)
개념 설명
투포인터는 두 개의 포인터를 사용하여 배열이나 리스트의 특정 구간을 탐색하는 기법입니다.
이 기법은 주로 정렬된 배열에서 특정 조건을 만족하는 부분 배열이나 값을 찾는 데 사용됩니다.
두 포인터는 일반적으로 시작점과 끝점을 나타내며, 조건에 따라 포인터를 이동시키면서 문제를 해결합니다.
특징
- 효율성: O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
- 활용도: 정렬된 배열이나 리스트에서 특정 조건을 만족하는 부분 배열을 찾는 문제에 적합합니다.
과정 설명
- 초기화: 배열의 시작(left)과 끝(right)을 가리키는 두 포인터를 설정합니다.
- 조건 확인: 두 포인터가 가리키는 값의 합을 계산합니다.
- 포인터 이동:
- 합이 목표값(target)과 같으면 인덱스 쌍을 반환합니다.
- 합이 목표값보다 작으면 left 포인터를 오른쪽으로 이동시킵니다.
- 합이 목표값보다 크면 right 포인터를 왼쪽으로 이동시킵니다.
- 반복: 포인터가 교차할 때까지 반복합니다.
예시 문제: 두 수의 합 (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) 시간 복잡도로 문제를 해결할 수 있습니다.
- 활용도: 부분 배열이나 구간에서 최대/최소값, 특정 조건을 만족하는 문제에 적합합니다.
과정 설명
- 초기화: 윈도우의 크기와 위치를 설정합니다.
- 윈도우 내 값 계산: 현재 윈도우 내의 값을 계산합니다.
- 최대/최소값 갱신: 현재 값이 최대/최소값 조건을 만족하면 값을 갱신합니다.
- 윈도우 이동: 윈도우를 오른쪽으로 한 칸씩 이동시키면서 맨 왼쪽 값을 빼줍니다.
- 반복: 배열 끝까지 순회하며 조건을 만족하는 값을 찾습니다.
예시 문제: 최대 부분합 (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
이처럼 투포인터와 슬라이딩 윈도우는 배열의 특정 구간에서 조건을 만족하는 값을 찾는 데 매우 유용한 기법입니다.
각각의 알고리즘을 잘 이해하고 활용하면 다양한 문제를 효율적으로 해결할 수 있습니다.
'algorithm > CodingTest' 카테고리의 다른 글
Python 코딩테스트 08: 다익스트라 알고리즘 (0) | 2024.07.29 |
---|---|
Python 코딩테스트 07: 백트래킹 (0) | 2024.07.29 |
Python 코딩테스트 05: 이진 탐색 (0) | 2024.07.29 |
Python 코딩테스트 04: BFS (0) | 2024.07.29 |
Python 코딩테스트 03: DFS (0) | 2024.07.29 |