Colin's Blog
배열 요소의 부분 합 배열 생성하기

배열의 여러 요소들의 합을 저장하는 새로운 배열을 만들고 싶을 때, 부분 합 배열을 사용할 수 있습니다. 부분 합 배열은 원본 배열의 각 요소까지의 합을 저장하는 배열입니다.

알고리즘 설명

부분 합 배열을 생성하는 알고리즘은 간단합니다. 먼저, 빈 배열을 생성한 후, 원본 배열의 첫 번째 요소를 부분 합 배열의 첫 번째 요소로 저장합니다. 그런 다음, 원본 배열의 두 번째 요소부터 마지막 요소까지 반복하면서 이전 부분 합 배열의 요소와 현재 원본 배열의 요소를 더해서 부분 합 배열에 추가합니다. 이렇게 하면 부분 합 배열이 생성됩니다.

예시 코드

def partial_sum_array(arr):
    n = len(arr)
    partial_sum = [0] * n
    partial_sum[0] = arr[0]
    
    for i in range(1, n):
        partial_sum[i] = partial_sum[i-1] + arr[i]
        
    return partial_sum

사용 예시

다음은 사용 예시입니다.

arr = [1, 2, 3, 4, 5]
partial_sum = partial_sum_array(arr)
print(partial_sum)  # [1, 3, 6, 10, 15]

위의 예시에서 원본 배열 [1, 2, 3, 4, 5]의 부분 합 배열은 [1, 3, 6, 10, 15]입니다.

결론

부분 합 배열은 배열의 요소들의 합을 효율적으로 계산하고 저장하기 위한 유용한 자료구조입니다. 알고리즘을 사용하여 부분 합 배열을 만들 수 있으며, 이를 활용하여 다양한 문제를 해결할 수 있습니다.

참고 자료

© 2018 Colin. All rights reserved.