투 포인터

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현 할 수 있다.

투 포인터의 수행단계

1. 리스트의 시작위치에서 투포인터의 시작인덱스와 끝인덱스를 지정합니다.
2. 시작과 끝의 범위 안에서 조건에서 원하는 값을 검색합니다.
3. 원하는 값을 찾았다면 문제에 조건에 맞게 카운트를 하거나 알고리즘을 종료합니다.
4. 조건의 범위에서 원하는 값을 찾지 못한다면 끝 인덱스나 시작 인덱스를 증가 시킵니다.
5. 2번에으로 돌아가 반복합니다.

투 포인터 시간 복잡도

• 투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적입니다. 또한 한 번의 반복으로 모든 요소를 처리하기에 효율적입니다.

• 일반적으로 빅오 표기법을 이용하여 표기하였을때 O(N)입니다. 이는 배열이나 리스트 크기에 비례하여 알고리즘의 수행시간이 증가한다는 의미입니다.

슬라이딩 윈도우

• N개의 원소를 갖는 배열이 있고, W의 넓이를 갖는 창문이있다고 가정합니다. (N,W는 고정된 상수)
• 창문을 왼쪽부터 시작하여 한 칸씩 오른쪽으로 이동
• 매 순간 창문안에서의 정보 유출 필요 (Ex.합, 곱, 평균 등..)

슬라이딩 윈도우를 활용한 구간합

W의 넓이의 창문안의 숫자를 구하는 문제를 예를 들어서 설명해보겠습니다.
창문을 한칸 옮길때마다 (W-1)칸은 겹치게 됩니다. 즉, 창문을 옮길때마다 W개를 전부 다 더하는 작업을 하지말고, 이전의 결과를 활용하는 방향으로 접근하는 것이 슬라이딩 윈도우의 기본 원리입니다.

기존엔 모든 창문마다 O(W)합을 구해서 전체가 O(NW)의 시간이 걸렸지만, 슬라이딩 윈도우를 활용하면 처음 창문에서만 O(W)이고, 이후에 한 칸씩 밀때는 O(1)에 구간 합을 구할 수 있으므로, 전체 시간 복잡도는 O(N)이 됩니다.