C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 연관 컨테이너(Associative Containers) 자료구조 중 std::multiset과 std::multimap에 대해 정리한 글입니다.(std::set과 std::map에 대해 알고 있다고 가정하고 정리하였습니다.)[자료구조] C++ Container Library : Associative Containers - set & map [자료구조] C++ Container Library : Associative Containers - set & mapC++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 연관 컨테이너(Associative Containers) 자료구조 중 std::set과 std::map에 대해 정리한 글입니..

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 연관 컨테이너(Associative Containers) 자료구조 중 std::set과 std::map에 대해 정리한 글입니다.📚 연관 컨테이너 (Associative Containers)📖 연관 컨테이너란?키(key)를 기반으로 데이터를 저장하고 빠르게 검색하도록 설계된 자료구조데이터를 키(key) 기준으로 정렬된 상태로 유지내부적으로 이진 탐색 트리(Binary Search Tree)로 이루어져 있으며, C++ STL에서는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree, Red-Black Tree)로 이루어져 있음📌 대표 컨테이너👉 C++ STL에서 제공하는 4가지 기본 연관 컨테이너set..

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequential Containers)에 해당하는 std::list에 대해 정리한 글입니다.📚 std::list📖 std::list이중 연결 리스트(Doubly Linked List) 구조를 기반으로 한 컨테이너모든 원소가 서로 앞뒤로 연결되어 있음중간 삽입 및 삭제가 매우 효율적으로 동작std::vector, std::deque와 가장 큰 차이점➡️ std::list는 메모리가 연속적이지 않고, 각 원소가 다음 혹은 이전 원소를 가리키는 포인터를 가지고 있다.📌 std::list 사용 예시 코드#include // 필수 헤더#include using namespace std;int main() { list..

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequeential Containers)에 해당하는 std::deque에 대해 정리한 글입니다.📚 std::deque📖 std::dequeDouble Ended Queue앞쪽(Front)과 뒤쪽(Back) 둘 다 빠르게 삽입 및 삭제할 수 있는 자료 구조➡️ vector처럼 메모리가 연속적이지는 않지만, 양쪽 끝 삽입 및 삭제가 $ O(1) $ 성능을 가지는 컨테이너📌 std::deque 사용 예시 코드#include #include // 필수 헤더using namespace std;int main() { deque dq; // 덱 생성 dq.push_back(1); // 뒤에 추가 ..

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequential Containers)에 해당하는 std::vector에 대해 정리한 글입니다.📚 순차 컨테이너 (Sequential Container)📖 순차 컨테이너란?순서가 있는 데이터 집합을 관리하는 컨테이너"순서대로" 저장하고, 저장된 순서에 따라 탐색, 수정, 삽입, 삭제를 할 수 있음내부적으로 배열이나 연결 리스트(Linked List)를 기반으로 동작구현이 단순하기 때문에 가볍고 빠르다는 특징이 있다. 저장할 데이터가 정렬 상태를 유지할 필요가 없을 때 사용하기 적합하다.📌 대표 컨테이너std::vector : 가변 크기 배열 | 동적 배열std::deque : 양쪽 삽입 및 삭제가 빠름 | 블록 배열 (..

정보 단위비트 (bit)컴퓨터가 이해하는 가장 작은 정보 단위binary digit의 줄임말로, 하나의 비트는 0 또는 1의 값을 가짐일반적으로 n bit는 $ 2^n $ 가지의 정보 표현이 가능바이트 (byte)비트를 8개 묶은 단위 (1 byte = 8 bit)컴퓨터에서 데이터를 처리하는 기본 단위문자 하나(ex. 알파벳, 숫자, 특수기호 등)를 표현하는 데 일반적으로 1 byte 사용기타킬로바이트 (kB) : 바이트를 1,000개 묶은 단위 (1 kB = 1,000 byte)메가바이트 (MB) : 킬로바이트를 1,000개 묶은 단위 (1 MB = 1,000 kB)기가바이트 (GB) : 메가바이트를 1,000개 묶은 단위 (1 GB - 1,000 MB)테라바이트 (TB) : 기가바이트를 1,000개 ..

컴퓨터가 이해하는 정보컴퓨터는 오직 0과 1로 표현된 정보(이진수 형태의 정보)만 이해할 수 있음데이터 : 숫자, 문자, 이미지, 동영상 등 정적인 정보명령어 : 데이터를 처리하고 컴퓨터를 동작시키는 지시 정보컴퓨터의 핵심 부품중앙처리장치 (CPU, Central Processing Unit)주기억장치 (메모리, Main Memory)보조기억장치 (Secondary Storage)입출력장치 (Input / Output Devices)주기억장치는 크게 RAM(Random Acceess Memory)과 ROM(Read Only Memory)으로 구분되는데, 주로 메모리라는 용어는 RAM을 지칭함전체 구성 구조가장 큰 사각형은 메인보드이며, 메인보드 내부에는 시스템 버스가 존재 ➡️ 시스템 버스를 통해 핵심 ..

이 글은 다익스트라 알고리즘에서 최단 경로를 기록하는 방법에 대해 정리하였습니다.최단 경로를 기록하는 이유✅ 다익스트라 알고리즘은 기본적으로 시작 노드에서 각 노드까지의 최소 비용(거리)을 구하는 데 최적화된 알고리즘이다. 하지만 실제 문제에서는 최단 거리 뿐만 아니라 어떤 경로로 이동했는지도 필요한 경우가 존재한다.➡️ 지도 문제 : 도시 간 최단 거리와 구체적인 경로➡️ 네트워크 경로 제어 : 최소 비용 라우팅에 사용➡️ 최단 경로 관련 알고리즘 학습 : 문제 풀이 이해도 상승🌐 기본 다익스트라 알고리즘은 아래 글 참고https://devkuk.tistory.com/25 [알고리즘] 최단 경로 알고리즘 - 플러드 필(Flood Fill)과 다익스트라(Dijkstra)이 글은 BFS 알고리즘을 활용하..

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..

이 글에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 알고리즘인 크루스칼 알고리즘과 프림 알고리즘에 대해 정리하였습니다.최소 신장 트리(Minimum Spanning Tree, MST)MST의 개념가중치가 있는 무방향 그래프에서, 모든 정점을 연결하면서 그 간선들의 가중치 합이 최소가 되는 서브그래프를 의미조건 : 모든 정점을 포함 + 사이클이 없는 트리 구조 + 간선 가중치의 합이 최소MST를 구하는 대표 알고리즘크루스칼(Kruskal) 알고리즘간선을 가중치 오름차순으로 정렬한 뒤, 가장 작은 것부터 하나씩 트리에 포함시킬지 결정이미 사이클이 형성되는 간선은 버리고, 아니면 포함사이클 판별을 빠르게 하기 위해 Union Find(서로소 집합, DSU)를 사용U..