철학과 학생의 개발자 도전기

M원 검색트리(M-way Search Tree) 특징 차수를 2에서 m으로 확장해 이진탐색트리의 높이 문제를 해결한 자료구조 각 노드는 m-1개의 레코드와 m개의 서브트리를 가질 수 있다. 각 노드의 레코드들은 정렬되어 있다. B 트리 특징 높이 문제를 개선한 M원 검색트리에서 균형 문제도 해결한 자료구조 데이터의 삽입, 삭제 시 균형을 맞추는 알고리즘을 수행한다. 규칙 모든 단말 노드는 같은 레벨에 있다. 노드는 최대 M개, 최소 ⌈M/2⌉개의 자식을 가진다. 노드는 최대 M−1개, 최소 [M/2]−1개의 키를 가진다. 노드의 키가 X개면, 자식의 수는 X+1개다. 시간 복잡도 원소 삽입, 삭제, 탐색: O(logN) Key 삽입 과정 요소를 삽입할 단말 노드를 선택 후 Key 삽입 Key의 최대개수..

트라이란? 문자열을 효율적으로 탐색하기 위한 트리 형태의 자료구조 검색(reTRIEve)이라는 단어에서 유래되었으며, 검색엔진이나 자동완성 등에서 사용된다. 자식 노드의 포인터를 저장해야하므로 저장 공간이 추가로 요구된다. (배열 또는 HashMap 사용) 시간 복잡도 원소 삽입, 삭제, 탐색: O(M) (M은 문자열의 길이) 원소 탐색 과정 1. 루트의 자식 노드에서 첫번째 글자를 찾는다. 2. 첫번째 글자의 자식 노드에서 다음 글자를 찾는다. 3. 마지막 글자에 해당하는 노드가 존재하고, 노드에 실제 값이 존재하면 탐색 성공 *삽입과 삭제도 위 탐색 과정을 거친 후, 노드를 추가하거나 삭제하면 된다.

해시 테이블 특징 Key-Value 매핑 구조 해시 함수를 이용해서 키에 해당하는 값에 빠르게 접근 가능 해시 함수: 입력값을 고정된 길이의 출력값으로 변환 -> 주소값으로 사용 해시 알고리즘에 따라 성능이 달리진다. 시간복잡도 원소 접근, 삽입, 삭제: 평균 O(1) -> 최악의 경우 O(N) *해시 충돌 서로 다른 키가 같은 해시값을 가질 수 있다. 충돌 문제에 대한 대응으로 체이닝 기법을 사용한다. 최악의 경우, 체이닝으로 연결된 데이터를 탐색하면서 시간복잡도가 O(N)이 될 수 있다. 체이닝을 선형구조가 아니라 레드 블랙 트리 등의 트리 구조로 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.

1. 트리 특징 루프가 없는 무방향 그래프 구조 루트, 부모, 자식, 형제 노드로 구성되는 계층형 자료구조 하나의 루트가 존재하며, 자식 노드는 하나의 부모 노드만 가진다. 2. 힙 특징 최대값이나 최소값을 빠르게 찾기 위한 자료구조 왼쪽 자식 노드부터 채워지는 완전이진트리 구조 중복을 허용한다. 우선순위 큐를 구현하는 데 사용된다. 시간복잡도 원소 삽입: O(logN) 원소 삭제: O(logN) *원소 삽입 1. 최하단에 노드를 삽입한다. 2. 부모 노드와 값을 비교해서 힙 종류에 맞게 스왑한다. 3. 스왑되지 않을 때까지 반복한다. *원소 삭제 1. 루트 노드를 삭제한다. 2. 최하단 노드를 루트 노드로 옮긴다. 3. 자식 노드와 값을 비교해서 힙 종류에 맞게 스왑한다. 4. 스왑되지 않을 때까지 반..

1. 스택 특징 LIFO 구조 입력과 출력이 한 곳에서만 발생한다. (top) 삽입 연산을 push, 삭제 연산을 pop이라고 부른다. 시간복잡도 원소 접근: O(N) 원소 삽입, 삭제: O(1) 원하는 순서 혹은 데이터를 찾으려면 순차적으로 접근해야 한다 -> 최악의 경우 O(N) 삽입과 삭제는 한 곳에서만 발생한다 -> O(1) 2. 큐 특징 FIFO 구조 입력은 맨 뒤(rear), 출력은 맨 앞(front)에서만 발생한다. 삽입 연산을 enqueue, 삭제 연산을 dequeue라고 부른다. 시간복잡도 원소 접근: O(N) 원소 삽입, 삭제: O(1) 원하는 순서 혹은 데이터를 찾으려면 순차적으로 접근해야 한다 -> 최악의 경우 O(N) 삽입과 삭제는 각각 한 곳에서만 발생한다 -> O(1) 3. 스..

1. 배열 특징 메모리에 데이터가 연속적으로 저장되는 자료구조 고정된 크기의 메모리를 미리 할당받는다. 순서가 존재하며 데이터를 참조할 때 인덱스를 사용한다. (0번부터 시작) 시간복잡도 원소 접근: O(1) 원소 삽입, 삭제: O(N) 배열의 시작 주소와 offset만 알면 offset 덧셈을 통해 원하는 인덱스에 한 번에 접근할 수 있다 -> O(1) 삽입을 할 경우, 삽입에 필요한 공간을 마련하기 위해 원소들을 한 칸씩 뒤로 밀 수 있다 -> 최악의 경우 O(N) 삭제를 할 경우, 데이터의 연속성을 보장하기 위해 원소들을 한 칸씩 앞으로 밀 수 있다 -> 최악의 경우 O(N) 2. 연결 리스트 특징 데이터가 비연속적으로 저장되며 순서를 가지는 자료구조 각 노드는 데이터 값과 다음 노드의 주소를 가지..