[알고리즘] 투 포인터

투 포인터

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

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

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

  • 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문에 투포인터 알고리즘으로 해결 할 수 있다.

  • 만약 리스트 내 원소에 음수데이터가 포함되어있는 경우에는 위 알고리즘으로 해결 할 수 없다.

    # 특정 합계 값이 5라고 가정 답은 3 (2,3) (3,2) (5)
    
    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개의 리스트가 주어지고, 두 리스트의 원소를 합쳐서 정렬한 결과를 계산하는 것
  • 위 알고리즘은 병합정렬(Merge Sort)과 같은 알고리즘에서 사용된다.

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

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

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

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

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

     # 사전에 정렬된 리스트 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]):
                  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=' ')