[윤용호]

Except of cond * cond 를 허용할 경우 문제를 풀 수 없을 뿐만 아니라

문제의 정의조차 애매해지게 됩니다.

예를 들어,
A={1}∪(B-C)
B={2}∪A
C={3}∪D
D={4}∪(B-C)

이런 조건을 받았다고 생각해 봅시다. (조카는 네명이라고 칩시다)

1. 수업시간에 배운 알고리즘을 적용할 경우.

다음과 같은 sequence의 해를 얻게 됩니다.

pass 1 : 0 / 0 / 0 / 0
pass 2 : 1 / 2 / 3 / 4
pass 3 : 12 / 12 / 34 / 24
pass 4 : 12 / 12 / 234 / 124
pass 5 : 1 / 12 / 1234 / 14
pass 6 : 1 / 12 / 134 / 4
pass 7 : 12 / 12 / 34 / 24

pass 7과 pass 3에서 같은 해가 나오지만 나란히 두 번 같은 해가 나온 것이 아니므로

무한 루프를 돌며 종료하지 않게 됩니다. 즉, 문제를 풀 수 없습니다.


2. 약간 변형된 알고리즘을 사용할 경우.

shopping list에 아이템을 '추가'하기만 한다고 생각해서 문제를 푼다고 생각해봅시다.

즉, 저렇게 무한루프를 돌게 되더라도

최종적으로 모든 해의 union을 하면 해가 될것이라 생각하고

애초에 다음 pass에서 새로운 해를 얻을때 기존의 해에 '추가'만 한다고 생각하는 것입니다.

그럼 해에서 있던 아이템이 빠질 일은 없을테니 적어도 무한루프를 돌지는 않게 됩니다.

(수업시간에 선물 문제를 마칠 즈음 있었던 질문이 이 알고리즘이었다고 생각합니다)

여기에 그 방법을 적용하여봅시다.

pass 1 : 0 / 0 / 0 / 0
pass 2 : 1 / 2 / 3 / 4
pass 3 : 12 / 12 / 34 / 24
pass 4 : 12 / 12 / 234 / 124
pass 5 : 12 / 12 / 1234 / 14 <-
pass 6 : 12 / 12 / 1234 / 14

이렇게, 처음과 달리 pass 5에서 A의 선물 리스트에서

2가 빠지지 않으면서 pass 6에서 종료할 수 있습니다.

A={1,2}
B={1,2}
C={1,2,3,4}
D={1,4}

이 해가 주어진 조건을 만족하는지 보겠습니다.

A={1}∪(B-C) = {1}∪({1,2}-{1,2,3,4})={1} ⊂ {1,2} , 즉 A는 불만이 없습니다.
B={2}∪A = {2}∪{1,2} = {1,2} ⊂ {1,2}, 즉 B는 불만이 없습니다.
C={3}∪D = {3}∪{1,4} = {1,3,4} ⊂ {1,2,3,4}, 즉 C는 불만이 없습니다.
D={4}∪(B-C) = {4}∪({1,2}-{1,2,3,4})={4} ⊂ {1,4}, 즉 D도 불만이 없습니다.

네명의 모든 조카들이 불만이 없어졌네요.

하지만,
A={1}
B={1,2}
C={1,2,3,4}
D={4}
이 것을 대입해도 모든 조카들이 불만이 없는것을 확인할 수 있습니다.

즉, 위의 알고리즘으로 얻은 set들은

minimal한 shopping list라는 조건을 만족하지 못합니다.

또는
A={1}
B={1,2}
C={2,3,4}
D={1,4}

이 것을 대입해도 모든 조카들이 불만이 없어집니다. 그런데,

C에게 주는 선물은 줄었고 D에게 주는 선물은 늘었군요.

둘중에 어느것이 더 minimal하다고 말할 수 있을까요?

해가 유일해지지 않는다, 혹은 해의 정의가 바뀌어야 한다...

이런 문제도 덤으로 생기게 됩니다.


따라서 Except of cond * cond를 허용하면 문제를 풀 수 없습니다.
_________________
TA

[최종욱]

흥미로운 내용이군요. 제가 궁금하게 여겼던 부분에 대한 좋은 반례를 들어 주신 것 같습니다.

답변 감사합니다~
_________________
Jongwook Choi
Seoul National University, School of Computer Science & Engineering