큐를 사용하여 스택 구현: 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에 게시됨
C 언어를 이용한 연결 큐(Linked Queue)의 구현과 메모리 관리
연결 큐(Linked Queue)는 연결 리스트(Linked List)의 동적 메모리 할당 특성과 큐의 선입선출(FIFO, First-In-First-Out) 원칙이 결합된 효율적인 자료구조입니다. 고정된 크기를 가지는 배열 기반의 큐와 달리, 메모리가 허용하는 한 자유롭게 확장할 수 있다는 장점이 있습니다.
1. 연결 큐의 구조 정의
연결 큐를 구현하기 위해서는 데이터를 저장하는 개별 단위인 ' ...
5월 24일 19:36에 게시됨