[파이썬 알고리즘] 누적합 알고리즘과 투 포인터 알고리즘

누적 합(prefix sum)

구간 합을 빠르게 구할수 있는 알고리즘으로 첫 번째 데이터 부터 특정 데이터까지 더한 값을 구할 수 있다.

구간 합을 여러번 계산하는 상황에서 유리하다.

누적 합을 계산하는데 O(n)시간이 걸리고 그 후 구간 합을 한번 계산할 때 마다 O(1)의 시간이 걸린다.

쿼리(Query)를 이용하여 사용하는것이 유리하다.

• 쿼리(Query) : 데이터의 계산 또는 조회를 요청하는 입력 / 튜플로 이루어져 있다.

누적 합 알고리즘 쿼리 예시코드


expenses = [25000,12000,32000,13000,27000,42000,5000]    # 날짜별 지출내역
n = len(expenses)

prefix_sum = [0] * (n+1)    #누적 합 리스트 / 0번 ~ n번

for i in range(n):
    prefix_sum[i+1] = prefix_sum[i] + expenses[i]    #i번째 = 1일 ~ i일 까지 지출 합

queries = [(1,2),(1,3),(2,3),(3,6),(1,7),(1,1),(7,7)]

for start, end in queries:    #구간 합 계산
    total = prefix_sum[end] - prefix_sum[start -1]
    print(f"{start}일 ~ {end}일 까지 쓴 돈 : {total:,}원")


출력:
1일 ~ 2일 까지 쓴 돈 : 37,000원
1일 ~ 3일 까지 쓴 돈 : 69,000원
2일 ~ 3일 까지 쓴 돈 : 44,000원
3일 ~ 6일 까지 쓴 돈 : 114,000원
1일 ~ 7일 까지 쓴 돈 : 156,000원
1일 ~ 1일 까지 쓴 돈 : 25,000원
7일 ~ 7일 까지 쓴 돈 : 5,000원

---

투 포인터(two pointer)

두개의 포인터로 조건에 맞는 답을 탐색하는 알고리즘

• 포인터 : 가르키는 것 이라는 뜻으로 리스트의 특정 위치를 가리키는 변수

n개의 데이터를 한 번씩 지나감으로 시간복잡도는 O(n)

데이터를 먼저 정렬 후 진행 할 경우 시간 복잡도는 O(n log n)

투 포인터 알고리즘 예시 코드

weights = [2,4,5,6,7,8]    #정렬된 무게

left, right = 0, len(weights)-1    #왼쪽 = 첫번째 인덱스, 오른쪽 = 마지막 인덱스 에서 시작
boxes = 0

while left < right:      # 두개의 무게를 짝지을 수 있을 동안 반복
    if weights[left] + weights[right] <= 10:    #10kg 이내일 경우 함께 포장
        left += 1
        right -= 1
    else:    #10kg이 넘을 경우 무거운 짐만 포장
        right -= 1
    boxes += 1

if left == right:    #1개가 남은 경우
    boxes += 1

print(f"최소 택배 수 : {boxes}개")


출력 :
최소 택배 수 : 4개