[Algorithm] 투 포인터 알고리즘

1. Two Pointer Algorithm 정의

- 1차원 배열에서 각자 다른 원소를 가리키고 있는 두 개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘

- 쉽게 말해 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘

- 배열이나 리스트가 정렬되어 있을 때 사용된다.

- 정렬의 필요 여부는 기억해야할 과거 정보에 의존한다. 예를들어 i~j까지의 구간의 합 중 최대 값을 구하려면 기존 배열의 값들에서 슬라이딩 윈도우 기법으로 구해야 한다. 이 때는 정렬이 필요가 없다. 

---

 

2. Two Pointer Algorithm 수행 단계

1. 배열 또는 리스트의 시작 위치에 start, end 포인터를 설정한다.

2. 두 포인터 사이의 구간을 조사하고 조건을 확인한다.

3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘 종료

4. 조건을 만족하지 못했을 경우, start나 end 포인터를 이동시킨다.

5. 다시 2번으로 돌아가 반복

---

3. Two Pointer Algorithm 종류

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

• 고정된 길이의 윈도우를 사용하여 길이 만큼 배열을 탐색
• 부분 배열의 합이나 평균 등을 구할 때 사용한다.

https://velog.io/@jminkyoung/AL-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-JavaScript

• 문제 예시
  • 프로그래머스 - 할인 행사
  • https://dongyeop00.tistory.com/154

자바 [Programmers] 2단계 - 할인 행사

 

2. 두 포인터의 합과 차

• i번째부터 j까지의 합이 특정 값에 도달하거나 2개의 포인터의 합이 특정 값에 도달 할 때 사용되는 알고리즘

https://colabear754.tistory.com/69

    private static void twoPoint(){
        int start = 0, end = 0;
        int sum = 0;

        while(true){
            if(sum >= M){
                sum -= num[start++];
            }else if(end == N){
                break;
            }else{
                sum += num[end++];
            }

            if(sum == M){
                count++;
            }
        }
    }