[알고리즘] 투포인터

투포인터 알고리즘

1. 투포인터 알고리즘은 두개의 포인터를 기준으로 검색을 하며 원하는 값을 찾는 알고리즘이다.

2. 반드시 검색을 하는 목록은 정렬이 이뤄져 있어야 한다.

3. O(n^2) 의 시간복잡도를 O(n)으로 작업 할 수 있어서 소요 시간을 획기적으로 단축 할 수 있다.

---

예제 - 두배열의 공통된 값을 찾기

int[] arr1 = {1, 4, 6, 7, 8, 10}

int[] arr2 = {2, 4, 5, 8, 9}

위와같은 순차정렬된 두개의 배열이 존재 할 때.

공통된 값을 추출하는 알고리즘을 작성해보자.

 

단순 중첩for문을 사용한 코드는 아래와 같다.

int[] arr1 = {1, 4, 6, 7, 8, 10}
int[] arr2 = {2, 4, 5, 8, 9}
List<Integer> list = new ArrayList<>();

for(int i=0; i<arr1.length; i++){
    for(int j=0; j<arr2.length; j++){
    	if(arr1[i]==arr2[j]){
        	list.add(arr1[i]);
        }
    }
}

실제 기록을 (arr1 : arr2) 로 표현 해보면

------------------------------------------------

(1,2) (1,4,) (1,5) (1,8) (1,9)

.

.

.

(10,2) (10,4) (10,5) (10,8) (10,9)

------------------------------------------------

위와같이 O(n^2)의 시간복잡도를 갖는 알고리즘인것을 확인 할 수 있다.

이제 투포인터 알고리즘으로 짜여진 코드를 보자.

 

투포인터 알고리즘을 사용한 코드

int[] arr1 = {1, 4, 6, 7, 8, 10}
int[] arr2 = {2, 4, 5, 8, 9}
List<Integer> list = new ArrayList<>();

//arr1의 인덱스
int p1=0;
//arr2의 인덱스
int p2=0;

while(p1<arr1.length && p2<arr2.length){
    if(arr1[p1]==arr2[p2]){
    	//arr1[p1]==arr[p2] 이므로 어떤걸 추가해도 상관 없음
    	list.add(arr1[p1]);
        p1++;
        p2++;
    }else if(arr1[p1]<arr2[p2]){
    	p1++;
    }else{
    	p2++;
    }
}

위에 작성한 알고리즘도 실제 기록을 (arr1 : arr2)로 표현 해보자

------------------------------------------------

(1,2) (4,2) (4,4) (6,5) (6,8) (8,8) (10,9)

------------------------------------------------

O(n)의 시간복잡도를 갖는 알고리즘으로 불과 몇차례 만에 알고리즘이 종료되었다.

 

 

Sliding Window 과 비교

비슷한 느낌이긴하나 Sliding Window알고리즘은 규칙적으로 일정한 구간을 훑으며 진행하지만

투포인터 알고리즘은 비교적 불규칙한것같다?...