노트 #1

▶ 출처 : https://www.youtube.com/watch?v=rI8NRQsAS_s

문제1) 배열의 특정 연속된 구간을 처리하는 경우 ( 시간제한: O(n) )

ex) [1,2,3,2,5]중에서 합이 5인 '연속 수열의 개수'를 구하는 문제 

 

▶ 투 포인터를 활용한 알고리즘 코드

# 데이터 개수:n, 부분연속수열의 합: m
n = 5
m = 5
data = [1,2,3,2,5]

start = 0
end = 0
result = 0
sum_val = data[0]

end_flag=0 # end는 범위를 넘어버릴 가능성이 있으므로 while조건 체크후, flag체크후 sum_val 늘려주기

while start < n and end < n:

    if end_flag == 1:
        sum_val += data[end]
        end_flag=0

    print(start, end, sum_val)

    if sum_val < m:
        end += 1
        end_flag = 1
    elif sum_val > m:
        sum_val -= data[start]
        start += 1
        start_flag = 1
    elif sum_val == m:
        print('>>find!')
        result += 1
        end += 1
        end_flag = 1

print(result)

'''
n, m = 5, 5 # 데이터 개수:n, 부분연속수열의 합: m
data = [1,2,3,2,5]

result = 0
sum_val = 0
end = 0

for start in range(n):
    # end를 가능한 만큼 이동시키기
    while sum_val < m and end < n:
        sum_val += data[end]
        end += 1
    # 부분합이 정확히 m일때 카운트 증가
    if sum_val == m:
        result += 1
        print('현재 인덱스: start, end=', start, end)

    # 다음 start넘어가기 전에 data[start]를 sum_val에서 빼주기 
    sum_val -= data[start]

print(result)
'''

 

 

 

문제2) 구간 합 빠르게 계산하기 ( 시간제한: O(n+m) )

ex) [10,20,30,40,50]에서 Left와 Right정보가 들어왔을때 구간합 계산하기

 

▶ Prefix Sum을 활용한 알고리즘 코드

n = 5 # 데이터 개수:n
data = [10,20,30,40,50]

# Prefix Sum 배열 계산후 저장
sum_val = 0
prefix_sum = [0]
for a in data:
    sum_val += a
    prefix_sum.append(sum_val)

# left = 2, right=4 일때 구간 합 계산 ?
left = 2
right = 4

print(prefix_sum[right] - prefix_sum[left-1])