블로그

1. Unordered_map 간단 요약 Hash Table을 기반으로 만들어진 많은 양의 자료를 검색하는 데 특화된 자료구조로, key와 value를 저장하는 점에서 Map과 비슷해 보이지만, key를 정해진 hash function을 통해 key 값을 특정 주소로 변환하여 value에 접근하므로 이론상 O(1)의 탐색 시간을 가지고, Map과 달리 데이터를 정렬하여 저장하지 않는다는 차이가 있다. 단점으로는 서로 다른 key에 대해 동일한 주소를 얻으면 충돌이 발생하여, 이를 방지하기 위한 안전장치가 필요하다. 2. Unordered_map 구조 - 해시 테이블(Hash Table) - 반복자 사용이 가능하여 begin(), end() 등등의 STL 반복자 규칙을 공유한다. - bucket의 다른 이..

1. Map 간단 요약 STL에 속한 Map은 key로 정렬되는 Red-Black Tree 구조이며, key마다 value를 가진다. 데이터의 삽입/삭제 및 탐색의 시간복잡도가 O(logn)으로 빠르다. 2. Map 구조 - Map은 Red-Black Tree로 구현되어있다. 이 때 노드의 크기 비교는 key값을 이용한다. - Red-Black Tree : 자가 균형 이진 탐색 트리 1) 조건 - 모든 노드는 빨간색 또는 검은색이다. - 루트 노드는 항상 검은색이다. - 모든 리프 노드(Null leaf, NIL : 값을 가지지 않는 트리의 끝에 있는 노드)는 검은색이다. - 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속될 시 Double Red라고 부르고, 아래 소개하는 방법들로 해결한다. - ..

1. Queue 간단 요약 Queue는 Stack과 반대로 추가된 순서대로 원소가 빠져나오는 선입선출(FIFO, First In First Out)구조를 가진 자료구조이다. Queue또한 iterator를 지원하지 않아 순회탐색이 불가능하다. STL에서는 Stack과 거의 동일한 함수를 지원한다. 2. Queue 구조 - front() : 가장 먼저 추가한 원소 - back() : 가장 마지막에 추가한 원소 - push() : back() 뒤에 원소 추가 - pop() : front()에 해당하는 원소 제거 - size() : Queue의 크기 3. Queue 함수 정리 1) 크기 관련 - empty() : Queue가 비어있다면 true, 아니라면 false 반환 - size() : Queue의 크기 ..

1. Stack 간단 요약 Stack은 가장 나중에 추가한 원소가 가장 먼저 나오는 후입선출(LIFO, Last In First Out)구조를 가진 자료구조이다. 인덱스를 통한 접근은 불가능하고, 가장 나중에 추가한 원소를 제거하기 전에는 해당 원소를 제외한 나머지 원소의 값을 알 수 없다. STL Stack의 경우 Vector같은 컨테이너와 달리 iterator를 제공하지 않아 순회탐색이 불가능하다. 2. Stack 구조 - top() : 가장 마지막에 추가한 원소 - push() : 원소 추가 - pop() : top() 제거 - size() : Stack의 크기 3. Stack 함수 정리 1) 크기 관련 - empty() : Stack이 비어있다면 true, 아니라면 false 반환 - size()..

1. List 간단 요약 C++ 표준 라이브러리에 포함된 List의 경우, 원소의 값과 앞/뒤를 가리키는 포인터를 가진 노드들로 이루어진 이중 연결 리스트(Double linked list)이다. 동적 할당을 통해 관리하며 리스트의 특성상 삽입/삭제가 효율적이다(노드끼리 연결/끊기만 하면 되므로 O(1)). 하지만 탐색에는 불리한 구조이다(인덱스 접근이 불가능하므로 O(n)). 2. List 구조 - begin() : 가장 앞 노드(iterator) - end() : 가장 마지막 노드가 다음으로 가리키는 위치(iterator, 실제 노드가 있지 않다) - front() : 가장 앞 원소 - back() : 가장 마지막 원소 - size() : 원소의 개수 3. List 함수 정리 1) 반복자(iterat..

1. Vector 간단 요약 Vector는 C++ 표준 라이브러리(Standard Template Library, STL)에 속한 컨테이너 중 하나로 가변 배열이다. Vector는 동적 할당을 활용하므로 Heap에 생성되며 메모리를 효율적으로 관리할 수 있다. 하지만 원소의 추가/삭제에 있어서는 효율적이지 않다(추가/삭제 시 다른 원소를 옮겨야하므로 O(n)). 2. Vector의 구조 - begin() : 가장 앞 원소가 있는 위치 - end() : 가장 마지막 원소 바로 뒤 - front() : 가장 앞 원소 - end() : 가장 뒤 원소 - size() : 원소의 개수 - capacity() : 할당된 크기 3. Vector 함수 정리 1) 반복자(iterator) 관련 - begin() : 가장..

1. 배열(Array) - 동일한 타입의 데이터 저장 - 실제 저장된 메모리 주소도 연속적, 인덱스로 데이터 접근 가능 - 일반적인 선언은 정적 배열(크기 고정), STL의 Vector는 동적 배열(가변 크기) 2. 연결 리스트(Linked List) - 노드의 연결로 이루어져 있음, 노드는 값과 다음 노드를 가리키는 포인터로 구성 - 연결 리스트 가장 앞 요소는 Head, 마지막 요소는 Tail - 인덱스로 접근이 불가능, 순차적 접근 - 하지만 삭제 및 삽입이 용이 3. 스택(Stack) - 후입선출(Last In First Out, LIFO) 구조 : 가장 마지막에 추가한 데이터를 가장 먼저 꺼냄 4. 큐(Queue) - 선입선출(First In First Out, FIFO) 구조 : 가장 먼저 추..