리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘
예를 들면, 학생 40명이 순서대로 일렬로 세워져 있는 경우, 1번부터 10번까지 라고 부르듯 시작점과 끝점 2개의 점을 통해 데이터의 범위를 표현할 수 있다.
'특정한 합을 가지는 부분 연속 수열'문제에 적용가능하다.
n = 5 # 데이터의 개수 N
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) # 3
정렬되어 있는 두 리스트의 합집합에도 활용할 수 있다. 이는 병합 정렬(Merge Sort)의 Conquer 영역의 기초가 되기도 한다. 순서는 다음과 같다.
# 사전에 정렬된 리스트 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=' ') # 1 2 3 4 5 6 8
해당 문서는 '이것이 코딩 테스트다. with 파이썬 - 나동빈 저'의 책을 공부하며 정리한 글입니다.