---

투 포인터 알고리즘(Two Pointers)

1. Two Pointers Algorithm란?

• 연속되고 길이가 가변적인 부분 1차원 배열들에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 구간을 효율적으로 탐색하는 알고리즘이다.
• 리스트에서 데이터에 순차적으로 접근해야 할 때 시작점과 끝점 2개의 점으로 위치를 기록하며 탐색한다.
• 시간 복잡도는 O(N)

---

2. Two Pointers 수행 조건

1. 두 개의 포인터를 사용하기 때문에 두 개의 인덱스를 가르키는 변수가 필요하다.
2. 일반적으로 시작점을 가르키는 변수는 left 또는 start를 사용하고, 끝점을 가르키는 변수는 right 또는 end 를 사용한다.
3. 인덱스는 start = end = 0 부터 시작하고, start ≤ end 조건을 항상 만족해야 한다.
4. 두 포인터 사이의 구간을 조사하고 조건을 확인해야합니다.
5. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료합니다.
6. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킵니다.
7. 다시 4번 단계로 돌아가 반복합니다.

---

3. Two Pointers 동작 방식

• 투 포인터는 크게 두가지 방식으로 작동합니다
  • 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식
  • 빠른 포인터(fast runner)가 느린 포인터(slow runner)보다 앞서는 형식(토끼와 거북이)

---

3-1. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식

• 이 방식은 맨 처음 인덱스와 맨 끝의 인덱스가 중간으로 이동하면서 탐색한다.
• 주로 정렬된 배열에서 중복된 수가 없어야 한다.
• 특정 조건을 만족하는 두 요소를 찾기 위해 사용된다.

- 예시: 처음으로 두 수의 합이 12가 되는 배열을 출력해라

- 코드 풀이

sequence = [1, 4, 7, 8, 10, 21]  # 정렬된 배열

start, end = 0, len(sequence) - 1   # 두 개의 포인터 설정
sum = 0  # 초기 합 설정

while start < end:
    sum = sequence[start] + sequence[end]
    if sum == 12:   # sum이 12가 될 때
        print([sequence[start], sequence[end]])  # 결과값 리스트
        break
    elif sum < 12:  # sum이 12보다 작으면 start 포인터를 증가
        start += 1
    else:  # sum이 12보다 크면 end 포인터를 감소
        end -= 1

1. 포인터 설정: 배열의 첫 번째 요소를 가리키는 start 포인터와 마지막 요소를 가리키는 end 포인터를 설정합니다.
   start는 배열의 시작 인덱스(0)를 가리키고, end는 배열의 마지막 인덱스(len(sequence) - 1)를 가리킵니다.
2. 루프 조건: while 루프를 사용해 start 포인터가 end 포인터보다 작을 때까지 반복합니다. 이 조건은 두 포인터가 교차하지 않는 한 계속 탐색을 진행함을 의미합니다.
3. 합 계산 및 비교:
   • 각 반복에서 start와 end가 가리키는 요소의 합을 계산합니다.
   • 합이 12와 같으면 해당 요소를 리스트로 출력하고 루프를 종료합니다.
   • 합이 12보다 작으면 더 큰 값을 찾기 위해 start 포인터를 오른쪽으로 이동시킵니다.
   • 합이 12보다 크면 더 작은 값을 찾기 위해 end 포인터를 왼쪽으로 이동시킵니다.
4. 결과 출력: 목표값(12)을 만드는 두 수를 찾으면 그 수를 출력하고 루프를 종료합니다.

---

3-2. 빠른 포인터(fast runner)가 느린 포인터(slow runner)보다 앞서는 형식(토끼와 거북이)

• 이 방식은 두 포인터의 시작 위치는 모두 0이지만 , 두 포인터의 이동 속도를 다르게 사용하여 탐색을 한다.
• 주로 fast는 반복문마다 값이 커지고, slow는 조건에 따라 값이 커지도록 설정한다

- 예시: 연속된 수들의 부분합 중에 그 합이 9 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하라.

- 코드 풀이

arr = [1,2,3,4,5]   # 주어진 수열

start, end = 0,0  # 시작과 끝 인덱스 초기화
min_len = len(arr) + 1  # 최소 길이를 수열의 길이 + 1 초기 설정 (가능한 최단 길이를 찾기 위해)
sum = arr[start]  # 현재 구간의 합을 arr[start] 값으로 초기화

while True:
    # 현재 구간의 합이 9보다 작으면 구간을 확장해야 함
    if sum < 9:
        end += 1  # 구간 끝을 오른쪽으로 이동
        if end == len(arr):  # 배열의 끝에 도달했을 경우 루프 종료
            break
        sum += arr[end]  # 새로운 끝값을 구간 합에 추가
    # 현재 구간의 합이 9 이상일 경우 최소 길이를 갱신하고 구간 시작을 이동
    elif sum >= 9:
        min_len = min(min_len ,end - start + 1)  # 최소 길이를 갱신
        sum -= arr[start]  # 구간 시작값을 구간 합에서 제거
        start += 1  # 구간 시작 인덱스를 오른쪽으로 이동

# 최소 길이가 초기값인 경우 적절한 구간을 찾지 못했으므로 0을 출력, 그렇지 않으면 최소 길이를 출력
print(min_len if min_len != len(arr) + 1 else 0)

1. 포인터 설정: 배열의 첫 번째 요소를 가리키는 start 포인터와 end 포인터를 설정합니다. 초기에는 두 포인터 모두 배열의 첫 번째 요소를 가리키게 됩니다.
2. 루프 조건: while 루프를 사용하여 특정 조건이 만족될 때까지 탐색을 진행합니다. 이 경우에는 배열의 합이 목표값(예: 9) 이상이 될 때까지 루프가 계속됩니다.
3. 구간 확장 및 축소:
   • 현재 구간의 합이 목표값(9)보다 작으면 end 포인터를 오른쪽으로 이동시켜 구간을 확장합니다.
   • 반대로 구간의 합이 목표값 이상일 경우, 현재 구간의 길이를 계산해 최소 길이를 갱신한 후 start 포인터를 오른쪽으로 이동시켜 구간을 축소합니다.
4. 결과 출력: 루프가 종료되면, 목표값을 만족하는 최소 구간의 길이를 출력합니다. 만약 그러한 구간이 없다면 0을 출력합니다.

---

4. 슬라이딩 윈도우(Sliding Window) vs. 투 포인터(Two Pointers)

• 슬라이딩 윈도우
  

• 정의: 고정된 크기의 윈도우(부분 배열)가 배열 위를 이동하며 데이터를 탐색하는 방법.
• 특징: 윈도우의 크기가 고정적이며, 데이터를 처리하는 구간의 크기가 변하지 않음.
• 포인터 개수: 두 개의 포인터가 필요하지 않음. 고정된 크기의 윈도우로 처리.
• 투 포인터
  • 정의: 두 개의 포인터를 사용해 배열의 특정 구간을 가변적으로 탐색하는 방법.
  • 특징: 구간의 크기가 가변적이며, 문제 상황에 따라 포인터의 위치를 변경해 구간을 조절함.
  • 포인터 개수: 2개의 포인터로 구간의 시작과 끝을 조절.
• 핵심 차이
  • 슬라이딩 윈도우는 고정된 길이의 구간을 사용하고,
  • 투 포인터는 가변적인 길이의 구간을 사용함.