투 포인터(Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음

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

문제해결 아이디어

코드 구현

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1,2,3,2,5] # 전체 수열

cnt = 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:
        cnt += 1
    interval_sum -= data[start]

print(cnt)

구간 합(Interval Sum)

• 구간 합 문제: 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제

문제 설명

코드 구현

# 데이터의 개수 N과 데이터 입력받기
n = 5
data = [10,20,30,40,50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]

for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산(세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right]-prefix_sum[left - 1])