[기타 알고리즘] 투 포인터

 '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 의 appendix B의 순서에 해당하는 글들을 읽으며 정리하였다.

 이 책은 접하게 된지 이틀밖에 되지 않았지만 체계적으로 적혀있는 것 같아서 한 번 끝까지 독학해보고자 한다..!!

 블로그에는 글들만 정리하였지만, 실제 책에는 그림으로 상세한 설명이 나와있다 !

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

투 포인터

투 포인터 알고리즘이란 

리스트에 순차적으로 접근해야 할 때 2 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 리스트에서 순차적인 접근을 할 때에는 '시작점'. '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

사용되는 예시

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

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

 

예를들어 1,2,3,2,5를 갖는 리스트가 주어져있다고 생각해보자.

합이 5가 되는 것을 찾아본다면 1,2,3,2,5  1,2,3,2,5   1,2,3,2,5 만 존재하여 3가지 경우가 존재한다.

 

이의 알고리즘을 만들어보면 다음과 같다.

 1) 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.

 2) 현재 부분합이 M과 같다면 카운트 한다.

 3) 현재 부분합이 M보다 작으면 end를 1 증가시킨다.

 4) 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.

 5) 모든 경우를 확인할 때 까지 2번부터 4번까지의 과정을 반복한다.

 

이는 기본적으로 시작점(start)을 반복문을 사용하여 증가시키고,  증가시킬 때마다 끝점(end)을 그것에 맞게 증가시키는 방법으로 구현해야 한다. 이는 기본적으로 시작점(start)을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점(end)을 오른쪽으로 이동시키면 항상 합이 증가한다. 즉, 리스트 내 원소에 음수 데이터가 포함되어 있다면 투 포인터 알고리즘으로 문제를 해결할 수 없다.

코드는 다음과 같게 된다.

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) # 3

 

 

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

이미 정렬되어 있는 2 개의 리스트가 입력으로 주어질 때, 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것이 문제의 요구사항이다. 이는 2 개의 리스트 A,B가 주어졌을 때, 2 개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가르키면 된다. 이 문제에서는 정렬된 리스트가 주어지므로 원소를 앞에서부터 확인하면 된다.

 

이것도 알고리즘을 만들어본다면 다음과 같다.

 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]

# 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
result = [0] * (n+m)
i,j,k = 0,0,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=' ')

 

 

이 문제를 보니 파이썬은 똑똑해서 집합이라는 것이 존재하기 때문에 집합으로 처리하면 알고리즘 없이 가능할 것 같아서 한번 코드를 짜봤다.

# 사전에 정렬된 리스트 A,B 선언
n,m = 3,4
a = [1,3,5]
b = [2,4,6,8]

set_a = set(a)
set_b = set(b)

result = list(set_a.union(set_b))
    
# 결과 리스트 출력
for i in result :
	print(i,end=' ')