슬라이딩 윈도우 알고리즘 : 2개의 커서가 중요하다.

 제가 응원하는 롯데랑 키움 경기 보느라 지금 글을 씁니다. 둘이서 경기하면 어떻게 하냐고요? 그건 좀 난감한 질문이네요. 뜬금없이 야구 이야기를 하다니. 오랫만에 ps에서 쓸 법한 알고리즘을 해 보겠습니다. 슬라이딩 윈도우라고, 코테에서 은근히 나오는 친구가 하나 있습니다. 톡에서도 질문을 받았었고요. 그것만 잠깐 해 보도록 하겠습니다.

 

---

 아래의 문제를 생각해 보겠습니다.

 

 

 길이가 n인 배열이 있습니다. 이 중에서 (부분 순서하고는 다른) 부분 배열을 뽑을 건데 제가 좋아하는 팀인 롯데는 1번 이상, 키움은 2번 이상 나와야 합니다. 그러한 조건을 만족하는 최소 부분 배열의 길이는 어떻게 될까요? 라는 문제를 생각해 보겠습니다. 일단 brute한 해결책을 먼저 생각해 보겠습니다.

 

 

 0번 인덱스를 기준으로 보면, 5번 인덱스까지 보아야 합니다. 0번부터 5번까지를 보면, 롯데가 2번, 키움이 2번 나왔으니까, 조건을 만족하기 때문입니다. 0번부터 4번까지만 보면, 롯은 2번이 나오지만 키는 1번밖에 나오지 않기 때문에, condition을 만족하지 않습니다.

 

 다음에 1번째 인덱스를 보겠습니다.

 

 

 이 경우에도, 5번째 인덱스까지 가야 합니다. 마찬가지 이유입니다. 롯이 1번 이상 나오고, 키가 2번 이상 나타나는 최초의 지점이기 때문입니다. 2번째로 가 보겠습니다.

 

 

 아무리 뒤져봐도 2번째 원소부터 선택한 부분 배열의 경우에는, 키가 2번 이상 나오지 않습니다. 어떻게 선택하던지요. brute하게 탐색한다면 최악의 경우에, 배열의 길이가 n이라면, 한 location당, 배열의 끝까지 탐색을 해야 합니다. location이 총 n개이기 때문에, 최악의 경우에 거의 (n(n-1))/2만큼의 탐색을 해야 합니다. 일례로, '자이언츠'가 1번 이상 나오는 부분배열 중 가장 짧은 길이를 찾으라고 하고, 이런 식으로 배치되어 있다면 어떨까요?

 

 

 0번째 원소에서 출발해 봅시다. 아. 롯데가 맨 끝에 있군요. 끝에까지 가야겠네요.

 

 

 1번째 위치부터 출발해 보도록 하겠습니다. 그런데, 아. 또 맨 끝에 목표물이 있군요. 또 끝까지 가야 합니다. 좀 비효율적인 듯 싶습니다. 어떻게 하면 비효율적인 작업을 효율적으로 개선할 수 있을까요?

 

 

---

 당연한 사실 하나를 관찰해 보겠습니다.

 

 예를 들어보겠습니다.

 

 예를 들어 위와 같은 배열에서 3번째 위치에, 기아는 0번 나타났습니다. -1번 나타나지 않았습니다. -2번 나타나지 않았습니다. 0번 나타났습니다. 대신에, 히어로즈는 1번 나타났습니다. 기아는 0번 나타났지만, 3번째 위치에 키움은 1번 나타났습니다. 임의의 위치인 3번째에 특정한 문자열은 0번, 또는 1번 나타난다는 이야기는 이런 소리입니다.

 

 그러면 당연하게도 아래가 성립합니다.

 

 구간 [s,e]에 구간 [s',e']이 포함되는 그림인데. 정말 그럴까요? 일단 3가지 케이스로 나누어서 생각해 보겠습니다. 먼저, s=s'이고, e=e'이면 생각할 필요도 없습니다. s=s'이고 e'<e인 경우에는 어떨까요?

 

 

 제가 구간을 단순화 해서 그려보았습니다. s=s'이고 e'<e입니다. 그러면 구간 [s', e']은 보라색 구간일 거고, 구간 [s, e]는 보라색 + 연두색 구간일 겁니다. 중요한 것은, 임의의 위치에 특정한 문자열 S가 나타나는 횟수는 0 아니면 1입니다. 그렇다면, e'+1번째 위치부터, e번째 위치까지 특정 문자열 S가 나타나는 횟수는 최소한 0보다 크거나 같을 겁니다. k는 보라색 + 연두색의 합, k'은 보라색의 합입니다. 당연하게도 연두색 부분에서 문자열 S가 나타나는 횟수는 0보다는 크거나 같습니다. 따라서, k'은 k보다 작거나 같습니다.

 

 s<s'이고 e'=e라면 어떨까요?

 

 

 구간 [s,e]는 연두색 + 보라색으로 표현할 수 있습니다. 구간 [s',e']는 보라색으로만 표현할 수 있습니다. 구간 [s,e]는 [s',e']에다가 연두색 부분을 더한 것입니다. 연두색 구간에 S가 나타나는 횟수는 0보다는 크거나 같으므로, k'은 k보다 작거나 같습니다. s<s'이고, e'<e라면 어떨까요?

 

 

 [s', e']은 보라색 구간을, [s, e]는 연두, 보라, 노란색 구간을 의미합니다. 당연하게도 연두색이랑 노란색 구간에서 S가 출현하는 빈도는 0보다 크거나 같으니 k'은 k보다 작거나 같습니다. 이 당연한 결과를 가지고 어떤 알고리즘을 설계할 수 있을까요?

 

 

