Runtime 오류
정렬관련 문제를 풀기위해(해당 문제 링크) 정렬함수를 작성하다가 이상하게 Runtime 오류가 발생하여 그 이유를 찾아보았는데, 정렬함수 작성시에는 Strict weak Ordering 규칙을 반드시 지켜야한다는 내용의 글을 보게 되었다.
Strict weak Ordering은 어떤 값들에 대해 대소관계를 규정할 때 모순이 발생할 수 있는 상황과 그런 상황을 방지하기위해 지켜야하는 규칙에 관련된 내용이었다.
그래서 찾아본 내용에 맞게 한 번 코드를 수정해 제출해보니 Runtime 오류 문제가 정말 없어지는 걸 볼 수 있었다.
<오류코드>
bool compare(vector<int> &a, vector<int> &b) {
if(a[0] < b[0]) return false;
else if(a[0] == b[0]){
if(a[1] < b[1]) return false;
else if(a[1] == b[1]) {
if(a[2] < b[2]) return false;
else if(a[2] == b[2]) {
if(a[3] != K) return false;
}
}
}
return true;
}<수정한 코드>
bool compare(vector<int> &a, vector<int> &b) {
if(a[0] > b[0]) return true;
else if(a[0] == b[0]){
if(a[1] > b[1]) return true;
else if(a[1] == b[1]) {
if(a[2] > b[2]) return true;
else if(a[2] == b[2]) {
if(a[3] == K) return true;
}
}
}
return false;
}처음 오류가 난 나의 코드는 if문 조건을 빠져나오면 전부 true로 귀결되어 버렸는데 이 과정에서 Strict Weak Ordering 규칙을 어기는 경우가 생겼다.
확실히 이렇게 알고보니 내 코드처럼 조건을 빠져나가면 결국 true로 귀결되는 코드는 Strict Weak Ordering 규칙을 어기기 쉬운 환경이 되어버리는 것 같더라.
애시당초 내가 직접 return 값에 true와 false를 지정해주는 것보다는, 아예 부등호 연산을 return 값으로 주어 계산 판단을 컴퓨터에게 맡기는 것이 더 나은 것 같다.
Strict Weak Ordering
Strict Weak Ordering는 수학의 순서론에서 다루는 여러 규칙들과 그 형식에 관한 내용이다.
두 수에 관한 비교함수를 작성할 때 Strict Weak Ordering을 준수해야한다는 것은 결국 모순을 일으키지 않게 순서론에서 말하는 규칙들을 지키라는 것이다.
Strict Weak Ordering이 말하는 조건규칙은 총 4가지가 있다.
어떤 값 a,b,c 들에 대해서
1) comp(a,a)는 false를 return
--> a > a 가 true가 되는 것은 모순2) comp(a,b) = true이면 comp(b,a)는 false를 return
--> a > b 가 true인데 b > a 가 true가 되는 것은 모순3) comp(a,b) = true, comp(b,c) = true이면 comp(a,c)는 true를 return
--> a > b , b > c가 true인데 a > c 가 false가 되는 것은 모순4) comp(a,b) = false, comp(b,a) = false이고 comp(y,c) = false, comp(c,y) = false이면 comp(a,c)와 comp(c,a)도 모두 false를 return
--> a > b 가 false이고 b > a가 false라는 것은 a == b 라는 것을 뜻함
즉 a == b이고 b == c 인데 a != c가 되는 것은 모순
위 조건에 따르면 a와 b에 같은 값이 들어왔을때(Case comp(a,a)) 무조건 false가 return 되어야 한다.
그런데 런타임 오류가 났던 나의 첫번째 코드를 보면 a와 b의 값이 동일한 경우 if 조건들을 다 벗어나고 결국 true로 return 되버리는 경우가 존재하는 것을 알 수 있다.
그 부분에서 모순이 존재헀고 오류가 났던 것이었다.
Compare 함수에 대한 여담
C++ sort 함수가 받는 사용자 지정의 Compare 함수는 리턴값이 true면 첫번째 인자가 두번째 인자보다 앞에 있다고 판단한다.
(즉 만약 return a > b 이면, a가 b보다 큰값일 때 항상 true를 리턴하므로 a가 b보다 앞에 온다. 내림차순이라는 의미)
(예를들어 a가 5 , b가 3이라고 하면 return 5 > 3 이므로 return 값은 true가 될 것이다. 따라서 첫번째 인자인 5가 3 앞에 있다고 판단될 것이다. 즉 5 3 순으로 정렬이 진행될 것이고 이것은 내림차순이다)
(참고출처)
https://www.boost.org/sgi/stl/StrictWeakOrdering.html
https://panty.run/strict-weak-ordering/
