18. [JAVA] 투 포인터, 슬라이딩 윈도우

알고리즘을 공부하다 투포인터, 슬라이딩 윈도우라는 것을 공부해야할 일이 생겨서 정리합니다

 

 

블로그는 해당 블로그를 참고 했습니다

 

https://bbangson.tistory.com/72

[Java]투 포인터 / 슬라이딩 윈도우 알고리즘

 

 

 

---

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

 

 

해당 알고리즘의 차이는 부분 배열 길이의 변화 여부 입니다

 

 

간단하게, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 윈도우 알고리즘은 부분 배열의 길이가 고정적 입니다

 

 

 

---

 

투 포인터

 

 

투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 이치시키는 알고리즘입니다

 

값이 연속 된다는 말은 정렬을 뜻하는 것일 수도 있으니 부분 배열로 작성하였습니다. 만약 문제에서 주어진 배열이 연속된 부분 배열을 통하여 문제를 해결하라는 것이 아니면 투 포인터 알고리즘은 사용이 불가능합니다(arr[0] 과 arr[3] 같이 연속되지 않는 경우) / 단, 정렬을 사용해서 사용할 수 있는 방법도 존재한다

 

 

투 포인터 알고리즘의 유형

 

1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우

2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우

 

투 포인터로 해결해야 하는 문제에서는 모든 배열의 값들을 필연적으로 탐색하여 특정 조건을 일치시키는 개수 혹은 최저, 최대 값 등을 찾는 문제이므로 대게 '조합', '백트래킹'을 떠올리기 쉽습니다. 틀린 키워드는 아니지만 '백 트래킹' 으로 시간을 줄여준다고 하더라도 출제자는 '투 포인터' 를 의도하고 출제하기 때문에 시간 초과를 벗어날 순 없을 것 입니다

 

 

예를 들어 배열이

 

1 2 3 4 5 6 

 

합이 10이 되는 구간을 구하는 문제일 때

 

투 포인터에서는 해당 배열의 arr[0] 번째에 L,R 위치를 둘 다 둡니다

 

Target 10

1 2 3 4 5 6

L  : 1

R : 1

1 2

먼저 R을 1 증가 시키고 L ~ R 까지의 합이 몇인 지를 확인합니다

 

SUM : 3

 

Target 보다 작기 때문에 R을 1 증가시켜 그 다음 배열을 선택합니다

L : 1

R : 3

1 2 3

SUM : 6

 

역시 Target 보다 값이 작기에 계속 반복합니다

 

L : 1

R : 4

1 2 3 4

SUM : 10

 

SUM이 10이 됬기에 횟수를 하나 늘려줍니다

 

그리고 난 뒤 다시 R을 1증가시킵ㄴ다

 

L : 1

R : 4

1 2 3 4 5

SUM : 15

 

Target보다 켜졌기 때문에 L 을 1 증가시킵니다

 

L : 2

R : 4

2 3 4 5

SUM : 14

 

이런 형태로 반복해서 배열의 끝까지 조사하는 방식을 투 포인터 방식이라고 합니다

 

보통 배열은 L > R 이 되면 즉 L이 R을 넘어서면 즉 배열이 끝나면 종료한다는 조건식으로 반복문을 종료 합니다

 

 

[문제]

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

 

---

 

 

슬라이딩 윈도우

 

 

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만 부분 배열의 길이가 고정적입니다. 투 포인터는 L,R 값을 증가시켜서 범위를 늘려갔지만 슬라이딩 윈도우는

고정 된 창문을 계속 증가시켜간다는 개념으로 생각하면 편합니다

 

 

만약 배열

 

1 2 3 4 5 6 7 8 9

 

가 있다고 합니다

 

창문의 크기는 3 이고 

 

해당 창문의 합을 구해서 Target과 같은지 확인합니다

 

이 때 주목할 점은

 

i = 1 : 6 / 1 + 2 + 3

i = 2 : 9 / 2 + 3 + 4

 

즉 배열의 첫번 째 값은 삭제 되지만

나머지 값들은 사용이 가능합니다

 

이 부분을 잘 활용해서 슬라이딩 윈도우를 사용하면 됩니다

 

 

https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