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(n^2) 시간만에 정답을 찾아볼 수 있습니다.
슬라이딩 윈도우는 위 코드의 개선판이라고 보시면 되는데요.
자세한 원리는 아래와 같습니다.만약 \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)이기 때문입니다.
10년 전 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;
}
감사합니다 ^^
10년 전 link
-
-
-
infoefficiency -
네 ㅠㅠ 답변 감사합니다. 시작할 때 큐에 0을 입력 하고 해야 하는거 같기도 하고... 애매하네요ㅠ
10년 전 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) 이 있잖아요 ㅎㅎ
솔직히 이 부분 구현을 정확히 이해를 한게 아니라서 질문 드리기가 좀 애매한데 설명좀 해주시면 정말 감사하겠습니다 ^^
감사하니다
10년 전