알고리즘 질문입니다.

Knuth 에게 Literate Programming 을 부탁하는 E-mail 이라도 보낼까요?
-_-

A, 와 B 의 각 set 에 자신의 set 내의 순서와 원래 어느 set 에 존재했는지 기록한 다음 정렬하고 합병한 후 다시 원래대로 정렬하는 것을 생각해볼 수 있겠군요.

A 의 크기가 M 이고 B 의 크기가 N 이면

1. 자신의 set 내의 순서와 어느 set 인지 기록한다.
time complexity : M + N

2. 각 set 을 정렬한다.
time complexity : M log M + N log N

3. 두 set 을 합병한다.
time complexity : M + N

4. 두 set 을 재정렬한다.
time complexity : (M+N) log (M+N)
이 경우 비교우선순위는 우선 어느 set 에 속해 있는지 본 후
같은 set 에 속해 있다면 원래의 set 의 자기 순서를 비교하면 되겠죠.

결국 최대 연산비용은 4번이 되는군요.
그다지 좋아보이지 않군요. -_-

위의 경우는 정렬 algorithm 에서 Bucket Sort 라고 하나요?
http://en.wikipedia.org/wiki/Sort_algorithm
WikiPedia 에서.

생각하는 Programming 의 첫 주제에서 bit 연산을 도입해서
1/8 로 필요한 용량을 줄이는 방법을 보여주었죠.

파이썬으로 무식하게 비교하는 것이긴 하지만 올려봅니다

a = [3, 5, 4, 1]
b = [4, 2, 5, 1, 6, 9, 10]
                                                                                
a.extend([x for x in b if a.count(x) == 0])

1. A를 소팅해서 D를 만든다.
2. B원소 개수만큼 루프를 돌면서 B[i] 를 D에서 찾는다. (binary_search같은)
3. 찾을 수 없으면 A에 B[i]를 추가한다.

이렇게 하면 D 복사 소팅 + M * logN 정도가 아닐까요?

8) 감사합니다.

p.s. i가 세개입니다. -_-;

복사/정렬 대신에 hash를 쓰세요. 대략 O(M+N) 시간에 끝낼 수 있습니다.

제가 문제를 잘못 이해한건가요? 무지 쉬워 보이는데..
A 는 그냥 더하고.. A 에서 원소가 발생 했는지 안했는지만 체크해서..
B 를 더할때 A 에서 발생 하지 않은것만 추가하면 될거 같은데..

A = [3,5,4,1]
B = [4,2,5,1,6,9,10]
C = A # 즉 C 랑 A 랑 같음..

Table = [0 for i in range(0,100)]
for i in A:
Table[i] = Table[i] + 1
for i in B:
if Table[i] == 0:
C.append(i)
print C

최대값이 몇억이라면 비트저장에만도 엄청난 메모리가 소비될텐데요... 그리고 메모리 초기화 하는데도....

또하나 문제가 B원소값이 이리저리 점프하는 성질을 가졌다면 발생 비트 테이블의 페이지 문제로 속도가 확 떨어질 것입니다.

cdpark님께서 말씀하신 해쉬가 값의 존재 여부를 가장 빠르게 판단할 수 있는 것으로 보입니다. 정수라면 해쉬 함수를 크게 걱정하지 않아도 될테고... 그래도 정렬된 vector 의 binary_search도 왠만큼하니까...

p.s. cdpark님은 C++에서 어떤 해쉬 컨테이너를 사용하고 계십니까?

p.s. 벌레3호입니다.

숫자의 범위가 대충 1~10 정도 될거라고 예상했거든요..
답은 해쉬밖에 없군요
A 의 집합이 10000 개가 나온다면 테이블을 5001개 정도 잡고 해슁(+Quadratic probing) 써서 처리하시면 될듯..

zflute님이 생각한 것과 거의 같구요.
다른 점이라면 원소가 있는지 없는지 찾을 때 다 찾는게 binary로 찾는다는거죠.
그것만으로도 O(NlogM)정도의 복잡도를 가질 수 있습니다.
다음은 C++ 예제입니다.
이렇게 하면 set c에 저장이 되겠네요.

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

main()
{
    int a[] = {3, 5, 4, 1}; 
    int b[] = {4, 2, 5, 1, 6, 9, 10};

    set<int> c(a, a+sizeof(a)/sizeof(int));
    c.insert(b, b+sizeof(b)/sizeof(int));
}

또 순서가 필요하다면 int result[]배열을 만들고 c에 있는지 없는지 확인하면 해서 result에 더하면 될 것 같습니다.

각원소에 비트를 할당할이유가 없어보이는데 그리고 그비트도 실제 만만치 않을듯.

일단 A를출력한후 A와B를 비교하여 원소가 많은쪽을 정렬하시고
만일 A가 많다면 간단히 B를 A에서찾아 없으면 출력하시면되고
만일 B가 많다면 A를 읽어 B값을 찾아 제거한후 출력하시면 됩니다.

A = 3, 5, 4, 1 
B = 4, 2, 5, 1, 6, 9, 10 
 

C = 3, 5, 4, 1, 2, 6, 9, 10 

대충 자바로 하면..

Set set = new HashSet();
for(int i=0;i<a.length;i++)
    set.add(a[i]);

for(int i=0;i<b.length;i++)
    if( !set.contains(b[i]) )
        set.add(b[i]);

다시 생각해 보니 contains가 필요하군요. contains로 물어 보지 않으면 순서가 바뀌니까.. 역시 알고리즘은 차분히 생각을 해봐야 하는가 봅니다.