[python]투포인터

이것이 코딩 테스트다 with Python 의 도서를 보고 공부하며 정리한 게시글 입니다.

투 포인터

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

예시

한 반에 학생이 40명 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우 

-> 2,3,4,5,6,7번 학생을 지목해야 할 때, 번호로 한명씩 부르기 보단 '2번부터 7번까지의 학생' 이라고 부르곤 함 

==> 즉, 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점 과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음

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

양의 정수로만 이루어진 리스트가 주어졌을 때, 그 부분 연속 수열 중에서  특정한 합 을 갖는 수열의 개수를 출력

예) 1,2,3,2,5를 차례대로 원소를 갖는 리스트가 주어져 있다고 한다.

이때 합계 값을 5라고 설정하면 다음과 같은 3가지 경우의 수만 존재.

- [1,2,3,2,5]

- [1,2,3,2,5]

- [1,2,3,2,5]

부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록한다.

특정한 부분합을 m이라고 할 때, 구체적인 알고리즘은 다음과 같다.

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

소스

n = 5 # 데이터의 개수
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
   
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m :
        count += 1
    interval_sum -= data[start]

print(count)

 

-> 시작점을 loop를 돌며 증가시키며, 증가할 때마다 끝점을 맞게 증가시킴

시작점을 오른쪽을 이동시키면 합이 감소, 끝점을 오른쪽으로 이동시키면 합이 증가

하지만, 리스트 내 원소에 음수 데이터가 포함되어 있을 경우는 투 포인터 알고리즘 사용 할 수 없음

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

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

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]):
        # 리스트 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 = ' ')

=> 병합 정렬과 같은 일부 알고리즘에 사용되고 있다.