투 포인터
- 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제풀이 전략
- 일반적으로 배열이 정렬되어 있을 때 유용하며, 2개의 포인터가 좌우로 자유롭게 움직이면서 문제를 풀이한다.
- 대표적인 문제로 배열의 구간합과 관련된 문제나 수열의 연속합과 같은 문제에서 사용한다.
예제
- 배열에서 구간합이 m 이상인 구간의 최소 길이 찾기
n, m = map(int, input().split())
a = list(map(int, input().split()))
left, right = 0, 0
ans = n + 1
sum = a[0]
while left <= right and right < n:
# 합이 m보다 작은 경우
# 오른쪽 포인터를 한 칸 이동하고 sum에 더한다.
if sum < m:
right += 1
if right < n:
sum += a[right]
# 합이 m보다 큰 경우
# sum에서 빼고 왼 쪽 포인터를 한 칸 이동한다.
elif sum >= m:
ans = min(ans, right - left + 1)
sum -= a[left]
left += 1
if left > right and left < n:
right = left
sum = a[left]
# 합이 m이 되는 경우
# 오른쪽 포인터를 한 칸 이동하고 sum에 더한다.
else:
ans = min(ans, right - left + 1)
right += 1
if right < n:
sum += a[right]
if ans == n + 1:
print(0)
else:
print(ans)
슬라이딩 윈도우
- 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘
- 투 포인터와 비슷하지만 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 따로 구분한다.
네트워크
- 슬라이딩 윈도우는 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하는 네트워크 용어이기도 하다.
- 네트워크에서 패킷을 전송할 때 고정 사이즈의 윈도우가 옆으로 이동하면서 그 다음 패킷들을 전송하는 방식을 말한다.
'Python > Algorithm' 카테고리의 다른 글
빅오 표기법 (Big-O) (0) | 2022.06.08 |
---|---|
다이나믹 프로그래밍 (DP) (0) | 2022.03.04 |
그래프 관련 알고리즘 (0) | 2022.03.01 |
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
트라이 (0) | 2022.02.27 |