---

개념

투 포인터(Two Pointers)는 배열 또는 리스트에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘 기법입니다. 이 기법은 선형 시간 안에 해결할 수 있는 몇 가지 문제들을 효율적으로 해결하는 데 사용됩니다.

---

작동 방식

1. 배열 또는 리스트를 정렬된 상태로 가정합니다. (정렬되어 있지 않은 경우에도 사용 가능하지만, 일부 제약이 따를 수 있습니다.)

2. 시작 지점과 끝 지점을 나타내는 두 개의 포인터를 설정합니다. 이 포인터들은 일반적으로 배열의 양쪽 끝을 가리키는데, 시작 지점은 왼쪽 끝, 끝 지점은 오른쪽 끝을 가리킵니다.

3. 시작 지점과 끝 지점을 기준으로 문제의 조건을 충족하는 영역을 좁혀나갑니다. 이를 위해 두 포인터를 이동시키면서 필요한 조건을 검사하고 필요에 따라 포인터들을 조작합니다.

4. 원하는 결과가 나올 때까지 포인터들을 이동시키고 조작하는 과정을 반복합니다

---

특징

투 포인터 알고리즘은 주로 정렬된 리스트나 배열에서 특정한 조건을 만족하는 부분을 찾거나, 두 개의 포인터를 이동시키면서 원하는 결과를 얻는 경우에 사용됩니다.

1. 두 개의 포인터 사용: 투 포인터 알고리즘은 리스트나 배열에서 두 개의 포인터를 사용합니다. 일반적으로 왼쪽 포인터와 오른쪽 포인터를 사용하며, 두 포인터는 초기에 리스트의 양 끝에서 시작합니다. 포인터를 이동하면서 원하는 결과를 얻을 때까지 반복적으로 수행합니다.

2. 동시 이동: 투 포인터 알고리즘은 두 포인터를 동시에 이동시킵니다. 보통 두 포인터는 서로 다른 방향으로 이동하거나, 같은 방향으로 이동하며 일정한 조건을 만족하는 경우에 사용됩니다. 이러한 동시 이동은 효율적인 문제 해결을 위해 사용되며, 전체적인 탐색 범위를 줄여 시간 복잡도를 개선할 수 있습니다.

3. 선형 시간 복잡도: 투 포인터 알고리즘은 대부분 선형 시간 복잡도를 가지며, 리스트나 배열을 한 번만 순회하면서 문제를 해결합니다. 이는 효율적인 알고리즘 설계를 가능하게 합니다.

4. 정렬된 리스트나 배열에서 유용: 투 포인터 알고리즘은 정렬된 리스트나 배열에서 특히 유용하게 사용됩니다. 정렬된 상태에서는 양 끝에서부터 포인터를 이동시키면서 원하는 결과를 찾거나 조건을 만족하는 부분을 찾을 수 있습니다. 이는 이진 탐색과 유사한 개념을 가지고 있으며, 정렬된 데이터의 특성을 이용하여 문제를 해결합니다.

5. 메모리 사용량: 투 포인터 알고리즘은 일반적으로 상수 개의 변수(포인터)만 사용하므로 메모리 사용량이 매우 적습니다.

투 포인터 알고리즘은 특히 부분 배열의 합, 두 요소의 합, 정렬된 리스트의 합 등과 관련된 문제들을 효과적으로 해결할 수 있습니다. 리스트나 배열에서 두 개의 포인터를 사용하여 문제를 해결하는 특징은 투 포인터 알고리즘의 가장 큰 특징 중 하나입니다.

---

구현 방법

1. 초기 포인터 설정: 일반적으로 왼쪽 포인터와 오른쪽 포인터를 사용합니다. 이들 포인터는 초기에 리스트나 배열의 양 끝에서 시작합니다.

2. 포인터 이동 조건 설정: 문제에 따라 포인터를 어떻게 이동시킬지 결정합니다. 왼쪽 포인터를 오른쪽으로 이동하거나, 오른쪽 포인터를 왼쪽으로 이동하거나, 두 포인터를 같은 방향으로 이동시키는 등 다양한 방식으로 이동할 수 있습니다. 이동 조건은 문제의 제약과 조건에 따라 결정됩니다.

3. 포인터 이동 및 조건 체크: 포인터를 이동하면서 원하는 조건을 만족하는지 체크합니다. 이동 조건에 따라 포인터를 한 칸씩 이동하거나 여러 칸씩 이동시킬 수 있습니다.

4. 알고리즘 종료 조건: 문제에 따라 알고리즘을 종료할 조건을 설정합니다. 종료 조건은 원하는 결과를 얻거나 포인터가 리스트나 배열의 끝에 도달한 경우 등 다양하게 설정될 수 있습니다.

---

예시

투 포인터는 일반적으로 선형 시간에 문제를 해결할 수 있기 때문에 효율적입니다. 몇 가지 예시로는 다음과 같은 문제들이 있습니다.

1. 두 수의 합: 주어진 정렬된 배열에서 두 개의 수를 선택하여 합이 특정한 값을 가지는지 확인하는 문제입니다. 투 포인터를 사용하여 시작 지점과 끝 지점을 이동시키면서 합을 조사할 수 있습니다.

2. 배열의 합이 특정한 값이 되는 부분 배열: 주어진 배열에서 합이 특정한 값이 되는 연속된 부분 배열을 찾는 문제입니다. 시작 지점과 끝 지점을 이동시키면서 부분 배열의 합을 계산하고 조건에 따라 포인터를 이동시킵니다.

3. 정렬된 배열의 두 수의 차이: 주어진 정렬된 배열에서 두 개의 수의 차이가 특정한 값을 가지는지 확인하는 문제입니다. 시작 지점과 끝 지점을 이동시키면서 차이를 조사하고 조건에 따라 포인터를 이동시킵니다.

위 예시들은 투 포인터의 활용 사례 중 일부입니다. 투 포인터는 배열이나 리스트에서 연속된 영역을 탐색하거나 특정한 조건을 만족하는 영역을 찾을 때 유용하게 사용될 수 있습니다.