A: 자료구조는 컴퓨터에서 데이터를 효율적으로 저장하고 조작할 수 있도록 조직화하는 방법입니다. 데이터의 삽입, 삭제, 검색 등의 연산을 효율적으로 수행하기 위해 데이터들 간의 관계를 정의한 것이라고 할 수 있습니다. 좋은 자료구조를 선택하면 알고리즘의 효율성을 크게 향상시킬 수 있습니다.

A: 배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조입니다. 인덱스를 통해 직접 접근이 가능하여 검색의 시간복잡도가 O(1)입니다. 하지만 중간에 원소를 삽입하거나 삭제할 때는 다른 원소들을 이동시켜야 하므로 O(n)의 시간이 걸립니다. 크기가 고정되어 있어 메모리를 효율적으로 사용할 수 있지만, 동적으로 크기를 변경하기 어렵다는 단점이 있습니다.

A: 연결리스트는 노드들이 포인터로 연결된 동적 자료구조입니다. 배열과 달리 메모리상에서 연속적으로 저장되지 않으며, 각 노드가 데이터와 다음 노드의 주소를 가지고 있습니다. 삽입과 삭제는 O(1)로 배열보다 빠르지만, 특정 위치에 접근하려면 처음부터 순차적으로 탐색해야 하므로 검색은 O(n)입니다. 동적으로 크기를 조절할 수 있어 메모리를 유연하게 사용할 수 있습니다.

A: 스택은 LIFO(Last In First Out) 구조로 마지막에 들어간 데이터가 먼저 나오는 자료구조입니다. push와 pop 연산을 통해 데이터를 추가하고 제거하며, 함수 호출이나 재귀 알고리즘에 주로 사용됩니다. 큐는 FIFO(First In First Out) 구조로 먼저 들어간 데이터가 먼저 나오는 자료구조입니다. enqueue와 dequeue 연산을 사용하며, BFS나 작업 스케줄링에 활용됩니다.

A: 해시 테이블은 해시 함수를 사용하여 키를 배열의 인덱스로 변환하고, 해당 위치에 값을 저장하는 자료구조입니다. 이상적인 경우 삽입, 삭제, 검색이 모두 O(1)의 시간복잡도를 가집니다. 하지만 서로 다른 키가 같은 해시값을 가지는 충돌이 발생할 수 있어, 체이닝이나 오픈 어드레싱 같은 충돌 해결 방법이 필요합니다.

A: 이진 트리는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리 구조입니다. 왼쪽 자식과 오른쪽 자식으로 구분되며, 계층적 데이터를 표현하는 데 적합합니다. 루트 노드부터 시작해서 레벨별로 데이터를 저장하며, 트리 순회 방법으로는 전위, 중위, 후위 순회가 있습니다.

A: 이진 탐색 트리는 왼쪽 서브트리의 모든 노드 값이 루트보다 작고, 오른쪽 서브트리의 모든 노드 값이 루트보다 큰 성질을 만족하는 이진 트리입니다. 이 성질 덕분에 검색, 삽입, 삭제 연산을 평균적으로 O(log n)에 수행할 수 있습니다. 하지만 트리가 한쪽으로 치우친 경우 최악의 경우 O(n)이 될 수 있습니다.

A: 힙은 완전 이진 트리의 형태를 가진 자료구조로, 최대 힙과 최소 힙으로 나뉩니다. 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지며, 최소 힙은 그 반대입니다. 우선순위 큐를 구현하는 데 주로 사용되며, 힙 정렬 알고리즘의 기반이 됩니다. 삽입과 삭제 연산이 O(log n)의 시간복잡도를 가집니다.

A:AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1인 자기 균형 이진 탐색 트리입니다. 더 엄격한 균형 조건을 유지하여 검색 성능이 우수하지만, 삽입과 삭제 시 회전 연산이 자주 발생합니다. Red-Black 트리는 각 노드에 색깔 정보를 추가하여 균형을 유지하는 트리로, AVL 트리보다 균형 조건이 완화되어 삽입과 삭제가 더 효율적입니다.

