배열의 모든 요소가 같은 부호를 갖고 있는지 판단하기

   해결해야 하는 문제는 배열(container)에 있는 모든 요소(실수 형)가 같은 부호를 갖고 있는지를 판단하는 것이다. 가장 직관적인 방법은 아마도 다음과 같을 것이다.

bool all_value_have_same_sign(const std::vector<double>& value)

{

        if(value.empty() == true) return false;

        if(value.size() == 1) return true;

        bool is_negative = (value[0] < 0);

        bool is_positive = (value[0] > 0);

        std::vector<double>::const_iterator pos = value.begin() + 1;

        for(; pos != value.end(); pos++){

                is_negative &= (*pos < 0);

                is_positive &= (*pos > 0);

                if(is_negative == false && is_positive == false) return false;

        }

        return true;

}

즉, 배열의 모든 원소를 차례대로 순회를 하는데, 한 변수 (위 코드에서 is_negative)는 지금까지의 값들이 음수였는지를 기록하고, 또 다른 변수 하나 (위 코드에서 is_positive)는 지금까지의 값들이 양수였는지를 기록하는 것이다. 만약 이 두 변수가 모두 false가 되면 부호가 다른 값을 만나는 것이 된다. 왜냐 하면, 다음과 같기 때문이다.

P1: 모든 원소가 양수이다.
Q1: is_positive는 true이다.

P2: 모든 원소가 음수이다.
Q2: is_negative는 true이다.

로 두면 명제 "P1 또는 P2 이면 Q1 또는 Q2 이다"의 대우는

" NOT(Q1 OR Q2) 이면 NOT(P1 AND P2)이다"

이고, 이것은, 다시

"NOT Q1 AND NOT Q2 이면 NOT P1 OR NOT P2이다"

가 된다. 따라서,

" is_positive와 is_negative가 둘 다 false 이면 (모든 원소가 양수는 아니고) 혹은 (모든 원소가 음수는 아니다) " 가 된다. 즉,
" is_positive와 is_negative가 둘 다 false 이면 (양수 중에 음수가 적어도 하나 있다) 혹은 (음수 중에 적어도 하나 양수가 있다)" 가 되고, 이것은 결국
" is_positive와 is_negative가 둘 다 false 이면 양수와 음수가 섞여 있다"
가 되기 때문이다.

두 번째 아이디어는 인접한 두 요소의 부호가 같은지만을 판단하는 것이다.

bool all_value_have_same_sign(const std::vector<double>& value)

{

        if(value.empty() == true) return false;

        if(value.size() == 1) return true;

        bool is_negative = (value[0] < 0);

        std::vector<double>::const_iterator pos = value.begin() + 1;

        for(; pos != value.end(); pos++){

            if(is_negative != (*pos < 0)) return false;

            is_negative = (*pos < 0);

        }

        return true;

}

이것에 대한 증명은 다음과 같다.

원소가 (v1, ..., vn) 이 있을 때, sign(v_i) == sign(v_{i+1}) for all i = 1, ..., n-1 only if sign(v_i) == sign(v_j} for all 1 <= i, j <= n 이 맞는지를 확인해 보면 된다. Let sign(v_i) == sign(v_{i+1}) for all i = 1, ..., n-1 (1). Suppose that ∃ i < j such that sign(v_i) ≠ sign(v_j). If i - j = 1, then it contradicts to (1). Therefore, there must be (a_1, ..., a_m) such that i < (a_1, ..., a_m) < j. By (1), sign(v_i) == sign(v_{a_1}). By the induction, sign(v_{a_m}) == sign(v_j), which is contradiction. Q.E.D.

조금 쉽게, 다시 설명하면, 우리가 알아 보고자 하는 것은, 모든 인접한 두 원소의 부호가 같을 때, 전체 원소가 모두 같은 부호를 갖고 있는가? 이다. 즉, i 번째 부호와 i+1 번째 부호가 모든 i 에 대하여 같았을 때, 어느 두 원소를 선택해도 부호가 같을 것인가? 이다. 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같았는데(1), 어느 두 원소를 뽑았더니 부호가 다른 원소가 있었다고 가정해 보자. 그 각각의 원소의 인덱스를 a 와 b라고 하고, a 가 더 작은 값이라고 하자. 만약 a == b + 1 이었다면 (1)에 모순되기 때문에 말이 안되므로 a 와 b 사이에는 몇 개의 정수가 들어 갈 수 있게 되서, (a, a+1, ..., b-1, b) 의 sub-sequence를 만들 수 있게 된다. (1)에 의해 a 번째와 a+1 번째 원소의 부호는 같아야 하며, 같은 식으로 계속 해나가다 보면 b-1번째와 b번째의 부호도 같아야 하고, 따라서 a 번째부터 b번째의 원소의 부호는 모두 같다. 그런데 이것은 가정에 모순이므로, 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같았는데, 어느 두 원소를 뽑았더니 부호가 다른 원소가 있을 수는 없다. 즉, 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같다면 모든 원소의 부호가 같다.

그런데, 좀 더 생각을 해보면, 아주 간단하게는 모든 원소의 부호가 첫 번째 원소의 부호와 같으면 된다. 증명은 쉽고, 코드도 쉽다... >.<"" 어려운 문제인 줄 알았는데... ㅋㅋㅋ 두 실수 (a,b)에 대하여 relation R을 부호의 같음으로 정의하면 R은 equivalence relation 이 되기 때문에.