오늘은 배열의 부분합을 구하는 효율적인 방법에 대해 소개해볼까 합니다.
문제를 풀다보면, 배열의 부분합을 구하고 이를 비교하여 최댓값 혹은 최솟값을 찾아야 하는 경우가 발생하기 마련입니다.
난이도 있는 문제에서는 배열의 크기가 커지거나 적절한 방법을 사용하지 않으면 시간 초과가 되기도 하구요. 개발에 있어선 긴 시간으로 효율이 매우 떨어지기도 합니다.
오늘 소개하고자 하는 내용의 중심입니다 . N x N의 배열이 있을 때, 여기서 M x M의 배열의 합의 크기를 구하는 것입니다. 우리는 이 크기의 합 중 가장 큰 값 혹은 작은 값을 필요로 할 것입니다.
일반적으로 가장 많이 생각하는 방법입니다. M x M의 배열들의 합을 구하는 것이죠. 각각 계속해서 구한다면 일반적으로 O(N^2*M^2)의 시간 복잡도를 요구할 것입니다. 왜냐하면 N^2개의 배열들을 한칸한칸 움직일 때마다 M^2번 구해야 하기 때문이죠.
(물론 M의 크기가 클수록 계산해야할 수가 적어지긴 하겠지만요!)
조금 더 생각하시면 이런 생각이 가능합니다. 슬라이딩 윈도우(sliding window) 알고리즘인데요. 첫 번째 M x M의 배열의 합을 구했다면, 다음엔 추가되는 부분만 더하고, 빠지는 부분만 빼는 방식입니다.
위의 그림에선 빨강색을 더하고 노랑색을 빼는 방식이죠. M이 커질수록 보다 효율적입니다. 덧셈을 그만큼 덜하기 때문이죠. 시간 복잡도는 O(N^2*M) 정도입니다.
오늘 제가 말하고자 하는 핵심은 아래에 있습니다.
예를 들어 보았습니다. 먼저 다음과 같이 합 연산을 해줍니다. 각 배열까지의 크기의 합들을 다 더한 것입니다. 여기서 우리는 O(N^2) 번의 연산을 필요로 할 것입니다.
(힌트를 드리자면, 덧셈도 아래 알고리즘의 뺄셈 방식처럼 할 수 있습니다. 먼저 알고리즘을 이해해주세요!)
그 다음입니다. 잘 봐주세요. 우리는 각 배열의 위치에, 그 위치까지의 합을 더해 놓았습니다. 여기까지 이해가 안되시면 앞의 그림을 다시 보고 와주세요.
위의 그림에서 우리가 구하고자 하는 크기는 파랑박스 안의 M * M 합입니다.
연산은 다음과 같습니다.
파랑박스 = 빨강박스 - 노랑박스 - 녹색박스 + 보라박스
이해 되셨나요? 우리는 값의 계산을 위해 단 세번의 덧셈뺄셈 연산만을 요구로 합니다.
시간 복잡도는 O(N^2)입니다.
-
효율이 얼마나 좋은지를 따져보겠습니다.
우리가 계산해본 결과 순서대로 O(N^2*M^2), O(N^2*M), O(N^2)였습니다.
그럼 N = 10000, M = 100 정도의 작은 수로 계산해볼까요?
1초에 1억 개의 연산을 한다는 일반적인 가정을 해보겠습니다.
O(N^2*M^2) 1,000,000,000,000 = 1조 = 10000초
O(N^2*M) 10,000,000,000 = 100억 = 100초
O(N^2) 100,000,000 = 1억 = 1초
효율차이가 엄청난 것을 볼 수 있습니다. 실제로 더 큰 값을 요구로 하는 프로그램이나 문제들이 존재하니까 그런 경우 효율이 훨씬 좋아질 것입니다.
EmoticonEmoticon