chamMal

트리는 Node와 Edge로 구성된 자료 구조로 계층적인 구조를 나타낼 때 주로 사용된다. ex) 폴더 구조, 조직도, 가계도 하나의 노드에서 다른 노드로 이동하는 경로는 유일하며, 노드가 N개일 때 트리 전체의 엣지의 수는 N-1개이다. 또한 Cycle이 존재하지 않고,모든 노드는 서로 연결되어 있으며, 하나의 엣지를 끊으면 2개의 sub-tree가 되는 것이 특징이다. 이 중 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 특별한 형태의 트리이다. 이진 트리의 종류 - 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리 - 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모두 ..

Heap 자료구조는 완전이진트리 구조로 최고 depth-1까지의 이진트리가 꽉 채워진 이진트리형태이다. Min heap과 Max heap으로 구현할 수 있으며, 중복값을 허용하고, 반 정렬상태(형제 node끼리는 정렬 순서를 보장하지 않음)이다. 최소값/최대값을 빠르게 찾아내는 유용한 자료구조이다. 데이터 삽입 1. 트리의 가장 끝 위치에 데이터를 삽입 2. 부모 노드의 키와 비교한 후 부모 자리와 교체(반복) 데이터 삭제 1. root 노드를 반환 및 삭제 2. 가장 마지막 위치의 node를 root로 변경 3. 자식 노드 중 비교하여 부모 노드와 자리 교체(반복) Java 내에서 minheap와 maxheap의 구현은 PriorityQueue : java.util.PriorityQueue 로 쉽게 할..

LinkedList 는 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지 않는 자료구조로 단방향, 양방향, 원형으로 구현할 수 있다. 데이터를 동적 할당할 수 있고, 데이터 추가/삭제가 용이하다는 장점이 있지만, 데이터를 검색할 때에는 Array에 비해 상대적으로 느리다는 단점이 있다. Java 내에서는 Garbage Collection(가비지 컬렉션 : 불필요한 메모리를 알아서 정리) 기능이 있어 삭제 시에 다음 Pointer를 Null로 변경해주면 LinkedList 상에서 데이터 삭제된 걸로 구현할 수 있으며, 가르키는 포인터가 삭제된 데이터는 메모리 상에서 삭제된다. LinkedList 의 시간 복잡도 접근, 검색 : O(n) 추가/삭제 : O(1) java LinkedList ( java..

HashMap 자료 구조는 { key : value } 쌍으로 이루어져 있고, 많은 양의 데이터를 검색할 때 뛰어난 성능을 발휘한다. Key와 value는 원하는 클래스나 데이터로 넣을 수 있고, key는 중복될 수 없으며 value는 중복값이 가능하다. 예시로는 아래처럼 선언하면 된다. HashMap map = new HashMap(); HashMap map = new HashMap(); HashMap map = new HashMap(); HashMap map = new HashMap(); 추가, 검색할때에 시간 복잡도는 O(1) 갖는다. HashMap 생성자와 method는 아래와 같다. 생성자 / 메서드 설명 HashMap() - HashMap 객체를 생성 ex) HashMap map = new H..

1. Array Array는 많은 수의 데이터를 다룰 때 사용되는 자료 구조로 각 데이터를 인덱스로 1:1 대응하도록 구성되어 있고, 데이터가 메모리 상 연속적으로 저장되어 있다. Data 'a' 'b' 'c' Index 0 1 2 char[] arr = {'a','b','c'}; arr[0]; // 'a' arr[1]; // 'b' arr[2]; // 'c' 배열은 인덱스를 이용해 데이터에 빠르게 접근이 가능하지만, 선언할 때에 미리 최대 길이를 정해서 생성해야 한다. char[] arr = new char[3]; char[] arr = {'a','b','c'}; 배열의 시간 복잡도 Access O(1) Search O(n) Add, delete O(n) Access : 배열의 인덱스 번호를 알고 있다..

Queue는 FIFO(First In First Out : 먼저 들어온 데이터가 먼저 나가는 구조)를 가진 자료 구조이다. 데이터를 입력한 순서대로 데이터가 처리되므로 여러 방식으로 활용될 수 있다. 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봅니다. 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됩니다. 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책 시간 복잡도 : 조회, 접근 : Ο(n) , 삽입 삭제 : Ο(1) java 내에는 Queue는 Interface 클래스라 구현 시에 Linkedlist로 구현하는 게 편함(java.util.Queue) Enqueue : add(), offer() Search : get(), conta..

Stack은 LIFO(Last In First Out : 마지막에 들어온 데이터가 먼저 나가는 구조)를 가진 자료 구조이다. 데이터가 입력된 순서의 역순으로 처리되기 때문에 여러 방식으로 사용될 수 있다. 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 후위 표기법 계산 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) 시간 복잡도 : 조회, 접근 : Ο(n) , 삽입 삭제 : Ο(1) import java.util.Stack; Stack stack = new Stack(); stack.push(1); stack.push(2)..