[자료구조] 트리(Tree)
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. * 트리(Tree) - 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure) [트리의 구조] * 트리 용어 - 노드(Node) : 트리를 구성하는 원소(자료) - 간선(Edge) : 노드를 연결하는 선 - 루트 노드(Root Node) : 트리의 시작 노드, Level 0 - 형제 노드(Sibling Node) : 같은 부모 노드의 자식 노드들 - 서브 트리(Subtree) : 자식 노드들은 각각 독립하여 새로운 트리를 구성할 수 있으며, 각 노드는 자식노드 수만큼의 수를 가짐 - 노드의 높이(=레벨) : 루트에서 그 노드에 이르는 경로에 있는 간선의 수 ..
[자료구조] 큐(Queue)
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. * 큐(Queue) - 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어짐 - 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out) 구조 [큐의 구조] - Front : 저장된 원소 중에서 첫번째 원소 - Rear : 저장된 원소 중에서 마지막 원소 * 큐의 연산 - enqueue() - 큐에 끝(rear)에 항목을 추가 - dequeue() - 큐에 맨 앞(front)에 항목을 제거 - peek() - 큐에 맨 앞(front)에 있는 항목을 반환 - isfull() - 큐가 가득 찼는지 확인 - isempty() - 큐가 비어 있는지 확인 * 큐 구현 방법 1)..
[자료구조] 스택(Stack)
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. * 스택(Stack) - 쌓아 올린다는 의미로, 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조 - 같은 구조의 크기의 자료를 top이라고 정한 한 곳으로만 쌓을 수 있고, top으로만 접근하도록 제한하여 만든 자료구조 - 삭제 시에도 top을 통해서만 가능하기 때문에 top이 가리키고 있는 스택의 마지막 자료만 삭제할 수 있음 - 후입선출(LIFO, Last-In-First-Out) 구조 [스택의 구조] - Bottom : 가장 밑에 있는 데이터 또는 인덱스 - Top : 가장 위에 있는 데이터 또는 인덱스 - Capacity : 스택에 담을 수 있는 데이터의 총 용량 - Size : 현재 스택에 담겨져있는 데이터..
[자료구조] 연결 리스트(Linked List)
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. * 연결 자료구조/비순차 자료구조(Linked Data Structure/Nonsequential Data Structure) - 순차 자료구조 방식에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식 - 순차 자료구조 방식에서처럼 원소의 논리적인 순서와 물리적인 순서가 일치할 필요 없음 - 각 원소에 저장되어있는 다음 원소의 주소에 대한 참조에 의해 연결되는 방식으로, 물리적인 순서를 맞추기 위한 오버헤드 발생X - 여러 개의 작은 공간을 연결하여 전체를 표현하므로 크기 변경이 유연하고, 조금 더 효율적으로 메모리 사용할 수 있음 * 노드(Node) - 연결 자료구조 방식에서 단위로 저장함 -..
[자료구조] 리스트(List)
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. * 리스트(List) : 데이터를 나열하는 것 * 선형 리스트/순서 리스트(Linear List/Ordered List) - 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트 - 특징 1) 자료들이 순서대로 연속적으로 메모리에 저장됨 2) 삽입, 삭제 시 순서에 변함이 없음 3) 접근 속도가 빠름 4) 알고리즘이 간단함 * 순차 자료구조 - 원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조 - 순차 자료구조에서의 i번째 위치 = 시작위치 + (i-1) * 원소의 길이 - 배열을 이용하여 구현함 - 원소 삽입/삭제 시 물리적으로 원소를 당기거나 밀어야 해서 추가적인 오버헤드 발생 -> 삽입/삭..
[자료구조] 자료구조의 분류
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다. [자료구조의 분류] * 선형 구조 : 자료간의 앞뒤 관계가 일대일로 고정되어 있는 자료구조 ex. 리스트(List), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), 덱(Deque) * 비선형 구조 : 자료 간에 선형 구조가 아닌 계층(Hierarchical)구조나 망(Network)구조를 갖는 자료구조 ex. 트리, 그래프 * 파일 구조 - 서로 관련 있는 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조 - 보조기억장치에 데이터가 실제로 기록되는 자료구조 ex. 순차 파일, 색인 파일, 직접 파일