알고리즘/누적합1 누적합이란 무엇인가? 누적합을 알기 전... 이 알고리즘을 접하기 전에는 for문을 통해 리스트를 순회하며 전부 하나하나씩 더하거나, 파이썬 내장함수인 sum을 이용해 합을 구하고는 했다. 하지만 이런 방식은 시간 복잡도상 치명적인 결함을 가지고 있다. 일단 for문으로 리스트를 일정 구간만큼 순회해야하는 시간복잡도 O(N) 그리고 순회해서 일정 구간에대한 연산 M번. (sum또한 같은 시간복잡도를 지닌다) 총 시간복잡도는 O(NM)이 되게 되는데, 만약 전체를 더해야한다면 , M은 N이 되고 최악의 경우 O(N^2)의 시간복잡도를 지닌다. 누적합이란 무엇인가? 하지만 만약 배열의 특정 구간을 더해야 한다면, 그 배열의 데이터가 변하지 않는 이상, 특정구간까지의 합은 변할 가능성은 없다. 즉 [0]~[1] 의 합은 쭉 그 값.. 2023. 4. 6. 이전 1 다음
