CS/Data Structure

덱(Deque) 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다. 두 개의 포인터를 사용하여, 양쪽에서 삽입과 삭제를 처리한다. double ended queue -> deque 덱(Deque)의 종류 스크롤(Scroll) - 입력이 한쪽 끝으로만 가능하도록 설정한 덱 셸프(Shelf) - 출력이 한 쪽 끝으로만 가능하도록 설정한 덱 JAVA에서의 덱(Deque) Interface로 구현이 되었으며, 이를 구현한 클래스는 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등이 있다. Deque 값 추가 deque.offerFirst() : 앞쪽에 데이터 삽입 deque.offerLast() : 뒤쪽에 데이터 삽입 deque.offer()..

힙(Heap) 최대 값 / 최소 값을 빠르게 찾아내기 위해 만들어진 "완전 이진 트리" 를 기본으로 한 자료구조이다. 이진 탐색 트리에서는 중복 값을 허용하지 않지만 힙 트리에서는 중복 값을 허용한다. 자바에서는 주로 우선순위 큐(Priority Queue)를 구현하는 데에 사용된다. 힙(Heap)의 종류 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 경우 부모 노드의 키 값 >= 자식 노드의 키 값 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 경우 부모 노드의 키 값

Stack과 Queue란 Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out)구조로 이루어져 있고, Queue는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 이루어져 있다. Stack과 Queue의 활용 Stack의 활용 예 - 수식 계산, 수식 괄호 검사, 프로그램의 뒤로 가기/앞으로 가기 등 Queue의 활용 예 -최근 사용 문서, 인쇄작업 대기 목록, 버퍼(Buffer) 등 Java로 작성한 Stack과 Queue 예제 import java.util.Queue; import java.util.Stack; import java.util.LinkedList; public class Main { public ..

해시테이블 검색하고자 하는 Key값을 가지고 Value를 찾는 자료구조이다. 동작 원리 검색하고자 하는 Key값을 HashFunction를 통해 HashCode를 생성한다. 이때, Key값은 문자열, 정수, 파일 데이터 등 다양한 값일 수 있다. HashFunction는 입력한 Key값으로 동일한 HashCode를 만들어준다. (동일한 Key값은 항상 같은 HashCode를 생성) HashCode를 나머지 연산 등의 방법으로 배열의 인덱스 환산하여 Value을 탐색한다. Value를 반환한다. HashTable를 왜 사용하는가? 미리 고정된 크기의 배열을 만들어 두고, 생성되는 HashCode를 배열의 Index로 사용하기 때문에 검색속도가 매우 빠르다. HashAlgorithmCollision 만일 H..