μ§ν© μ°μ° κ³μ°κΈ° μ¬μ©λ²
λ μ§ν© A, Bμ μμ μμ κ΅μ§ν© ν¬κΈ°λ₯Ό μ λ ₯νλ©΄ ν©μ§ν©Β·κ΅μ§ν©Β·μ°¨μ§ν©Β·λμΉμ°¨μ§ν©μ μμ μλ₯Ό μλμΌλ‘ κ³μ°ν©λλ€. ν¬ν¨-λ°°μ μ리λ₯Ό κΈ°λ°μΌλ‘ νλ©°, νλ₯ κ³μ°μ΄λ μ§ν©λ‘ κΈ°μ΄ νμ΅μ μ μ©ν©λλ€.
μ£Όμ μ°μ° 곡μ
- ν©μ§ν© |AβͺB| = |A| + |B| β |Aβ©B|
- μ°¨μ§ν© |AβB| = |A| β |Aβ©B| (Aμλ§ μνλ μμ)
- μ°¨μ§ν© |BβA| = |B| β |Aβ©B| (Bμλ§ μνλ μμ)
- λμΉμ°¨μ§ν© |Aβ³B| = |AβͺB| β |Aβ©B|
μμ: |A|=10, |B|=8, |Aβ©B|=3μ΄λ©΄ |AβͺB|=15, |AβB|=7, |BβA|=5, |Aβ³B|=12μ λλ€.
μμ£Ό 묻λ μ§λ¬Έ
λ€. κ΅μ§ν©μ΄ 곡μ§ν©(μμ μ=0)μ΄λ©΄ λ μ§ν©μ μλ‘μ(disjoint)λΌ νλ©° κ³΅ν΅ μμκ° μμ΅λλ€.
κ΅μ§ν©μ A, Bμ λΆλΆμ§ν©μ΄λ―λ‘ min(|A|, |B|)λ₯Ό μ΄κ³Όν μ μμ΅λλ€. μ΄ κ²½μ° μ€λ₯ λ©μμ§κ° νμλ©λλ€.
λ μ§ν© μ€ μ νν νλμλ§ μνλ μμλ₯Ό μ λ μ¬μ©ν©λλ€. νλ₯ λ‘ μ XOR μ΄λ²€νΈ κ³μ°κ³Ό λμΌν κ°λ μ λλ€.