본문 바로가기

ALGORITHM/코딩테스트를 위한 자료구조와 알고리즘 with c++ 정리

 (13)
BST 구현하기 #include struct node { int data; node* left; node* right; }; struct bst { node* root = nullptr; node* find(int value) { return find_impl(root, value); } private: node* find_impl(node* current, int value) { if (!current) { std::cout data == value) { std::cout left) current->left = new node{ value, NULL, NULL }; else insert_impl(current->left, value); } else { if (!current->right) current->right =..
이진 검색 트리(BST) 이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진 트리입니다. 이진 검색트리의 특징 부모 노드의 값 >= 왼쪽 자식 노드의 값 부모 노드의 값
트리 순회 일단 트리가 구성되어 있따면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 있습니다. 다양한 순회 방법에 대해 간략히 알아보겠습니다. 전위 순회(pre-order traversal) 이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문합니다. 중위 순회(in-order traversal) 왼쪽 노드를 먼저 방문하고, 그다음에 현재 노드, 마지막으로 오른쪽 노드를 방문합니다. 후위 순회(post-order traversal) 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문합니다. 레벨 순서 순회(level-order traversal) 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른..
트리(조직도 구조 만들기) "트리"는 계층적인 자료구조를 표현하기 위해서 사용한다. 이진트리를 구현해보자. 이진트리는 하나의 노드에 두 개의 자식노드를 가질 수 있다. 데이터가 저장된 부분을 노드(node)라고 한다. 노드와 노드 사이를 잇는 선을 간선(edge)라고한다. 회사의 조직도를 구현해본다. 예를 들어서 다음 그림과 같은 모습이다. #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; // 새로운 트리를 만드는 정적 함수 static org_tree create_org_structure(const std::string& pos) { org_tree tree; tree.root = new n..
std::queue 큐는 first in - first out 구조를 가지고 있다. 식당이나 놀이공원에서 줄을 먼저 선 순서대로 나가는 것이라고 생각해보자. #include #include int main() { std::queue q; q.push(1); q.push(2); q.push(3); q.pop(); q.push(4); }
std::deque 덱(deque)은 양방향 큐(double-ended queue)의 약자입니다. 덱의 필요조건 push_pront(), pop_front(), push_back(), push_pop_back() 동작이 o(1)의 시간 복잡도로 동작해야 합니다. 모든 원소에 대해 임의 접근 동작이 o(1) 시간 복잡도로 동작해야 합니다. 덱 중간에서 원소 삽입 또는 삭제는 o(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작합니다. n은 덱의 크기입니다. 덱을 이용한 삽입 삭제 #include #include int main() { std::deque deq = { 1,2,3,4,5 }; // 맨 뒤에 0 추가 deq.push_front(0); // 맨 뒤에 6 추가 deq.push_back(6); //..
반복자 무효화 #include #include #include int main() { std::vector vec = { 1,2,3,4,5 }; auto v_it4 = vec.begin() + 4; vec.insert(vec.begin() + 2, 0); // --------------------------- std::list lst = { 1,2,3,4,5 }; auto l_it4 = next(lst.begin(), 4); lst.insert(next(lst.begin(), 2), 0); } 벡터와 리스트의 반복자 무효화 비교 벡터는 원소를 추가할 때 용량을 초과하게 되면 벡터의 모든 원소를 새 메모리 공간으로 복사하는 동작이 발생합니다. 그렇기 떄문에 이전에 사용하던 반복자를 사용하게 되면 오류를 발생시키게 됩니다..
std::list의 삽입 또는 삭제 함수 사용하기 std::list 삽입과 삭제 #include #include int main() { std::list list1 = { 1,2,3,4,5 }; list1.push_back(6); list1.insert(next(list1.begin()), 0); list1.insert(list1.end(), 7); list1.pop_back(); std::cout

티스토리툴바