힙(Heap)이란? 힙은 완전 이진 트리를 기반으로 하는 자료구조로, 각 노드의 키 값이 그 자식 노드의 키 값보다 항상 크거나(최대 힙) 혹은 항상 작은(최소 히프) 특성을 가집니다. 힙은 우선순위 큐, 힙 정렬 등 다양한 알고리즘과 데이터 처리에 사용됩니다. 힙의 특징 완전 이진 트리: 모든 레벨이 완전히 채워져 있으며, 마지막 레벨을 제외하고 왼쪽부터 채워집니다. 힙 속성: 모든 부모 노드는 그 자식 노드보다 큰(또는 작은) 키 값을 가집니다. 힙의 종류 최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큽니다. 최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작습니다. 힙의 주요 연산 삽입(Insertion): 새로운 요소를 추가하며, 힙..
자료구조
해시 테이블(Hash Table)이란? 해시 테이블은 키(Key)를 값(Value)에 매핑하는 자료구조입니다. 고유한 해시 함수를 사용해 키를 해시 코드로 변환하고, 이를 사용해 데이터를 저장 및 검색합니다. 해시 테이블의 주요 특징 효율적인 데이터 저장 및 검색: 평균적으로 O(1)의 시간 복잡도를 가집니다. 해시 함수: 키를 해시 테이블의 인덱스로 변환하는 함수입니다. 충돌(Collision): 두 개 이상의 키가 같은 인덱스에 매핑되는 경우를 말합니다. 해시 테이블의 구현 해시 함수의 선택: 좋은 해시 함수는 충돌을 최소화하고 균등한 데이터 분포를 제공합니다. 충돌 해결 기법: 체이닝(Chaining): 각 인덱스에 연결 리스트를 사용하여 충돌을 해결합니다. 오픈 어드레싱(Open Addressin..
그래프(Graph)란? 그래프는 노드(Node) 또는 정점(Vertex)과 이를 연결하는 간선(Edge)으로 구성된 자료구조입니다. 네트워크 모델링, 경로 찾기, 사회 연결망 분석 등 다양한 분야에서 활용됩니다. 그래프의 기본 요소 노드(Vertex): 그래프의 기본 단위, 데이터가 저장되는 점입니다. 간선(Edge): 노드들을 연결하는 선으로, 두 노드 간의 관계를 나타냅니다. 인접(Adjacency): 두 노드가 간선으로 연결되어 있는 상태를 말합니다. 그래프의 종류 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프입니다. 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프입니다. 가중치 그래프(Weighted Graph): 간선에 가중치(비용, 거리 등)가..
트리(Tree)란? 트리는 계층적 구조를 가진 비선형 자료구조입니다. 각 요소는 노드(Node)라고 하며, 한 노드에서 다른 노드로 가는 연결선을 간선(Edge)이라고 합니다. 트리는 한 개의 루트 노드(Root Node)에서 시작하며, 각 노드는 여러 자식 노드(Child Node)를 가질 수 있습니다. 트리의 주요 특징 계층적 관계: 트리는 부모-자식 관계를 통해 데이터를 조직합니다. 루트 노드: 트리의 최상위에 있는 노드입니다. 자식 노드: 하위에 연결된 노드들입니다. 리프 노드(Leaf Node): 자식이 없는 노드입니다. 서브트리(Subtree): 노드와 그 자손들로 구성된 트리입니다. 트리의 종류 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가집니다. 이진 탐색 트리(B..