A: B-트리는 하나의 노드에 여러 개의 키를 저장할 수 있는 다진 트리로, 디스크 I/O를 최소화하는 데 최적화되어 있습니다. 디스크에서 한 번의 읽기로 여러 키를 가져올 수 있어 외부 저장장치의 특성에 적합합니다. 또한 모든 리프 노드가 같은 레벨에 있어 일정한 검색 성능을 보장하며, 삽입과 삭제 시에도 트리의 균형을 자동으로 유지합니다.

A: 체이닝은 같은 해시값을 가진 데이터들을 연결리스트로 연결하는 방법입니다. 구현이 간단하고 테이블이 가득 차도 동작하지만, 추가 메모리가 필요하고 캐시 성능이 떨어질 수 있습니다. 오픈 어드레싱은 충돌 발생 시 다른 빈 슬롯을 찾는 방법으로, 선형 탐사, 제곱 탐사, 이중 해싱 등이 있습니다. 메모리 효율성이 좋지만 삭제가 복잡하고 클러스터링 문제가 발생할 수 있습니다.

A: 인접 행렬은 2차원 배열로 그래프를 표현하는 방법입니다. 두 정점 간의 연결 여부를 O(1)에 확인할 수 있고 구현이 간단하지만, 정점 수의 제곱만큼 메모리를 사용하여 희소 그래프에서는 비효율적입니다. 인접 리스트는 각 정점마다 연결된 정점들의 리스트를 유지하는 방법으로, 간선 수에 비례하는 메모리만 사용하여 효율적이지만, 두 정점의 연결 여부 확인이 O(V)까지 걸릴 수 있습니다.

A: 트라이는 문자열을 저장하고 검색하는 데 특화된 트리 자료구조입니다. 각 노드가 하나의 문자를 나타내며, 루트에서 특정 노드까지의 경로가 하나의 문자열을 구성합니다. 문자열의 길이를 m이라 할 때 삽입, 삭제, 검색이 모두 O(m)에 가능합니다. 자동 완성, 사전 검색, IP 라우팅 등에 활용되며, 공통 접두사를 가진 문자열들을 효율적으로 저장할 수 있습니다.

A: 세그먼트 트리는 배열의 구간에 대한 쿼리를 효율적으로 처리하기 위한 트리 자료구조입니다. 각 노드가 특정 구간의 정보를 저장하며, 리프 노드는 배열의 개별 원소를 나타냅니다. 구간 합, 최댓값, 최솟값 등의 쿼리를 O(logn)에 처리할 수 있고, 원소 값 변경도 O(log n)에 가능합니다. 대량의 구간 쿼리가 있는 문제에서 효과적으로 사용됩니다.

A: Union-Find는 서로소 집합들을 효율적으로 관리하는 자료구조입니다. 각 집합을 트리로 표현하고, 트리의 루트를 집합의 대표로 사용합니다. Find 연산은 원소가 속한 집합의 대표를 찾고, Union 연산은 두 집합을 하나로 합칩니다. 경로 압축과 랭크에 의한 합치기 최적화를 적용하면 거의 상수 시간에 연산이 가능하며, 크러스칼 알고리즘이나 연결 성분 찾기에 활용됩니다.

A: 동적 배열은 크기를 런타임에 조절할 수 있는 배열입니다. 내부적으로 고정 크기의 배열을 사용하되, 용량이 부족해지면 더 큰 배열을 할당하고 기존 데이터를 복사합니다. 일반적으로 용량이 가득 찰 때마다 2배씩 확장하는 전략을 사용하여, 삽입의 분할상환 시간복잡도를 O(1)로 만듭니다. 메모리 사용량과 복사 비용 사이의 균형을 맞춘 효율적인 자료구조입니다

A: 스킵 리스트는 정렬된 연결리스트에 여러 레벨의 "지름길"을 추가한 확률적 자료구조입니다. 각 노드가 여러 레벨의 포인터를 가져서 빠른 검색을 가능하게 합니다. 검색, 삽입, 삭제가 평균적으로 O(log n)의 성능을 보이며, 구현이 이진 탐색 트리보다 간단합니다. Redis 같은 시스템에서 정렬된 집합을 구현하는 데 사용됩니다.

