[알고리즘] 투 포인터(Two pointers)

💡 투 포인터란?

효율적인 배열 탐색을 위해, 두 개의 포인터를 동시에 사용하여 배열을 순회하는 알고리즘. 배열을 반복적으로 탐색해야 하는 문제에서 시간 복잡도를 크게 줄일 수 있음.

두 가지 유형

1️⃣포인터 2개가 같은 방향으로 진행

• 부분합의 개수를 구하는 문제에서 자주 사용됨.

1. 두 포인터(start, end)의 위치를 0으로 초기화
2. 부분합이 목표와 같다면 count, end 증가
3. 부분합이 목표보다 작다면 end 증가
4. 부분합이 목표보다 크다면 start 증가
5. 2~4 반복
6. 배열의 끝에 start가 도달하면 종료

1️⃣ 문제풀이

백준 2003

 		int sum=0, count=0, size=2, end;

        for(int i=0;i<n;i++){ //틀 사이즈가 1인 경우
            if(arr[i]==m) {
                count++;
            }
        }

        while (size<=n) {
            end=size;
            for(int i=0;i<size;i++){ //첫 부분합
                sum+=arr[i];
            }
            if(sum==m) { //첫 부분합이 찾는 값이라면, count증가
                count++;
            }

            if(size!=n){ //배열의 크기보다 사이즈가 작을 때
                for(int start=0;start+size<n;start++, end++){
                    sum=sum-arr[start]+arr[start+size];
                    if(sum==m) {
                        count++;
                    }
                }
            }
            sum=0; //초기화
            size++; //틀 사이즈 증가
        }

투 포인터 개념을 몰랐을 때 슬라이딩 윈도우를 반복하는 형태로 짠 코드이다. ArrayIndexOutOfBoundsException을 해결하기 위해 조건을 추가하다 보니 코드가 더럽다. 코드가 체계적이지 못한 게 보인다,,

		int count=0, start=0, end=0, sum=0;

        while (true){
            if(sum>m){
                sum-=arr[start++];
            }else if(end==n)break;
            else{
                sum+=arr[end++];
            }
            if(sum==m) count++;
        }

투 포인터 개념을 공부하고 이를 적용한 코드이다. 코드 길이도 짧아졌고, 중첩 반복문이 사라졌기 때문에 시간복잡도도 줄었다.

2️⃣ 포인터 2개가 양 끝에서 시작하여 반대 방향으로 진행

• 정렬에 사용됨
• 배열 속 두 수의 합을 구함

관련 문제 추후 추가 예정