눈물보다 땀을

우선순위큐 특징

-

-

-

-

이진힙트리 특징

-

-

-  enqueue 시 일어 나는 절차

- pop시 일어 나는 절차

구현해보기

c++

c#

특징

-

-

-

-

구현하기

c++

c#

Graph

- 

- 

종류

 - 

 - 

 - 

구현방법 3가지와  장담점

- 

- 

- 

배열

- 

- 

-

- 

장점

-

- 

-

- 

단점

-

- 

-

- 

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

-

- 

-

- 

장점

-

- 

-

- 

단점

-

- 

-

- 

시간복잡도

- push_back =>

- 중간삽입/삭제 =>

- 임의접근=>

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

-

- 

-

- 

장점

-

- 

-

- 

단점

-

- 

-

- 

시간복잡도

- 중간 삽입/삭제 =>

- 임의접근 =>

스택

-

- 

-

- 

시간복잡도

- push,pop => 

큐

-

- 

-

- 

시간복잡도

- enqueue, dequeue =>

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

-

- 

-

- 

동적 배열 vs 연결리스트

-

- 

-

- 

직접 구현해보기

c++ (동적배열, 연결리스트, 스택, 큐)

c# (동적배열, 연결리스트)

배열

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

- 연속된 공간을 할당

장점

- 연속된 공간을 사용하기 때문에 임의접근(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)

이진 힙 트리

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

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

- 새로운 값 추가

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

- 최대값 꺼내기

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