투 포인터, 슬라이딩 윈도우

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

두 알골리즘은 1차원 배열을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여
O(N)으로 줄일 수 있다는 공통점이 있습니다.

 

이 두 알고리즘의 차이는

 

사용자가 찾고자 하는 부분 배열의 길이의 변화 여부 입니다.

• 투 포인터 (가변적 길이)
• 슬라이딩 윈도우 (고정적 길이)

---

투 포인터

길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘 입니다.

 

예시로 두 배열이 주어지고 그 배열의 공통 원소를 구한다고 할 때, 배열을 정렬 후

각 배열의 포인터를 하나씩 만들어 준 다음 같은 값이 나오면 두 포인터 다 + 1

만약 같은 값이 안나왔을 경우 더 작은 값의 포인터는 그대로 둔 뒤 더 작은 값의 배열의 포인터를 +1 해준다.

 

이런 식으로 사용하는 알고리즘을 투 포인터 방식이라고 한다.

 

위에 설명한 문제를 아래의 표로 예시를 들어보겠습니다.

 

1)

A	1 A[pi]	5	9	10
B	4 B[pj]	9	10	15

2)

A	1	5 A[pi]	9	10
B	4 B[pj]	9	10	15

3)

A	1	5 A[pi]	9	10
B	4	9 B[pj]	10	15

4)

A	1	5	9 A[pi]	10
B	4	9 B[pj]	10	15

5)

A	1	5	9	10 A[pi]
B	4	9	10 B[pj]	15

 

예제)

2022.01.21 - [인프런_자바_알고리즘_기초/Two pointers, Sliding window] - [인프런] 03-01 두 배열 합치기

2022.01.21 - [인프런_자바_알고리즘_기초/Two pointers, Sliding window] - [인프런] 03_02 공통원소 구하기

---

슬라이딩 윈도우

 

부분 배열의 길이(크기)가 고정적이기 때문에 창문을 왼쪽부터 오른쪽으로 밀어 오면서 일정한 배열의 값들을 구할 때 사용합니다.

 

투 포인터와 다르게 변수가 2개 일 필요가 없으며, 각 배열의 끝을 알 수 있습니다.

 

아래와 같은 그림이 슬라이딩 윈도우 예시입니다.

Current(현재 배열) -> Next(다음 배열) 갈때 창문틀이 움직이면서 포함되지 않는 값들은 빼버리며 포함되는 값들을 더해줍니다.

슬라이딩 윈도우

예제)

2022.01.21 - [인프런_자바_알고리즘_기초/Two pointers, Sliding window] - [인프런] 03_03 최대 매출