A: 블룸 필터는 어떤 원소가 집합에 속하는지를 확률적으로 검사하는 자료구조입니다. 비트 배열과 여러 개의 해시 함수를 사용하여 원소를 저장합니다. 거짓 양성은 있을 수 있지만 거짓 음성은 없어서 "확실히 없다" 또는 "있을 수도 있다"라는 답을 줍니다. 메모리를 매우 효율적으로 사용하여 대용량 데이터에서 중복 검사나 캐시 시스템에 활용됩니다.

A: LRU(Least Recently Used)는 가장 오래 사용되지 않은 데이터를 교체하는 방식으로, 연결리스트와 해시맵을 조합해서 O(1)에 구현할 수 있습니다. LFU(Least Frequently Used)는 가장 적게 사용된 데이터를 교체하며, FIFO는 가장 먼저 들어온 데이터를 교체합니다. Random은 무작위로 선택하는 방식으로 구현이 간단합니다. 각각 지역성의 종류에 따라 다른 성능을 보입니다.

A: KMP 알고리즘에서는 부분 매치 테이블(접두사 함수)을 사용하여 불일치 시 얼마나 이동할지 미리 계산합니다. Rabin-Karp 알고리즘은 롤링 해시를 사용하여 문자열의 해시값을 효율적으로 업데이트합니다. Aho-Corasick 알고리즘은 트라이와 실패 함수를 결합하여 여러 패턴을 동시에 검색합니다. 접미사 배열이나 접미사 트리는 문자열의 모든 접미사 정보를 저장하여 복잡한 문자열 질의를 처리합니다.

A: 메모리 풀은 미리 큰 메모리 블록을 할당해두고, 필요할 때마다 작은 단위로 나누어 사용하는 메모리 관리 기법입니다. 동적 할당과 해제의 오버헤드를 줄이고, 메모리 단편화를 방지하며, 할당 속도를 향상시킵니다. 특히 같은 크기의 객체를 자주 생성하고 삭제하는 상황에서 효과적이며, 게임 엔진이나 실시간 시스템에서 널리 사용됩니다.

A: 스레드 안전성을 위해 뮤텍스나 스핀락 같은 동기화 기법을 사용할 수 있습니다. Lock-free 자료구조는 원자적 연산(atomic operations)을 사용하여 락 없이도 동시성을 보장합니다. Copy-on-Write 방식은 읽기가 많은 상황에서 효과적이며, 세분화된 락킹은 전체 자료구조가 아닌 부분적으로만 락을 거는 방법입니다. 각 방법은 성능과 복잡성 사이의 트레이드오프를 가집니다.

A: 압축 자료구조는 이론적 최소 공간에 가까운 메모리를 사용하면서도 효율적인 연산을 지원하는 자료구조입니다. 예를 들어, 비트 벡터에서 rank와 select 연산을 상수 시간에 지원하면서도 추가 공간을 거의 사용하지 않습니다. Wavelet 트리, FM-인덱스 등이 대표적이며, 대용량 데이터 처리나 생물정보학에서 활용됩니다.

A: 영속적 자료구조는 수정 연산 후에도 이전 버전을 그대로 유지하는 자료구조입니다. Path copying, Fat node, Copy-on-Write 등의 기법을 사용하여 구현하며, 함수형 프로그래밍 언어에서 주로 사용됩니다. 버전 관리, 되돌리기 기능, 병렬 처리에서 유용하지만 일반적으로 더 많은 메모리를 사용합니다.

A: 근사 자료구조는 정확한 결과 대신 근사치를 빠르게 제공하는 자료구조입니다. HyperLogLog는 집합의 크기를 근사적으로 계산하고, Count-Min Sketch는 원소의 빈도를 추정합니다. 스트리밍 데이터나 대용량 데이터에서 실시간 분석이 필요할 때 사용하며, 정확성을 일부 포기하는 대신 메모리와 처리 시간을 크게 절약할 수 있습니다.