mondegreen

[Part1-Chapter06-Clip01] 구간 합 계산 시 누적합 배열을 활용한다면 해당 인덱스로 접근하여 한 번에 연산이 가능하기 때문에 시간 복잡도가 현저히 낮아진다. 해당 특정 배열의 원소가 갱신된다면 해당 원소의 인덱스부터 그 이후 모든 누적합 원소에 수정이 필요하기 때문에 배열의 길이인 N만큼 순회해야 하므로 시간 복잡도는 O(N) 이다. 만약 갱신하는 것을 반영해 구간합을 구한다면 누적합 배열을 사용한다 하더라도 시간 복잡도가 크게 낮아지지 않는다는 것을 알 수 있다. - 백준 11659 구간 합 구하기 4 한 달 전에도 풀었던 문제인데 시간 초과 때문에 Scanner 대신에 BufferedReader와 StringTokenizer를 사용했고 String 대신 StringBuilder를 사..