728x90 구간합1 [Algorithm] Pregix Sum (누적합, 구간합) 누적합, 구간합 배열의 일부 구간에 대한 합을 빠르게 구할 수 있음 N개의 원소의 합을 구하는 경우 완전 탐색으로 구하면 O(N) 구간합으로 구하면 O(1) 1차원 배열 sum이라는 리스트를 만들어서 sum[i]에 arr[0] ~ arr[i-1] 의 합을 저장 0 부터 i 까지의 합을 구하고 싶은 경우 : sum[i+1] i 부터 j 까지의 합을 구하고 싶은 경우 : sum[j+1] - sum[i] 2차원 배열 sum이라는 리스트를 만들어서 sum[i][j]에 arr[0][0] ~ arr[i-1][j-1] 의 합을 저장 (0, 0) 부터 (i, j) 까지의 합을 구하고 싶은 경우 : sum[i+1][j+1] sum 리스트를 만드는 방법? # arr는 n*n 배열 # 1. 행단위로 더하고 열단위로 더하기 .. 2022. 9. 19. 이전 1 다음 728x90
