투 포인터

 투 포인터(Two Pointers) 알고리즘은 말 그대로 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 간단하게 얘기하면 '시작점'과 '끝점'을 이용하여 데이터의 범위를 표현하는 방법론입니다.

 

특정한 합을 가지는 부분 연속 수열

특정한 합을 가지는 부분 연속 수열을 찾아야 할 때, 투포인터 알고리즘이 유용하게 쓰일 수 있습니다. 절차는 다음과 같습니다.

---

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.

2. 현재 부분합이 M과 같다면 카운트한다.

3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다.

4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.

5. 모든 경우를 확인할 때까지 2번부터 4번까지 과정을 반복한다.

---

 위에 제시한 절차를 코드로 옮기면 다음과 같습니다.

n = 5 # 데이터의 개수
m = 5 # 찾고자 하는 부분함
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

for start in range(n):
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
    
print(count)

 

정렬되어 있는 두 리스트의 합집합

 정렬된 두 리스트의 합집합을 구할 때도 투 포인터 알고리즘이 유용하게 사용될 수 있습니다. 물론 파이썬의 집합 객체를 이용하여 union연산을 해도 간단하게 같은 결과를 얻을 수 있습니다. 다만 병합 정렬(Merge soft)와 같은 알고리즘이 내부적으로 이러한 과정을 통해 이루어진다는 것은 주목할 만합니다. 절차는 다음과 같습니다.

---

1. 정렬된 리스트 A와 B를 입력받는다.

2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.

3. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다.

4. A[i]와 B[j] 중에서 더 작은 원소를 결과 리스트에 담는다.

5. 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번 과정을 반복한다.

---

위의 과정을 코드로 옮기면 다음과 같습니다.

n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

result = [0] * (n + m)
i, j, k = 0, 0, 0
while i < n or j < m:
    if j >= m or (i < n and a[i] <= b[j]):
        result[k] = a[i]
        i += 1
    else:
        result[k] = b[j]
        j += 1
    k += 1
    
for i in result:
    print(i, end=' ')