Lock-free Stack Lock-free Stack은 락(lock)을 사용하지 않고 동시성을 제공하는 LIFO(Last-In-First-Out) 자료구조. 이 자료구조는 여러 스레드가 동시에 스택에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 스택에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Stack은 주로 다음과 같은 방식으로 구현된다: ...
블룸 필터 (Bloom filter) 블룸 필터(Bloom Filter)는 공간 효율적인 확률적 데이터 구조로, 원소가 집합에 속하는지 여부를 빠르게 확인하는 데 사용된다. 1970년 Burton Howard Bloom이 고안한 이 구조는 **거짓 양성(false positive)**은 허용하지만 **거짓 음성(false negative)**은 절대 발생하지 않는다. 블룸 필터는 빠른 검색과 극도의 공간 효율이 필요한 시스템에서 필수적이다. 특히 대용량 데이터 처리, 실시간 애플리케이션, 메모리 제약 환경에서 강력한 성능을 발휘한다. 다만 정확성이 절대적이라면 전통적 해시 테이블이 더 적합하다. 핵심 구성 요소 비트 배열(Bit Array): 모든 비트가 0으로 초기화된 배열 (크기 m) 해시 함수(Hash Functions): 원소를 비트 배열의 인덱스로 매핑하는 k개의 독립적 해시 함수 동작 과정 삽입(Add) 원소를 k개의 해시 함수로 해싱 → 각 결과값을 비트 배열의 인덱스로 사용 → 해당 위치의 비트를 1로 설정. 예시: 원소 “apple"을 3개의 해시 함수로 해싱 → 인덱스 1, 4, 7 → 비트 배열 [0,1,0,1,0,0,1,0,0,0] 갱신. ...
Lock-free Queue Lock-free Queue는 락(lock)을 사용하지 않고 동시성을 제공하는 FIFO(First-In-First-Out) 자료구조이다. 이 자료구조는 여러 생산자(producer)와 소비자(consumer)가 동시에 큐에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 큐에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Queue는 주로 다음과 같은 방식으로 구현된다: ...
동적 배열 (Dynamic Array) 동적 배열은 크기가 고정되지 않고 필요에 따라 자동으로 확장 또는 축소될 수 있는 데이터 구조이다. 정적 배열이 생성 시점에 고정된 크기를 가지는 반면, 동적 배열은 요소가 추가되거나 제거됨에 따라 내부적으로 메모리를 재할당하여 크기를 조정한다. 일반적인 프로그래밍 언어에서는 다음과 같이 구현되어 있다: Python의 list Java의 ArrayList C++의 vector JavaScript의 Array 기본적으로 동적 배열은 내부적으로 정적 배열을 사용하지만, 그 크기를 자동으로 관리하는 추상화 계층을 제공한다. 동적 배열은 단순하면서도 강력한 자료구조로, 현대 소프트웨어 개발에서 가장 기본적이고 널리 사용되는 데이터 구조 중 하나이다. 그 구현 원리와 성능 특성을 이해하면 다양한 문제 상황에서 적절한 자료구조를 선택하는 데 도움이 된다. ...
Array vs. Linked List 데이터 구조는 프로그래밍에서 데이터를 효율적으로 저장하고 관리하기 위한 방법을 제공합니다. 이 중에서도 배열과 연결 리스트는 가장 기본적이면서도 중요한 데이터 구조이다. 두 구조는 서로 다른 특성과 장단점을 가지고 있어 적절한 상황에 맞게 선택해 사용해야 한다. 배열은 인덱스를 통한 빠른 접근과 간단한 구현이 장점이지만, 크기가 고정되어 있고 중간 삽입/삭제가 비효율적이다. 반면 연결 리스트는 동적 크기 조정과 효율적인 삽입/삭제가 장점이지만, 임의 접근이 불가능하고 추가 메모리를 사용한다. 적절한 상황에 맞는 자료구조 선택은 효율적인 프로그램 개발의 핵심이다. 따라서 문제의 특성과 요구사항을 잘 분석하여 최적의 자료구조를 선택해야 한다. 때로는 두 자료구조의 장점을 결합한 하이브리드 접근 방식이나 다른 고급 자료구조를 활용하는 것이 더 나은 해결책이 될 수도 있다. ...