Data-Structures

Non-Primitive Linear Data Structure vs. Non-Linear Data Structure 데이터 구조는 크게 Linear Data Structure와 Non-Linear Data Structure로 나눌 수 있다. 측면 Linear Data Structure Non-Linear Data Structure 정의 데이터 요소가 순차적 또는 선형적으로 배열된 구조 데이터 요소가 순차적이거나 선형적으로 배열되지 않은 구조 구조 단일 레벨 구조 다중 레벨 구조 데이터 관계 요소 간 1:1 관계 요소 간 1:N 또는 N:N 관계 순회 단일 실행으로 모든 요소 순회 가능 단일 실행으로 모든 요소 순회 불가능 구현 복잡성 구현이 상대적으로 간단 구현이 상대적으로 복잡 메모리 사용 메모리 사용이 덜 효율적 메모리 사용이 더 효율적 시간 복잡도 입력 크기에 따라 증가 특정 작업에서 더 효율적 데이터 접근 순차적 접근 계층적 또는 네트워크 기반 접근 삽입/삭제 상대적으로 간단 더 복잡하지만 유연함 응용 분야 간단한 데이터 저장 및 처리 복잡한 관계 표현, AI, 이미지 처리 등 예시 배열, 연결 리스트, 스택, 큐 트리, 그래프, 해시 테이블, 힙 공통점: ...

Primitive Data Structure vs. Non-Primitive Data Structure Primitive Data Structure Primitive data structure는 프로그래밍 언어에 내장된 가장 단순하고 기본적인 데이터 타입이다. 이들은 단일 값을 표현하며, 더 이상 분해할 수 없는 가장 작은 단위의 데이터 구조이다. 주요 특징 단순성: 가장 기본적이고 이해하기 쉬운 데이터 타입이다. 고정 크기: 일반적으로 고정된 메모리 크기를 가진다. 효율성: 메모리 사용과 접근 시간 측면에서 매우 효율적이다. 직접 표현: 컴퓨터 하드웨어에서 직접 지원되는 데이터 타입이다. 값 의미론: 변수에 실제 값이 직접 저장된다. 스택 할당: 주로 스택 메모리에 할당되어 빠른 접근이 가능하다. 주요 primitive data structure들을 비교 분석하여 정리한 표: ...

Suffix Array vs. Suffix Tree vs. Trie Suffix Array, Suffix Tree, 그리고 Trie는 모두 문자열 처리와 패턴 매칭을 위한 데이터 구조로, 각각 고유한 특성과 용도를 가지고 있다. 특성 Suffix Array Suffix Tree Trie 기본 구조 모든 접미사를 정렬하여 저장하는 1차원 배열 모든 접미사를 트리 형태로 저장하는 압축된 트리 구조 문자열을 문자 단위로 저장하는 트리 구조 메모리 효율성 O(n), 매우 효율적 O(n), 하지만 실제로는 4n 정도로 큼 O(ALPHABET_SIZE key_length n), 매우 큼 구축 시간 O(n log n) O(n) (Ukkonen’s Algorithm 사용 시) O(n * key_length) 검색 시간 O(m log n + occ), m은 패턴 길이 O(m + occ), m은 패턴 길이 O(m), m은 검색할 문자열 길이 구현 난이도 비교적 간단 매우 복잡 비교적 간단 LCP 계산 추가 배열 필요 트리 구조에서 직접 계산 가능 해당 없음 패턴 매칭 이진 검색 이용 트리 순회로 직접 검색 트리 순회로 직접 검색 공간 지역성 매우 좋음 (연속된 메모리) 보통 (포인터로 인한 흩어짐) 나쁨 (노드가 메모리에 흩어짐) 주요 응용 텍스트 검색, DNA 분석 문자열 처리, 바이오인포매틱스 사전 구현, 자동 완성 동적 업데이트 어려움 가능하나 복잡 쉬움 접두사 검색 어려움 가능하나 비효율적 매우 효율적 최장 공통 접두사 추가 작업 필요 직접 계산 가능 직접 계산 가능 최장 공통 부분 문자열 LCP 배열 필요 직접 계산 가능 부적합 압축 가능성 제한적 매우 좋음 있음 (압축 트라이) 캐시 성능 매우 좋음 보통 나쁨 실제 사용 사례 대용량 문자열 검색 시스템 생물정보학, 문자열 처리 자동 완성, 사전 검색 추가적인 중요 고려사항: ...

