- 정렬되지 않은 정수 배열에 중복 원소가 존재하는지 확인하는 함수
- [자주하는 실수] - < 연산자의 성질 (strict weak ordering)
1. a<a는 항상 거짓입니다. - 비반사성(irreflexivity)
2. a<b가 참이면 b<a는 거짓입니다. - 비대칭성(asymmetry)
3. a<b가 참이고 b<c가 참이면 a<c입니다. - 전이성(transitivity)
4. a<b와 b<a가 모두 거짓이면 a와 b는 같은 값으로 간주합니다. - 상등 관계의 전이성(transitivity of equivalence)
=> a와 b가 같고, b와 c가 같다면 a와 c도 같아야 합니다.
ex)
- 두 정수 집합의 포함 관계를 파악하는 잘못된 비교 함수
{1}, {2}, {2,3}
{1} < {2,3} false
{2} < {2,3} true
{1} < {2} false
{2} < {1} false
4번 성질에 의해 {1} = {2}
{1} < {2, 3} false
{2, 3} < {1} false
4번 성질에 의해 {1} = {2,3}
{1} = {2} = {2,3} ?
- 두 정수 집합의 포함 관계를 파악하는 비교 함수
a와 b가 완전히 같은 경우를 제외하고는 어느 때도 두 집합이 같다고 판단하지 않는 것입니다. 우리가 원하는 조건이 성립하지 않는 두 집합에 대해서도 별도의 순서를 정해 줘야 합니다.
※ 사실 진부분집합 확인은 의미가 없다.
- [디버깅과 테스팅] - 스캐폴딩(scaffolding)
프로그램을 테스트할 때 유용하게 사용할 수 있는 기법
알고리즘 문제 해결에서 스캐폴딩은 코드의 정당성을 확인하거나 반례를 찾는데 유용하게 쓰입니다.
reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
