'Data Structure' 태그의 글 목록

CS

[자료구조] 힙 (Heap)

2024.11.08

힙 (Heap) 란?특수한 트리 기반 데이터 구조힙은 우선순위 큐를 구현하기 위한 완전 이진 트리 형태의 자료구조최대 힙 (Max Heap)과 최소 힙(Min Heap) 총 2가지가 존재한다.최대 힙 (Max Heap)부모의 노드가 항상 자식의 노드보다 큰 구조한쪽 노드만 계속 진행되서는 안된다.왼쪽과 오른쪽 하위 트리에도 같은 작업을 수행해야한다.부모의 값보다 자식의 값이 크면 안된다.최소 힙(Min Heap)부모의 노드가 항상 자식의 노드보다 작은 구조한쪽 노드만 계속 진행되서는 안된다.왼쪽과 오른쪽 하위 트리에도 같은 작업을 수행해야한다.부모의 값보다 자식의 값이 작으면 안된다.장단점장점최대값 또는 최소값을 빠르게 찾고 삽입할 수 있음.우선순위 큐나 작업 스케줄링에서 활용하기 좋음.단점중간 요소에 ..

CS

[자료구조] 해시 테이블 (Hash Table)

2024.11.08

해시 테이블 (Hash Table) 란?키-값 쌍을 빠르게 삽입, 조회, 제거하는 데 사용되는 데이터 구조 장단점장점평균적으로 O(1)의 시간에 검색, 삽입, 삭제가 가능해 빠름.큰 데이터를 관리하기에 유리하며, 중복 데이터 방지에 유용.단점충돌 발생 시 성능이 저하될 수 있음.해시 함수에 따라 성능이 달라질 수 있으며, 메모리 효율성이 떨어질 수 있음.구현vector를 사용한 구현#include #include #include class HashTable{private: int BUCKET; std::vector > table; public: HashTable(int b) { this->BUCKET = b; table.resize(BUCKET); } ~HashTable() {}; // 유일한 인덱스..

CS

[자료구조] 트라이 (Trie)

2024.11.08

트라이 (Trie) 란?문자열을 저장하고, 효율적으로 탐색하기 위한 트리 형태의 자료구조tree 형태의 자료구조정보 검색 같은 분야에서 활용된다.위와 같은 그림처럼 빠르게 단어를 찾는 것에 효율적으로 동작할 수 있다. 장단점장점문자열 검색에 효율적이며, 접두사 검색을 O(m) 시간에 수행 가능 (m은 문자열 길이).자동 완성 기능 구현에 유용.단점많은 메모리를 사용하며, 자식 노드가 많아질수록 성능이 저하될 수 있음.구현class TrieNode를 사용한 구현#include #include #include class TrieNode{private:public: TrieNode *child[26]; bool wordEnd; TrieNode() { wordEnd = false; for(int i = 0;..

CS

[자료구조] 그래프 (Graph)

2024.11.07

그래프 (Graph) 란?그래프는 정점(vertex)과 간선(edge)로 이루어진 자료구조트리 (Tree) 와 무슨 차이가 있냐고 생각할 수 있는데,그래프에 경우에는 트리와 다르게 정점마다 간선이 없을 수도 있고 부모 자식개념이 존재하지 않는 등 차이점이 존재한다.지하철 노선도 등의 최단경로를 찾거나 sns에서는 공통된 친구를 찾는 등에 활용된다.장단점장점복잡한 관계를 모델링할 수 있음 (소셜 네트워크, 경로 탐색 등)다양한 알고리즘을 통해 최단 경로, 연결성 등을 찾을 수 있음.단점구현과 연산이 복잡하고 메모리 사용이 큼.순환이 발생할 경우 처리가 어려울 수 있음.구현를 사용한 구현#include #include class Graph{private: int V; std::vector > adjMatri..

CS

[자료구조] 트리 (Tree)

2024.11.07