---

 다시, 문제로 돌아와서 키가 2번 이상, 롯이 1번 이상 나타나는 부분 배열 중 최소 길이를 찾아보겠습니다.

 

 

 0번째부터 시작했을 때, 4번째까지 가야, 조건을 만족합니다. 0번째부터 시작했을 때, 5번째까지 가 볼 필요가 있을까요? 아니면 6번째, 7번째까지 갈 필요가 있나요? 그럴 필요 없습니다. 왜냐하면, [0,4]는 [0,5]나 [0,6]에 포함되기 때문입니다. 그리고 [0,4]에서 이미 롯이 1번 이상, 키가 2번 이상 나왔기 때문에, 더 이상 가 볼 필요가 없습니다. 이것을 s의 위치는 0, e의 위치는 4에 있다고 칭하겠습니다.

 

 이 때 어떻게 할 거냐. s를 하나 증가시킵니다.

 

 

 이 경우는, s가 1이고 e가 4인 상황입니다. 부분 배열 [1,4]에는 롯이 2번 나오지만 키는 1번 나옵니다. 여기서 이런 의문이 들 수 있습니다. 물론, [1,4]는 조건을 만족하지 않지만, 이 상황에서 [1,3]이나 [1,2]는 만족할 수도 있지 않을까? 그런데 잘 생각해 보면, 이것은 당연하게도 아님을 알 수 있습니다.

 

 

 왜냐하면, 임의의 위치에서 히어로즈나 롯데가 나오는 빈도가 0 아니면 1이기 때문입니다. 예를 들어, [1, 3]인 경우에는 [1, 4]에서 구간 [4, 4]가 빠졌는데요. 구간 [4, 4]에는 공교롭게도 키움이 있었습니다. 설령 키움이 없었다고 하더라도, 상황이 변하지 않는다는 것은 말할 수 있습니다.

 

 그렇기 때문에, s를 한 칸 증가시킨 다음에, 조건을 검사했을 때 만족하지 않는 경우에는 e를 1칸 증가시켜야 합니다.

 

 

 그러면 이 경우에, [1, 4]에서 [1,5]로 증가했습니다. 즉 e가 4에서 5로 하나 증가한 셈입니다. 이 때, 롯의 갯수는 2, '키'의 갯수도 2이니, 조건을 만족하네요. [1,6], [1,7] 이런 것은 볼 필요도 없음을 알 수 있습니다. 그러면 s가 1일 때, e가 5가 되니, 구간 [1,5]를 후보해에 넣은 다음에 s값을 하나 증가시킵니다.

 

 

 s=2, e=5입니다. 이 경우에는 condition을 만족하나요? 네. s=2이고, e=5인 후보해도 고려 대상에 넣으면 됩니다. [2, 6], [2,7] 등은 볼 필요조차 없음을 알 수 있습니다. s를 하나 증가시켜봅시다.

 

 

 s=3이고 e=5인 상황입니다. 조건을 만족하나요? 아닙니다. 따라서, e를 계속 증가시킵니다.

 

 

 계속 증가시켰는데도 답이 안 나옵니다. 구간 [3,8]인 경우에 만족하는 경우가 없습니다. 그러면 어떻게 하면 될까요? 끝내면 됩니다. e는 끝까지 갔습니다. 구간 [3,8]에서 만족하지 않는데, [4,8], [5,8]이 condition을 만족할 리가 없기 때문입니다. 후보해들 중에 제일 작은 구간을 가지는 부분 배열의 길이는 4라고 답하시면 됩니다.

 

 그러면 시간 복잡도는 어떻게 될까요? s도 감소를 하지 않고 계속 증가하고, e도 계속 증가하고 감소를 하지 않기 때문에, n이 배열의 길이라고 한다면, O(n)입니다.

 

 

---

 제가 언급한 알고리즘이 만능인 거 같습니다. 그런데, 이러한 방법을 쓰면 안 되는 경우가 있습니다. 부분합이 4 이상인 부분 배열의 최소 길이를 구해야 한다고 생각해 보겠습니다.

 

 그런데, 배열 안에 음수가 들어갈 수도 있습니다. 어떻게 해야 할까요? 위에서 설명한 대로 풀어도 될까요? 그렇게 풀어 보겠습니다. 일단, 0번째 위치부터 보았을 때, -3 + 2 + 3 + 3을 하면 4니까, 0번째부터 보았을 때에는 [0, 3]을 뽑아야 될 겁니다. 조건을 만족하니까, 그 다음에 s를 하나 증가시킵니다.

 

 

 다음에 1번째 부터 보았을 때, 3번째 까지 합은 2 + 3 + 3 = 7입니다. 7은 4보다 크거나 같으므로 조건을 만족합니다. 그러니, 1번째 위치부터 출발하였을 때 부분합이 4 이상인 최소 길이는 3이다. 라고 하면 될 건데요. 위에 있는 슬라이딩 윈도우에 따르면 말입니다. 그런데, 사실은

 

 

 1번째 위치부터 보았을 때에는, 2번째까지만 선택해도 4보다 크거나 같음을 알 수 있습니다. 이는 s<=s'이고 e'<=e일 때, 구간 [s,e]의 합이 구간 [s',e']의 합보다 크거나 같다는 보장을 할 수 없기 때문입니다.