참조
이 글은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 읽고 작성하였습니다.

투 포인터

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미합니다. 예를 들어서 한 반에 학생이 40명이 있을 때, 모든 학생을 번호순대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보겠습니다. 2,3,4,5,6,7번 학생을 지목해야 할 때, 번호로 한명씩 부르기보다는 '2번부터 7번까지의 학생'이라고 부를 수도 있습니다. 이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있습니다.

특정한 합

이런 투 포인터 알고리즘을 이용하여 '특정한 합을 가지는 부분 수열 찾기' 문제를 풀 수 있습니다. '특정한 합을 가지는 부분 연속 수열 찾기 문제'는 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 '특정한 합'을 갖는 수열의 개수를 출력하는 문제입니다.

특정한 합 예시

1,2,3,2,5를 차례대로 갖는 리스트가 주어졌 있다고 가정하겠습니다.

이 문제를 투 포인터 알고리즘을 이용하여 풀겠습니다. 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점입니다. '특정한 합을 가지는 부분 연속 수열 찾기' 문제에서는 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록합니다. 특정한 부분합을 M이라고 할 때, 구체적 알고리즘은 아래와 같습니다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다
2. 현재 부분합이 M과 같다면 카운트한다
3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다
4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다

위의 알고리즘을 통해 부분합이 5인 부분 연속 수열의 수를 계산하기 위한 구체적인 과정을 알아보겠습니다.

0. 알고리즘에 따라서 초기 단계에서는 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 합니다. 이때 현재의 부분합은 1이므로 무시됩니다.
   

1. 이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킵니다. 현재 부분합은 3이므로 이번에도 마찬가지로 무시됩니다.
   

2. 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킵니다. 현재 부분합은 6이므로 이번에도 마찬가지로 무시됩니다.
   

3. 이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킵니다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이기에 카운트를 증가시킵니다.
   

4. 이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킵니다. 현재 부분합이 3이므로 무시합니다.
   

5. 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킵니다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이기에 카운트를 증가시킵니다.
   

6. 이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킵니다. 현재 부분합은 2이므로 무시합니다.
   

7. 이전 단계에서의 부분합이 2였기 때문에 end를 1 증가시킵니다. 현재 부분합은 7이므로 무시됩니다.
   

8. 이전 단계에서의 부분합이 7이었기 때문에 start를 1 증가시킵니다. 현재 부분합은 5이므로 하나의 경우를 찾은 것이기에 카운트를 증가시킵니다.
   

결과적으로 카운트된 경우의 수는 3입니다. 투 포인터 알고리즘은 구현 가능한 방식이 매우 많다는 특징이 있습니다. 아래의 코드에서는 시작점(start)을 반복문을 이용하여 증가시키며, 증가할 때마다 끝점(end)을 그것에 맞게 증가시키는 방식으로 구현하였습니다. 이 문제를 투 포인터 알고리즘으로 해결할 수 있는 이유는 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문입니다. 만약 리스트 내 원소에 음수 데이터가 포함되어 있는 경우에는 투 포인터 알고리즘으로 문제를 해결할 수 없습니다.

소스코드

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

# 카운트
count = 0
# 합을 계산하기 위한 변수
interval_sum = 0
# 끝점 변수
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)

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

투 포인터 알고리즘은 '정렬되어 있는 두 리스트의 합집합' 같은 문제에 효과적으로 사용할 수 있습니다. 이 문제는 이미 정렬되어 있는 2개의 리스트가 입력으로 주어지고 이 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것이 문제의 요구사항입니다.

이 문제를 풀기 위해 2개의 리스트 A, B가 주어졌을 때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키면 됩니다. 이 문제에서는 기본적으로 이미 정렬된 결과가 주어지므로 리스트 A와 B의 원소를 앞에서부터 확인하면 됩니다.

1. 정렬된 리스트 A와 B를 입력받는다
2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가키리도록 한다
3. 리스트 B에서 처리되지 않은 원소 중 가작 작은 원소를 j가 가리키도록 한다
4. A[i]와 B[j]중에서 더 작은 원소를 결과 리스트에 담는다
5. 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복합니다.

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

0. 초기 단계에서는 두 리스트의 모든 원소가 들어갈 수 있는 크기의 결과 리스트를 하나 생성합니다. 또한 i가 리스트 A의 첫 번째 원소를 가리키도록 하고, j가 리스트 B의 첫 번째 원소를 가리키도록 합니다.
   

1. 현재 i와 j가 가리키는 두 원소를 비교합니다. A[i]=1, B[j]=2입니다. A[i] < B[j]이므로 결과 리스트에 i가 가리키고 있는 원소를 담습니다. 이후에 i를 1 증가시킵니다.
   

2. 현재 i와 j가 가리키는 두 원소를 비교합니다. A[i]=3, B[j]=2입니다. A[i] > B[j]이므로 결과 리스트에 j가 가리키고 있는 원소를 담습니다. 이후에 j를 1 증가시킵니다.
   

3. 현재 i와 j가 가리키는 두 원소를 비교합니다. A[i]=3, B[j]=4입니다. A[i] < B[j]이므로 결과 리스트에 i가 가리키고 있는 원소를 담습니다. 이후에 i를 1 증가시킵니다.
   

4. 현재 i와 j가 가리키는 두 원소를 비교합니다. A[i]=5, B[j]=4입니다. A[i] > B[j]이므로 결과 리스트에 j가 가리키고 있는 원소를 담습니다. 이후에 j를 1 증가시킵니다.
   

5. 현재 i와 j가 가리키는 두 원소를 비교합니다. A[i]=5, B[j]=6입니다. A[i] < B[j]이므로 결과 리스트에 i가 가리키고 있는 원소를 담습니다. 이후에 i를 1 증가시킵니다.
   

6. 이제 리스트 A에 있는 모든 원소가 결과 리스트에 담겼습니다. 남은 리스트 B에 있는 모든 원소를 겨로가 리스트에 담으면 됩니다.
   

결과적으로 정렬된 리스트 A와 B의 데이터 개수가 각각 N,M이라고 할 때, 이 알고리즘의 시간 복잡도는 O(N+M)입니다. 단순히 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문입니다.

소스코드

# 사전에 정렬된 리스트 A와 B 선언
n, m = 3, 4
a = [1,3,5]
b = [2,4,6,8]

# 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
result = [0] * (n + m)
# 인덱스 초기화
i = 0
j = 0
k = 0

# 모든 원소가 결과 리스트에 담길 때까지 반복
while i < n or j < m:
    # 리스트 B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때
    if j >= m or (i < n and a[i] <= b[j]):
        # 리스트 A의 원소를 결과 리스트로 옮기기
        result[k] = a[i]
        # 리스트 A 인덱스 더하기
        i += 1
    # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
    else:
        # 리스트 B의 원소를 결과 리스트로 옮기기
        result[k] = b[j]
        # 리스트 B 인덱스 더하기
        j += 1
    # 결과리스트 인덱스 더하기
    k += 1

# 결과 리스트 출력
for i in result:
    print(i, end=" ")

이 '정렬되어 있는 두 리스트의 합집합' 알고리즘의 경우 병합 정렬(Merge Sort)와 같은 일부 알고리즘에서 사용되고 있습니다.