배열 내 132 패턴 존재 여부를 판별하는 효율적인 알고리즘
132 패턴 문제의 이해
배열 nums가 주어졌을 때, i < j < k 인덱스 순서를 만족하면서 nums[i] < nums[k] < nums[j] 관계를 가지는 패턴이 존재하는지 확인하는 문제입니다. 즉, 첫 번째 숫자가 가장 작고, 두 번째 숫자가 가장 크며, 세 번째 숫자가 그 중간 값을 가지는 부분 수열을 찾아야 합니다.
1. 브루트 포스(Brute Force) 방식
가장 직관적인 방법은 ...
7월 26일 18:57에 게시됨
C++ 세그먼트 트리 구현 및 지연 전파(Lazy Propagation) 완벽 가이드
세그먼트 트리(Segment Tree)는 펜윅 트리(Fenwick Tree)와 유사하게 구간 합을 구하는 데 주로 사용되지만, 이 외에도 구간 최소/최대값 탐색, 구간 색칠 등 다양한 구간 연산을 효율적으로 처리할 수 있는 강력한 자료구조입니다. 본 가이드에서는 C++를 사용하여 세그먼트 트리의 기본 구현부터 지연 전파(Lazy Propagation)를 활용한 고급 기법까지 단계별로 다룹니다. ...
7월 23일 20:44에 게시됨
C++ 환경에서의 효율적 데이터 탐색과 정렬 전략 분석
1. 정렬된 시퀀스 기반 검색 메커니즘
데이터가 순차적으로 정리되어 있는 배열이나 벡터 내 특정 값을 신속하게 locating 하는 것은 알고리즘 설계의 핵심 요소다. 여기서는 대표적인 비선형 탐색 기법 세 가지를 다룬다.
1.1 이분 탐색 (Binary Search)
범위를 반으로 나누어 목표값을 축소하는 고전적인 방법이다. 선형 검색의 O(n) 한계를 극복하고 로그 시간인 O(log ...
7월 17일 06:51에 게시됨
자바 ArrayList 핵심 로직 직접 구현하기
자바 컬렉션 프레임워크에서 가장 널리 사용되는 ArrayList는 내부적으로 동적 배열을 기반으로 동작합니다. 이번 글에서는 ArrayList의 핵심 동작 원리를 깊이 이해하기 위해, 최소한의 코드로 커스텀 리스트를 직접 구현해 보겠습니다.
기본 구조 및 변수 정의
먼저 SimpleList라는 제네릭 클래스를 정의합니다. ArrayList와 마찬가지로 데이터를 저장하기 위해 Object ...
7월 15일 16:35에 게시됨
Redis 5.0.7 소스 분석 - 정수 집합 구현
Redis의 정수 집합(intset) 관련 파일은 intset.h와 intset.c로 구성되어 있습니다.
intset은 정렬된 정수 배열과 유사한 작업을 수행하지만, 데이터 유형에 따라 메모리 최적화가 이루어집니다.
데이터 구조
1 typedef struct custom_set {
2 uint32_t format;
3 uint32_t size;
4 int8_t elements[];
5 } custom_set;
custom_set 구조는 가변 길이 구조체 ...
7월 14일 03:09에 게시됨
큐를 사용하여 스택 구현: LeetCode 225 풀이
문제 정의
두 개의 큐를 활용하여 후입선출(LIFO) 방식의 스택을 구현해야 합니다. push, top, pop, empty 네 가지 기본 연산을 지원해야 하며, 큐의 기본 기능인 push to back, peek/pop from front, size 및 is empty만 사용할 수 있습니다.
해결 방법 1: 단일 큐 사용
스택의 마지막 요소를 큐의 맨 앞에서 제거해야 하는 점이 어려움입니다. 이는 큐의 끝 요소를 제 ...
6월 27일 17:07에 게시됨
그래프 순회 알고리즘: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.
시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 ...
6월 8일 16:40에 게시됨
Android SparseArray: 효율적인 데이터 관리
SparseArray는 Android 플랫폼에서 제공하는 특화된 데이터 구조로, 특정 사용 사례에서 표준 Java 컬렉션인 HashMap<Integer, E>보다 뛰어난 성능과 메모리 효율성을 제공합니다. 주요 특징은 다음과 같습니다:
키-값 쌍 형태로 데이터를 저장하며, 내부적으로 이진 탐색을 사용하므로 탐색 시간 복잡도는 O(logN)입니다.
키를 int 배열로 직접 저장하여 ...
6월 5일 02:11에 게시됨
삽입 정렬(Insertion Sort)의 동작 원리와 성능 최적화
삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 배열을 나누어, 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘입니다.
1. 동작 원리와 루프 불변성
삽입 정렬의 핵심 아이디어는 루프 불변성(Loop Invariant)으로 설명할 수 있습니다. 길이 n인 배열 data에 대해, 인덱스 [0, i) 범위는 항상 정렬된 상태를 유지하며, 인덱스 ...
5월 29일 16:40에 게시됨
세그먼트 트리 심화: 다중 지연 전파와 세그먼트 트리 비트 구현
세그먼트 트리(Segment Tree)는 배열의 구간 연산을 효율적으로 처리하기 위한 강력한 자료구조입니다. 기본적인 구간 합 구하기를 넘어, 여러 종류의 업데이트를 동시에 처리하거나 구간 내 최솟값/최댓값을 갱신하는 고급 기법들이 존재합니다. 본 글에서는 지연 전파(Lazy Propagation)를 활용한 다중 연산 처리와 세그먼트 트리 비트(Segment Tree Beats)를 포함한 고 ...
5월 26일 20:46에 게시됨