5개의 댓글이 있습니다.
-
-
VOCList -
제가 지금 책이 없어서.. 임의의 양수 배열을 가지고 아이디어만 설명해볼게요.
임의의 양수 배열 $arr[0 \ldots n - 1]$이 있습니다.
먼저 이 배열에서 부분합이 $S$가 되는 영역을 찾는 가장 단순한 코드를 살펴볼게요.for(int i = 0; i < n; i++) int sum = 0; for(int j = i; j < n; j++) { sum += arr[j]; if(sum == S) { // 찾음, [i, j] 범위의 원소들 } } }위 코드처럼 $O(n2)$ 시간만에 정답을 찾아볼 수 있습니다.
슬라이딩 윈도우는 위 코드의 개선판이라고 보시면 되는데요.
자세한 원리는 아래와 같습니다.만약 $\Sigma_{i=a}b arr[i] < S$ 라고 가정해봅시다.
그렇다면 $arr[a]$가 양수이기 때문에 $\Sigma_{i=a+1}b arr[i] < \Sigma_{i=a}b arr[i] < S$가 성립합니다.이 말은, 위 for loop에서 $i = a$ 일 때 $j = b$ 까지는 $sum < S$임을 확인했다면, $i = a + 1$일 때 $j$는 $b + 1$부터만 검사해도 무방하다는 것을 뜻합니다. 왜냐면 $j$가 $b$일 때까지, 즉 $a + 1$ 번째 원소부터 $b$번째 원소까지의 합은 당연히 $S$보다 작을테니까요.
이는 $i$가 $0$ 부터 $n - 1$까지 돌아갈 때, 각각의 $i$가 검사를 시작해야 하는 $j$의 시작 위치는 이전 루프에서 계산값을 참고하여, 굳이 확인하지 않아도 당연히 작은 부분을 건너뛸 수 있다는 것을 의미합니다.
이와 같은 기법을 사용할 때, 1차원 수직선상에 양 끝 점의 움직임을 그려보면 마치 창문을 옆으로 미는 모양새와 비슷하다 하여 Sliding window라는 이름이 붙었습니다.
코드로 표현하면 아래와 같습니다.
int end = 0, sum = 0; for(int i = 0; i < n; i++) { while(end < n && sum < S) sum += data[end++]; if(sum == S) { // 찾음, [i, end) 범위의 원소들 } sum -= data[i]; }이 때 총 시간복잡도는 $O(n)$이 되며, 그 이유는 $i$가 $0$부터 $n - 1$ 까지 도는 동안 안 쪽의 while loop의 수행 회수도 총 합이 $O(n)$이기 때문입니다.
12년 전 link
-
-
-
infoefficiency -
위에 설명해준시것은 잘 이해했습니다 정말 감사합니다 ^
그런데 책에 있는 코드가 아직 잘 이해가 안된 것 같습니다 ㅠ
예를 들어서
1,2,3,4,5,6 에서 합이 6인 부분은 (1,2,3)과 6 이 있는데 코드를 실행시키면 (1,2,3)이 부분을 세지 않더라구요 ㅠ
책 코드를 문제에 맞게 조금 변형 시킨 것입니다.int cnt=0; long long psum=0; queue <long long> psums; int k=6; int data[6]={1,2,3,4,5,6}; for(int i=0; i<n; ++i){ psum+=data[i]; psums.push(psum); while(psums.front() + k < psum) psums.pop(); if(psums.front()+k==psum) ++cnt; } cout<<cnt<<endl;순수 책의 코드는 다음과 같습니다.
int countPartialSums(int k, int n){
RNG rng;
int ret=0;
long long psum=0;
queuepsums; for(int i=0; i<n; ++i){ psum+=rng.next(); psums.push(psum); while(psums.front() + k < psum) psums.pop(); if(psums.front()+k==psum) ++ret; } return ret;}
감사합니다 ^
12년 전 link
-
-
-
infoefficiency -
네 ㅠㅠ 답변 감사합니다. 시작할 때 큐에 0을 입력 하고 해야 하는거 같기도 하고... 애매하네요ㅠ
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
infoefficiency
만약에 배열 1 2 3 4 5 6에서
합이 6인 부분을 찾는 다고 하면
코드에 있는 대로 하면
psums.front() + k < psum은
1+6 < 1
1+6 < 3
1+6 < 6
1+6 < 10
3+6<10
6+6<10
6+6<15
10+6<15
10+6 <21
으로
좌변과 우변이 같아지는 부분이 1번 나오는 것 같아요 ㅠ
그런데 연속 부분합이 6이 되는 곳은
(1,2,3) 하고 (6) 이 있잖아요 ㅎㅎ
솔직히 이 부분 구현을 정확히 이해를 한게 아니라서 질문 드리기가 좀 애매한데 설명좀 해주시면 정말 감사하겠습니다 ^
감사하니다
12년 전