[Algorithm] 스캐닝 메소드(Scanning Method)

스캐닝 메소드(Scanning Method)

• 일렬로 나열된 데이터가 주어질 때, 문제에서 요구하는 어떤 특정 구간과 그 구간의 길이를 구하고자 할 때가 있다.

 

예

• 아래와 같이 배열 a에 0 또는 1의 데이터가 주어질 때, 연속적으로 1이 발생되는 최대 구간의 길이와 그 때의 위치를 구하라.

X	1	0	1	1	0	1	1	1	1	0
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

• 구간 [1, 1]에는 연속된 1이 1개 발생되었고, 구간 [3, 4]에는 연속된 1이 2개 발생되었으며 구간 [6, 9]에는 연속된 1이 4개 발생되었다.
• 여기서 연속적으로 1이 발생되는 최대 구간은 [6, 9]이고, 구간의 길이는 4가 된다.

 

3중 for 문을 이용하여 구하기

• 다소 무식한 방법이긴 하지만, 3중 for 문을 이용하여 모든 구간을 하나씩 검사하는 방법이 있다.
• [1, 1], [1, 2], [1, 3], ..., [1, 10], [2, 2], [2, 3], ..., [2, 10], [3, 3], ..., [9, 10], [10, 10]과 같이 2개의 구간을 결정한 다음에 다시 결정된 구간을 순환하면서 1의 개수를 파악하는 방법이다.

for (int i = 1; i <= 10; i++) {
    for (int j = i; j <= 10; j++) {
        for (k = i; k <= j; k++) {
            if (a[k] == 1) {
                cnt++;
            }
        }
    }
}

• 시작 구간을 나타내는 for 문 i는 1부터 10까지 회전하고, 도착 구간을 나타내는 for 문 j는 시작 구간 이전에 올 수 없으므로 i부터 10까지 회전한다.
• 구간의 범위 i와 j가 결정되면 구간 사이의 연속된 1이 존재하는지 확인을 위한 순환문 k가 필요하다.
• 따라서 구간 [i, j]를 검사하기 위해서 k는 i부터 j까지 회전하면서 1의 개수를 카운팅한다.

 

if (j - i + 1 == cnt && max < cnt) {
    max = cnt;
    left = i;
    right = j;
}

• 1의 개수 카운팅이 완료된 다음에는 카운팅된 1의 개수와 구간의 길이가 같다면 구간 i부터 j까지는 모두 1로 채워졌다고 할 수 있다.
  • 예를 들어, 구간 [3, 5]는 3, 4, 5로 구간의 길이는 5 - 3 + 1 = 3이 되고, 카운팅된 1의 개수는 2개이기 때문에 [3, 5]는 모두 1로 채워졌다고 할 수 없다.
  • 하지만 구간 [6, 9]는 6, 7, 8, 9로 구간의 길이는 9 - 6 + 1 = 4가 되고, 카운팅이 된 1의 개수는 4개이기 때문에 구간 [6, 9]는 모두 1로 채워졌다고 할 수 있다.
• 구간 [i, j]의 구간의 길이는 j - i + 1 이 되고, 구간의 범위에서 카운팅한 1의 개수와 구간의 길이가 같다면 구간 [i, j]는 0 없이 모두 1로 채워져 있다고 판단할 수 있다.
• 그리고 cnt 값이 구간의 최대 길이 max 값을 변경할 수 있으면, max 값과 구간의 시작 위치 i와 마지막 위치 j를 변경해준다.
• 모든 순환이 완료되면 max 값은 연속적으로 1이 발생된 최대 구간의 길이가 되고, left는 최대 구간의 시작 위치, right는 최대 구간의 마지막 위치가 된다.

 

알고리즘

#include <iostream>
using namespace std;

int main() {
    int a[11] = { -1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0 };
    int cnt, max = 0, left, right;
    
    for (int i = 1; i <= 10; i++) {
        for (int j = i; j <= 10; j++) {
            cnt = 0;
            for (int k = i; k <= j; k++) {
                if (a[k] == 1) {
                    cnt++;
                }
                
                if (j - i + 1 == cnt && max < cnt) {
                    max = cnt;
                    left = i;
                    right = j;
                }
            }
        }
    }
    
    cout << left << " " << right << endl;
    cout << max << endl;
    
    return 0;
}

6 9
4

 

2중 for 문을 이용하여 구하기 (부분합(Partial Sum))

• 구간 [i, j]에 몇 개의 1이 들어있는지 확인하기 위해서 또 다른 순환 k를 회전시켜 1의 개수를 일일이 카운팅하게 된다면 모두 3중으로 된 for 문의 회전이 발생하게 된다.
• 물론 이렇게 3중 for 문을 이용하여 문제에서 요구하는 값을 구하는 것도 괜찮으나, 데이터 개수가 많아지면 상당히 많은 연산과 시간이 필요하게 된다.
• 그런데 부분합(Partial Sum) 알고리즘을 이용한다면 또 다른 순환 k를 회전시킬 필요 없이 구간 [i, j]에 들어 있는 1의 개수를 바로 카운팅할 수 있다.

X	1	1	2	3	3	4	5	6	7	7
s[0]	s[1]	s[2]	s[3]	s[4]	s[5]	s[6]	s[7]	s[8]	s[9]	s[10]

 

for (int i = 1; i <= 10; i++) {
    s[i] = s[i - 1] + a[i];
}

• s[1]에는 구간 [1, 1]의 1의 개수를, s[2]에는 구간 [1, 2]의 1의 개수를, s[3]에는 구간 [1, 3]의 1의 개수를, ..., s[i]에는 구간 1부터 i까지의 1의 개수를 s[1] 부터 s[10]까지 미리 구해 놓는다.

