목록Data Structure (4)
코드몽키
Hash해시(Hash)는 키(Key)를 일정한 규칙(함수)를 통해 고정된 크기의 값으로 변환하는 과정을 말한다.해시(Hash Function)는 바로 그 변환 규칙을 일컫는다. 임의의 크기의 입력(문자열, 숫자)을 받아 고정된 크기의 해시 값(Hash Value, Hash Code)을 반환한다. 해시 자료구조는 이 해시 함수를 활용해서 데이터를 효율적으로 저장하고 검색하는 자료구조를 말한다. 저장된 자료의 양과 관계없이 평균적으로 상수 시간(O(1))에 삽입과 조회가 가능한 자료구조가 바로 해시 테이블이다. 해시 기반 자료구조를 Java에서 실제로 사용한다고 가정해보자 먼저 car 라는 키 값(Key)을 가지고 자동차의 가격(Value) 2000 을 저장하려고 한다. 그럼 코드에선 Hash Functi..
Queue큐(Queue)는 대기열에 가장 먼저 추가된 요소가 가장 먼저 제거되는 선입선출(FIFO) 원칙을 따르는 자료구조이다.먼저 삽입된 데이터가 먼저 제거되는 특성을 가진다. 이러한 특징 때문에 큐는 순서 보장, 흐름 제어, 비동기 처리가 필요한 다양한 컴퓨터 시스템에서 핵심적인 역할을 수행한다. ADT에서 정의한 큐의 기본연산연산설명시간 복잡도create큐 생성 또는 초기화O(1)enqueue큐의 뒤(rear)에 요소 삽입O(1)dequeue큐의 앞(front)에서 요소 제거 후 반환O(1)peek큐의 앞(front) 요소 확인O(1)isEmpty큐가 비어있는지 확인O(1)isFull큐가 가득찼는지 확인(배열 기반)O(1) 큐는 두 개의 포인터(인덱스)를 기반으로 동작한다.Front는 큐에서 데..
Stack스택(Stack)은 후입선출(LIFO, Last In First Out)의 원칙을 따르는 선형 자료구조로, 데이터의 삽입과 삭제가 한쪽 끝(Top) 에서만 이루어진다. 중간 데이터에 직접 접근할 수 없으며, 반드시 마지막에 들어온 데이터부터 제거해야한다. 추상 자료형(ADT) 관점에서 바라보면 스택은 다음 연산을 기본으로 정의한다.연산설명시간 복잡도push(item)스택의 Top에 요소 삽입O(1)pop()Top 요소 제거 및 반환O(1)peek()Top 요소 확인 (삭제 X)O(1)isEmpty()스택이 비어있는지 확인O(1)size()요소 개수 반환O(1) java에서 배열 기반으로 Stack를 직접 구현해 보았다.class Stack { private int[] arr; pri..
추상적 자료구조는 자료구조의 기초를 이루는 매우 중요한 개념이다. ADT(Abstract Data Type)는 자료구조의 사용 방식과 작동 방식을 정의하는 추상적인 개념에 해당한다. 스택(Stack), 큐(Queue), 리스트(List), 트리(Tree), 그래프(Graph) 등 각각의 ADT로 구현 세부사항을 추상화 하고 어떻게 사용되는지에 대한 규칙을 제공한다. 예를 들면 Stack은 LIFO(Last In, First Out) 원칙을 따르도록하고, Stack에 저장되는 데이터를 어떻게 추가하고 삭제하고 조회하는지 push, pop, peek 등의 연산을 정의한다. ADT는 단순히 “데이터를 담는 그릇”이 아니라 어떻게 접근하고 다루는지(연산)까지 포함하는 개념이다. ADT는 이러한 추상적인 규격을 ..