[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 투 포인터

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 투 포인터

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

---

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

• 이러한 투 포인터 알고리즘을 이용하여 '특정한 합을 가지는 부분 연속 수열 찾기' 문제를 풀어보자. '특정한 합을 가지는 부분 연속 수열 찾기' 문제는 양의 정수로만 구성된 리스트가 있을 때, 그 부분 연속 수열 중에서 '특정한 합'을 갖는 수열의 개수를 출력하는 문제이다.
• 예를 들어 다음과 같이 1, 2, 3, 2, 5를 차례대로 원소로 갖는 리스트가 주어져 있다고 하자.
• [1, 2, 3, 2, 5]
  • 이때 합계 값을 5라고 설정하면 다음과 같은 3가지 경우의 수만 존재한다.
    • [1, (2), (3), 2, 5]
    • [1, 2, (3), (2), 5]
    • [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번까지의 과정을 반복한다.

• 소스코드

  # 데이터의 개수
  n = 5 
  # 찾고자 하는 부분합 M
  m = 5
  # 전체 수열
  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
      if interval_sum == m:
          count += 1
      interval_sum -= data[start]
  
  print(count) # 출력: 3

---

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

• 투 포인터는 '정렬되어 있는 두 리스트의 합집합' 같은 문제에 효과적으로 상용할 수 있다. 이 문제에서는 이미 정렬된 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번 과정을 반복한다.

• 소스코드

  
  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]
          i += 1
      # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
      else:
          # 리스트 B의 원소를 결과 리스트로 옮기기
          result[k] = b[j]
          j += 1
      k += 1
  
  # 결과 리스트 출력
  for i in result:
      print(i, end = ' ')

  시간복잡도는 O(N + M)이다. 단순히 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문이다.

---

구간 합 계산

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

  • 예를 들어, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 했을 때, 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 으로 90이 될 것이다.

• 이러한 구간 합 계산 문제는 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다. 다수의 구간에 대해서 합을 각각 구하도록 요구된다.

  • 예를 들어, M개의 쿼리가 있다고 가정해보자. 각 쿼리는 Left, Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다.

    
    결과적으로 `M`개의 쿼리가 주어졌을 때, 모든 쿼리에 대하여 구간의 합을 출력하는 문제가 전형적인 '구간 합 계산'문제이다.
    

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

---

• 구간 합 계산을 위해 가장 많이 사용되는 기법은 바로 접두사 합(Prefix Sum)이다. 각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다.
  • 접두사 합: 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것

• 구간 합 알고리즘
  1. N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장
  2. 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] - P[L-1]이다.
• 예를 들어, [10, 20, 30, 40, 50]과 같이 5개의 데이터가 있다고 하자. 이 5개의 데이터에 대해서 접두사 합을 계산하면 아래와 같다.
  • P = [0, 10, 30, 60, 100, 150]
    • P[0] = 0, P[1] = 10, P[2] = 30, P[3] = 60, P[4] = 100, P[5] = 150
  • 예를 들어, 다음과 같이 쿼리 3개가 있다고 했을 때, 구간 합을 구하는 과정을 확인해보자.
    1. 첫 번째 쿼리: 첫 번째 수부터 세 번재 수까지의 구간([1,3]) 합은?
       • P[3] - P[0] = 60
    2. 두 번째 쿼리: 두 번째 수부터 다섯 번째 수까지의 구간([2, 5]) 합은?
       • P[5] - P[1] = 140

• 소스코드

  n = 5
  data = [10, 20, 30, 40, 50]
  
  sum_value = 0
  prefix_sum = [0]
  for i in data:
      sum_value += i
      prefix_sum.append(sum_value)
  
  left = 3
  right = 4
  print(prefix_sum[right] - prefix_sum[left-1])

  시간복잡도는 O(N + M)이다.