눈물보다 땀을

스패팅트리

최소스패닝트리(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

- 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

배열

- 데이터 공간 개수를 고정해서 할당

- 연속된 공간을 할당

장점

- 연속된 공간을 사용하기 때문에 임의접근(Random Access)가 빠르다.

단점

- 할당된 공간 확장,축소 불가

- 연속된 공간을 사용하기 때문에 중간 삽입/삭제 불가

동적배열(C++ stl::vector, C# Collections.Generic.List)

- 연속된 공간 사용

- 일반 배열과 다르게 공간 재할당이 가능하다

- 공간 재할당시 기존 공간보다 더 큰 공간으로 데이터들 복사가 일어난다.

- 최초 할당된 공간이 작으면 초기 데이터 삽입시 재할당이 많이 일어남으로 초기에 실제 사용할 공간보다 여유분을 갖고 크게 할당하는 것이 공간 재할당시 발생하는 오버헤드를 줄일 수 있다.

장점

- 연속된 공간을 사용하기 때문에 임의접근(Random Access)가 빠르다.

- 일반 배열과 다르게 공간 재할당이 가능하다

단점

- 연속된 공간을 사용하기 때문에 중간 삽입/삭제 불가

- 공간 재할당이 가능하지만, 데이터 복사로 인해 오버헤드가 발생. 데이터 복사할 떄는 기존 공간 보다 더 넓은 임의의 크기(1.5배~2배) 공간을 할당받아 재할당하게 된다. 이로 인해 재할당시 오버헤드는 점점 줄어 들게된다.

시간복잡도

- push_back O(1)

- 중간삽입/삭제 O(N)

- 임의접근 O(1)

연결리스트(양방향) (C++ stl::vector, C# Collections.Generic.LinkedList)

- 데이터를 노드 개념으로 관리하고 노드는 자신 이전, 이후 노드 정보를 갖는다

장점

- 중간 삽입/삭제가 빠르다

단점

- 연속된 공간을 사용하지 않으므로 임의접근이 느리다.

시간복잡도

- 중간 삽입/삭제 O(1) !물론 임의 삽입/삭제를 위해선 c++의 경우 iterator를 통해서 삽입/삭제할 위치를 알고 있어야 한다.

- 임의접근 O(N)

스택

- LIFO(Last In First Out). 후입선출

- 선형 자료구조

- interface : push, pop, peek

- 요소가 하나도 없는 경우 pop이나 peek하면 크래시 발생

- stl::stack은 내부적으로 deque로 구현되어 있다.

- stl:; stack은 c#의 stack과 다르게 반환값이 없다. top()을 이용해서 값을 참조할 수 있다. 이유는 성능상의 문제인것 같다. pop을 할떄 성능의 이점을 위해 참조값을 넘기면 실제로 데이터 공간에서 데이터가 사라지면 문제가 되고, 그렇다고 복사값을 넘기면 성능적으로 떨어진다. 따라서 pop은 공간에서 제거만하고, top은 참조값만 던지는 형태로 구분되어 사용되는 것 같다.

- 동적배열, 리스트로 구현 가능하다.

시간복잡도

- push,pop O(1)

큐

-FIFO(First In First Out), 선입선출

-interface : enqueue, dequeue,peek

- 요소가 하나도 없는 경우 pop이나 peek시 크래시 발생

- stl::queue는 내부적으로 deque 로 구현되어 있다.

- 순환구조배열, 연결리스트로 구현 가능하다.

시간복잡도

- enqueue, dequeue O(1)

왜 스택과 큐 사용하는 걸까?

스택과 큐는 자료구조적으로 의미가 명확하기 떄문이다. 예를 들어 '스택을 이용하여 구현 했다'라고 하면 스택이 의미하는 후입선출의 개념으로 구현되었 구나라고 소통의 이점이 생긴다.

동적 배열 vs 연결리스트

- 일반적으로 동적배열이 더 많이 쓰인다. 동적 배열은 데이터가 연속적으로 관리된다는 점에서 캐시에 이점도 챙길 수 있기 때문이다.

- 연결리스트는 동적배열과 다르게 c++ stl 기준으로 push_front가 있다 동적배열에서 지원하지 않는 이유는 동적배열을 이용한 중간 삽입/삭제는 느리기 때문에 api 차원에서 지원하지 않는 것이다.

- 연결리스트는 동적배여로가 다르게 c++ 기준으로 []연산자 오버로딩을 지원하지 않는다. 연결리스트의 경우 임의접근이 느리므로 api 차원에서 지원하지 않는다.

- 연결리스트는 랜덤 엑세스가 느린데 어떻게 중간 삽입/삭제는 빠른가? 중간 위치를 알려면 결국 랜덤 엑세스 해야되는거 아닌가? -> c++ 기준 list가 중간 삽입/삭제가 빠른 경우는 iterator를 통해서 삽입/삭제 위츠를 알고 있는 경우이다.

선형 구조

- 자료를 순차적으로 나열한 형태

- 배열, 연결 리스트, 스택, 큐 등

비선형구조

- 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

- 트리, 그래프 등

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 유니티로 만드는 mmorpg 게임 개발 시리즈] part3 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

특징

- Enqueue 순서와 상관없이 중요도가 가장 높은 순서대로 Pop을 한다.

- 이진 힙트리를 이용 => 트리 정보를 선형자료구조로 관리할 수있다.

- 삽입/삭제 시간복잡도 : log2(n) -> 트리 높이를 따른다.

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 언리얼로 만드는 mmorpg 게임 개발 시리즈] part3: 자료구조와 알고리즘 강의 내용을 정리했습니다.

특징

- 자식 노드가 최대 2개인 트리

이진 트리 종류

이진 검색 트리

- 좌측으로 가면 루트보다 값이 작아지고, 우측으로 가면 루트보다 값이 커지는 형태로 노드를 배치 해서 검색에 용이하다.

- 노드가 좌우 균형 잡혀 있으면 효율적이지만, 한쪽에 기울어지면 효율성이 떨어진다. 트리 재배치를 통해 균형을 유지하는 것이 관건이다. (AVL, Red-black)

이진 힙 트리

- 부모 노드 값이 자식 노드보다 커야 한다. (자식 노드의 순서는 상관없다)

- 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 한다. => 이렇게 규칙을 지정 하면 노드의 개수를 알면 트리 구조를 알수 있다. => 이로 인해서 트리 정보를 선형자료구조에 넣어 사용할 수있다.

- 새로운 값 추가

마지막 노드 위치에 노드를 추가하고, 부모 노드와 크기를 비교해서 부모 노드가 추가된 노드 값보다 작으면 교체 된다. 같은 방식으로 부모 노드가 자식 노드보다 값이 작아지도록 반복 탐색한다.

- 최대값 꺼내기

루트 노드를 제거하고 마지막 노드를 루트 노드에 위치한다. 새롭게 지정된 루트 노드를 자식중 더 큰 값과 비교해서 루트 노드가 자식보다 작으면 교체 된다. 같은 방식으로 자식 노드와 비교,교체를 반복해서 힙트리 법칙을 유지한다.