배열 (Array) 배열은 동일한 데이터 타입의 여러 값을 연속적인 메모리 공간에 순차적으로 저장하는 선형 자료구조로, 인덱스를 통해 빠른 접근이 가능한 특징이 있다. 배열은 초기 한 번 선언 시 정해진 크기를 가지며, 이 크기를 변경하기 어렵기 때문에 메모리 관리와 연산 측면에서 장단점을 지니고 있다. 배열은 같은 데이터 타입의 값들을 하나의 변수명으로 관리하며, 각 요소는 메모리상에 연속된 위치에 저장된다. **인덱스(index)**를 이용하여 원하는 위치의 데이터를 빠르게 검색할 수 있으며, 대부분 0번부터 시작하는 경우가 많다. 배열은 선형 자료구조이므로, 요소들이 순차적으로 배치되어 있어 특정 인덱스에 접근할 때 기본 위치에 오프셋을 더하는 방식으로 계산된다. https://www.geeksforgeeks.org/introduction-to-arrays-data-structure-and-algorithm-tutorials/ ...
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 배열 필요 직접 계산 가능 부적합 압축 가능성 제한적 매우 좋음 있음 (압축 트라이) 캐시 성능 매우 좋음 보통 나쁨 실제 사용 사례 대용량 문자열 검색 시스템 생물정보학, 문자열 처리 자동 완성, 사전 검색 추가적인 중요 고려사항: ...
그래프 (Graph) 그래프는 컴퓨터 과학에서 가장 유연하고 강력한 자료구조 중 하나이다. 다양한 관계를 표현할 수 있어 현실 세계의 복잡한 문제를 모델링하는 데 매우 유용하다. 그래프는 다양한 문제를 해결하는 데 사용되는 강력한 자료구조이다. 인접 행렬, 인접 리스트, 간선 리스트 등 다양한 방법으로 표현할 수 있으며, DFS, BFS 등의 탐색 알고리즘부터 다익스트라, 벨만-포드 등의 최단 경로 알고리즘, 크루스칼, 프림 등의 최소 신장 트리 알고리즘까지 다양한 알고리즘이 그래프에 적용된다. 현실 세계의 많은 문제들을 그래프로 모델링할 수 있기 때문에, 그래프 이론은 컴퓨터 과학에서 매우 중요한 분야이다. 특히 소셜 네트워크, 내비게이션 시스템, 웹 페이지 랭킹 등 현대 기술의 핵심 부분에 그래프 알고리즘이 적용되고 있다. ...
무방향 그래프(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): 해당 정점에서 나가는 간선의 개수 방향 그래프의 표현 방법 방향 그래프 예시 ...
Cuckoo Hash Table Cuckoo Hash Table은 해시 충돌 문제를 해결하기 위해 개발된 해시 테이블의 한 종류로, 두 개 이상의 해시 함수를 사용하여 각 키에 대해 여러 개의 가능한 위치를 제공한다. 특징 다중 해시 함수: 일반적으로 두 개 이상의 해시 함수를 사용한다. 결정적 성능: 최악의 경우에도 일정한 시간 복잡도를 보장한다. 동적 재배치: 충돌 발생 시 기존 항목을 다른 위치로 이동시킨다. 장점 빠른 검색 속도: O(1) 시간 복잡도로 검색 연산을 수행한다. 공간 효율성: 높은 로드 팩터를 유지할 수 있다. 삭제 연산 지원: Bloom Filter와 달리 효율적인 삭제가 가능하다. 단점 삽입 연산의 복잡성: 최악의 경우 무한 루프에 빠질 수 있어 재해싱이 필요할 수 있다. 구현의 복잡성: 일반 해시 테이블에 비해 구현이 더 복잡하다. 응용 데이터베이스 인덱싱 네트워크 라우팅 테이블 캐시 시스템 스팸 필터링 동작 원리 삽입: ...
Circular Linked List 이는 Linked List의 한 변형으로, 데이터를 저장하고 조직하는 특정한 방식을 제공한다. Circular Linked List(원형 연결 리스트)는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트의 변형이다. 이 구조에서는 리스트의 끝이 존재하지 않으며, 모든 노드가 연결되어 원을 형성한다. https://www.geeksforgeeks.org/circular-linked-list/ 특징 마지막 노드의 next 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다. 리스트의 어느 노드에서 시작하더라도 모든 노드를 순회할 수 있다. 리스트의 끝과 시작이 연결되어 있어 순환 구조를 가진다. 장점 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다. 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 순환적인 데이터 구조를 표현하기에 적합하다. 메모리를 효율적으로 사용할 수 있다. 단점 구현이 단순 연결 리스트보다 복잡하다. 무한 루프에 빠질 가능성이 있어 순회 중단이 어려울 수 있다. 노드 삭제 시 이전 노드를 찾기 위해 전체 리스트를 순회해야 할 수 있다. 응용 Circular Linked List는 다음과 같은 상황에서 유용하게 사용된다: ...
Circular Queue (Circular Buffer) 이는 선형 큐의 확장된 버전으로, 데이터를 효율적으로 저장하고 관리하는 특정한 방식을 제공한다. Circular Queue는 마지막 요소가 첫 번째 요소와 연결되어 원형 구조를 형성하는 큐 데이터 구조이다. 이는 ‘Ring Buffer’라고도 불리며, 고정 크기의 배열을 사용하여 데이터를 연속적인 루프로 저장한다. https://www.geeksforgeeks.org/what-is-circular-queue-circular-queue-meaning/ 특징 원형 구조: 마지막 위치가 첫 번째 위치와 연결되어 있다. FIFO (First In First Out) 원칙을 따른다. 두 개의 포인터: 큐의 front와 rear를 추적하는 두 개의 포인터를 사용한다. 고정 크기: 초기화 시 크기가 설정되며, 이후 변경이 어렵다. 장점 메모리 효율성: 선형 큐의 주요 한계인 메모리 낭비 문제를 해결한다. 빠른 연산: 삽입과 삭제 연산의 시간 복잡도가 O(1)이다. 공간 재사용: 큐의 앞부분이 비어있을 때 재사용이 가능하다. 캐시 지역성: 연속된 메모리 사용으로 CPU 캐시 성능이 향상된다. 단점 크기 제한: 고정 크기로 인해 오버플로우와 데이터 손실 가능성이 있다. 구현 복잡성: 선형 큐보다 구현이 복잡하다. 디버깅 어려움: 원형 구조로 인해 디버깅이 어려울 수 있다. 동적 크기 조정의 어려움: 크기를 동적으로 조정하기 어렵다. 응용 CPU 스케줄링: 운영 체제에서 프로세스 관리에 사용된다. 트래픽 관리 시스템: 교차로에서의 효율적인 흐름 제어에 활용된다. 메모리 관리: 운영 체제의 메모리 관리에 사용된다. 스트리밍 서비스: 오디오 및 비디오 스트리밍에 활용된다. 네트워크 패킷 관리: 라우터와 스위치에서 패킷 데이터 처리에 사용된다. 동작 원리 초기화: front와 rear 포인터를 -1로 설정한다. 삽입(Enqueue): 큐가 가득 찼는지 확인한다. rear 포인터를 원형으로 증가시킨 ((rear + 1) % size). 새 요소를 rear 위치에 삽입한다[11]. 삭제(Dequeue): 큐가 비어있는지 확인한다. front 위치의 요소를 반환한다. front 포인터를 원형으로 증가시킨다 ((front + 1) % size). 구성 요소 배열: 데이터를 저장하는 고정 크기의 배열. front 포인터: 큐의 첫 번째 요소를 가리킨다. rear 포인터: 큐의 마지막 요소를 가리킨다. size: 큐의 최대 크기를 나타낸다. 구현 방식 JavaScript를 사용한 Circular Queue 구현 예시: ...