5개의 댓글이 있습니다.

• 
  VOCList

  제가 지금 책이 없어서.. 임의의 양수 배열을 가지고 아이디어만 설명해볼게요.

  임의의 양수 배열 arr[0 \ldots n - 1]$arr[0 \ldots n - 1]$이 있습니다.
  먼저 이 배열에서 부분합이 S$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)$O(n^2)$ 시간만에 정답을 찾아볼 수 있습니다.

  슬라이딩 윈도우는 위 코드의 개선판이라고 보시면 되는데요.
  자세한 원리는 아래와 같습니다.

  만약 \Sigma_{i=a}^b arr[i] < S$\Sigma_{i=a}^b arr[i] < S$ 라고 가정해봅시다.
  그렇다면 arr[a]$arr[a]$가 양수이기 때문에 \Sigma_{i=a+1}^b arr[i] < \Sigma_{i=a}^b arr[i] < S$\Sigma_{i=a+1}^b arr[i] < \Sigma_{i=a}^b arr[i] < S$가 성립합니다.

  이 말은, 위 for loop에서 i = a$i = a$ 일 때 j = b$j = b$ 까지는 sum < S$sum < S$임을 확인했다면, i = a + 1$i = a + 1$일 때 j$j$는 b + 1$b + 1$부터만 검사해도 무방하다는 것을 뜻합니다. 왜냐면 j$j$가 b$b$일 때까지, 즉 a + 1$a + 1$ 번째 원소부터 b$b$번째 원소까지의 합은 당연히 S$S$보다 작을테니까요.

  이는 i$i$가 0$0$ 부터 n - 1$n - 1$까지 돌아갈 때, 각각의 i$i$가 검사를 시작해야 하는 j$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)$O(n)$이 되며, 그 이유는 i$i$가 0$0$부터 n - 1$n - 1$ 까지 도는 동안 안 쪽의 while loop의 수행 회수도 총 합이 O(n)$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;
  queue psums;

  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

• 
  Being

  맨 앞에 0이 있어야 첫 번째 원소까지 포함시키는 부분합이 제대로 나올 것 같네요. 지금 책이 없어서 어느 쪽 문제인지는 확인이 어렵습니다.

  
  10년 전 link

• 
  infoefficiency

  네 ㅠㅠ 답변 감사합니다. 시작할 때 큐에 0을 입력 하고 해야 하는거 같기도 하고... 애매하네요ㅠ

  
  10년 전 link

• 
  JongMan

  이 링크 를 봐주세요. ^^; 혼란을 드려 죄송합니다.

  
  10년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.