자료구조 (14) 썸네일형 리스트형 [자료구조] 힙 힙(Heap)이란? 완전 이진 트리 형태로 구성된 자료구조이며, 특정 조건(힙 속성)을 만족하도록 정렬된 트리이다.힙은 우선순위 큐(Priority Queue)와 같은 문제를 효율적으로 해결할 때 유용하다. 힙 속성(Heap Property)최대 힙(Max-Heap)최소 힙(Min-Heap)최대 힙(Max-Heap)부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음.루트 노드가 가장 큰 값을 가짐. 최소 힙(Min-Heap)부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음.루트 노드가 가장 작은 값을 가짐. 힙 연산1. 삽입(Insert)새로운 노드를 힙의 마지막 위치에 삽입.부모와 비교하며 힙 속성을 유지하도록 교환(상향 조정, upheap).2. 삭제(Delete)일반적으로 루트 노드(최댓값.. [자료구조] B-트리(B-Tree) 목차B-Tree 란B-Tree 개념B-Tree 특징B-Tree의 동작B-Tree의 시간 복잡도B-Tree 활용 사례B+Tree란? B-트리(B-Tree)란? B-트리(B-Tree)는 균형 잡힌 트리 자료구조로, 특히 데이터베이스나 파일 시스템에서 대용량 데이터를 효율적으로 저장하고 관리하기 위해 고안된 트리이다. 이진 트리와 달리, B-트리는 각 노드가 여러 개의 자식 노드와 여러 개의 키를 가질 수 있는 구조이다.이 때문에 높이를 낮게 유지하여, 빠른 검색과 삽입, 삭제 연산이 가능하다.B-트리의 주요 개념M-차 B-트리:B-트리의 차수(M)는 각 노드가 가질 수 있는 최대 자식 노드의 수를 나타낸다.예를 들어, 3차 B-트리는 각 노드가 최대 3개의 자식을 가질 수 있다.노드의 키 개수각 노드는 .. [자료구조] Set과 Hash set 목차Set의 개념Set의 주요 특징Set이 적합/부적합한 상황Set의 시간 복잡도Set과 List의 비교Set 의 구현체들Hash Set Set 이란?Set(집합)은 중복된 요소를 허용하지 않는 데이터를 저장하는 추상 자료형이다. 주로 빠른 검색, 삽입, 삭제 연산을 위해 사용된다.Set은 수학적 집합과 유사하게 동작하며, 중복된 값이 없고 순서에 상관없이 요소들이 저장된다.Set은 해시 테이블이나 이진 탐색 트리와 같은 데이터 구조를 기반으로 구현되며, 내부적으로 어떤 자료구조로 구현되었느냐에 따라 성능이 달라진다.Set의 주요 특징중복된 요소 허용 안 함: Set은 중복된 값을 저장할 수 없다. 같은 값을 여러 번 추가해도 하나만 저장된다.순서 없음: Set의 요소들은 특정한 순서가 없으며, 요소를 .. [자료구조] Red-Black 트리 목차Red-Black 트리의 개념Red-Black 트리의 특징NIL 노드Red-Black 트리의 균형 유지Red-Black 트리의 시간 복잡도Red-Black 트리의 활용 사례 Red-Black 트리란Red-Black 트리는 각 노드가 레드(Red) 또는 블랙(Black)의 색상을 가지며, 이를 통해 트리의 균형을 적당히 유지한다.엄격한 균형을 유지하는 AVL 트리와는 달리, Red-Black 트리는 트리의 높이가 완전히 균형을 이루지 않아도 특정 규칙을 통해 높이의 편차를 제한함으로써 효율성을 확보한다.NIL 노드란?NIL 노드는 트리의 리프 노드를 나타내는 NULL에 해당하는 특수 노드이다.실제 데이터 값을 갖지 않는 가상 노드이며, 색깔은 항상 블랙이다.값이 있는 노드와 동등히 취급Red-Black.. [자료구조] AVL 트리 목차AVL 트리의 개념Balance FactorAVL 트리의 균형 유지AVL 트리의 삽입/삭제AVL 트리의 시간 복잡도AVL 트리의 장단점 AVL 트리란 무엇인가?AVL 트리는 자가 균형을 유지하는 이진 탐색 트리의 한 종류이다.이진 탐색 트리의 성능이 편향된 트리로 인해 저하될 수 있는 문제를 해결하기 위해 도입되었다.AVL 트리는 트리의 모든 노드가 균형 상태를 유지하도록 Balance Factor를 사용하여 노드 간 높이 차이를 관리한다. AVL 트리의 구조와 Balance Factor AVL 트리는 각 노드에 대해 Balance Factor(BF)를 정의하여 균형을 유지한다.이는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이를 나타내며, 이 값은 -1, 0, 1 중 하나여야 한다.Bala.. [자료구조] 이진 탐색 트리 목차이진 탐색 트리의 개념이진 탐색 트리의 특징트리 순회 방식시간 복잡도이진 탐색 트리의 장단점 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree, BST)는 트리 구조 중에서도 특정 규칙을 따르는 트리로,데이터를 효율적으로 관리하고 검색할 수 있는 구조이다. 이진 탐색 트리의 개념이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조로, 다음 규칙을 따른다.왼쪽 서브 트리는 해당 노드의 값보다 작은 값들을 가진다.오른쪽 서브 트리는 해당 노드의 값보다 큰 값들을 가진다.이 규칙 덕분에 이진 탐색 트리는 빠른 데이터 검색, 삽입, 삭제 연산을 지원할 수 있다.이진 탐색 트리의 특징 이진 트리에서 최소값과 최대값 최소값: 이진 탐색 트리.. [자료구조] 트리 구조와 이진 트리 목차트리 구조트리 관련 주요 용어트리 구조의 특징이진 트리형태에 따른 이진 트리의 종류 트리 트리는 여러 개의 노드(node)로 이루어진 자료 구조이며, 각 노드는 부모와 자식 간의 관계를 가진다.트리 구조는 비선형 자료 구조로, 여러 개의 데이터를 계층적으로 표현할 수 있는 형태이다.트리는 루트 노드를 기준으로 하위 노드가 가지(branch)를 뻗어나가는 구조로 형성되며, 각 노드가 하나의 부모와 연결된다.트리에서는 순환(cycle)이 발생하지 않으며, 노드는 하나의 부모 노드만을 가질 수 있다.트리 관련 주요 용어 간선노드와 노드를 연결하는 선링크나, 브렌치라고 불리기도 한다.루트 노드최상단에 있는 노드트리의 시작점2자녀 노드모든 노드는 0개 이상의 자녀 노드를 가진다.부모 노드자녀 노드를 가지는 노.. [자료구조] 해시 테이블 Hash Table키(Key)를 통해 값(Value)을 빠르게 찾기 위해 사용하는 자료구조이다.해시 테이블은 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스에 매핑하는 방식으로 동작하며,이를 통해 O(1)의 시간 복잡도로 데이터 검색, 삽입, 삭제 작업을 할 수 있다. 해시 테이블의 특징해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 특정 인덱스로 변환하고, 그 인덱스에 값을 저장한다.해시 함수(Hash Function)는 입력값(키)을 받아서 특정 해시 값을 반환하는 함수로, 이 해시 값은 배열의 인덱스가 된다.해시 테이블은 해시 충돌(Hash Collision)이 발생할 수 있는데, 이는 다른 키들이 같은 해시 값을 가질 때 발생한다. 이를 해결하기 .. [자료구조] 스택과 큐 스택후입 선출(LIFO, Last In First Out) 형태로 데이터를 저장하는 구조여기서 가장 마지막에 넣은 3번이 가장 먼저 나온다. 이렇게 나중에 넣은 것이 가장 먼저 나오는 것을 후입 선출이라 하고, 이런 자료 구조를 스택이라 한다.블럭을 빼려면 위에서 부터 순서대로 빼야한다. 스택 주요 동작push: 데이터를 스택에 넣는 연산.pop: 스택에서 가장 마지막에 들어간 데이터를 꺼내는 연산.peek: 스택의 최상위 데이터를 제거하지 않고 반환하는 연산. 스택 사용 사례스택 메모리스택 프레임 장점간단한 구현: 스택은 자료의 추가와 제거가 하나의 끝에서만 이루어지기 때문에 구현이 단순하다.빠른 데이터 처리: 마지막에 추가된 데이터에 접근하는 것이 O(1)로 매우 빠르다.재귀적 문제 해결: 재귀적인 .. [자료구조] 배열 리스트, 연결 리스트 배열의 경우 2가지 불편함이 있었다.배열의 길이를 동적으로 변경 불가.데이터를 추가하기 힘들다.(데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 미는 코드를 직접 작성해야 하기 때문)배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다. List 자료 구조순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.일반적으로 배열과 리스트는 구분해서 이야기한다. 리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.(데이터가 추가되면 배열이 꽉 찰 때마다 자동으로 더 큰 배열을 할당하고 기존 데이터를 복사하는 방식으로 크기를 늘린다.)배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다. 리스트: 순서가 있고 중복을 허용하지만.. 이전 1 2 다음
