[Algorithm] 투 포인터 알고리즘

들어가기 앞서

• 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
• ‘특정한 합을 가지는 부분 연속 수열 찾기’ 또는 ‘정렬되어 있는 두 리스트의 합집합’과 같은 문제에 사용된다.

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

• 투 포인터 알고리즘을 이용하여 ‘특정한 합을 가지는 부분 연속 수열 찾기’ 문제를 풀어보자.

  • 해당 문제는, 양의 정수로만 구성된 리스트가 주어졌을 때,
  • 그 부분 연속 수열 중에서 ‘특정한 합’을 갖는 수열의 개수를 출력하는 문제이다.

• 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이며,

• 해당 문제에서는 부분 연속 수열의 시작점(start)와 끝점(end)의 위치를 기록한다.

• 특정한 부분합을 M이라고 할 때, 알고리즘의 구체적인 순서는 다음과 같다.

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

• 투 포인터 알고리즘은 구현 가능한 방식이 매우 많다는 특징이 있다.

• 이 문제를 투 포인터 알고리즘으로 해결할 수 있는 이유는,

• 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문이다.

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

• 예제 코드는 아래 코드와 같다.

    n = 5                   # 데이터의 개수 N
    m = 5                   # 찾고자 하는 부분합 M
    data = [1, 2, 3, 2, 5]  # 전체 수열
  
    count = 0           # 부분합이 m인 데이터의 개수
    interval_sum = 0    # 구간 합
    end = 0             # 끝 인덱스
  
    # start를 차례대로 증가시키며 반복
    for start in range(n):
  
        # end를 가능한 만큼 이동시키기
        # 현재 부분합이 M보다 작다면 
        while interval_sum < m and end < n:
            # start와 end의 부분합을 추가    
            interval_sum += data[end]
            # end 1 증가
            end += 1
  
        # 부분합이 m일 때 카운트 증가
        if interval_sum == m:
            count += 1
  
        # start를 1 증가시키기 전, 부분합에서 현재 start 인덱스의 값 뺄셈
        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번의 과정을 반복한다.

• 결과적으로 정렬된 리스트 A와 B의 데이터 개수가 각각 N, M이라고 할 때,

• 이 알고리즘의 시간 복잡도는 O(N + M)이 된다.

• 단순히, 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문이다.

• 예제 코드는 아래와 같다.

    # 사전에 정렬된 리스트 A와 B 선언
    n, m = 3, 4
    a = [1, 3, 5]
    b = [2, 4, 6, 8]
  
    # 결과 리스트 초기화
    result = []
    i = 0
    j = 0
  
    while (len(result) != n+m):    
  
        # a 리스트가 전부 처리되었다면, b 리스트의 남은 요소를 모두 추가
        if (i == n):
            result += b[j:]
        # b 리스트가 전부 처리되었다면, a 리스트의 남은 요소를 모두 추가
        elif (j == m):
            result += a[i:]
        # a 리스트의 요소가 b 리스트의 요소보다 작거나 같다면
        elif (a[i] <= b[j]):
            result.append(a[i])
            i += 1
        # b 리스트의 요소가 a 리스트의 요소보다 작다면
        else:
            result.append(b[j])
            j += 1
  
    # 결과 리스트 출력
    print(result)

참고

• 이것이 취업을 위한 코딩 테스트다. with python