CS ﹒ Algorithm/Baekjoon
2022. 9. 1.
Java 백준 문제풀이 (38) 11659, 11660 : 구간합구하기4,5
관련이 있는 문제라서 두 개를 연달아 풀었다. 4번은 1차원 배열 구간합이라서 엄청나게 쉽고, 5번은 풀어본 경험이 있거나 머리 속에서 그림이 그려지는 사람이 아니라면 어려울 수 있다. 우선 구간 합 알고리즘이 필요한 이유는 필요할 때마다 합을 구하는 것보다 미리 누적값으로 표를 만들어놓고 가져오는 것이 효율적이기 때문이다. 만약 2차원 배열에서 매번 구간합의 구하면 O(NM)의 시간복잡도를 가지게 되지만 구간합을 미리 구해놓고 값을 꺼내오기만 한다면 O(1)로 해결되기 때문에 당연히 엄청난 차이가 날 수 밖에 없다. 크게 설명할 게 없다. 미리 더해놓고 필요할 때 꺼내되, 해당 구간에 속하지 않는 부분을 제거해주면 된다. 즉, 1차원 배열에서 구간합을 구하는 공식은 배열[x2] - 배열 [x1-1]이다..