스패닝 트리(Spanning Tree) 스패닝 트리(Spanning Tree) 는 무방향 그래프(Undirected Graph)의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프이다. 다시 말해, 원래 그래프의 모든 정점을 최소한의 간선으로 연결한 트리 구조이다. 신장 트리는 그래프 이론의 핵심 개념으로, 다양한 실제 문제 해결에 활용된다. 최소 신장 트리 알고리즘인 크루스칼, 프림, 보로프카는 각각 다른 상황에서 최적의 성능을 보이며, 알고리즘 선택은 그래프의 특성과 문제 요구사항에 따라 달라진다. 신장 트리의 응용은 네트워크 설계, 클러스터링, 이미지 처리 등 다양한 분야에 걸쳐 있으며, 그 변형과 확장은 더 복잡한 문제를 해결하는 데 도움이 된다. 최적화 기법과 효율적인 자료구조를 활용하면 대규모 그래프에서도 신장 트리를 효과적으로 계산할 수 있다. ...

무방향 그래프(Undirected Graph) 무방향 그래프(Undirected Graph) 는 각 간선(Edge)에 방향성이 없는 그래프이다. 즉, 정점 A와 정점 B가 간선으로 연결되어 있으면, A에서 B로 가는 것과 B에서 A로 가는 것이 동일하다. 무방향 그래프 특징 간선이 양방향(↔)으로 연결됨 정점 간 이동에 방향성이 없음 정점의 차수(Degree)는 해당 정점과 연결된 간선의 개수 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 알고리즘이 적용 가능 연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph) 개념 적용 가능 무방향 그래프의 표현 방법 1 2 3 A — B | | C — D A - B (A와 B는 서로 연결됨) A - C (A와 C는 서로 연결됨) B - D (B와 D는 서로 연결됨) C - D (C와 D는 서로 연결됨) 무방향 그래프의 인접 행렬(Adjacency Matrix) 표현 A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0 설명 ...

방향 그래프(Directed Graph) 방향 그래프(Directed Graph, Digraph) 는 각 간선(Edge)에 방향성이 부여된 그래프이다. 즉, 간선이 단방향이므로 A → B 는 이동할 수 있지만 B → A 로는 이동할 수 없다. 방향 그래프는 일방향 관계가 있는 다양한 시스템을 모델링할 수 있다. 웹, 사회 연결망, 컴퓨터 시스템, 생물학적 네트워크 등 다양한 분야에서 방향 그래프를 활용한 알고리즘과 모델이 개발되고 있다. 방향 그래프 특징 간선이 한 방향(→)으로만 연결됨 단방향 관계를 표현할 때 사용 (예: 팔로우 관계, 웹 페이지 링크) 진입 차수(In-degree)와 진출 차수(Out-degree) 개념이 존재 진입 차수(In-degree): 해당 정점으로 들어오는 간선의 개수 진출 차수(Out-degree): 해당 정점에서 나가는 간선의 개수 방향 그래프의 표현 방법 방향 그래프 예시 ...

Stack vs. Queue 스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 널리 사용되는 선형 자료구조로, 데이터의 저장 및 처리 방식에서 차이가 있다. 스택(Stack) 스택은 후입선출(LIFO, Last-In First-Out) 방식의 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입과 삭제는 모두 스택의 **탑(top)**에서 이루어진다. 주요 연산: 삽입(Push): 데이터를 스택의 탑에 추가한다. 삭제(Pop): 스택의 탑에 있는 데이터를 제거하고 반환한다. 탑 확인(Peek): 스택의 탑에 있는 데이터를 제거하지 않고 확인한다. 비어있는지 확인(IsEmpty): 스택이 비어 있는지 여부를 확인한다. 큐(Queue) 큐는 선입선출(FIFO, First-In First-Out) 방식의 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입은 **후단(Rear)**에서, 삭제는 **전단(Front)**에서 이루어진다. ...

