✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조 트리(Tree)? 계층적인 자료를 표현하는 데 이용되는 자료구조. 그래프의 한 종류이다. 예) 컴퓨터 directory 노드(Node) : 그래프의 정점 루트 노드 : 트리의 기준이 되는 노드. 나무의 뿌리를 생각하면 된다. 루트 노드에서 가지가 뻗어나가는 이미지. 부모 노드 : 자신과 인접한 노드들 중 루트 노드로 향하는 노드 자식 노드 : 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드 단말 노드 : 자식 노드가 존재하지 않는 노드. 가지의 끝 형제 노드 : 부모 노드가 같은 노드 가지(Branch) : 그래프의 간선. 트리에서는 양방향 간선만 사용한다. 부트리(Sub Tree) : 부분 그래프와 비슷하게 ..
✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조 그래프(Graph)? 정점(vertex)과 간선(edge)으로 이루어진 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현한다. 정점마다 간선이 있을 수도 있고 없을 수도 있다. 정점(vertex) : 위치라는 개념. node라고도 부름 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선. link, branch라고도 부름 인접 정점 : 간선에 의해 직접 연결된 정점 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(내차수) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(외차수) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 : 경로를 구성하는 데 사용된 간선의 수 단순 경..
✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 불가능? 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들 연결 리스트(Linked List) 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다. 단일 연결 리스트(Singly Linked List) 각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트 일반적으로 큐를 구현할 때 사용된다. Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있다 FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)를 연결합니다.(?) 이..
✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 불가능? 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들 덱(Deque) 덱은 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능하게 만든 큐이다. 간단하게 말해서 스택과 큐의 성질을 모두 가지는 자료구조이다. double-ended queue의 줄임말이다. 덱의 연산 양쪽 끝에서 데이터의 삽입과 삭제를 모두 할 수 있기 때문에 스택과 큐의 연산 모두 구현 가능 데이터 삽입 addFirst() : 덱의 앞쪽에 데이터 추가. 용량 제한이 있는 덱의 경우 용량을 초과하면 예외가 발생한다. addLast() : 덱의 마지막에 데이터 추가. 용량 제한이 있는 덱의 경우 용량 초과 시 ..
✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 불가능? 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들 큐 (Queue) 먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 자료구조. 즉, 스택과 반대이다. 큐의 추상화 연산 enqueue(item) : item을 큐의 맨 뒤쪽에 추가 dequeue() : 큐의 맨 앞쪽의 데이터 삭제 peek() : 큐의 맨 앞 데이터를 반환 isfull() : 큐가 가득 찼는지 확인 isempty() : 큐가 비어 있는지 확인 큐의 구현 1. 배열을 이용한 구현 public class ArrayQueue { int MAX = 1000; int front; //머리..
✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 불가능? 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들 스택 (Stack) 먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out) 자료구조. 즉, 한 쪽 끝에서만 자료를 넣고 뺄 수 있음 스택의 추상화 연산 push(item) : item 하나를 스택의 가장 윗부분에 추가 pop() : 스택에서 가장 위에 있는 항목 제거 peek() | top(): 스택의 가장 위에 있는 항목을 반환 isEmpty() : 스택이 비어 있을 때 true 반환 isFull() : 스택이 가득 차 있을 때 true 반환 getSize() : 스택에 있는 요소 수 반환 스택의 ..
✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 가능? 모든 자료에 O(1)의 시작복잡도로 접근이 보장되는 자료구조들 1. 배열 배열(array) : 같은 타입의 변수들로 이루어진 유한 집합 배열 요소(element) : 배열을 구성하는 각각의 값 인덱스(index) : 배열의 위치를 가리키는 숫자. 0에서 시작 1차원 배열, 2차원 배열 등이 있음 배열이 차지하는 메모리의 크기 = 배열의 길이 X sizeof(타입); int[] array1; //배열 선언 int[] array2 = new int[10]; //heap 메모리에 할당 int[] array3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //선언과 동시에..