cnt = s[j] = s[i - 1];

• 구간 [i, j]에 있는 1의 개수를 카운팅하기 위해서 또 다른 순환이 발생하는 것이 아니라 s[j] - s[i - 1] 값을 확인한다면 구간 i부터 j까지에 있는 1의 개수를 순환문의 발생 없이 한 번의 연산으로 바로 카운팅 할 수 있다.

 

알고리즘

#include <iostream>
using namespace std;

int main() {
    int a[11] = { -1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0 }, s[11] = { 0 };
    int cnt, max = 0, left, right;
    
    for (int i = 1; i <= 10; i++) {
        s[i] = s[i - 1] + a[i];
    }
    
    for (int i = 1; i <= 10; i++) {
        for (int j = i; j <= 10; j++) {
            cnt = s[j] - s[i - 1];
            if (j - i + 1 == cnt && max < cnt) {
                max = cnt;
                left = i;
                right = j;
            }
        }
    }
    
    cout << left << " " << right << endl;
    cout << max << endl;
    
    return 0;
}

6 9
4

 

1중 for 문을 이용하여 구하기 (스캐닝 메소드(Scanning Method))

• 스캐닝 메소드(Scanning Method) 알고리즘을 이용하면 한 번의 순환으로 위에서 제시된 문제를 해결할 수 있다.
• 마치 스캐너가 시작점에서 도착점으로 전체 내용을 스캔하듯이 한 번의 순환으로 구하고자 하는 문제를 해결할 수 있다고 해서 스캐닝 메소드(Scanning Method)라고 부른다.
• 처음에 구간의 시작 위치를 결정해야 하는데, 구간의 시작 위치는 깃발을 꽂아서 표시하도록 한다. 구간의 처음 시작 위치는 1이 된다.

X	1	0	1	1	0	1	1	1	1	0
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

 

① i 값이 1일 때

• a[1] 값이 1이므로 cnt 값을 1 증가시킨다.
• cnt 값은 1이 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max보다 크므로 max 값은 1이 되고, 구간의 시작 위치는 깃발의 위치가 되고 구간의 마지막 위치는 현재의 i 값이 된다. (max = 1, left = 1, right = 1)

 

② i 값이 2일 때

• a[2] 값이 0이므로 지금까지 계산되었던 좌측 구간 [1, 1]은 의미가 없어지게 된다.
• 새롭게 출발하기 위해서 cnt 값을 0으로 초기화한 후, 깃발의 위치를 3으로 옮겨놓는다.

X	1	0	1	1	0	1	1	1	1	0
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

 

③ i 값이 3일 때

• a[3] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 1이 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 값을 변경할 수 없으므로 max 값은 그대로 유지된다. (max = 1, left = 1, right = 1)

 

④ i 값이 4일 때

• a[4] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 2가 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 보다 크므로 max 값은 2가 되고, 구간의 시작 위치는 깃발의 위치가 되고 구간의 마지막 위치는 현재의 i 값이 된다. (max = 2, left = 3, right = 4)

 

⑤ i 값이 5일 때

• a[5] 값이 0이므로 지금까지 계산되었던 좌측 구간은 의미가 없어지게 된다.
• 새롭게 출발하기 위해서 cnt 값을 0으로 초기화한 후, 깃발의 위치를 다음 위치 6으로 옮겨놓는다.

X	1	0	1	1	0	1	1	1	1	0
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

 

⑥ i 값이 6일 때

• a[6] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 1이 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 값을 변경할 수 없으므로 max 값은 그대로 유지된다. (max = 2, left = 3, right = 4)

 

⑦  i 값이 7일 때

• a[7] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 2이 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 값을 변경할 수 없으므로 max 값은 그대로 유지된다. (max = 2, left = 3, right = 4)

 

⑧ i 값이 8일 때

• a[8] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 3가 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 보다 크므로 max 값은 3가 되고, 구간의 시작 위치는 깃발의 위치가 되고 구간의 마지막 위치는 현재의 i 값이 된다. (max = 3, left = 6, right = 8)

 

⑨  i 값이 9일 때

• a[9] 값이 1이므로 cnt 값을 1 증가시킨다. 
• cnt 값은 4가 되었다. 그리고 cnt 값이 max 값을 변경할 수 있는지 확인한다.
• cnt 값이 max 보다 크므로 max 값은 4가 되고, 구간의 시작 위치는 깃발의 위치가 되고 구간의 마지막 위치는 현재의 i 값이 된다. (max = 4, left = 6, right = 9)

 

⑩ i 값이 10일 때

• a[10] 값이 0이므로 지금까지 계산되었던 좌측 구간은 의미가 없어지게 된다.
• 새롭게 출발하기 위해서 cnt 값을 0으로 초기화한 후, 깃발의 위치를 다음 위치 11로 옮겨놓는다.

X	1	0	1	1	0	1	1	1	1	0
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

 

• 이와 같은 방법으로 i 값이 1부터 10까지 단 한번의 순환만으로 연속된 1의 최대 구간의 길이와 구간의 위치를 구할 수 있다.

 

알고리즘

#include <iostream>
using namespace std;

int main() {
    int a[11] = { -1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0 }, s[11] = { 0 };
    int cnt = 0, flag = 1, max = 0, left, right;
    
    for (int i = 1; i <= 10; i++) {
        if (a[i] == 1) {
            cnt++;
        }
        else {
            cnt = 0;
            flag = i + 1;
        }
        
        if (max < cnt) {
            max = cnt;
            left = flag;
            right = i;
        }
    }
    
    cout << left << " " << right << endl;
    cout << max << endl;
    
    return 0;
}

6 9
4