Prefix1 [알고리즘] 누적합 prefix sum 누적합? 누적 합(prefix sum) 알고리즘은 계산양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘 입니다. 예를 들어 1.그냥 더하기 arr[0]~arr[5]까지 입력을 받은 후, arr[0]부터 arr[5]까지 합을 구해야 될때 5번 더하기를 해야 합니다. 2.누적합 이용 누적합을 이용하면 arr[0]~arr[5]에 각각 누적합을 더해서 넣어 줍니다. 그 후에, arr[0]부터 arr[5]까지 합을 구하려면 따로 연산없이 바로 바로 불러 올 수 있습니다. arr[0]~arr[5]의 합은 arr[5] 또한 arr[2]~arr[5]의 값 또한 arr[5] - arr[1]계산 1번을 통해 구할 수 있습니다. 얼핏 보면 시간차가 별로 안날 수도 있다고 생각할 수도 있지만, ex) 배열 수가 매우 .. 2022. 4. 5. 이전 1 다음 반응형