Octree Octree는 3차원 공간을 재귀적으로 분할하여 표현하는 트리 기반의 데이터 구조로, 3차원 공간을 8개의 동일한 크기의 정육면체(옥탄트)로 재귀적으로 분할하는 트리 구조이다. 각 노드는 공간의 한 영역을 나타내며, 필요에 따라 더 작은 영역으로 세분화된다.  특징 계층적 구조: 공간을 재귀적으로 분할하여 계층적으로 표현한다. 적응적 해상도: 필요한 영역만 세밀하게 분할하여 효율적인 공간 표현이 가능하다. 8분할: 각 노드는 최대 8개의 자식 노드를 가질 수 있다. 장점 효율적인 공간 표현: 복잡한 3차원 구조를 효율적으로 표현할 수 있다. 빠른 검색: 계층 구조를 활용하여 특정 영역의 빠른 검색이 가능하다. 메모리 효율성: 균일하지 않은 데이터 분포에 대해 메모리를 효율적으로 사용한다. 단점 구현 복잡성: 구현과 관리가 상대적으로 복잡할 수 있다. 메모리 오버헤드: 트리 구조로 인한 추가적인 메모리 사용이 발생할 수 있다. 불균형 가능성: 데이터 분포에 따라 트리가 불균형해질 수 있다. 응용 3D 컴퓨터 그래픽스: 3D 모델링, 렌더링, 충돌 감지 등에 사용된다. 로보틱스: 3D 환경 매핑 및 경로 계획에 활용된다. 게임 개발: 3D 게임 월드의 효율적인 표현과 관리에 사용된다. 과학 시뮬레이션: 대규모 3D 시뮬레이션에서 공간 데이터 관리에 활용된다. 동작 원리 초기화: 전체 3D 공간을 포함하는 루트 노드로 시작한다. 분할: 필요에 따라 각 노드를 8개의 자식 노드로 분할한다. 데이터 할당: 각 노드에 해당 영역의 데이터를 할당한다. 재귀적 분할: 특정 조건(예: 데이터 밀도, 깊이 제한)을 만족할 때까지 2-3 과정을 반복한다. 구성 요소 노드: 3D 공간의 한 영역을 나타내며, 데이터와 자식 노드에 대한 참조를 포함한다. 루트 노드: 전체 3D 공간을 나타내는 최상위 노드이다. 내부 노드: 8개의 자식 노드를 가질 수 있는 중간 노드이다. 리프 노드: 더 이상 분할되지 않는 최하위 노드로, 실제 데이터를 저장한다. 구현 방식 Octree의 기본적인 구현은 재귀적인 트리 구조를 사용한다. 다음은 Python을 사용한 간단한 Octree 구현 예시: ...

