재민의 IT 공부기록

자바의 가비지 컬렉션(Garbage Collection, GC)은 JVM(Java Virtual Machine)에서 자동으로 메모리를 관리하는 메커니즘이다. 가비지 컬렉터는 프로그램 실행 중 더 이상 사용되지 않는 객체들을 탐지하고 메모리에서 제거하여 메모리 누수를 방지하고, 응용 프로그램이 효율적으로 메모리를 사용할 수 있게 한다. 자바의 가비지 컬렉션은 몇 가지 특징을 가지고 있다. 먼저, 객체의 생성과 힙 메모리를 관리한다. 자바 프로그램에서 객체가 생성되면 힙 메모리에 할당된다. 힙 메모리는 프로그램이 실행되는 동안 동적으로 할당되는 메모리 영역이다. 객체가 더 이상 참조되지 않을 때, 즉 프로그램에서 해당 객체에 접근할 수 없게 되면 이 객체는 가비지(garbage)로 간주된다. 가비지 컬렉션은..

절차적 언어는 high level language의 초기 버전으로서, 연속적인 command를 실행하는데에 집중하는 언어로 작용한다. 이해하기 쉽고, 코드를 짜기도 쉬우며, 재사용되기 어렵다는 점이 특징이다. 객체지향 언어는 연속적인 프로그래밍을 목적으로 하지 않는다. 그 대신 각 객체를 선언하고, 객체간의 관계를 표현한다. 이러한 객체지향 언어는 코드 재사용, 유지보수, 추상화에 도움이 된다.  # 절차적 프로그래밍 예제 def add_numbers(a, b):     return a + b def main():     num1 = 5     num2 = 3     result = add_numbers(num1, num2)     print(f"두 숫자의 합: {result}") if __name__ ..

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

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-트리는 항상 ..