이진 탐색 트리빠른 검색을 위해 사용하는 비선형 자료구조(트리 형태이므로)논리적으로 데이터가 정렬되어 있고 정렬된 상태를 유지하면서 데이터의 삽입/삭제를 O(logN)에 할 수 있다.아래 그림과 같이 왼쪽: 현재 노드 데이터보다 작은 값을 가지는 노드오른쪽: 현재 노드 데이터보다 큰 값을 가지는 노드 시간복잡도데이터 삽입/삭제O(logN)X라는 데이터 접근O(logN)X보다 Ceiling/Floor에 접근O(logN) 사용사례Java TreeMap, TreeSet내부적으로 이진 탐색 트리 중 하나인 Red-Black Tree 구조를 사용해서 데이터를 저장 및 관리한다. Java HashMap Chaining같은 key값에 여러 개의 value값을 가지는 경우 8개 이상을 가지는 데이터에서는 BST 형태로..
CS/Data Structure
연결리스트메모리 상에서는 데이터가 비연속적으로 저장되어 있는 선형 자료구조물리적으로 연속되어 있지 않고 논리적으로 다음 노드의 주소값을 저장해서 논리적으로 연속성을 구현[데이터, 다음/이전 노드 주소값] 쌍으로 저장head, tail 노드의 주소값을 항상 저장하고 있어 양 끝에서는 빠르게 접근 가능 연산삽입 1. 삽입하고 싶은 직전 노드까지 이동한다.2. 새로운 노드를 생성해서 데이터를 넣는다.3. 삽입하고 싶은 직전 노드에서 다음 노드의 주소값을 새로운 노드로 복사한다.4. 삽입 직전 노드에서 다음 노드를 생성한 노드로 가리킨다. 삭제 1. 삭제하고 싶은 노드까지 이동한다.2. 이전 노드의 다음 주소값을 삭제 다음 노드의 주솟값을 가리키게 한다.3. 삭제 노드의 메모리 할당을 해제한다. 시간복..
우선순위 큐우선순위가 높은 데이터가 먼저 들어오면 먼저나가는(FIFO) 비선형 자료구조힙이라고하는 자료구조를 사용해서 구현 힙우선순위 큐를 구현하기 위해 고안된 완전 이진 트리여러 데이터 중 우선순위가 높은 값을 찾기에 용이하다.힙에 있는 데이터의 배열을 순회했을 때, 정렬된 데이터가 아니다.(Java Iteration X) 최소 힙(Min Heap)우선순위가 낮은 데이터부터 꺼낸다. 최소 힙(Min Heap)우선순위가 높은 데이터부터 꺼낸다. 우선순위 큐 != 힙제일 중요한 것은 우선순위 큐가 힙이랑 동일한 자료구조가 아니라는 것이다. 힙이라는 것을 우선순위 큐를 구현하기 위해서 만든 자료구조라고 볼 수 있다. 트리구조인 힙보다 비효율적이겠지만, 배열을 넣을때마다 정렬해서 우선순위가 높고, 낮은 값을 ..
HashTable[key, value] 쌍으로 저장하는 비선형 자료구조이다.일정 크기의 배열을 생성 => key 값을 해시 함수를 통해 배열 Index 변환 => Index에 [key, value] 저장 비선형 자료구조 이유?선형 자료구조는 순차적으로 데이터를 저장한다.하지만, HashTable에서는 해시 함수로 어떤 인덱스 값이 나올지 몰라서, 순차적으로 저장하지 않으므로, 비선형 자료구조이다. 시간복잡도x라는 value값이 있는지 탐색O(N)x라는 key값이 있는지 탐색O(1)x라는 key에 접근O(1)[key, value] 저장, 삭제O(1) 해시충돌(Hash Collision)HashTable은 일정한 크기에 배열에 [key, value]를 저장해서 유한한 메모리에 저장해야한다.해시 함수를 사용해..
야구를 보러가거나 놀이기구를 기다릴때, 기다린 순서대로 먼저 탄다. 큐를 줄을 서는 것으로 생각하면 된다. 큐데이터가 논리적(물리적 x)로 저장되어 있는 자료구조chunk라는 단위로 내부적으로 저장FIFO(First In First Out)자료구조이다. 연산Enqueue: 큐에 데이터를 넣는다.Dequeue: 큐에 데이터를 꺼낸다. 시간복잡도i번째 데이터 접근O(N)x라는 데이터 탐색O(N)맨 앞 데이터 접근(peek)O(1)데이터 추가(Enqueue)O(1)데이터 추가(Dequeue)O(1) 사례CPU 스케쥴링운영체제에서 여러 프로세스가 CPU를 할당받으려고 할때, 큐에 추가된다. 네트워크 패킷라우터에서 데이터 패킷이 들어오는 순서대로 큐에 저장되고, 들어온 순서에 맞춰서 전송한다. 배치 처리(Ba..
롤 유저들은 나서스라는 챔프에 대해 알 것이다. 나서스는 q스킬이 스택을 쌓고 있다고 흔히들 표현하는데, 그 스택이라고 생각하면 기억하기 용이할 것이라고 생각한다.(데미지에 대한 데이터를 쌓는다) 스택데이터가 논리적(물리적 x)으로 저장되어 있는 자료구조LIFO(Last In First Out) 마지막에 들어온 데이터가 첫번째로 나가는 자료구조 두가지 연산push : 데이터를 넣는 연산pop : 데이터를 꺼내는 연산 시간복잡도맨위에 있는 데이터를 접근(peek)O(1)i번째 데이터 접근O(N)x라는 데이터가 있는지 탐색O(N)push 연산O(1)pop 연산O(1) ErrorStack 메모리를 초과Stack Overflow ErrorStack 데이터가 없을 때, pop을 수행할 경우, Empty Stac..
자료구조데이터를 효율적으로 저장하고 관리하기 위한 체계적인 구조어떤 자료구조를 선택하는가에 따라서, 성능과 효율성에 영향을 미칠 수 있으며, 상황에 따라 적절한 자료구조를 사용하는 것이 중요하다.예를 들어, 1~10억 까지 임의의 숫자 100만개의 데이터 원소가 배열과 힙(우선순위 큐를 구현하기 위한 자료구조)에 저장되어있다고 할때, 가장 작은 수를 찾는다고 하자.배열을 사용해서 데이터를 저장하면, 모든 수들을 순회해서 가장 작은 수를 찾아야한다.(100만번 연산)힙을 사용해서 데이터를 저장하면, 가장 상위 노드에 있는 값이 가장 작은 수이다.(log(100만)연산) 이와 같이 어떤 자료구조를 사용하는가에 따라서 프로그램의 성능은 매우 달라질 수 있다. 자료구조는 형태에 따라 선형/비선형 자료구조로 구분..
