투 포인터(Two-Pointers) & 슬라이딩 윈도우(Sliding Windows) 알고리즘

*️⃣  투 포인터 정의

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘
• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리

*️⃣  투 포인터 동작 방식

• left(l), right(r) 이나 start(s), end(d) 으로 포인트의 이름을 붙임
• 처음에 start=end=0 이고, 조건은 항상 두 포인터들의 관계는 start <= end 이다.
• 2개의 포인터는 현재 부분 배열의 시작(start)과 끝(end)을 가르킨다.

*️⃣  투 포인터 알고리즘 문제의 유형

• 포인터 2개가 같은 방향으로 진행하는것
• 포인터 2개가 양끝에서 시작하여 반대로 진행하는 것
• 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

 

---

 

*️⃣  슬라이딩 윈도우 정의

• 고정된 크기의 윈도우를 사용하여 데이터를 처리하는 알고리즘
• 투 포인터 패턴과 유사하다
• 특정한 조건에 따라 윈도우가 커지거나 닫히거나, 새로 생성될수도 있다

*️⃣  슬라이딩 윈도우 동작 방식

 

• 윈도우 설정: 시작점에서 고정된 크기(혹은 초기 크기)의 윈도우를 설정
• 윈도우 이동: 한 요소씩 윈도우를 한쪽 방향으로 이동하면서 새로운 요소를 윈도우에 추가하고, 윈도우의 앞쪽에 있는 요소를 제거한다
• 연산 적용: 각 윈도우가 형성될 때마다 원하는 연산을 수행(예: 합계 계산, 최대/최소 값 찾기 등)

 

 

*️⃣  슬라이딩 윈도우 알고리즘 문제의 유형

• 배열이나 문자열같은 선형 구조에서 요소의 일정 범위값을 비교
• 배열이나 리스트와 같은 데이터 구조에서 연속된 부분 배열의 합이나 최대값 등을 계산

 

---

 

 

*️⃣ 투 포인터와 슬라이딩 윈도우

✦ 차이점

• 투 포인터 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변함
• 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있음

 

✦ 공통점

선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.

 

 

 

참고

 

[Algorithm] Two-Pointers Algorithm (투 포인터 알고리즘)

슬라이딩 윈도우 알고리즘: 효율적인 문제 해결 방법