"누워서 읽는 알고리즘" 의 퀴즈 정답...

친구들이 좋은 답변을 해 줬는데..

일단 정답들은 다음과 같다.

1. 임의의 원소들을 갖고있는 A 와 B 의 두 집합 (set) 이 있다. A 가 B 의 부분집합인지 여부를 확인하는 방법에 대해 설명하시오. ( 책에서는 세가지 해법을 소개했다. )

- A 의 원소의 갯수를 m, B 의 원소의 갯수를 n 이라 할 때.

정답 1 ) 가장 무식한 Brute Force 방법.  A 의 모든 원소에 대해서 루프를 돌면서 각각의 원소들이 B 에 존재하는지를 검사한다. A 와 B 에 대해서 이중 루프를 돌기 때문에 시간 복잡도는 O(m*n) 이 된다.

정답 2 ) A 와 B 를 정렬한 다음에 1 과 같은 작업을 수행한다. 정답 1 과 다른 점은 A 의 i 번째 원소에 대해서 B 에서 존재하는 지를 찾았을 경우 ( 이때 발견한 B 의 인덱스를 j 라 하면 ),  그 다음번 검색은 A 의 i+1 번째 원소부터 B 의 j 번째 인덱스에서 검색 작업을 시작하기 때문에 정답 1 처럼 매번 A 와 B 에 대해서 전체 루프를 돌 필요가 없다는 점이다.( 중복이 없을 경우 j+1 번째 인덱스 부터 시작. 이 내용들을 책에서는 그림을 그려가면서 몇페이지에 걸쳐서 설명하고 있는데 여기에서는 이정도만 써도 이해하리라 믿고... )
이 경우 시간복잡도는 A 와 B 를 정렬하는데 소요되는 O(mlongm + nlogn) 이 된다.
사실 이 문제는 도널드 크누스 교수가 "정렬과 검색" 의 관계에 대해서 설명하기 위해서 처음 고안해 낸 문제라 한다. "대부분의 데이터는 정렬을 할 경우 검색 작업이 매우 쉬워진다" 는 것인데, 사실 얼핏 보기에 당연해 보이기도 하지만 나는 저 이야기를 완전히 이해하는데 오랜 시간이 걸렸다. -_-;

정답 3 ) 해쉬를 이용한다. 즉, B 를 모두 해쉬 자료구조에 담아놓은 후, A 가 B 에 속하는지 여부만 검사하면 된다. 해쉬 자체의 시간복잡도는 O(1) 이지만 B 의 원소 전체를 해쉬에 담기 위한 과정 ( 시간복잡도 O(n) ) 과 A 의 모든 원소가 해쉬 내에서 존재하는지를 검사하기 위해서 A 의 원소 전체를 한번 검사하는 과정 ( 시간복잡도 O(m) ) 이 소요되므로 전체 시간복잡도는 O(m+n) 이 된다.
정답 3 의 경우 정답 1, 2 에 비해서 상대적으로 빠르지만 해쉬 테이블의 크기 만큼 메모리를 사용하는 trade off 가 있다는 것도 알아두어야 한다.

이 문제를 굳이 블로그에 포스팅 한 이유는 이상의 세가지 방법 이외에 혹시 다른 방법은 없을까 하는 생각에서 글을 올린 것이었다.
사실 이 문제를 처음 읽었을때 저 세가지 방법 정도만 생각이 났었고 책에서도 세가지의 해법만 제시했었지만 잘 생각해보면 다른 해법도 있지 않을까 하는 생각이 든다. 혹시 다른 아이디어가 있으신 분은 댓글로 달아 주시면 감사하겠다..

2. 물컵안에 물이 들어있다. 다른 어떠한 도구도 사용하지 않고 이 물컵의 물이 절반이 되는지를 확인하는 방법은 무엇일까? 

정답은 컵을 기울여서 컵의 물이 아래와 같이 되는지를 보고 판단하면 된다. 즉, 컵을 기울여서 물이 컵 입구 끝에 도달했을 때 반대편 끝이 컵의 바닥 모서리에 닿는지 여부를 보면 된다.

책에 삽입된 그림에서 가져옴.