리스트(List)는 순서가 있고 변경 가능한 자료형 모음입니다. Python에서는 대괄호 []를 사용해 리스트를 작성하며, 인덱스 번호를 통해 각 항목에 접근할 수 있습니다. 음수 인덱싱은 뒤에서부터 시작하는 방식으로, -1은 마지막 항목을 가리킵니다. 또한 시작 위치와 끝 위치를 지정해 인덱스 범위를 설정할 수 있으며, 이 경우 지정된 항목들로 이루어진 새로운 리스트가 반환됩니다.
접두사 합(Prefix Sum)이란?
접두사 합은 리스트의 첫 번째 요소부터 해당 위치까지의 누적 합을 의미합니다. 예를 들어 [3, 4, 1]의 접두사 합은 [3, 7, 8]이 됩니다. 즉, 각 인덱스마다 처음부터 그 위치까지의 값을 모두 더한 결과를 새로운 리스트로 만드는 것입니다.
예제
아래 예제는 리스트 컴프리헨션(list comprehension)과 sum(), 그리고 리스트 슬라이싱을 조합하여 접두사 합 리스트를 생성하는 방법을 보여줍니다.
# 리스트 컴프리헨션 + sum() + 리스트 슬라이싱 활용
# 리스트 초기화
test_list = [3, 4, 1, 7, 9, 1]
# 원본 리스트 출력
print("원본 리스트 : " + str(test_list))
# 접두사 합 리스트 생성
res = [sum(test_list[:i + 1]) for i in range(len(test_list))]
# 결과 출력
print("접두사 합 리스트 : " + str(res))출력 결과
원본 리스트 : [3, 4, 1, 7, 9, 1] 접두사 합 리스트 : [3, 7, 8, 15, 24, 25]
동작 원리
range(len(test_list))를 통해 리스트의 각 인덱스 i를 순회하고, test_list[:i + 1] 슬라이싱으로 처음부터 현재 위치까지의 부분 리스트를 추출한 뒤 sum()으로 합산합니다. 이 과정을 반복하면 각 위치별 누적 합이 담긴 새로운 리스트가 완성됩니다.
대안: itertools.accumulate 활용
더 효율적인 방법으로는 표준 라이브러리인 itertools의 accumulate() 함수를 사용할 수 있습니다. 이 방식은 매번 슬라이스를 다시 계산하지 않고 한 번의 순회로 누적 합을 구하므로 성능 면에서 유리합니다.
from itertools import accumulate
test_list = [3, 4, 1, 7, 9, 1]
res = list(accumulate(test_list))
print("접두사 합 리스트 : " + str(res))
# 출력: 접두사 합 리스트 : [3, 7, 8, 15, 24, 25]