[ 알고리즘 유형] 투 포인터 알고리즘 (Two Pointer Algorithm)

투포인터 

- 배열이나 리스트에서 '두개의 포인터를' 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘

- 정렬되어 있는, 배열 또는 리스트의 경우에 사용함

 

투 포인터 방법

1단계 : 배열 또는 리스트의 시작 위치에서 첫 번째 포인터와 두번째 포인터 설정

2단계 : 두 포인터 사이의 구간을 조사하고 조건 확립

3단계 : 조건 만족할 경우, 종료

4단계 : 조건이 만족하지 않을 경우, 첫번째 또는 두번째 포인터로 이동

5단계 : 2단계로 돌아가 재수행

 

투 포인터 시간 복잡도

- 투 포인터 알고리즘은 선형시간 복잡도를 가지며, 효율적이다.

- 한번의 반복으로 모든 요소를 처리

- 빅오 표기법으로  O(N), 배열 또는 리스트의 크기에 비례하여 수행시간 증가

 

투 포인터의 종류

1) 고정 길이 슬라이딩 윈도우

  - 고정된 길이의 윈도우를 사용하여 배열이나 리스트 탐색

  - 아래 이미지는 위도우 사이즈를 3으로 고정한 후 움직이는 모습

  - 배열의 합 또는 평균을 계산하는 문제에 사용됨

2) 가변 길이 슬라이딩 윈도우

  - 가변 길이의 윈도우를 사용하여 배열이나 리스트를 탐색

  - 최소 길이 부분 배열이나, 최대 길이 부분 배열을 찾는 문제에 사용됨

 

 

3) 두 포인터의 합과 차

  - 배열이나 리스트에서 두개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결

  - 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 문제에 사용됨

 

 

 

 

 

투 포인터 단계별 백준문제

https://www.acmicpc.net/step/59