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