Juuunew 살아남기

이진탐색트리는 이진트리의 한 종류로 아래와 같은 특징을 가진다. 각 노드의 키는 중복되지 않는다. 루트 노드의 왼쪽 서브 트리는 루트 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 루트 노드의 오른쪽 서브 트리는 루트 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 좌우 서브 트리도 모두 위와 같은 이진탐색트리의 특징을 갖는다. 내가 찾으려는 키가 루트 노드의 키보다 작으면 왼쪽 트리로, 크면 오른쪽 트리로 탐색하면 되기 때문에 기존의 이진트리보다 탐색이 빠르다는 장점이 있다. 이진탐색트리에서는 무조건 트리의 높이(h) 이하의 탐색이 이루어진다. public class BinarySearchTree { public static void main(String[] args) { } Node r..

트리는 비선형 자료구조 중 하나로 노드로 이루어져있으며 데이터들이 계층적으로 연결되어 저장된다. 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조 이기도 하다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 루트 노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드 : 루트 노드 방향으로 직접 연결된 노드 자식 노드 : 루트 노드 반대 방향으로 직접 연결된 노드 형제 노드 : 같은 부모 노드를 갖는 노드들 리프 노드 : 루트 노드를 제외하고 차수가 1인 정점. 자식이 없는 노드 간선 (Edge) 노드와 노드 간의 연결선 레벨 (level) 루트에서 기준 노드까지 연결된 간선 수의 합 깊이 (dept..

스택은 한쪽 끝으로만 데이터를 넣고 뺄 수 있는 후입선출(Last-In-First-Out) - [나중에 들어온 데이터가 가장 먼저 빠져나간다] 형태의 자료구조이다. 대표적으로 컴퓨터 내부 프로세스 구조의 함수 동작 방식이 스택이다. 가장 쉬운 예시로 실행 취소(ctrl + z)를 생각할 수 있다. 실행취소를 여러번 할 때 가장 최근에 수행되었던 작업부터 취소되는 것을 떠올리면 된다. class Stack { class Node { private T data; private Node nextNode; public Node(T data) { this.data = data; } } private Node top; public T pop() { // 맨 위에 값이 null -> Exception if (top ..

큐는 스택과 반대로 선입선출(First-In-First-Out) - [먼저 들어온 데이터가 먼저 빠져나간다] 형태의 자료구조이다. 맛집의 웨이팅을 생각하면 편하다! (먼저 온 사람이 먼저 먹고 퇴장!) class Queue { class Node { private T data; // 데이터 private Node nextNode; // 다음 노드 // 생성자를 통해 data를 전달받은 뒤 내부 변수에 저장 public Node(T data) { this.data = data; } } // 앞과 뒤의 주소를 알기위한 변수 private Node first; private Node last; public void add(T item) { // 노드 생성! Node t = new Node(item); // 맨..

리스트는 어떠한 순서를 가지고 원소들이 나열된 형태의 자료구조이다. 리스트는 순차 리스트와 연결 리스트 두 종류로 구분된다. 보통 순차 리스트는 배열(Array)을 사용해 표현하지만 자바에서는 ArrayList라는 Java API가 따로 존재한다. 순차 리스트는 데이터를 삽입하거나 삭제하고 나면, 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업을 해야 하므로 삽입이나 삭제 연산이 많다면 그만큼 시간이 오래 걸린다. (대신 조회 시에는 해당 인덱스만 조회하면 되므로 시간이 단축된다.) 연결리스트는 특정 노드를 삽입하거나 삭제할 때 순차 리스트에 비해 연산 속도가 빠르며, 조회 시에는 index[0] 부터 시작되어 연산 속도가 느리다. 연결리스트 (LinkedList) Linked List는 ..

배열 (Array) 배열(Array)은 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조이다. 같은 종류의 데이터를 순차적으로 저장하며 데이터를 효율적으로 관리하기 위해 사용한다. 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영역에 할당되며, 주소값(인덱스)은 힙 영역에 생성되는 배열의 주소값이다. 장점 빠른 접근이 가능함. (인덱스를 이용해 접근하기 때문) 데이터의 크기가 확정적일 때 메모리나 처리속도 면에서 좋다. 단점 선언할 때 크기가 고정되기때문에 데이터 추가/삭제의 어려움이 있다. (사이즈를 넘어가면 배열을 새로 만들어야 함) 중간에 요소를 삽입하거나 삭제할 경우에는 해당 요소 뒤에 있는 요소들의 위치를 이동시켜야 한다. 🌟 element : 배열을 구성하는 각..

자료구조란? 자료(데이터)에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 대한 이론 자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 공간 크기에 따라 하나를 선택할 수 있다. 자료구조의 종류 자료구조는 크게 4가지로 분류할 수 있다. 단순 구조 : boolean(true/false), 정수, 실수, 문자 및 문자열과 같이 프로그래밍 언어에서 기본적으로 제공하는 자료 선형 구조 : 데이터들이 순차적으로 일렬로 저장되어 있는 형태 비선형 구조 : 선형구조처럼 나열되어 있지는 않지만 하나의 자료가 다른 자료와 연결되는 형태의 파일 구조 : 같은 성질을 가지는 데이터들을 모아 놓은 파일을 일정한 규칙에 따라 저장하는 형태 이 중 선형 구조와 비선형 구조에 관하여 ..