자료구조 16 딕셔너리(Dictionary) 라이브러리 C#: System.Collections.Generic, Dictionary<K, V> Python: {:}, dict() C++: <unordered_map>, std::unordered_map<K, V> C++에서는 딕셔너리와... 2024.06.14 컴퓨터 공학, 자료구조 해시 테이블(Hash Table)과 개방 주소법(Open Addressing), 체이닝(Chaining) 탐색 시간 평균: $O(1)$ 최악: $O(N)$ (충돌 발생시) 요소 추가/삭제 평균: $O(1)$ 최악: $O(N)$ (충돌 발생시) 해시 테이블(Hash Table)은 키(Key) 를 값(Value) 에 매핑하여 키-값 쌍을 효율적으로 저장하고 ... 2024.06.13 컴퓨터 공학, 자료구조 우선순위 큐(Priority Queue)와 힙(Heap) 라이브러리 C++: <queue>, std::priority_queue<T> C#: System.Collections.Generic, PriorityQueue<T, P> JAVA: java.util, PriorityQueue<E> Python: impo... 2024.06.11 컴퓨터 공학, 자료구조 트리, 이진 탐색 트리 (Binary Search Tree) 탐색 시간 평균: $O(log N)$ 최악: $O(N)$ 요소 추가/삭제 평균: $O(log N)$ 최악: $O(N)$ 트리 (Tree) 트리(Tree)형 자료구조는 비선형 계층 관계(부모-자식 관계) 자료구조입니다. 각 노드(Node)는 방향이 ... 2024.01.24 컴퓨터 공학, 자료구조 큐(queue) 개요 헤더 파일: <queue> STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조. 탐색 시간: $O(1)$ (Front 탐색) 요소 추가/삭제: $O(1)$ (Enqueue 및 Dequeue) 큐(Queue)는 선형 자료구조이면서 선입선출(First I... 2023.12.08 컴퓨터 공학, 자료구조 스택(stack) 개요 헤더 파일: <stack> STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조. 탐색 시간: $O(1)$ (TOP 탐색) 요소 추가/삭제: $O(1)$ 스택(Stack)은 선형 자료구조이면서 후입선출(Last In First Out, LIFO) 특성을... 2023.12.06 컴퓨터 공학, 자료구조 덱(deque) 개요 헤더 파일: <deque> STL 시퀀스 컨테이너 (sequence container): 시퀀스 블록 집합 컨테이너 탐색 시간: $O(1)$ 요소 추가/삭제 양쪽 끝에서의 추가/삭제: $O(1)$ 중간에서의 요소 추가/삭제: $O(N)$ 덱(Deque, Double-En... 2023.12.02 컴퓨터 공학, 자료구조 시퀀스 컨테이너의 삭제와 이터레이터 무효화(erase(), remove()) vector를 사용하다 보면 다음과 같은 에러를 한 번씩은 봤을 수 있습니다. erase()를 쓰거나 insert()를 쓰다 보면 가끔 invalidated iterator라는 표현이 나옵니다. Expression: can’t increment invalidated vector iterator 만약, 본 적 없다면, 이미 알고 잘 쓰고 계시거나... 2023.12.01 컴퓨터 공학, 자료구조 리스트 개요 헤더 파일 <list>: 이중 연결 리스트(doubly linked list) <forward_list>: 단일 연결 리스트(singly linked list) STL 시퀀스 컨테이너 (sequence container): 노드(Node)기반 연결형 선형 자료구조 탐... 2023.11.29 컴퓨터 공학, 자료구조 [STL] vector 개요 헤더 파일: <vector> STL 시퀀스 컨테이너 (sequence container): 선형 자료구조 탐색 시간: $O(1)$ (임의 접근) 요소 추가/삭제 $O(1)$ (재할당 하는 경우를 제외하고 배열의 마지막 위치에 요소를 추가하거나 삭제하는 경우) $O(N)$ (중간에 삽입/삭... 2023.11.25 컴퓨터 공학, 자료구조 [STL] array 개요 헤더 파일: <array> STL 시퀀스 컨테이너 (sequence container): 선형 자료구조 탐색 시간: $O(1)$ (임의 접근) std::array는 배열의 STL 버전입니다. 자료 구조의 형태는 고정된 크기의 배열 그 자체지만, 기존의 배열을 사용하는데 있어서 문제점은 인덱스를 직접 지정해 줄 수 있... 2023.11.23 컴퓨터 공학, 자료구조 [자료구조 기본] 배열 배열이란, 연속적인 메모리 공간에 동일한 타입의 데이터를 저장하는 기본적인 형태의 자료구조 입니다. 여기에서 중요한 것은 물리적으로 연속적인 메모리 공간이고 동일한 타입을 저장한다는 것입니다. C++ (C++ 11)에서는 std::array라는 표준 템플릿 라이브러리(Standard Template Library, STL)가 추가되었습니다. 특징... 2023.11.22 컴퓨터 공학, 자료구조 STL - 알고리즘 (Algorithm) STL 알고리즘(Algorithm)은 데이터를 처리하고 조작하는 데 사용되는 함수 템플릿의 집합입니다. C++ STL의 <algorithm> 헤더 파일에는 다양한 알고리즘 함수들이 포함되어 있습니다. 이 알고리즘들의 일부를 나름대로 카테고리별로 나누어 표로 정리해 봤습니다. 정렬 알고리즘 설명 ... 2023.11.21 컴퓨터 공학, 자료구조 STL - 반복자 (Iterator) (with.C++) 반복자, 흔히 이터레이터(Iterator)라 불리는 이것은 STL(Standard Template Library)에서 매우 중요한 역할을 합니다. (이후 반복자라는 단어 보다는 이터레이터라는 단어를 사용하겠습니다.) 이터레이터는 컨테이너에 저장된 데이터를 순회하여 각 데이터에 대한 접근을 제공하는 객체입니다. 단순히 array나 vector와 ... 2023.11.19 컴퓨터 공학, 자료구조 STL - 컨테이너 (Container) STL 컨테이너란? STL 컨테이너는 프로그래밍 언어에서 데이터를 저장하고 관리하는 다양한 방법을 말하는 자료 구조입니다. 동일한 타입의 여러 종류의 객체를 저장하는 일종의 집합이라고 볼 수 있습니다. 다양한 종류의 컨테이너가 있으며, 각각 고유한 방식으로 데이터를 저장하고 관리합니다. 주요 컨테이너 유형 1. 시퀀스 컨테이너 (Seque... 2023.11.18 컴퓨터 공학, 자료구조 STL - Standard Template Library 란? STL(Standard Template Library)은 일반화 프로그래밍(Generic Programming) 기법을 활용하여, 데이터 타입에 얽매이지 않고 유연하게 적용될 수 있는 자료 구조와 알고리즘을 제공하는 라이브러리입니다. 여기서 일반화 프로그래밍(Generic Programming)이란, 데이터 타입에서 독립적인 코드를 작성할 수 있게 ... 2023.11.16 컴퓨터 공학, 자료구조