prefix_sum 알고리즘을 이용한 문제풀이

2019-02-11

.

1

  • 최초 누적합문제 풀이
# 최초 누적합문제
def solution(data, queries):
    
    result_list = []
    
    for start, end in queries:
        result_list.append(sum(data[start-1:end]))
        
    return result_list

## 문제에서 주어진 테스트 코드

N = 5
M = 5
data = [10, 20, 30, 40, 50]
queries = [[1, 3], [2, 4], [3, 5], [1, 5], [4, 4]]

solution(data, queries)

[60, 90, 120, 150, 40]
  • 문제식별 : 최악의 조건에서 프로세싱 속도가 저하되는 현상
import time
from random import randint

N = 100000
M = 10000

data = [randint(1,N) for _ in range(N)]
queries = [sorted([randint(1,N), randint(1,N)]) for _ in range(M)]

%%time
result = solution(data, queries)

Wall time: 10.5 s
  • 문제해결 : prefix_sum을 이용한 문제 재풀이
# 메인문제
def solution(data, queries):
    
    result_list = []
    acc_list = [0]
    acc_num = 0

    for element in data:
        acc_num += element
        acc_list.append(acc_num)
        
    for start, end in queries:
        result_list.append(acc_list[end]-acc_list[start-1])
        
    return result_list

## 문제에서 주어진 테스트 코드

N = 5
M = 5
data = [10, 20, 30, 40, 50]
queries = [[1, 3], [2, 4], [3, 5], [1, 5], [4, 4]]

solution(data, queries)

[60, 90, 120, 150, 40]

import time
from random import randint

N = 100000
M = 10000

data = [randint(1,N) for _ in range(N)]
queries = [sorted([randint(1,N), randint(1,N)]) for _ in range(M)]

%%time
result =solution(data, queries)

Wall time: 21.8 ms