글 읽기 - 정렬이 왜 가능한지 잘 모르겠습니다.

jinhan814 3년 전 3

정렬에 사용하는 비교함수는 다음의 4가지 성질을 만족해야한다고 들었습니다.

1. compare(a, a) = false (비반사성, irreflexivity)

2. compare(a, b) = true => compare(b, a) = false (비대칭성, asymmetry)

3. compare(a, b) = true && compare(b, c) = true => compare(a, c) = true (전이성, transitivity)

4. compare(a, b) = false && compare(b, a) = false => a == b (상등 관계의 전이성, transitivity of equivalence)

문제 풀이에서 bool compare(string a, string b) { return a + b > b + a; }를 비교함수로 사용해주었는데, 이 비교함수로 왜 정렬이 가능한지 잘 모르겠습니다. 1, 2번 성질은 어렵지 않게 보일 수 있었는데 3번 성질과 4번 성질을 어떻게 증명해야할까요?? 특히 4번 성질은 "101", "101101"과 같은 경우는 a != b인데 compare(a, b)와 compare(b, a)가 모두 false로 나와서 만족을 하지 않는 거 같은데 혹시 이렇게 같은 문자열이 반복되는 경우는 a == b라고 생각해야하나요??

읽어주셔서 감사합니다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main() {
	fastio;
    vector<string> v;
    /*
    풀이과정은 스포가 될 수 있을 거 같아서 생략했습니다.
    */
	sort(v.begin(), v.end(), [&](string a, string b) {
		return a + b > b + a;
	});
	for (auto i : v) cout << i; cout << '\n';
}

djm03178 3년 전 2

이게 저도 궁금했었는데, 최소 다이아 중위권 이상의 증명 난이도가 들어간다고 하는 것 같습니다. (저는 모릅니다.)

doju 3년 전 1

a를 x자리 수, b를 y자리 수라고 가정한 뒤 a + b > b + a가 나타내는 바를 수식으로 표현하고 정리해 보세요.

guillaume007 3년 전 1

재미있는 질문이네요!

문제에서 '순서'를 생각 할 때

예를 들어 입력이

2 2

101 101101

로 주어지면 답은 101101101 이겠죠?

정렬을 진행했을 때 101 101101 이 되든, 101101 101이 되든 출력이 동일하게 나옵니다.

즉 '순서' 에서는 101 == 101101 이 성립한다고 이해할 수 있을 것 같습니다.

112224 3년 전 1

제가 이해한 대로 적어보자면,

정렬에 사용하는 비교함수는 4가지 성질을 만족해야 하는 것이 맞지만(하나라도 지켜지지 않을 시 정렬이 종결되지 않음)

지금 주신 예제로 봐서는 compare(a,b)에 들어가는 parameter a,b에 대한 비교로 받아들이고 있으신 것 같습니다.

3번을 보자면 parameter인 a>b>c의 순서가 성립하는 것이 아니고, a+b>b+a && b+c>c+b 일 때, a+c>c+a 가 True라는 조건을 만족해야 합니다.

직관적으로도 참이지만, 간단한 예시를 들자면 a : x자리의 수(str) b: y자리의 수(str), c: z자리의 수(str)로 놓고 보시면 이해가 편하실 것 같습니다.

4번을 parameter가 아닌 최종적으로 비교가 이루어지는 두 값 (101+101101 과 101101+101)에 대해서 봐주시면 될 것 같습니다:)

dh0450 1년 전 0

혹시 Transitivity 증명했거나 관련 자료를 찾으셨나요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정렬이 왜 가능한지 잘 모르겠습니다.

jinhan814 3년 전 3

djm03178 3년 전 2

doju 3년 전 1

guillaume007 3년 전 1

112224 3년 전 1

dh0450 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말