C++ 표준 라이브러리인 std::priority_queue를 중심으로, 우선순위 큐가 정렬 안정성(stability)을 보장하지 않는 이유와 동작 방식을 정리한 글입니다.우선순위 큐와 정렬 안정성우선순위 큐 (priority queue)우선순위 큐는 가장 높은 우선 순위를 갖는 원소를 가장 먼저 꺼낼 수 있도록 하는 자료구조C++ 표준 라이브러리에서는 std::priority_queue 템플릿 클래스로 제공 ( 라이브러리 필요)내부적으로는 힙(heap)을 이용해 구현되어 있음우선순위 큐 기본 코드#include // 기본 예시std::priority_queue pq;pq.push(3);pq.push(10);pq.push(5);// top() = 10 (가장 큰 값)pq.pop(); // 1..

이 글은 서로소 집합 자료구조(Disjoint Set Union, DSU)에 대해서 정리한 글입니다.DSU와 Union Find✅ "Union Find"라는 이름은 합치기를 뜻하는 Union과 찾기를 뜻하는 Find라는 두 가지의 주요 연산에서 유래한 표현으로 서로소 집합 자료구조(Disjoint Set Union, DSU)과 동일한 자료구조를 의미✅ DSU는 "서로소(disjoint)인 여러 집합을 관리하고, 필요할 때 이 집합들을 합쳐(Union)주면서 집합의 대표나 구조를 빠르게 찾는(Find) 기법"을 의미하는 더 일반적이며 학술적인 표현 Union Find랑 DSU는 동일한 자료구조를 나타내는 용어이며, 이 글에서 사용하는 Union Find와 DSU는 동일한 개념으로 이해하면 됩니다.DSU(D..

이 글은 알고리즘을 설계할 때 많이 사용되는 대표적인 자료구조 중 하나인 스택(Stack)과 큐(Queue)에 대해 정리한 글입니다.스택 (Stack)스택의 개념스택은 데이터를 임시 저장하는 데 사용하는 자료구조후입선출, LIFO (Last-In, First-Out) : 가장 나중에 들어간 데이터가 가장 먼저 나오며, 물리적인 동작으로는 한쪽 끝에서만 데이터를 넣거나 뺼 수 있는 구조스택의 주요 연산스택의 기본 연산은 언어에 상관없이 동일하나, 구현 방법이나 문법은 언어 별로 차이가 있을 수 있다.Push새로운 데이터를 스택의 맨 위(top)에 삽입ex) push(item)Pop스택의 맨 위에 있는 데이터를 제거하고 반환스택이 비어 있는 상태에서 pop을 시도하면 에러(underflow)가 발생ex) i..

정적 배열과 동적 배열에 대해 정리한 글입니다. 기본 개념과 특징을 중점으로 정리하였습니다.정적 배열 (Static Array)정적 배열의 정의정적 배열은 배열의 크기가 컴파일 시 결정되는 배열의 의미일반적으로 스택 영역(stack section)에 할당되며, 프로그램이 시작될 때 필요한 메모리 공간을 이미 확보한 상태로 실행메모리 구조스택 영역 할당일반적으로 함수 내부에 정적 배열을 선언하면, 해당 함수가 호출될 때 스택에 고정된 크기의 메모리가 할당됨함수가 종료되면 스택이 정리되면서 배열도 소멸함고정 크기배열의 크기를 변경할 수 없음ex. int arr[10];으로 선언한 배열은 10개의 int 공간을 항상 차지함 (변경 불가)정적 배열의 장단점장점접근 속도가 빠름모든 요소가 연속적인 메모리에 저장되..

배열 (Array)컴퓨터 과학과 프로그래밍에서 가장 기본적이고 중요한 자료구조 중 하나효율적인 데이터 관리와 알고리즘 설계의 초석배열이란같은 데이터 타입의 값을 연속적인 메모리 공간에 저장하는 자료구조각 값은 고유한 인덱스를 통해 접근 가능데이터를 순서대로 저장하고, 빠르게 접근하거나 수정해야 할 때 사용주요 용어요소 (element) : 배열에 저장된 개별 데이터인덱스 (index) : 배열의 각 요소에 접근하기 위한 번호로, 대부분의 프로그래밍 언어에서 0부터 시작크기 (size) : 배열에 저장할 수 있는 최대 요소의 개수배열의 예시인덱스 (index)01234값 (element)1020304050위와 같이 선언된 배열에서 arr[2]는 값으로 30을 반환배열의 특징고정된 크기배열의 크기는 선언 시..