한 걸음씩 기록하며

1. Hash Table 1.1 정의 해시 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다. 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 Direct address table과 달리 해시 테이블은 키 값을 입력받아서 해시 함수를 통해 얻은 해시를 인덱스 배열(버킷)로 환산해서 데이터에 접근한다. 이렇듯 해시 테이블은 각각의 key에 해시 함수를 적용해 해시를 생성하고, 해시를 활용해 값을 저장하거나 검색한다. 1.2 해시 테이블 구성 요소 1) 키(Key) 키는 고유한 값으로, 다양한 길이의 값이 될 수 있으모, 해시 함수의 input이 된다. 키는 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야하기 때문에 해..

1. BST (Binary Search Tree) vs Tree Tree 트리는 그 자체로는 데이터의 특성에 아무런 제약이 없음 트리 구조는 특정한 값을 찾기 위해서 모든 값을 탐색해야함 (시간 복잡도 O(N)) BST 이진 탐색 트리는 이진 트리의 구조이지만, 데이터 값의 제약이 생긴다는 점에서 차이를 보인다. 아래와 같은 제약을 줆으로써, 탐색 속도를 향상시켜준다. (시간 복잡도 O(logN)) 하나의 노드라도 아래의 조건을 충족하지 못하면 BST가 아님 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 중복된 키를 허용하지 않음 2. BST 연산 2.1 검색 전..

1. 트리와 용어 정리 트리(Tree)는 그래프의 일종으로, 노드들이 나무가지처럼 연결된 비선형 계층적 자료구조이다. 트리는 데이터 구조의 계층적인, 상하 관계 속성을 표현한다. 선형적 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재했다. 트리도 내부적으로 순서 정보를 가지도록 구현할 수 있지만, 트리라는 자료구조 자체에서 데이터의 순서는 그리 중요한 요소가 아니다. * Tree와 관련된 용어 정리 - 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. - 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다. - 내부(internal) 노드: 단말 노드가 아닌 노드 - 간선(edge): 노드를 연결하는 선 (l..

Deque (Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말이다. rear로만 데이터를 삽입했던 큐와 달리, front와 rear에서 삽입과 삭제가 모두 가능한 양방향 큐이다. 연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고, 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다. 또한 중간에 데이터가 삽입될 떄 다른 요소들을 앞, 뒤로 밀 수 있다. 중간 삭제시 성능이 그리 좋진 않다. 삽입 삭제 연산은 O(1)의 시간 복잡도를 가지고, 스택&큐와 달리 index를 통해 요소들에 탐색이 가능하므로 검색 또한 O(1)의 시간복잡도를 가진다. 장점 구현자의 편의에 따라 deque는 stack처럼 사용할 수도 있고, queue처럼 사용할 수 있다...

1. Stack 후입선출(Last-In First-Out / LIFO) : 나중에 들어온 데이터가 먼저 나감 후임선출 방식의 자료구조로, 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 대표적인 스택의 활용으로는, 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이 있다. 장점 구조가 단순해서 구현이 쉽다. 데이터 저장/ 읽기 속도가 빠르다 단점 데이터 최대 개수를 미리 정해야한다. 저장 공간의 낭비가 발생할 수 있다. 미리 최대 개수만큼의 저장 공간을 확보해야한다. 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. (이 경우 위에서 열거한 단점이 발생한다.) 2. Queue 1) Queue 선입선출 (First-In Fast-Out / FI..

Linked List 1) Linked List (연결 리스트) 배열이 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조라면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다. 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 배열은 데이터만 가지고 있는 반면, 링크드 리스트는 데이터 + 다음 데이터의 주소 값을 가진다. 배열은 미리 셋팅하고 데이터를 넣으므로, 데이터를 추가할 수 없다 혹은 어렵다. (원래는) 링크드 리스트는 포인터가 있기 때문에 추가하기 쉽다. 장점 데이터 추가나 삭제가 쉽게 가능하고, 빠르다. ..

ArrayList(배열) *Array와 ArrayList는 거의 비슷하나 약간의 차이가 있다. 가장 큰 차이점은 길이를 조정할 수 있는가이다. Array는 고정 길이지만, ArrayList는 가변 길이이다. 가장 기본적인 자료구조로서, 같은 자료형의 변수들을 모아서데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 컴퓨터의 실제 메모리 공간을 연속적으로 사용하기에, 컴퓨터가 연산을 하기 쉬운 구조를 가지고 있음. (논리적 저장 순서와 물리적 저장 순서가 일치한다.) 장점 검색 속도가 그 어떤 자료구조보다 빠르다 인덱스를 통한 데이터 접근은 Random Access 방식 시간 복잡도 O(1) 캐시 히트의 가능성이 높다. (데이터가 군집되어 있기 때문) 단점 한번 고정적으로 선언된 배열..

1. Data Structure(자료구조)란? 자료(Data)란 현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합을 의미 가공되지 않은 데이터를 특정한 용도로 사용하기 위하여 처리/가공한 형태의 데이터를 정보(information)이라 한다. 자료구조는 자료의 집합으로서, 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열하여, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 의미한다. 즉 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 Q. 어떠한 구조로 데이터를 관리해야하는가? 자료구조의 선택 기준을 무엇으로 잡아야하는가? 1) 자료의 처리 시간, 2) 자료의 크기, 3) 자료의 활용 빈도, 4) 자료의 갱신..