아하하 첫 글은 임팩트가 강하도록 시류에 편승해보자.
우리 나라도 예외없이 그 파동에 꼼짝없이 휘말렸는데,
접착제로 쓰인다니 중학 기술 시간에 사용해봤을지도 모르는 그 물질을
음식물로 섭취하게 될 줄은 몰랐다.
현재 중국에서 원료가 수입된 것이 확인된 제품 중 검사를 하지 않은 제품이 (기준에 따라 다르지만) 302 품목~540 품목에 달한다고 한다.
자, 한건당 3시간 내지 6시간 정도를 소요해야 검사가 된다 한다.
검사 기계는 물론 이미 확보한 수량 만큼만 가동 가능할 것이므로 24시간 실험실을 가동해도 다음 주말에나 검사를 완료할 수 있다고 한다.
여기서 알고리즘 퀴즈 하나.
검사 시간을 줄일 수 있는 방법이 있을까? 물론 적합한 가정이 필요하다.
그 가정이란.
답: Divide and Conquer 를 이용하라. (나눠서 패기; 분할 정복이라고도 하던데..)
방법은,
1. 제품군을 반으로 쪼개어 적절히 시료를 취해서 모두 섞는다.
2. 각각을 검사해서 멜라민이 검출되는가를 살핀다.
3. 검사 결과 멜라민이 검출되지 않은 제품군은 통째로 안전 인증.
4. 검사 결과 멜라민이 검출된 제품군은 다시 반으로 쪼개면서 각각 검사.
물론 3번 부분이 오류를 내면 큰 문제가 생기므로, 검사 결과를 최대한 안전한 쪽으로 (보수적으로) 해석해야 할 것이다.
이렇게 하면 멜라민이 함유된 제품 수가 총 C개이고, 제품 총 종류가 N개였다고 할 때,
최악의 경우에 대략 C log_2 N 정도의 검사횟수를 거쳐서 결과를 낼 수 있다.
(엄밀히 계산하지 않아서 2~3배 정도는 틀릴 수도 있다. 누군가 정확한 걸 계산하면 업데이트 하겠다. ^^)
편의상 제품 수 N=512이고 멜라민 함유 제품 수 C=5 였다면 대충 45회 정도면 가능하고, C=10 이었다면 90회 정도면 가능하다.
이 방법의 가장 큰 장점은, 적합 제품을 빨리 걸러낼 수 있다는 것이다.
즉 안전 인증을 빨리빨리 많은 제품에 찍어줄 수 있다는 것.
(운이 좋으면 첫번째 검사에서 256개의 제품에 안전 인증을 찍어줄 수도 있다.)
문제는.. C가 좀 커지는 경우인데, 최악의 경우에 모든 제품에 멜라민이 함유되어있다면 1022회 검사를 해야하므로 오히려 시간상 손해를 본다.
