ITPE * JackerLab

개요Cartesian Tree는 주어진 수열을 기반으로 구성되는 이진 탐색 트리 구조로, 배열의 순서와 값의 최소(또는 최대) 조건을 동시에 만족하는 이진 트리다. 이는 RMQ(Range Minimum Query), LCA(Lowest Common Ancestor) 등 다양한 알고리즘 문제의 전처리 단계에서 유용하게 사용된다.1. 개념 및 정의Cartesian Tree는 다음 두 가지 성질을 모두 만족하는 트리다:이진 탐색 트리(Binary Search Tree): 노드의 중위 순회가 원래 수열과 일치해야 함힙 속성(Min-Heap 또는 Max-Heap): 부모 노드의 값이 자식보다 작거나 커야 함목적: 값 기반 정렬과 순서 기반 조회를 동시에 처리필요성: RMQ와 같은 문제에서 빠른 질의 처리를 위한 ..

개요Treap은 Tree와 Heap을 조합한 이름으로, 이진 탐색 트리(Binary Search Tree, BST)와 힙(Heap) 구조의 특성을 동시에 만족하는 확률적 자료구조입니다. 키에 대해 이진 탐색 트리 성질을, 우선순위에 대해 힙 성질을 유지함으로써 삽입, 삭제, 탐색 모두 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 잡힌 트리 구조를 확률적으로 유지할 수 있습니다.1. 개념 및 정의 항목 내용 정의각 노드가 키(Key)와 우선순위(Priority)를 가지며, 키는 BST, 우선순위는 힙 성질을 만족하는 이진 트리목적자가 균형(self-balancing) 유지로 빠른 탐색, 삽입, 삭제 지원필요성명시적 리밸런싱 없이 트리 높이 최적화를 달성하여 성능 향상Treap은 간단한 구조와..

개요프로세스 주소 공간은 운영체제가 실행 중인 프로세스에 대해 부여하는 가상 메모리 공간의 논리적 구조입니다. 이 공간은 일반적으로 코드(Code) 영역, 데이터(Data) 영역, 힙(Heap), 스택(Stack) 등으로 구분되며, 각 영역은 서로 다른 용도와 성격을 갖고 있어 메모리 관리, 보안, 디버깅 등 다양한 측면에서 중요한 의미를 가집니다. 본 글에서는 프로세스 주소 공간의 구조, 각 영역의 역할과 특징, 운영체제와의 관계, 실무 활용까지 정리합니다.1. 프로세스 주소 공간이란?운영체제는 각 프로세스에 대해 독립된 가상 메모리 공간을 할당합니다. 이 공간은 물리 메모리와 매핑되어 있으며, 프로세스 간 메모리 보호와 격리를 통해 안정성과 보안을 확보합니다. 대부분의 운영체제에서는 32비트/64비트..

개요힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 우선순위 조건을 만족하는 구조이다. 최소 힙(Min Heap)은 부모 노드 ≤ 자식 노드, 최대 힙(Max Heap)은 부모 노드 ≥ 자식 노드의 조건을 만족한다. 주로 **우선순위 큐(Priority Queue)**로 활용되며, 삽입/삭제 모두 평균 O(log n)의 성능을 제공한다.1. 힙의 구조 및 특징 항목 설명 트리 구조완전 이진 트리(왼쪽부터 채움)힙 조건부모 노드 ≥ 자식 노드 (최대 힙), ≤ (최소 힙)저장 방식배열 인덱스 기반 표현 (root: index 0)사용 용도우선순위 큐, 정렬 알고리즘 (Heap Sort) 등2. 힙의 배열 표현노드 위치인덱스 관계부모 노드i왼쪽 자식2i + 1오른쪽 자식2i..

개요다익스트라(Dijkstra) 알고리즘은 그래프 상에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다. 가중치가 있는 그래프에서 각 정점까지의 최소 비용을 계산하며, 우선순위 큐를 사용해 탐색 효율을 극대화한다. GPS 내비게이션, 네트워크 라우팅, 교통망 분석 등 다양한 실무 분야에서 핵심적으로 사용된다. 본 글에서는 다익스트라 알고리즘의 개념, 동작 원리, 구현 방식, 시간 복잡도, 활용 사례를 체계적으로 정리한다.1. 개념 및 정의다익스트라 알고리즘은 음수 간선이 없는 가중치 그래프에서 시작 노드로부터 모든 노드까지의 최단 경로를 구하는 탐색 알고리즘이다. 각 정점까지의 거리를 지속적으로 업데이트하며, 우선순위 큐(Priority Queue)를 사용해 가장 짧은 ..