눈물보다 땀을

스패닝 트리에  대해 설명하시오

-

-

최소스패닝트리에 대해 설명하시오

-

-

DisjointSet 자료구조의 특징

-

-

- 

시간 복잡도

-

용도

-

경로압축의 원리는?

-

링크압축의 원리는?

-

직접 구현 해보기

C++

스패팅트리

최소스패닝트리(MST)

크루스칼(Kruskal) 알고리즘

PPT

DisjointSet(상호배타적집합, 서로소 집합)

- 서로 공통된 원소를 가지고 있지 않은 두개 이상의 집합을 말한다.

- DisjointSet data Structure를 사용하면 서로 다른 원소들이 어떤 집합에 속해 있는지를 판단하기에 유용하다.

- 정의에 의해 Disjoint Set 사이에는 교집합이 없기 때문에, 합 연산을 하는 과정에서 두 집합 사이의 겹치는 원소를 특별히 고려하지 않고 모든 원소들을 하나의 집합으로 합치는 것이 가능하다. 이 합하는 과정과 각 원소들이 어떤 집합 속에 있는지 판별하는 과정을 효율적으로 찾기 해서 Disjoint Set Union을 사용합니다.

DisjointSet은 트리를 이용하여 표현할 수 있습니다.

Union 합치기

일반적으로 아래와 같이 합치기 연산을 진행  했을 때는 O(N) 시간 복잡도를 갖게 됩니다.

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v) 
		return;
	
    _parent[u] = v;
}

랭크압축(Rank Compression) 통한 최적화

    void Merge(int u, int v)
    {
        u = Find(u);
        v = Find(v);

        if (u == v) // 대장이 같은지 체크
            return;

        if (_rank[u] > _rank[v])
            ::swap(u, v);

        _parent[u] = v;

        if (_rank[u] == _rank[v])
            _rank[v]++;  
    }

Find 찾기

일반적으로 아래와 같이 소속을 찾는 함수를 구현하게 되면 Find 함수가 호출될 때마다 재귀가 호출되므로 비효율 적입니다

    int Find(int u)
    {
        if (u == _parent[u])
        {
            return u;
        }

        return Find(_parent[u]);
    }

경로압축(Path Compression)을 통한 최적화

아래와 같이 소속을 찾는 함수가 호출하게 되면 u의 parent를 root parent로 바꿔주는 경로압축을 통해 이후에 호출되는 Find(u) 함수는 빠르게 탐색이 가능하게 됩니다.

    int Find(int u)
    {
        if (u == _parent[u])
        {
            return u;
        }
        
        return _parent[u] = Find(_parent[u]);
    }

Conclusion

- 소속을 합치고, 요소의 해당 소속을 찾는데 적합한 자료구조

- 시간 복잡도 : O(Ackermann(n)) = O(1)

PPT

map vs hash_map

map

- 

- 

hasp_map

- 

- 

- 

- 

C# dictionary는 무엇일까?

-

정의

-

-

시간 복잡도

- 삽입 : 

- 삭제 : 

- 검색 : 

삽입/삭제시 일어나는 flow에 대해서 간략히 설명하시오.

-

-

map vs hash_map

map

- stl container map은 균형 이진 트리인 레드 블랙트리로 이루어져 있다.

- 삽입/삭제/검색 시간 복잡도는 O(logN)이다.

hasp_map

- c++11 표준 기준으로 unorder_map이다.

- 삽입/삭제/검색 시간 복잡도는 O(1)이다

- 해시값일 이용해서 데이터를 관리한다. 때문에 많은 메모리를 사용하고 대신에 속도가 빠르다.

- 해쉬값을 관리하는 방법에는 선형 조사법(inear probing), 이차 조사법(quadramic probing), 체이닝 등이 있다.

C# dictionary는 무엇일까?

c# dictionary = c++ map (x)

c# dictionary = hash_map(c++ unordered_map)

정의

레드블랙트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로 '대칭형 이진 B트리'를 발전시켜 만들어 졌다. 레드 블랙 트리는 최악의 경우에도 우수한 실행시간을 보인다. 

시간 복잡도

트리에 n개의 원소가 있을 때 O(lonN)의 시간 복잡도로 삽입/삭제/검색이 가능하다.

특성

1. 노드는 레드 or 블랙

2. 루트 노드는 블랙이다.

3. 모든 리프 노드들(NIL)은 블랙이다.

4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다.(즉, 레드 노드는 연달아 나타날 수 없다. 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)

5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

사용예

C++11 기준 stl container map은 레드블랙트리로 만들어져 있다.

삽입 Flow

- 이진 탐색 트리 삽입 flow를 진행하고, redblack 특성을 만족시키기 위한 flow가 진행된다.

삭제 Flow

- 이진 탐색 트리 삭제 flow를 진행하고, redblck 특성을 만족시키기 위한 flow가 진행된다.

PPT