본문 바로가기

CS 과목(CS科目）/자료 구조(Data Structure)

DB Index에서 사용되는 B tree(데이터 삽입) 아래에 이진 탐색 트리에 대한 간단한 개요가 있다. 이진 탐색 트리는 최대 2 개의 자식 노드를 가질 수가 있다. 그러나 만약 자식 노드의 개수를 3개로 늘리면서, 이진 탐색 트리와 같은 동작 방식으로 데이터를 삽입,조희,삭제를 해주기 위해서는 어떻게 하면 될까??? 왼쪽의 BST의 왼쪽 서브 트리의 모든 노드는 50보다 작고, 오른쪽 서브 트리의 모든 노드는 50보다 크다. 오른쪽의 자녀 노드가 3개인 경우에도 이와 같은 규칙성을 가지게 해보자. 일단 자식 노드가 3개이므로, 각 노드의 부모 노드와의 대소관계는 BST가 2개였던 거와는 달리, 3개가 된다. 즉, 왼쪽 자식 노드부터 아래와 같이 정의가 된다. ( 참고로, 이때에는 부모 노드가 2개 있어야 한다 ) 1] SubTree < k1 : 왼쪽 서.. 더보기
Deque(덱) 1. Deque의 개념과 구조 Deque(데크)는 double-ended-queue의 줄임말로, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조이다. 아래 그림과 같이, 양방향에서 엘리먼트를 추가, 삭제할 수 있는 양방향 큐라고 생각하면 된다. 2. Deque에 존재하는 메서드 종류 Python에서 deque는 collections라는 모듈안에 deque클래스로 내장되어있다. 가장 기본적인 append() 메서드를 수행하면 다음과 같다. from collections import deque deq = deque(['a', 'b', 'c']) deq.append('d') print(deq) # deque(['a', 'b', 'c', 'd']) 기본 append()를 해주면 위의 예제와 같이 가장 .. 더보기
원형 큐(Circular Queue)를 사용하는 이유!!! 일반 적으로 큐는 push와 pop을 반복하다보면 점점 큐는 오른쪽으로 이동하게 된다. 그렇다면 결국,큐 배열의 최대 공간 까지 밖에 사용할 수 없다. 이를 보완하기 위해 원형큐를 이용하여 계속해서 공간을 활용 할 수 있다. ​ 최대공간크기의 -1 의 다음 공간은 0으로 하여 연속적으로 저장할 수 있게 한다. ​ ​ 큐가 가득 찬 것을 알기 위해서 front가 위치한 곳은 데이터를 저장할 수 없도록 비워둔다. %와 maxQueueSize를 이용하여 front와 rear값은 증가하지만, 같은 maxQueueSize만큼의 공간 에서만 데이터를 저장하도록 한다. ​ 이때 , front와 rear의 초기값은 0으로 시작한다. ​ ​ front와 rear의 값이 같다면 empty 조건이며, ​ rear+1의 위치.. 더보기
Stack, Queue, List, set 등의 자료구조 사용 시 주의 사항 데이터 구조는 말 그대로, 어떻게 데이터를 효울적으로 저장(insert), 삭제(delete), 탐색(peek)할 것인지에 대한 방법론이 다. 특히 저장(insert)와 삭제(delete)가 주된 동작(Operation)이다. 그러나 저장과 삭제 구현 시 주의해야 할 사항이 있다. 저장(insert)(맨 처음 삽입, 중간 삽입, 끝 삽입마다 동작(구현)이 다를 수 있음에 주의!) ex) Queue가 있다고 하자. 그 Queue에 데이터를 저장(insert)하려고 하는데, 만약 Queue가 이미 사이즈만큼 다 찼다면??? JAVA에서는 이때 OutOfMemory라는 예외(Exception)이 발생한다. 삭제(delete)(처음 삭제, 중간 삭제, 끝 삭제마다 동작(구현)이 다를 수 있음에 주의!!) ex).. 더보기
기술 문서에서 Queue라는 용어를 만났을 때의 주의점 Queue라고 해서 항상 FIFO를 의미하는 것은 아니다. EX) Queue라고 쓰여 있다고, 그 실체가 Prioriy Queue인 경우는 FIFO가 아니게 된다. -> 고로, 기술 문서에서 Queue라는 용어를 만나면, 문맥을 잘 파악을 해서, 1. FIFO를 보장하는 그 Queue인가? 2. 그냥 뭉뚱그려서 Queue라고 한 건지? 를 분별해야 한다. 더보기
Stack vs Queue(dequeue) 사용이 적절할 때 or 관련 에러(in JAVA) Stack : 가장 최근의 데이터가 필요할 떄! Queue(dequeue) : 1.가장 이전의 데이터가 필요할 때! 2.무언가를 대기시키고 싶을 때!(ex. Ready Queue, Waiting Queue) (아래는 JAVA를 기준으로 설명을 하였다.) Stack과 관련된 에러 1. stackoverflow : 할당된 스택 메모리가 다 찼을 떄!! -> 거의 대부분 재귀함수 떄문에 발생 Queue와 관련된 에러 1. OutOfMemory -> JAVA에서 Heap 메모리를 다 썼을 때 발생 -> Queue에 데이터가 쌓이기만 해서, heap 메모리를 다 잡아 먹어 버리면 발생 Solution : Queue의 사이즈를 고정시킨다. Q. 그럼 고정된 사이즈가 다 찼을 때는 어떻게 처리를 해 줘야 할까? A... 더보기

티스토리툴바