트리 (Tree) 란?트리는 계층적인 구조를 가진 자료구조로, 부모와 자식 노드 간의 관계를 나타낸다. 데이터 구조화가 용이해 파일 시스템, 계층적 데이터 저장 등에 사용 가능.장단점장점데이터 검색, 삽입, 삭제가 효율적 (특히 이진 탐색 트리의 경우).데이터 구조화가 용이해 파일 시스템, 계층적 데이터 저장 등에 사용 가능.단점균형이 맞지 않을 경우 성능 저하 가능.구현이 복잡하고 노드 추가 시 메모리 오버헤드 발생트리 (Tree)는 대충보면 링크드리스트 (Linked List)랑 구조가 비슷하다고 생각할수도 있는데.트리 (Tree)에 경우에는 하나의 부모가 여러개의 자식을 가지고 있고, 최상위의 노드의 경우에는 부모가 따로 없는 구조를 가지고있다.구현#include 을 활용한 다중계층 트리구현#in..

CS

[자료구조] 링크드리스트 (Linked list)

2024.10.30

링크드리스트 (Linked list) 란?연결 리스트는 각 노드가 데이터와 다음 노드의 주소를 포함하여 순차적으로 연결된 자료구조동적으로 크기를 조절할 수 있다.기존적으로는 현재의 노드가 다음 노드만을 참조하는 단일 연결 리스트(Singly Linked List) 부터 이전 노드와 다음 노드 모두를 참조하는 양방향 연결 리스트(Doubly Linked List) 등으로 다양하게 확장이 이루어질 수 있다.장단점장점동적으로 크기를 조절할 수 있다.배열과 달리 삽입 삭제의 용이하다.단점임의적으로 특정 데이터의 접근이 불가능하다.추가적인 메모리 비용이 든다. 단일 연결 리스트(Singly Linked List)장점:각 노드가 다음 노드만을 참조는 next만 가지고 있기때문에 양뱡향에 비해 메모리사용량이 줄어든다..

CS

[자료구조] 큐 (Queue)

2024.10.30

큐 (Queue) 란?큐는 FIFO(First In, First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조스택과는 다르게 먼저들어온것이 먼저나가는 FIFO 구조를 가지고있다.장단점장점데이터의 삽입과 삭제가 O(1) 시간으로 이루어져 빠르게 처리가 된다.단점중간과 마지막에 있는 데이터의 접근하려고하면 비효율적이다.구현#include 사용#include #include using namespace std;int main(void) { queue q; q.push(1); q.push(2); q.push(3); cout deque를 활용한 구현#ifndef CUSTOMQUEUE_HPP_#define CUSTOMQUEUE_HPP_#include #include template class Cu..

CS

[자료구조] 스택 (Stack)

2024.10.29

스택 (Stack) 이란?순서가 보존되는 선형 데이터 구조스택은 LIFO(Last In, First Out) 구조로, 마지막에 들어간 데이터가 가장 먼저 나오는 자료구조를 이야기한다.쌓인 접시나 하노이 탑을 예시로 생각하면 된다.장단점장점데이터의 삽입과 삭제가 O(1) 시간으로 이루어져 빠르게 처리가 된다.단점중간과 마지막에 있는 데이터의 접근하려고하면 비효율적이다.구현#include 사용#include #include using namespace std;int main(void) { stack s; s.push(1); s.push(2); s.push(3); cout 정적할당 방식으로 구현#ifndef CUSTOMSTACK_HPP#define CUSTOMSTACK_HPP#define MAX_SIZE ..

CS

[자료구조] 배열 (Array)

2024.10.29

배열 (Array)이란?가장 기본적인 데이터구조를 이야기한다.동일한 타입의 데이터를 연속적인 메모리 위치에 저장한다.장단점장점인덱스를 통해 각 요소에 O(1) 시간에 접근 가능하다.구현이 간단하고 메모리 사용이 효율적이다.단점크기가 고정되어있기때문에 크기를 변경하기위해서는 새로운 배열을 생성해야한다.중간에 요소를 삽입하거나 삭제할 경우에는 해당 요소 이외의 모든 요소를 이동해야하므로 비효율적이다.구현#include int main(void) { // stack int number[5] = {1, 2, 3, 4, 5}; char s[5] = {'a', 'b', 'c', 'd', 'e'}; // heap int* arr = new int[5]; arr[0] = 1; arr[1] = 2; delete arr..

티스토리툴바