공부의 기록/Data Structure (7) 썸네일형 리스트형 [자료 구조] Deque(Double-Ended Queue) - 자바 Front와 Rear 양쪽에서 삽입(enQueue)과 삭제(deQueue)가 가능한 자료 구조 Deque의 앞쪽으로 삽입하고, 뒤쪽으로 삭제하면 Queue처럼 사용할 수 있다. Deque의 앞쪽에 삽입하고 다시 앞쪽으로만 삭제하면 Stack처럼 사용할 수 있다. ⬛ 연산 addFirst(x) : 데이터 x를 덱의 Front에 추가, 용량을 초과하면 exception 발생 push(x)와 동일 → 덱을 스택으로 사용하고자 할 때 사용됨 offerFirst(x) : 데이터 x를 덱의 Front에 추가, 용량을 초과하면 false를 리턴 removeFirst() : 덱의 Front에 있는 데이터 삭제, 비어있으면 Exception 발생 pop()과 동일 → 덱을 스택으로 사용하고자 할 때 사용됨 remove(.. [자료 구조] Tree & Binary Tree의 개념 설명 ⬛ Tree의 개념 원소들 간에 1 : n 관계, 계층 관계를 가지는 자료 구조 노드(Node)와 간선(Edge)으로 이루어진 자료구조 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료 구조 Loop를 갖지 않는다. ⬛ Tree의 용어 노드(Node) : 트리의 기본 원소 간선(Edge) : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드는 간선으로 연결되어 있다. 루트 노드(Root Node) : 트리의 시작 노드로 부모 노드가 없는 최상위 노드 부모 노드(Parent Node) : 자식 노드를 가진 노드 자식 노드(Child Node) : 부모 노드의 하위 노드 형제 노드(Sibling Node) : 같은 부모를 가지는 자식 노드들 서브 트리(Sub-tree) : 부모 노드와의 연결을 끊었을 .. [자료 구조] Hash의 개념 설명 매핑 : 하나의 값을 다른 값으로 대응시키는 것 해시 함수란 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터(Key)를 고정된 길이의 데이터(Hash)로 매핑 ⬛ Hash Table 해시 테이블은 내부적으로 배열을 사용하여 저장하기 때문에 빠른 검색 속도를 가진다. 이때의 배열을 bucket이라고 한다. (key, value)를 저장하는 자료구조로 해시함수를 이용하여 key를 해시값으로 매핑하고, 이 해시값을 value를 저장하기 위한 인덱스로 사용 해시 테이블을 이용하여 데이터를 저장하면 key로 value를 찾을 때 해시 함수를 수행하여 value가 있는 위치를 찾을 수 있기 때문에 저장/삭제/조회 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가진다 전체 데이터의 양이 16이라고 하면 .. [자료 구조] Heap의 개념 설명과 구현 ⬛ 사전 지식 1. 완전 이진 트리 각 노드가 최대 2개의 자식 노드를 갖는 이진 트리 중 왼쪽부터 차례대로 채워져 있는 트리 최하단 레벨의 노드는 좌측부터 채워져 있어야 한다. 2. 우선순위 큐 우선순위가 높은 데이터가 먼저 나가는 형태의 큐 모든 항목은 우선순위를 가지며 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 큐에서 삭제 우선순위 큐의 구현 방법 배열로 구현할 경우 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 연결리스트로 구현할 경우에도 노드간의 연결을 거쳐 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 완전 이진트리인 힙으로 구현할 경우 최대 O(logN)의 시간 복잡도를 가진다. ⬛ Heap의 개념 우선순위 큐.. [자료 구조] Queue 개념 설명과 구현 ⬛ Queue 개념 한쪽 방향(Rear)에서는 자료의 삽입이, 다른 한 쪽 방향(Front)에서는 자료의 삭제가 이루어지는 FIFO(First In First Out) 형식의 자료 구조 Queue의 가장 먼저 들어온 요소를 Front, 가장 늦게 들어온 요소를 Rear라고 부르며 이 두가지 요소에 의해서만 접근이 가능 Rear에서 이루어지는 삽입 연산을 ‘enQueue’, Front에서 이루어지는 삭제 연산을 ‘deQueue’라고 한다. ⬛ Queue 연산 1. enQueue(int data) : Rear에 데이터를 추가 2. deQueue() : Front에 있는 데이터를 반환 후 삭제 3. peek() : Front에 있는 데이터를 반환 (삭제 x) ⬛ Queue 활용 프로세스 스케줄링 프린터 출력 .. [자료 구조] Stack 개념 설명과 구현(배열, 연결리스트) ⬛ Stack 개념 한 방향에서만 자료를 추가, 삭제할 수 있는 LIFO(Last In First Out) 형식의 자료 구조 가장 최근에 추가된 항목이 가장 먼저 삭제된다. 가장 최근에 추가된 데이터를 top이라고 부르고 추가와 삭제는 이 top에서만 이루어진다. 삽입하는 연산을 'push’라고 하며 삭제하는 연산을 ‘pop’이라고 한다. 만약 스택이 비어있을 때 자료를 꺼내려고 하면(pop) ‘Stack Underflow’가 발생 만약 스택이 꽉 차있을 때 자료를 넣으려고 하면(push) ‘Stack Overflow’가 발생 ⬛ Stack 연산 1. pop() : 스택에서 가장 위에 있는 항목(top)을 제거하며 반환 2. push(item) : item을 스택의 가장 윗 부분에 추가 3. peek().. [자료 구조] LinkedList 개념 설명과 구현 ⬛ LinkedList 개념 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조로 다음 노드에 대한 참조를 통해 연결된다. 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다. 동적으로 메모리를 사용할 수 있기 때문에 메모리를 효율적으로 사용할 수 있다. 삭제와 삽입의 과정만은 O(1)으로 해결되지만 해당 위치를 찾기 위해 첫 번째 노드부터 순차적으로 요소에 접근하는 과정에서 O(n)의 시간이 추가적으로 발생한다. 결국 O(n)의 시간복잡도를 가지게 된다. ⬛ LinkedList 연산 1. add(E e) : list의 끝에 지정된 요소를 추가 2. add(int index, E element) : list의 지정된 위치에 지정된 요소 삽입 3. addFirst(E e) : l.. 이전 1 다음
