재민

Naive Approach는 텍스트 패턴 매칭 알고리즘 중 가장 기본적이고 직관적인 방법이다. 이 방법은 단순히 텍스트 내에서 패턴을 찾기 위해 모든 가능한 위치에서 패턴을 하나씩 비교하는 방식으로 동작한다. Naive Approach는 다음과 같은 단계로 구성된다:텍스트와 패턴 길이 확인: 텍스트 T의 길이를 n, 패턴 P의 길이를 m이라고 할 때, 가능한 모든 시작 위치를 검사하기 위해 T의 길이에서 P의 길이를 뺀 만큼의 위치까지 반복을 수행한다.모든 시작 위치 검사: 텍스트의 각 가능한 시작 위치에서 패턴과의 일치를 검사한다. 이를 위해 T의 위치 i부터 i + m - 1까지의 부분 문자열을 패턴 P와 비교한다.패턴 일치 확인: 패턴의 모든 문자가 일치하는지 확인하고, 일치하면 그 시작 위치를 기..

Merge Sort는 분할 정복 방식으로 배열을 정렬하며, 안정적이고 O(nlogn)의 시간 복잡도를 갖지만, 몇 가지 단점이 있다:추가 메모리 사용: Merge Sort는 정렬 과정에서 추가적인 메모리 공간이 필요하다. 원본 배열과 동일한 크기의 보조 배열을 생성해야 하므로, 공간 복잡도가 O(n)이다. 이는 메모리 사용이 제한된 환경에서는 큰 단점이 된다.비연속적 데이터 접근: Merge Sort는 재귀적으로 배열을 분할하고 병합하는 과정에서 비연속적인 메모리 접근이 빈번히 일어난다. 이는 캐시 성능을 저하시킬 수 있으며, 메모리 접근 비용이 큰 환경에서는 성능 저하의 원인이 된다.Heap Sort는 이러한 Merge Sort의 단점을 다음과 같이 극복한다:제자리 정렬(In-place Sort): H..

