두 포인터 알고리즘 (Two pointers method)

참고 문헌 :

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

 

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터

---

두 포인터 알고리즘 (Two Pointers Method) 개념 정리

- 배열을 따라 두 개의 포인터를 이동시켜 원하는 값을 얻어내는 기법입니다.

- 해당 알고리즘으로 풀 수 있는 문제는 다음과 같습니다.

 

n개의 정수로 이루어진 배열(arr)과 합이 x인 부분 배열을 구하는 문제

 

문제풀이 : 

1. start = 0, end = 0으로 초기화합니다. sum은 arr[start]의 값으로 초기화합니다.

2. start <= end를 만족할 때 다음 단계를 수행합니다.

3. sum이 x보다 작으면 end을 1 증가하고 sum += arr[end]를 수행합니다.

4. sum이 x보다 크면 sum -= arr[start]를 수행하고 start을 1 증가합니다.

5. sum이 x와 같으면 종료합니다.

 

2 SUM 문제

 

설명 : 수 n개로 이루어진 배열(arr)과 합이 x가 되는 배열 원소의 두 개를 구하는 문제

 

문제풀이 : 

1. 숫자를 오름차순으로 정렬합니다.

2. start = 0, end = n - 1으로 초기화합니다.

3. arr[start]와 arr[end]의 합이 x 보다 작으면 start를 1 증가합니다.

4. arr[start]와 arr[end]의 합이 x 보다 크면 end를 1 감소합니다.

5. arr[start]와 arr[end]의 합이 x와 같으면 종료합니다.

6. start가 end보다 작으면 3 ~ 5번을 반복합니다.