재민

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는 데이터가 리프 노드에만 있으므로 검색 작업이 리프 노드에서 끝난다. 또한 리프 노드가 연결 리스트..

1. 검색 (Search)최악의 경우: O(logN)설명: B-트리는 M차 트리로 각 노드는 최대 M개의 자식을 가질 수 있다. 트리의 높이는 logN에 비례하므로, 검색 연산의 시간 복잡도는 O(logN)이다. 이는 각 레벨에서 이진 탐색을 사용해 최악의 경우 O(M)의 시간이 추가로 필요할 수 있지만, 일반적으로 M은 작기 때문에 시간 복잡도는 여전히 O(log N)에 가깝다.2. 삽입 (Insertion)최악의 경우: O(logN)설명: 삽입 연산 시 먼저 적절한 리프 노드를 찾아야 하며, 이는 검색과 동일하게 O(logN)의 시간 복잡도를 가진다. 이후 노드 분할이 필요할 경우, 분할 연산은 상수 시간 내에 수행되므로 전체 삽입 연산의 시간 복잡도는 O(logN)이다.3. 삭제 (Deletion)..

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

이 점수로 합격 후기를 적어도 되는가 싶기는 한데,, 어찌저찌 지난 3월 9일에 열린 sqld 시험에서 합격을 하였다. 사실 자격증 자체의 난이도가 높지 않기에, 원하는 분들은 공부 열심히 하면 가질 수 있는 자격증이지만 나에게는 의미가 나름 깊다. 그 이유는, 1) sqld 한 번 떨어지고 재시험이기 때문 2) 학부수업때 들었던 데이터베이스과목에서 무척 낮은 점수를 받았기에 자격지심이 있다고 생각(낮은 점수를 받은 사유: 복수전공 첫학기에 어려운 프로젝트랑 연결시키는 데베과제가 나와서 의욕을 상실함, 그로 인해 흥미도 잃음) 이러한 이유로 나한테는 sqld 합격의 기쁨은, 꽤나 높다고 할 수 있다. 지난 51회 시험에서는 1단원을 7문제 이상 맞추었는데, 쿼리를 거의 못 풀어서 40점대 점수를 맞았다...

관계형 데이터베이스에서, one-to-many(일대다), many-to-one(다대일), many-to-many(다대다)는 엔터티(테이블) 간의 관계를 설명하는 세 가지 주요 유형의 관계이다. One-to-Many (일대다) 관계: 한 쪽 엔터티(테이블)의 레코드가 다른 쪽 엔터티에서 여러 레코드와 관련된 경우이다. 예를 들어, 하나의 부서에 여러 개의 직원이 속하는 경우가 일대다 관계이다. 부서는 한 쪽에 위치하고, 여러 개의 직원은 다른 쪽에 위치한다. Many-to-One (다대일) 관계: 일대다 관계의 반대로, 다수의 레코드가 다른 테이블의 하나의 레코드와 관련된 경우이다. 위의 예에서 직원(다수)과 부서(하나)의 관계가 다대일 관계이다. Many-to-Many (다대다) 관계: 두 엔터티(테이블..

데이터베이스에서 뷰는 하나 이상의 기본 테이블에서 유도된 가상 테이블이다. 뷰는 실제 데이터를 저장하지 않고, 기존의 테이블이나 다른 뷰로부터 데이터를 가져와 가상의 테이블을 생성하는 데 사용된다. 이를 통해 데이터에 대한 접근을 제어하고, 데이터를 편리하게 검색하고 가공하는 데 사용된다. view는 이러한 역할을 한다. 1) 가상 테이블: 뷰는 실제로 데이터를 저장하지 않으며, 기존의 테이블이나 다른 뷰의 결과를 기반으로 쿼리를 수행하여 가상의 테이블을 만든다. 2) 데이터의 가시성 제어: 뷰를 사용하면 특정 사용자나 응용 프로그램이 필요로 하는 데이터만을 선택적으로 노출시킬 수 있다. 사용자에게 필요한 필드만을 보여주거나, 특정 행만을 보여줄 수 있다. 3) 복잡한 쿼리 단순화: 복잡한 쿼리나 여러 ..