Sorting은 데이터를 특정 순서대로 정렬하는 과정을 의미하며, 자료구조에서 중요한 개념 중 하나이다. Sorting 알고리즘은 크게 내부 정렬(Internal Sorting)과 외부 정렬(External Sorting)로 나눌 수 있다.내부 정렬 (Internal Sorting)내부 정렬은 모든 데이터를 주 메모리(RAM)에 적재할 수 있는 경우에 사용하는 정렬 방법이다. 주로 사용하는 내부 정렬 알고리즘은 다음과 같다.버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 요소를 비교하여 필요에 따라 위치를 바꾸는 과정을 반복하여 정렬하는 알고리즘이다. 가장 큰 요소가 맨 뒤로 "버블"처럼 이동하는 것에서 이름이 유래되었다.특징: 단순하지만 비효율적이다.시간 복잡도: O(n^2)삽입 정렬 (Ins..

자료구조에서 Hashing과 Collision은 데이터 저장과 검색 효율을 높이기 위한 중요한 개념이다.- Hashing (해싱)Hashing은 키(key)를 입력으로 받아 해시 함수(hash function)를 통해 고정된 크기의 해시 값(hash value) 또는 해시 코드(hash code)를 생성하는 과정이다. 이 해시 값을 사용하여 데이터를 해시 테이블(hash table) 내의 특정 위치에 저장하거나 검색할 수 있다. 해싱의 주요 목적은 데이터를 빠르게 저장하고 검색하는 것이다.- 해시 함수 (Hash Function)해시 함수는 키를 해시 값으로 변환하여 해시 테이블의 인덱스를 결정한다. 해시 함수는 결정적이어야 하며 동일한 키에 대해 항상 동일한 해시 값을 반환해야 한다. 또한, 효율적으로..

B+tree는 데이터베이스 및 파일 시스템에서 널리 사용되는 자료 구조로, 특히 검색과 범위 쿼리에 강점이 있다. B+tree의 구조와 장점에 대해 좀 자세히 작성해보도록 하겠다.[B+tree의 구조]노드 구성:내부 노드: 키와 자식 포인터를 포함하며 실제 데이터는 저장하지 않는다. 내부 노드는 검색을 위한 디렉토리 역할을 한다.리프 노드: 키와 데이터 포인터를 포함하며, 실제 데이터가 저장되는 노드다. 리프 노드 간에는 연결 리스트가 형성되어 있어 순차적으로 접근이 가능하다.연결 리스트:모든 리프 노드는 연결 리스트 형태로 연결되어 있어, 범위 쿼리(range query)를 수행할 때 매우 효율적이다. 한 리프 노드에서 다음 리프 노드로 쉽게 이동할 수 있다.균형 유지:B+tree는 항상 균형을 유지한..

B-tree와 B+tree는 데이터베이스와 파일 시스템에서 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 트리 구조이다. 두 트리는 여러 면에서 비슷하지만 몇 가지 중요한 차이점이 있다. 구조적 측면:B-tree는 모든 노드가 키와 데이터를 모두 가질 수 있다. 리프 노드와 내부 노드 모두 데이터 항목을 포함할 수 있다.B+tree는 내부 노드는 키와 데이터 포인터를 가지지만 실제 데이터는 리프 노드에만 저장된다. 리프 노드가 연결 리스트로 구성되어 있어 리프 노드 간의 순차 접근이 용이하다.검색 성능 측면:B-tree는 키를 찾기 위해 내부 노드와 리프 노드를 모두 탐색해야 할 수 있다.B+tree는 데이터가 리프 노드에만 있으므로 검색 작업이 리프 노드에서 끝난다. 또한 리프 노드가 연결 리스트..

B-트리의 필요성( BST와 AVL 트리의 문제점)BST (Binary Search Tree)는 편향될 경우 높이가 최대 N이 될 수 있다. 이는 탐색, 삽입, 삭제 시 최악의 경우 O(N)의 시간 복잡도를 초래한다. AVL 트리는 항상 균형을 유지하지만, 높이는 여전히 O(log N)이다. 이는 메모리 접근 속도가 느린 대용량 데이터베이스 시스템에서는 비효율적이다. BST와 AVL 트리는 메모리 내에서 사용될 때는 효율적일 수 있지만, 데이터베이스 시스템처럼 대용량 데이터를 다루는 경우에는 디스크 접근이 빈번해질 수 있고, 이는 매우 비용이 크기 때문에 디스크 접근 횟수를 최소화하는 것이 중요하다. B-트리는 이러한 문제를 해결하기 위해 고안되었다.  - B-tree의 특징균형 유지: B-트리는 항상 ..

내부 정렬 중 버블정렬은, 인접한 두개의 원소를 비교하여 자리를 교환하는 방식이다. 첫번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬되게 된다. (마지막으로 배열되는 원소는 비교를 끝까지 진행하므로!) 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 bubble 정렬이라 지어졌다고 한다. 버블 정렬의 경우, 선택 정렬과 달리 best case와 worst case로 나누어 보아야 한다. best case는 이미 정렬이 완료된 상태로, 비교만 진행하고 자리 교환은 이루어지지 않아도 된다. worst case는 자리 교환이 이루어져야 하기 때문에 시간이 더 필요하다. ..

Sorting은 순서없이 배열된 자료를 오름차순/내림차순 순서로 재배열 하는 것으로, sorting상에서 key는 자료를 정렬하는데 사용하는 기준이 되는 특정 값을 뜻한다. 내부정렬 중 선택정렬은, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬하는 sorting방법으로서, 전체 원소들 중 가장 작은 원소를 찾아 첫번째에 위치 > 두번째로 작은 원소를 찾아 두번째에 위치 를 마지막 원소까지 진행하는 방식이다. 선택정렬의 경우 시간복잡도는 O(n^2)가 된다. (비교 횟수는 첫번째 원소는 n개, 두번째는 n-1개 ...1개까지 비교하므로 전체 합은 n^2). 어느 경우에나 비교 횟수가 같은 것이 특징이다. [python 코드] def selection_sort(arr):..

다익스트라 알고리즘은 최단 경로 알고리즘 중 가장 많이 사용되는 알고리즘으로, 무방향 그래프와 방향 그래프 모두에서 사용 가능한 알고리즘이다.모든 간선은 음이 아닌 비용을 가진다는 가정을 바탕으로, 시작 정점으로부터 G의 모든 다른 정점까지의 최단 경로를 구하는 것을 목표로 한다. 다익스트라 알고리즘의 개념은 다음과 같다. 시작 정점 v에서 정점 u까지의 최단 경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 대해 단축되는 경로가 있는 지를 확인한다. 현재 알고 있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u] + cost[u][w]를 계산한 경로를 비교해 경로가 단축되면 dist[w]를 단축된 경로값으로 수정함으로써 최단 경로를 찾는다. [python..