본문 바로가기

분류 전체보기

 (158)
c++ stl heap 기록 stl의 heap 기능을 활용해서 임의의 벡터를 힙 구조로 변경해 줄 수 있다. std::make_heap(first iter, last iter)를 활용해서 벡터를 힙으로 변경 가능하다. (시간복잡도 : O(N)) std::pop_heap(first iter, last iter)를 활용해서 벡터의 최댓값을 맨 아래로 정렬 가능하다. (시간복잡도 : O(LogN) vector.pop_back()을 활용해서 맨 아래 있는 원소를 제거 가능하다. vector.emplace_back(element)를 활용해서 힙에 원소를 넣어줄 수 있다. std::push_heap(first iter, last iter)을 사용하면 emplace_back으로 넣은 원소가 포함된 벡터를 힙으로 바꿔줄 수 있다. 코드 >> 1 ..
c++ priority_queue 가장 큰 숫자 3개, 가장 작은 숫자 4개를 골라라 같은 문제가 나오면 priority_queue를 사용하도록 하자. Insertion, pop -> O(Logn) Min or Max -> O(1) Top이 Maximum 값 즉 Pop 하면 최대값이 없어지고 그다음 최대값이 Top으로 간다 Vector로 어떻게 Priority_Queue를 설정하는가 노드의 위치를 기반으로 인덱스를 설정해서 벡터에 넣는다 9 7 5 3 1 벡터에 9 7 5 3 1 순서로 입력한다. L = 2*idx+1 이고 R = 2*idx+2 이다. 그리고 만약 새로운 값이 들어 오면 bubble 인덱스를 통해서 순서가 조정된다. 만약 pop 명령어로 최상단의 값이 사라지면 먼저 top 바로 밑에 있는 노드가 올라가게 되고, 노드간 비..
c++ stack, Queue stack과 Queue는 Array를 활용해서 직접 구현하도록 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include /// /// Queue와 Stack은 성능을 위해서 Vector나 Array를 활용해서 직접 구현한다. /// /// /// int main() { // Stack std::stack nums; nums.emplace(1); nums.emplace(3); nums.emplace(5); std::cout
c++ list와 vector 비교 실무에서는 99% Vector를 쓴다고 보면 된다. Time Complexity Find Random Access Insertion/Deletion I/D back Vector O(N) O(1) O(n) O(1) List O(N) O(1) O(1) O(1) 각 연산에 대한 Time complexity를 보면 List가 좋아 보인다. 하지만 메모리는 연속 격자 구조 이기에 Vector가 훨씬 빠르다. List는 메모리가 여기 저기 흩어져 있다. 그리고 연속 구조가 아니기 때문에 병렬 프로그래밍이 어렵다. List는 emplace back, emplace front 명령이 있고 emplace(iterator, value)로 해당 위치에 value를 입력할 수 있다. 그리고 merge와 splice를 활용해서..
c++ set,map,unorded_set,unordered_map 정리 set, map은 트리 구조여서 O(log(n))으로 remove,insertion,access가 가능하다. 또한 sorted 되어 있다. 그리고 별도로 comparision operator를 정의해야 한다. unordered_set, unordered_map은 hash를 사용하여 O(1)로 가능하다. 이름과 같이 unordered이기 때문에 sort는 불가능하다. 그러나 사이즈가 커지면 O(n)의 복잡도로 rehashing이 일어날 수 있다. 이를 방지하기 위해서 reserve로 메모리를 미리 확보해야 한다. 또한 ==operator와 hashing 구조체를 별도로 구현해야 한다. 그리고 unoredred_map의 코드를 첨부한다. set과 unordered_set은 Key만 고려하면 되고 map과 u..
c++ unordered_set 사용 기록 unordered set을 사용하기 위해서는 직접 hash 구조체와 operator==를 정의해 주어야 한다. hash 구조체를 namespace std에 지정하면 별도로 hash 구조체를 안 넣어줘도 된다. unordered set은 time complexity가 O(1)이다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..
c++ map 사용 방법 map은 Key value 관계로 데이터를 저장한다. set과 마찬가지로 Key 값이 중복되면 저장이 잘 안된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include #include int main() { std::map numPairs; numPairs.emplace(2, 102); numPairs.emplace(3, 103); numPairs.emplace(4, 104); numPairs.emplace(5, 105); // 1이 중복이라 추가 안 됨; numPa..
c++ set, multiset, 커스텀 비교 함수, 커스텀 클래스 set은 search, removal, insertion을 logn time complexity로수행 가능하다. set을 사용할때 custom한 함수를 넣어서 비교를 할 수있다. 다만 중복 되면 입력이 잘 안된다. 따라서 중복이 되는 데이터를 다룰 때는 multiset을 사용하도록 하자 그리고 클래스를 넣을 수도 있는데 꼭 비교 operator를 넣어 주도록 하자 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..

티스토리툴바