[코이] 수열

IOI korea 공식 유튜브 영상 링크

https://www.youtube.com/watch?v=uH9VJRIpIDY

 

문제 링크

https://www.codeup.kr/problem.php?id=4726 <-- CodeUp

https://www.acmicpc.net/problem/2559 <-- BAEKJOON

 

deque reference

https://www.cplusplus.com/reference/deque/deque/

 

목차

1. Native한 구현 ( TLE )

2. 덱을 이용한 sliding window 해법 ( AC )

 

1. Native한 구현

계산량 O(n^2) 로 해결하는 방법이다. 문제에서도 보이지만 n이 100000이므로 n^2 를 하게되면 계산량이 1초를 넘어가게 된다.

 

짜는 방법은 그냥 다 해보는 코드를 짜면 된다. 2중 반복문을 통해서 합계를 구간마다 다 구해준 다음에 비교하는 방법이다.

 

여기서 주의해야할 점은 바로 반복문의 범위인데, [1, n] 의 범위에서 반복문을 돌릴 경우 범위에 맞지 않는 불필요한 연산이 존재하게 된다. 따라서 [1, n-k+1] 의 범위 내에서 돌려야 한다. 그리고 합을 구하는 과정에서도 그냥 돌리면 범위 외의 불필요한 연산도 연산을 해 버리므로 [i, min(i+k-1, n)] 의 범위에서 연산해야 한다.

 

글쓴이는 이 과정에서 vector에 다 때려 넣고 정렬을 때리는 방법을 사용하였다.

 

코드는 다음과 같다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int n, k, d[100010];
vector<int> V;

int min(int a, int b) { return a<b?a:b; }

int main()
{
  scanf("%d%d", &n, &k);
  for(int i=1; i<=n; i++)
    scanf("%d", &d[i]);

  for(int i=1; i<=n-k+1; i++)
  {
    int sum = 0;
    for(int j=i; j<=min(i+k-1,n); j++)
      sum += d[j];
    V.push_back(sum);
  }

  sort(V.begin(), V.end());

  printf("%d", V[V.size()-1]);

  return 0;
}

위에서도 말했지만 시간복잡도가 O(n^2) 이므로 100억 이상의 연산이 발생한다. 시간 초과가 나는 것은 당연하다.

 

2. deque를 이용한 sliding window 해법

아직까지 위 영상을 보고 오지 않았다면 꼭 보고 오길 바란다.

 

위 영상을 보고 왔다면 이 문제가 sliding window 기법을 써서 O(n) 에 해결하는 것이 가능하다는 감이 올 것이다.

 

합을 계속 비교해 주는 코드를 짜면 된다. 이 문제를 sliding window 로 구현하는 것은 그렇게 어렵지 않을 것이지만, 언제 sum 을 연산해서 비교해 줄 것인지에 집중해서 코드를 짜 주어야 한다. 수가 2개 들어오고 범위가 2개인 경우와 범위가 1인 경우 등을 생각하여 짜면 다음과 같은 결과물이 나온다.

if(i >= k)
{
  if(i > k)
  {
    sum -= D.front();
    D.pop_front();
  }
}

i >= k 라는 조건문을 걸어준 이유는 입력되는 수와 범위가 같은 경우를 생각해 주기 위함이고 i > k 인 경우 합을 비교해 주어야 하므로 위와 같은 코드를 짜게 되었다. 그리고 vector 에 넣는 이유는 합 비교 연산 순위 생각하기 귀찮아서 그냥 정렬 때려 버리기 위함이다. 비교 순서도 한번 생각해 보는 것을 추천한다.

 

이렇게 코드를 완성시켰다면, O(n) 의 시간복잡도 안에 문제를 해결한 것이다.

 

전체 코드는 다음과 같다.