ITPE * JackerLab

개요그래프(Graph)는 객체(정점, Vertex)와 이들 사이의 연결 관계(간선, Edge)를 표현하는 비선형 자료구조로, 소셜 네트워크, 지도, 통신망, 관계형 데이터 등 현실 세계의 다양한 구조를 표현하는 데 사용된다. 방향성, 가중치, 순환 여부에 따라 다양한 그래프가 존재하며, 탐색, 최단 경로, 최소 신장 트리, 위상 정렬 등의 알고리즘이 활용된다.1. 그래프의 구성 요소 구성 요소 설명 정점(Vertex)데이터를 저장하는 노드 (점)간선(Edge)정점 간의 연결 관계 (선)인접 정점특정 정점과 직접 연결된 정점차수(Degree)정점과 연결된 간선의 수2. 그래프의 분류분류 기준유형설명방향성방향 그래프간선에 방향이 있음 (A → B) 무방향 그래프간선에 방향이 없음 (A — B)가중치가중치 ..

개요힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 우선순위 조건을 만족하는 구조이다. 최소 힙(Min Heap)은 부모 노드 ≤ 자식 노드, 최대 힙(Max Heap)은 부모 노드 ≥ 자식 노드의 조건을 만족한다. 주로 **우선순위 큐(Priority Queue)**로 활용되며, 삽입/삭제 모두 평균 O(log n)의 성능을 제공한다.1. 힙의 구조 및 특징 항목 설명 트리 구조완전 이진 트리(왼쪽부터 채움)힙 조건부모 노드 ≥ 자식 노드 (최대 힙), ≤ (최소 힙)저장 방식배열 인덱스 기반 표현 (root: index 0)사용 용도우선순위 큐, 정렬 알고리즘 (Heap Sort) 등2. 힙의 배열 표현노드 위치인덱스 관계부모 노드i왼쪽 자식2i + 1오른쪽 자식2i..

개요이진 탐색 트리(BST, Binary Search Tree)는 이진 트리의 일종으로, 왼쪽 서브트리에는 루트보다 작은 값이, 오른쪽 서브트리에는 루트보다 큰 값이 저장되는 자료구조이다. 중복 없는 정렬된 데이터를 저장하면서 빠르게 탐색, 삽입, 삭제가 가능하며, 평균적으로 O(log n)의 성능을 보인다. 알고리즘 문제풀이와 데이터베이스, 메모리 관리 등 다양한 분야에 활용된다.1. BST의 구조와 특징 구성 요소 설명 루트(Root)트리의 최상위 노드노드(Node)데이터와 자식 포인터를 포함한 단위왼쪽 자식루트보다 작은 값오른쪽 자식루트보다 큰 값BST는 모든 노드에 대해 왼쪽 이 성립한다.2. BST의 연산 동작 원리연산동작 방식시간 복잡도 (평균/최악)탐색(Search)루트부터 값 비교, 작으..

개요이진 트리(Binary Tree)는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 계층적 구조이다. 트리의 기본이자 다양한 트리 기반 알고리즘의 뼈대 역할을 하며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie), 표현식 트리 등으로 확장된다. 노드의 위치와 순서가 중요한 구조로, 다양한 순회 알고리즘이 적용된다.1. 이진 트리의 구조와 용어 용어 설명 노드(Node)데이터를 저장하는 기본 단위루트(Root)트리의 시작 노드 (부모 없음)왼쪽 자식(Left Child)루트 기준 왼쪽 하위 노드오른쪽 자식(Right Child)루트 기준 오른쪽 하위 노드리프(Leaf)자식이 없는 노드서브트리(Subtree)특정 노드를 루트로..

개요트리(Tree)는 노드(Node)와 간선(Edge)로 구성된 계층적 비선형 자료구조로, 하나의 루트 노드(Root)에서 시작하여 자식 노드로 분기되는 구조를 가진다. 트리는 컴퓨터 과학에서 데이터 분류, 탐색, 계층 구조 표현 등 매우 널리 사용되며, 이진 트리, 이진 탐색 트리, 힙, 트라이, AVL 트리, B트리 등 다양한 종류가 있다.1. 트리의 개념과 구성 요소 구성 요소 설명 노드(Node)데이터를 담는 기본 단위루트(Root)트리의 시작 노드 (부모가 없음)부모(Parent), 자식(Child)노드 간 관계 정의리프(Leaf)자식이 없는 마지막 노드서브트리(Subtree)특정 노드를 루트로 하는 부분 트리간선(Edge)노드 간 연결 관계2. 트리의 특성특성설명비선형 구조노드 간 관계가 계..

개요덱(Deque, Double-Ended Queue)은 양쪽 끝(front, rear) 모두에서 삽입과 삭제가 가능한 선형 자료구조이다. 일반 큐는 FIFO, 스택은 LIFO 원칙만 따르지만, 덱은 스택과 큐의 기능을 모두 갖춘 유연한 자료구조로, 양방향에서 데이터를 처리할 수 있다. 파이썬에서는 collections.deque 모듈을 통해 효율적인 덱을 구현할 수 있다.1. 개념 및 정의 구성 요소 설명 front덱의 앞쪽 끝, 요소 삽입/삭제 가능rear덱의 뒤쪽 끝, 요소 삽입/삭제 가능연산append, appendleft, pop, popleft, peek덱은 입력 제한 덱(Input-Restricted Deque), 출력 제한 덱(Output-Restricted Deque) 등으로 확장 가능..

개요배열(Array)은 같은 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조로, 프로그래밍에서 가장 기본적이면서도 핵심적인 구조 중 하나다. 인덱스를 기반으로 요소에 빠르게 접근할 수 있으며, 리스트, 행렬, 문자열 등 다양한 형태로 확장되어 활용된다. 정렬, 탐색, 해싱, 동적 프로그래밍 등 거의 모든 알고리즘에서 필수적으로 사용된다.1. 개념 및 정의 항목 설명 정의같은 데이터 타입을 가지는 원소들이 메모리상에 연속적으로 배치된 구조인덱스0부터 시작하는 정수로, 각 원소에 접근하는 주소 역할특징빠른 접근 속도 (인덱스 기반), 고정된 크기 (정적 배열 기준)2. 배열의 특징항목설명시간 복잡도 (접근)O(1) (arr[i]로 바로 접근 가능)시간 복잡도 (삽입/삭제)O(n) (중간에 삽입/삭제..

개요비선형 자료구조는 데이터 간 관계가 일대일(one-to-one)이 아닌 계층적 또는 망형 구조로 표현되는 구조를 말한다. 대표적으로 트리(Tree)와 그래프(Graph)가 있으며, 복잡한 관계성, 네트워크 구조, 계층적 데이터 표현에 효과적이다. 선형 구조보다 연산이 복잡하지만, 현실 세계의 다양한 문제 해결에 핵심적인 역할을 한다. 본 글에서는 트리와 그래프의 개념, 유형, 주요 연산, 활용 사례를 체계적으로 설명한다.1. 개념 및 정의 자료구조 정의 특징 트리(Tree)계층적 구조로 부모-자식 관계를 갖는 노드 집합비순환, 루트에서 시작, 서브트리 구성 가능그래프(Graph)정점(Vertex)과 간선(Edge)으로 구성된 네트워크 형태순환 허용, 방향성/가중치 여부에 따라 다양화비선형 구조는 ..