본문 바로가기

c++9

Bubble Sort 작동방식 (간단) _Bubble Sort 거품 정렬 또는 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다 버블 솔트는 말 그대로 버블이라는 원 하나를 만들어 두개의 원소를 조사하여 더 작은 값을 큰 값이랑 스위치해 왼쪽으로 가게 만들어준다. Bubble Sort는 stable하다 (@@색은 버블이라 생각하면된다) [9, 3, 5, 7, 1] [9, 3, 5, 7, 1] --> [3, 9, 5, 7, 1] [3, 9, 5, 7, 1] --> [3, 5, 9, 7, 1] [3, 5, 9, 7, 1] --> [3, 5, 7, 9, 1] [3, 5,.. 2022. 7. 13.
Set, multiset, unodered_set, map, multimap, unodered_map set 은 이라는 헤더 파일을 가진다. std::set유형의 고유한 개체의 정렬된 집합을 포함하는 연관 컨테이너입니다 Key. 정렬은 키 비교 기능 Compare 를 사용하여 수행됩니다 . 검색, 제거 및 삽입 작업에는 로그 복잡성이 있습니다. 세트는 일반적으로 레드-블랙 트리 로 구현됩니다. Red-Black-Tree 란 binary-search-tree의 한 종류이다. 스스로 균형을 잡는 blanced tree이고 binary serch tree의 worst case의 단점을 개선시킨 트리이다. 모든노드는 black 아니면 red이다. nil노드는black이다. red노드는 연속하지 않는다. 임의의 노드에서 자손 nil노드까지 가는 경로의 black의 수는 같다 (자기자신은 카운트 제외) 위 같은 특.. 2022. 6. 9.
stack queue 스택 큐 stack 은 헤더 파일로 을 가진다. Container를 사용자가 설정할 수 있고 default 값으로 deque을 가진다. 덱(deque)이란 STL 컨테이너 라이브러리 중 하나인 Deque(Double Ended Queue) 덱은 큐(Queue)와 비슷하지만 큐와 다르게 삽입과 삭제가 앞, 뒤 양쪽으로 모두 가능합니다. 덱의 삽입과 삭제는 양쪽 끝(앞, 뒤)에서 이루어진다. 크기가 가변적이다. 인덱스가 존재하기 때문에 임의의 원소에 접근이 가능하다. Stack은 LIFO(Last In First Out)의 특성을 가진다 말 그대로 마지막에 들어온게 제일 먼저 나간다는 뜻으로 해석하면 된다. 간단한 예제 코드를 확인해보자. Queue( 큐 ) Queue같은 경우 FIFO (First In First .. 2022. 6. 9.
list vs vector vector와 list의 timecomplexity다. 이것만 보면 서로 장단 점이 있어 random access 를 할 때는 vector로 구현하고 i/d 를 쓸 때는 list를 쓰면 될 것 같다 하지만 99%가 vector를 쓴다 find 때문이다 TimeComplexity는 같지만 실행해보면 vector의 find가 훨씬 빠르다. 그 이유는 두가지 이유가 있는데 첫번째로 메모리 구조 때문이다. vector는 연속되게 저장된다 하지만 list는 3개씩 떨어진 상태로 저장된다. find를 하게 되면 vector에서는 1부터 4까지 하나씩 움직이며 찾게 되고 움직인 뒤 그 메모리는 캐시 된다 그런데 list는 떨어진 상태로 존재하기 때문에 1을 찾고 캐시를 하고 캐쉬가 캐시 미스가나고 2를 찾고 캐쉬를 .. 2022. 6. 6.

티스토리툴바