글의 목적

알고리즘을 잊은 미래의 나를 이해시키기 위함

투포인터

핵심: 리스트의 연속된 데이터 구간을 순차적으로 접근할 때 먼저 생각해 봐야할 알고리즘

사용이유: O(N^2)의 시간복잡도를 피하기 위함, 리스트의 모든 값을 하나하나 방문하지 않기 위함

사용예시: [1,2,3,2,5]의 리스트에서 두 값의 합이 5가 되는 경우의 수를 구할 때

원리:
1. 왼쪽 인덱스 값 고정, 오른쪽 인덱스 값은 타겟 값을 찾기 위해 한칸씩 전진
2. 타켓 찾거나, 타겟 보다 커질 경우 왼쪽 인덱스 한 칸 전진(당연히 왼쪽 인덱스 값을 현재까지 더한 값에서 빼줘야함)
3. 왼쪽 인덱스 값이 리스트의 길이보다 커질 때까지 반복

코드:

# summary: 현재까지 계산한 값
for start in range(n):
    while summary<m and end<n:
          summary+=data[end]
          end+=1
    if summary==m:
         result+=1
    summary-=data[start]

구간합

핵심: 미리 계산된 구간합을 활용한다.

사용이유: 구간합 계산에 있어 연산 횟수를 줄이기 위해 사용한다. 연산횟수를 어떻게 줄이냐? 만약 data=[10,20,30,40,50]의 데이터가 있다고 하자. 두번째~네번째까지의 구간합을 구하고 싶다. sum(data[1:5])를 하면 +연산을 3번한다. 하지만 미리 계산된 구간합 리스트를 만들어두면 단 한번의 연산으로 구간합을 구할 수 있다.

사용예시: 구간합=[0, 100, 300, 600, 1000, 1500]

원리: 각 인덱스까지의 구간합[R]-각 인덱스까지의 구간합[L-1]

코드:

data=[10,20,30,40,50]
# 0 10 30 60 100 150
summary=0 # 현재까지의 구간합
prefix_sum=[0]
for i in data:
	summary+=i
	prefix_sum.append(summary)
left=2
right=4
print(prefix_sum[right]-prefix_sum[left-1])