Algorithm & DataStructure/DataStructure 썸네일형 리스트형 STL map 소개 map은 레드 블랙트리로 이루어진 Container입니다. 레드블랙트리란 균형이진트리의 하나로 이진트리의 노드가 한쪽으로 편향되는 현상을 줄여 탐색의 효율을 유지하기 위해 고안된 트리입니다. 노드의 색상관계에 따라서 트리가 삽입 삭제시 균형을 맞추어 나갑니다. map은 탐색과 삭제 삽입이 모두 O(logn)의 효율을 가집니다. 그럼 map이 정말 완벽한 Container구나 생각하실 수 있는데, 노드가 삽입 삭제 될때 트리가 균형을 맞추는 과정에서 꽤 복잡한 연산이 이루어지게 됩니다. 때문에 map은 완벽한 Container가 아닌 탐색을 위한 Container다 하고 생각하시면 좋을 것 같습니다. map은 key와 value로된 노드로 구성되어 있습니다. Key는 자료를 찾고 트리를 구성하는데 영.. 더보기 Heap 소개 Heap이란 자료구조는 최대 최솟값을 구하기 위해 고안된 완전 이진 트리(마지막 레벨을 제외한 모든 노드가 꽉차 있는 노드 마지막 노드는 왼쪽부터 차있어야 한다.) 입니다. Root 노드를 제외한 모든 노드는 오름차순 혹은 내림차순이고, 마지막 왼쪽 노드를 제외한 모든 레벨은 완전 이진 트리를 형성한다. 때문에 Root 노드의 값이 최댓값 혹은 최솟값일 수 밖에 없습니다. Heap은 트리지만 일반적으로 노드로 구현되는 트리들과 달리 배열로 구현합니다. (배열로 구현할 경우 일반적인 트리는 완전 이진트리가 아니므로, 메모리의 낭비를 가져 온다. 배열에서 사용하지 않는 공간이 중간에 생기기 때문) 이유는 Heap을 노드로 구현하면 트리의 마지막 레벨의 왼쪽부터 노드를 추가하기가 힘듭니다. 배열로 구현할.. 더보기 STL Queue, Stack 소개 안녕하세요 오늘 소개해드릴 자료구조는 Stack 과 Queue입니다. Stack과 Queue는 노드기반으로 구현할수도 배열 기반으로 구현할 수도 있습니다. Top, Front(중간의 데이터를 삽입삭제 할일도, 랜덤접근을 할 이유가 없음)가 중요한 자료구조 이기 때문입니다. 그럼에도 노드기반으로 구현하는 이유는 크기의 확장때문인 것 같습니다. 배열 기반으로 구현할 경우 사이즈가 증가함에 따라 vector의 단점인 데이터 복사가 일어 날 수 있 기 때문입니다. 노드 기반이 훨씬 구현하기 편합니다. Stack : LIFO = Last In First Out 마지막에 들어간 요소가 처음으로 나온다. 스택을 사용하는 이유는 이전의 행동을 저장하거나, 뒤로가기등의 기능을 만들기 위해서 입니다. 또는 데이터를 .. 더보기 list 구현 소개 리스트는 노드기반 컨테이너 입니다. 때문에 노드를 설계하는 것이 중요합니다. 단일 list나 이중 list나 만드는 과정은 똑같으므로 단일 list를 보여드리겠습니다. 이중 list는 Node에 이전 노드를 가리키는 포인터를 추가하고, 단일과 똑같이 연결을 끊어주고 이어주면 됩니다. 핵심적인 예외처리만 설명하고, 일부 예외처리는 생략하겠습니다. 궁금하시면 댓글 남겨주세요 구현 Node tData : 데이터를 저장하는 변수 pNext : 다음 노드를 가리키는 포인터 pPrev : 이전 노드를 가리키는 포인터 Member Values m_pHead : 시작 노드를 가리키는 포인터 m_pTail : 마지막 노드를 가리키는 포인터 m_iCurCount : 데이터의 갯수, 노드의 갯수 Member Funct.. 더보기 STL list 소개 데이터들이 순차적으로 이루어져있는 노드기반 컨테이너입니다. (순차적이란 : 데이터를 넣은 순서를 유지한다.) 리스트의 시작을 Head라 부르고 마지막을 Tail이라고 부릅니다. 그림은 단일 연결리스트로 그렸지만 사실상 노드가 서로 연결되어있는 이중연결리스트로 구현되어 있습니다. 리스트의 장점은 포인터로 연결되어있기 때문에 데이터를 원하는 위치에 삽입하고 삭제하는 연산이 매우 간단합니다. 앞에 있는 포인터와 뒤에있는 포인터의 연결을 끊어주고 노드를 삭제해주면 삭제가 끝나고, 두개의 노드사이의 새로운 노드를 넣어 포인터를 연결해 주면 삽입이 끝납니다. 이와 같이 삽입 삭제가 매우 간단합니다. 하지만 탐색을 하는 작업이 매우 비효율 적입니다. 노드의 Head 부터 Tail 까지 모든 노드를 탐색해야 하기.. 더보기 vector 구현 소개 저번에 설명드렸던 vector를 구현한 것을 보여드리겠습니다. template으로 구현하였고 간단만 맴버함수들만 구현해 보았습니다. Inner Class로 구현한 Iterator와 Conatainer를 보여드리겠습니다. 구현 Container Memeber Variable m_pArr : m_iMaxCount만큼의 데이터를 저장하는 배열의 주소를 가리키는 포인터 입니다. m_iMaxCount : 배열의 최대 사이즈를 의미합니다. vector에서 capacity라고 보시면 됩니다. m_iCurCount : 배열의 현재 들어있는 요소들의 크기를 의미합니다. vector에서 size를 의미합니다. Public Member Functions public으로 제공하는 함수들의 목록입니다. push_back .. 더보기 STL vector vector vector 란 STL의 일종으로 임의접근(Random Access)을 지원하는 배열기반 컨테이너 입니다. vector는 내부적으로 크기를 확장하는 배열입니다. 때문에 가변 배열이라고도 부릅니다. vector는 배열과 같이 메모리블록에 데이터가 연속적으로 저장 됩니다. (임의 접근이 가능한 이유) 장점 메모리 블록에 데이터가 연속적으로 저장 되기 때문에 임의 접근이 가능합니다. 임의접근으로 데이터를 찾을 경우 O(1)의 상수시간 효율을 가집니다. (vecTemp[4]) 노드들이 연결되어있는 list와 다르게 메모리 블록에 데이터가 연속적으로 저장 되기 때문에 삽입순서 대로 순회할 경우 가장 빠릅니다. 단점 데이터가 추가 되거나 삭제될 때 큰 비용을 지불 할 수 있습니다. (insert -> .. 더보기 STL 컨테이너 컨테이너 컨테이너란 클래스 템플릿을 의미합니다. (데이터를 저장하는 객체) - 클래스와 객체는 의미가 다르지만 간단하게 이렇게 표현하겠습니다. 컨테이너를 선언 할 때 컨테이너의 포함될 요소의 형식을 지정해줘야 합니다 (Template) 컨테이너에는 삽입 삭제와 다른 작업을 위한 맴버함수 들이 존재합니다. 컨테이너는 레퍼런스 보다는 값을 제공합니다. 이것은 데이터 삽입시 삽입 될 데이터의 복사가 일어나고, STL내부에서 동적할당 하여 복사해주는 것을 의미합니다. 자료구조라도 할 수 있겠죠. 컨테이너는 특징에 따라 크게 시퀀스 컨테이너, 연관 컨테이너, 어댑터 컨테이너로 분류할 수 있습니다. 시퀀스 컨테이너란 지정된 요소가 삽입된 순서를 유지하는 컨테이너 입니다. vector, list, deque 등이 포.. 더보기 이전 1 다음
