알고리즘 문제 해결 전략 - 3장

• 정렬되지 않은 정수 배열에 중복 원소가 존재하는지 확인하는 함수

• [자주하는 실수] - < 연산자의 성질 (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) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략