[개발]자국/[그 외]
[코드트리] Intermediate Mid - Shorten Time Technique[Prefix Sum]
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. Prefix Sum[누적합] 누적합 배열을 만들어서 시간복잡도를 줄인다. 특정 배열이 주어졌을 때, 그 배열을 통해서 배열의 값들에 대해 누적된 합을 '누적합 배열'에 저장한다. '누적합 배열'의 인덱스가 올라갈 때마다, 원래 주어진 특정 배열에서 접근하는 값의 인덱스도 올라간다. Ex) 특정한 배열이 주어졌을 때, 단순하게 0번부터 현재 인덱스까지의 합을 누적합 배열에 넣는다고 가정하자. 그렇다면, 특정 배열의 값이 1 3 7 11 23 이렇게 주어진다면, 누적합 배열은 1 4 11 22 45 이렇게 배열이 구성된다. 누적합 배열[0]=특정 배열[0],누적합 배열[1]=특정 배열[0]+특정 배열[1], 누적합 배열..