BK-tree BK-Tree(Burkhard-Keller Tree)는 메트릭 공간(metric space)에서 효율적인 근사 검색을 위해 설계된 트리 기반 데이터 구조이다. 주로 레벤슈타인 거리(Levenshtein Distance)를 활용한 문자열 유사성 검색, 맞춤법 검사, DNA 시퀀스 분석에 활용된다. BK-Tree는 유사성 검색이 필요한 분야에서 여전히 유효하나, 최근에는 SymSpell 등 더 빠른 알고리즘도 등장했다. 그러나 이론적 우아함과 구현 용이성으로 교육 및 소규모 시스템에서 널리 사용된다. BK-트리의 주요 특징 메트릭 공간에서의 효율적인 검색: BK-트리는 요소 간의 거리를 기반으로 데이터를 구성하여, 특정 요소와 유사한 요소를 빠르게 찾을 수 있다. 이산 메트릭 사용: 주로 레벤슈타인 거리(편집 거리)와 같은 이산 메트릭을 사용하여 문자열 간의 유사성을 측정한다. BK-트리의 구조 및 동작 원리 노드 구성: 각 노드는 하나의 요소를 저장하며, 자식 노드는 부모 노드와의 거리(d)를 기준으로 분류된다. 삽입: 새로운 요소를 삽입할 때, 루트 노드부터 시작하여 현재 노드와의 거리를 계산한다. 계산된 거리에 해당하는 자식 노드가 없으면 해당 위치에 새로운 노드를 추가하고, 있으면 해당 자식 노드로 이동하여 동일한 과정을 반복한다. 검색: 특정 요소와 유사한 요소를 찾기 위해, 루트 노드부터 시작하여 현재 노드와의 거리를 계산한다. 이 거리가 설정한 임계값 이하인 경우 해당 노드를 결과에 추가하고, 자식 노드들 중 현재 거리와 임계값의 차이 범위 내에 있는 노드들만 재귀적으로 탐색한다. BK-트리의 예시 단어 집합 {“book”, “books”, “cake”, “boo”, “boon”, “cook”, “cape”, “cart”}가 있을 때, 레벤슈타인 거리를 사용하여 BK-트리를 구성하면 다음과 같은 구조가 될 수 있다: ...

BSP Tree (Binary Space Partitioning Tree) BSP Tree는 공간을 재귀적으로 분할하여 표현하는 트리 구조의 데이터 구조로, 유클리드 공간을 초평면(hyperplane)을 기준으로 재귀적으로 분할하여 볼록 집합으로 나누는 기법을 트리 구조로 표현한 것이다. 이 과정에서 생성되는 트리를 BSP 트리라고 한다. https://www.researchgate.net/figure/Constructing-a-bsp-tree_fig1_238973971 특징 이진 트리 구조: 각 노드는 최대 두 개의 자식 노드를 가진다. 재귀적 분할: 공간을 계속해서 두 부분으로 나누어 표현한다. 볼록 집합: 분할된 각 공간은 볼록 집합(convex set)의 형태를 가진다. 계층적 구조: 공간을 계층적으로 표현할 수 있다. 장점 효율적인 렌더링: 3D 그래픽에서 렌더링 속도를 향상시킬 수 있다. 공간 분할: 복잡한 3D 공간을 효과적으로 표현할 수 있다. 충돌 감지: 게임이나 시뮬레이션에서 충돌 감지에 유용하다. 가시성 결정: 어떤 객체가 보이는지 빠르게 결정할 수 있다. 단점 전처리 시간: 초기 트리 구성에 많은 시간이 소요될 수 있다. 메모리 사용: 복잡한 공간의 경우 많은 메모리를 사용할 수 있다. 동적 환경에서의 한계: 자주 변하는 환경에서는 효율성이 떨어질 수 있다. 응용 3D 컴퓨터 그래픽스: 렌더링 최적화에 사용된다. 컴퓨터 게임: 특히 1인칭 슈팅 게임에서 널리 사용된다. CAD 시스템: 조립식 입체 기하학(CSG)에 활용된다. 로봇 공학: 충돌 감지 등에 사용된다. 동작 원리 분할 평면 선택: 공간을 분할할 평면을 선택한다. 공간 분할: 선택된 평면을 기준으로 공간을 두 부분으로 나눈다. 재귀적 분할: 각 부분에 대해 1, 2 과정을 반복한다. 종료 조건: 정해진 깊이에 도달하거나 더 이상 분할이 필요 없을 때 종료한다. 구성 요소 노드: 공간을 표현하는 기본 단위. 분할 평면: 각 노드에서 공간을 나누는 기준이 되는 평면. 왼쪽/오른쪽 자식 노드: 분할된 공간을 표현하는 하위 노드. 리프 노드: 더 이상 분할되지 않는 최종 공간을 나타내는 노드. 구현 방식 다음은 Python을 사용한 간단한 BSP Tree 구현 예시: ...