투 포인터(Two Pointers) - start~end, merge sort, prefix sum

투 포인터 알고리즘

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘
• 연속된 40개의 숫자 중 2, 3, 4, 5, 6, 7을 지목해야 할 때 번호로 하나씩 부르기보다 '2부터 7까지'라고 부르는 방법
• 위 방법처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때
  '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

예시 문제

문제 1. 특정한 합을 가지는 부분 연속 수열 찾기

예를 들어 arr = [1, 2, 3, 2, 5]의 리스트와 M = 5의 값이 주어졌을 때

부분 연속 수열 중 M의 값을 가지는 수열의 개수를 구하라

 

[1, 2, 3, 2, 5]에서 합이 5인 부분 연속 수열의 조합은 

[2, 3], [3, 2], [5]와 같다. 

 

Pseudo Algorithm

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

여기서 헷갈릴 수 있는게 왜 부분합이 M보다 작을 때 end를 증가시키고, 부분합이 M보다 크거나 같을 때 start를 증가시키는지다.

3번의 경우만 먼저 생각해보자.

 

start와 end가 고정되어 있을 때 start ~ end의 부분합이 더 커질려면 start가 왼쪽으로 가거나 end가 오른쪽으로 가면 된다.

start가 왼쪽으로 갈 경우 이미 확인한 값이 되기 때문에 왼쪽으로 돌아가는 경우는 고려하지 않는다.

때문에 부분합이 더 커지려면 end가 오른쪽으로 가는 방법 밖에 없다. 

이는 end값을 +1 시키는 것으로 구현할 수 있다.

 

현재 부분합이 M보다 작다면, M과 같아지기 위해 부분합을 증가시킬 필요가 있다.

이 경우 end의 값을 1 증가시키는 것이다.

 

반대로, 부분합이 M보다 크거나 같을 경우에 대해서인데

클 경우는 M과 같아지려면 부분합이 작아져야하니 start를 증가시켜 범위를 축소시키는 것이다. 

같을 경우는 기록을 하고나서 다음 만족하는 조건을 찾기 위해 start를 한칸 증가시키는 것이라고 보면 된다.

 

위 방법에 대해 시작점(start)를 반복문을 통해 증가시키며,

증가할 때마다 끝점(end)을 그것에 맞게 증가시키는 방식으로 코드로 구현해보자

 

* 위 문제는 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고,
끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문에 
투 포인터 알고리즘으로 해결할 수 있다.
만약 리스트 내 원소에 음수 데이터가 포함되어 있는 경우 투 포인터 알고리즘으로 문제를 해결할 수 없다.

 

코드

arr = [5, 2, 3, 2, 5]
M = 5

count = 0
interval_sum = 0
end = 0

for start in range(len(arr)):  # start -> 0, 1, 2, 3, 4
  while interval_sum < M and end < len(arr):
    interval_sum += arr[end]
    end += 1

  if interval_sum == M:
    print(arr[start], arr[end-1])  # end 값을 interval_sum에 담고 +1 되었기에 -1 해준다.
    count += 1
  interval_sum -= arr[start]  # start가 증가되며 start에 해당하는 값이 interval_sum에서 제거

print(count)

 

문제 2. 정렬되어 있는 두 리스트의 합집합

이미 정렬되어 있는 2개의 리스트가 입력으로 주어질 때, 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산해 출력하시오

 

-> 이 문제는 2개의 포인터를 이용해 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키면 된다.

이 문제는 기본적으로 이미 정렬된 결과가 주어지므로 리스트 A와 B의 원소를 앞에서부터 확인하면 된다.

 

* 위 문제의 풀이는 병합 정렬 알고리즘의 구현 과정 중 하나이다.

* 이미 정렬되있다는 걸 꼭 체크하자

 

Pseudo Algorithm

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

 

코드

arr1 = [1, 3, 5]
arr2 = [2, 4, 6, 8]

def merge_sort(arr1, arr2):
  x, y = 0, 0
  result = []
  while x < len(arr1) and y < len(arr2):
    if arr1[x] < arr2[y]:
      result.append(arr1[x])
      x += 1
    else:
      result.append(arr2[y])
      y += 1

  while x < len(arr1):
    result.append(arr1[x])
    x += 1
  
  while y < len(arr2):
    result.append(arr2[y])
    y += 1
  
  return result

answer = merge_sort(arr1, arr2)
print(answer)

 

문제 3. 구간 합 계산

연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제다.

ex) 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있을 때 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90이다.

 

위 문제는 언뜻 쉬워보이지만 보통 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다.

다수의 구간에 대해 합을 각각 구하도록 요구하는데, 다음의 예시 문제를 들 수 있다.

 

M 개의 쿼리가 존재한다고 할 때 각 쿼리는 Left, Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다. 
결과적으로 M개의 쿼리가 주어졌을 때, 모든 쿼리에 대해 구간의 합을 출력하시오

만약 M개의 쿼리 각각, 매번 구간 합을 계산한다면 이 알고리즘은 O(NM)의 시간복잡도를 가진다. 

왜냐면 M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 모두 계산하라고 요구할수도 있기 때문이다. (첫 번째부터 N 번째 수까지)

 

그렇다면 N = 1,000,000, M = 1,000,000인 상황처럼 데이터 개수가 매우 많을 때

O(NM)의 시간복잡도로 동작하는 알고리즘으론 문제를 해결할 수 없을 것이다.

 

여러 번 사용될 만한 정보는 미리 구해 저장해놓을수록 유리한데, 

쿼리는 M개(변동가능)지만, N개의 수는 한 번 주어진 뒤에 변경되지 않는다. 

따라서 N개의 수에 대해 어떤 '처리'를 수행한 뒤 나중에 M개의 쿼리가 각각 주어질 때마다 빠르게 구간 합을 구할 수 있지 않을까?

 

위처럼 구간 합 계산을 위해 가장 많이 사용되는 기법은 '접두사 합(Prefix Sum)'이다. 

위치 각각에 대해 접두사 합(리스트 맨 앞부터 특정 위치까지의 합)을 미리 구해놓으면 빠르게 계산할 수 있을 것이다.

 

구현

만약 [10, 20, 30, 40, 50]에 대해 두 번째부터 네 번째 까지의 합을 구해야 할 때 -> 결과는 90이라고 하면

    1   2   3   4   5   번째 까지의 합
0  10  30  60 100 150

 

 

즉, 두 번째부터 네 번째 까지의 합

-> 처음부터 네 번째 까지의 합 - 처음부터 두 번째 '이전' 까지의 합인 것을 알 수 있다.(두 번째는 포함되어야하므로)

 

1. n 번째 까지의 합을 담은 리스트 만들기 -> save라 할거임
2. L 부터 R 까지의 합이라고 한다면 
   (R 까지의 합) - (L-1 까지의 합)

 

코드

arr = [10, 20, 30, 40, 50]
L = 2
R = 4

def prefix_sum(arr, L, R):
  save = [0]
  sum = 0
  for i in range(len(arr)):
    sum += arr[i]
    save.append(sum)

  return save[R] - save[L-1]

result = prefix_sum(arr, L, R)
print(result)

 

문제 4. 두 수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합