자료구조17 [STL] list #1 list (연결 리스트) list의 동작 원리 중간 삽입/삭제 처음/끝, 삽입/삭제 임의 접근 (Random Access) list li; for (int i = 0; i < 100; ++i) li.push_back(i); li.push_front(0); // vector는 처음 삽입이 비효율적이라 없음 int size = li.size(); //li.capacity(); // 없음 int first = li.front(); int last = li.back(); // li[3] = 10 // 임의접근 허용안됨 list::iterator itBegin = li.begin(); list::iterator itEnd = li.end(); li.insert(itBegin, 100); li.erase(li.be.. 2023. 5. 15. [STL] vector #4 vector 직접 만들기 template class Vector { public: Vector() : _cata(nullptr), _size(0), _capacity(0) { } ~Vector() { if (_data) delete[] _data; } T& operator[](const int pos) { return _data[pos]; } public: void push_back(const T& val) { if (_size == _capacity) { // 증설 작업 int newCapacity = static_cast(_capacity * 1.5); // capacity가 0 or 1 이면 0과 1.5 짤려서 1을 반환하기 때문에 체크 if (newCapacity == _capacity) newC.. 2023. 5. 15. [STL] vector #3 vector = 동적 배열 = 동적으로 커지는 배열 = 배열 원소가 하나의 메모리 블록에 연속하게 저장된다. 중간 삽입/삭제 (BAD) vector의 중간 삽입은 새로운 데이터를 중간에 하나만 딱 밀어넣는게 아니라, 기존에 있던 데이터를 모두 이동시키는 것이기 때문에 비효율적이다. 데이터 크기가 클수록 더욱 비효율적이다. 또한 vector는 연속된 메모리 블록이기 때문에, 원소를 중간 삭제했을 때 데이터를 날리고 끝나는 게 아니라 나머지 데이터도 이동해야 돼서 비효율적이다. [0] [1] [2] [3] [4] [0] [1] [5] [2] [3] [4] 결론은 vector의 중간 삽입/삭제는 비효율적이다. 처음/끝, 삽입/삭제 (처음 - BAD / 끝 - GOOD) 처음 삽입/삭제는 뒤에 있는 데이터가 이.. 2023. 5. 15. [STL] vector #2 반복자(iterator) : pointer와 유사한 개념. 컨테이너의 원소(데이터)를 가리키고, 다음/이전 원소로 이동 가능 vector v(10); for (vector::size_type i = 0; i < v.size(); i++) v[i] = i; vector::iterator it; iterator도 class다. 위 설명 코드 ex) class MyIterator { }; class MyVector { public: typedef MyIterator iterator; typedef unsigned int size_type; } pointer와 비교해서 설명한 ex) iterator는 pointer처럼 활용할 수 있다. vector v(10); for (vector::size_type i = 0.. 2023. 5. 15. [STL] vector #1 STL (Standard Template Library) 프로그래밍 할 때, 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리 컨테이너(Container) : 데이터를 저장하는 객체 (자료구조 Data Structure) vector (동적 배열) vector의 동작 원리 (size/capacity) 중간 삽입/삭제 처음/끝, 삽입/삭제 임의 접근 배열 const int MAX_SIZE = 10 int arr[MAX_SIZE] = { }; for (int i = 0; i < MAX_SIZE; ++i) arr[i] = i; 근데 여기서 추가로 데이터를 가지고 싶다면? 몬스터를 추가시키고 싶다면? 그러면 애초에 배열의 크기 10으로 잡아서 사용못하는 문제가 있을 것이다. 추가적으로 배열을 늘리는 것.. 2023. 5. 15. [Data Structure] 비선형 - 우선순위 큐 '우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다. 우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다. 여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자. 힙의 정의 힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루.. 2023. 3. 16. [Data Structure] 선형 자료구조 배열 배열은 가장 기초적인 선형 자료구조다. 배열의 원소들은 메모리 상의 연속된 위치에 저장된다. 이 특성 덕분에 캐시의 효율성을 극대화 할 수 있다. 캐시는 보통 메모리의 일정 영역을 저장해놓기 때문에 배열같이 연속적인 위치에 저장된 데이터의 경우 더 빠른 속도로 접근이 가능하다. 배열의 원소들은 각각 인덱스로 구분 가능하다. 주어진 인덱스에 있는 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 배열은 선언할 때 배열의 크기를 지정해야 한다는 문제점을 가지고 있다. 처음 선언한 크기보다 더 많은 자료를 집어넣을 수 없다. 동적 배열 (Dynamic Array) 배열의 크기를 변경할 수 없다는 문제를 해결하기 위해 크기가 변경되는 '동적 배열'이 고안됐다. 배열의 특성을 그대로 이어받지만 추가.. 2023. 3. 16. [Data Structure] 비선형 - Heap(힙) Heap(힙) Binary Tree(이진트리) 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값 최대 힙 → 힙 정렬 알고리즘 → 우선순위 큐 2023. 2. 21. [Data Structure] 비선형 - Tree(트리) 트리 구조는 맨 위의 사진과 같이 하나의 뿌리로부터 시작되어서 가지가 여러 갈래로 뻗어있는 자료 구조를 말한다. 트리 구조가 어디서 많이 봤다고 하면 착각은 아니다. 스포츠를 좋아하는 사람이라면 많이 봤을 것이라고 생각되는 토너먼트 대진표도 트리 구조이다. 아래서부터 차례로 올라가서 가장 꼭대기까지 가는 것이 토너먼트이다. 트리구조는 반대로 위의 뿌리 노드부터 시작해서 아래로 내려가는 구조다. Tree (트리) 노드로 이루어진 비선형 자료 구조 그래프가 계층적 구조를 가진 형태 최상위 노드(루트)를 가지고 있음 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 .. 2023. 2. 21. [Data Structure] 비선형 - Graph(그래프) Graph(그래프) 객체 간의 연결을 시각화한 것으로 정점(Vertex)간의 관계를 표현하는 자료구조 단순히 노드(N, node)와 그 노드를 연결한 간선을 하나로 모아놓은 자료 구조. 즉, 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다. nodes/vertices(노드) 사이에 edge(엣지)가 있는 collection directed(방향) 그래프는 일방통행 undirected(무방향) 그래프는 양방향 → 소셜 미디어 네트워크를 나타내는 데 사용 → 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용 → GPS에서 위치와 경로를 나타내는 데 사용 그래프의 용어 정점(vertex) : 그래프를 형성하는 노드 간선(edge) : 그래프에서 노드 간의 연결 (정점 간에 '선') - 아크라.. 2023. 2. 21. 이전 1 2 다음
