목록Algorithm (6)

어제의 나보다 성장한 오늘의 나

[C++][자료 구조] Map STL 구현 ( RbTree , Template ,Iterator , Operator overloading )

Map STL 구현 우리는 Map STL을 코딩하면서 정말 많이 사용한다. Pair로 저장할 수 있고 , 자동으로 정렬이 되고 , 삽입 / 삭제가 빠르고, … 장점이 되게 많기 때문이다. 오늘은 Map STL을 C++로 구현 해보고 Map에서 사용 된 기능 , 그 구조에 대해서 알아볼 것이다. 한 마디로 Map STL을 완전 뜯어 볼 생각이다. 많은 공부가 될 것이다. Map STL 구현 Full Code Github 주소 : https://github.com/ohinhyuk/MCNL-Study/blob/main/%EA%B3%A0%EC%9C%A4%EB%AF%BC%EA%B5%90%EC%88%98%EB%8B%98%20%EC%8A%A4%ED%84%B0%EB%94%94/week%202/RedBlack%20Tre..
c++/data_structure_구현 2022. 7. 23. 17:35
[c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제

공통 특징 ◎ 헤더파일 : ◎ iterator 사용 / 반환 ◎ 이진 탐색 구조 / 시간 복잡도 : O(log N) ◎ 오름차순 정렬되어 있어야 한다. ◎ 찾는 값이 벡터/배열 속에 여러 개 있을 경우 가장 앞에 있는 값을 가리키는 iterator 반환 Lower_bound ◎ 찾는 값이 없다면 찾는 값보다 큰 값 중 가장 작은 값을 찾는다. vector v = {6, 2, 3, 4 ,3 ,6 ,6 ,7, 2, 1}; sort(v.begin() , v.end()); // sorted : 1 2 2 3 3 4 6 6 6 7 cout
c++/문법 2022. 2. 13. 16:33
[C++] Singly Linked List(싱글 링크드 리스트) 구현

Singly Linked List란? ◎ 단일 방향으로 노드들이 연결되어 있는 STL container 중 하나이다. ◎ 데이터를 가지고 있는 연결된 노드들의 맨 앞과 맨 뒤에는 Head , Tail 이름의 노드가 있다. ◎ 노드들은 모두 next라는 노드 포인터를 가지고 있어서 다음 노드와 연결 할 수 있다. 구현 ◎ Class 와 Struct를 사용하여 좀 더 깔끔한 코드를 구현하였다. ◎ Template 을 사용하여 int 뿐만 아니라 다른 Type의 자료형을 위한 Container로도 사용할 수 있다. Coding 1) 기본 구조 template struct Node{ T data; // Node 속 data 저장 Node* next = nullptr; }; template class Singli..
c++/data_structure_구현 2022. 2. 12. 19:08
[C++] Priority Queue & Pair 사용법

Priortity Queue와 Pair를 함께 사용하면 어떤 기능을 할 수 있는지 알아보자. ① 기본적인 사용 첫 번째 인자 기준으로 내림차순 정렬, 같다면 두 번째 인자를 기준으로 내림차순 정렬. priority_queue pq; pq.push({1,2}); pq.push({1,3}); pq.push({2,2}); pq.push({2,5}); pq.push({3,1}); while(!pq.empty()){ cout
c++ 2022. 2. 12. 16:27
Stack(스택) 구현 & Stack STL 총정리

c++ 에서 array를 이용하여 stack을 구현하기. c++의 STL 중 하나인 Stack Container를 구현해봤다. Stack의 동작 원리 -LIFO (Last in First Out) : 가장 마지막에 들어온 값이 가장 먼저 나갈 수 있는 형태이다. 반대로 가장 먼저 들어온 값은 가장 마지막에 나갈 수 있다. Stack의 함수 1) empty - stack이 비어있다면 true를 return, 아니라면 false를 return. 2) push - 값을 stack에 집어넣는다. 3) pop - 가장 최근에 들어온 값을 stack에서 빼낸다. 4) top - 가장 최근에 들어온 값을 return. 5) size - stack의 크기를 return. 가 있다. 구현한 코드 설명 1) empty 스..
c++/data_structure_구현 2022. 2. 9. 19:28
sort( Bubble sort , Insertion sort , Selection sort , and Qsort)

1. bubble sort 필요한 그림 : (array에 맨앞 index start ,맨 뒤 index end , 움직이는 index : index ) 시간 복잡도 : O(N^2) (오름 차순 정렬일 때,) 가장 큰 값 부터 가장 작은 값 까지 차례로 오른쪽에 한 개씩 정렬해나가는 방법이다. stable sort이다. ※ stable sort 란 같은 값들이 array에 있을 때, sort 전의 같은 값들끼리의 순서가 sort후에도 보장된다는 것이다. 예를 들어 sort 전 1 3 1 2 5 의 어레이가 있다고 했을 때 sort 후 1 1 2 3 5 가 될 텐데 stable sort를 했다면 sort 전 맨 앞의 1 이 sort 후 맨앞의 1 이되고, unstable sort를 했다면 sort 전 맨앞의..
c++/data_structure_구현 2022. 2. 9. 18:59
Prev 1 Next