728x90 C, C++11 인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 이진 트리를 순회하는 세 개의 방법 정의 이진 트리(Binary Tree) 를 순회(Traversal)할 때 위와 같이 세 가지 방법이 존재한다. Inorder (중위 순회) : left Node -> root Node -> right Node preorder (전위 순회) : root Node -> left Node -> right Node postorder (후위 순회) : left Node -> right Node -> root Node 중위 순회 (Inorder Traversal) left Node -> root Node -> right Node 순서로 순회한다. 위 트리에선 (1) -> (3) -> (4) ->.. 2023. 1. 15. 이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 정의 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는 트리 설명 컴퓨터 과학에서 정말 많이 사용되는 자료구조이다. 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는다. 또한 이진 트리에서 부트리(Sub-Tree) 또한 이진 트리이다. Root : Tree의 최상위 노드 Parent / Child : 위 예시에서 임의의 노드 A노드는 B, C 노드의 Parent 이며, B, C 노드는 A 노드의 Child 노드이다. Sibling : 같은 Parent 노드를 가진 두 노드 Leaf Node : Child 노드가 없는 노드 Depth : 임의의 노드에서, Root 노드 까지의 간선의 수 Height : 최대 Depth의 값 Sub Tree : 트리에서, 임의의 노드를.. 2023. 1. 14. sstream [stringstream] #include stringstream 설명 sstream 은 string stream 의 약자이다. string stream 는 주어진 어떠한 문자열에서 원하는 자료형으로 정보를 얻을 수 있다. 또한 여러가지 자료형을 가진 데이터들이 들어올 때 효과적으로 관리를 할 수 있다. stringstream 은 저장이 된 문자열에서 공백(' ')과 줄바꿈('\n') 을 기준으로 문자열을 구분하여 처리한다. 1) 문자열에 대해서 띄어쓰기를 기준으로 원하는 자료형으로 분리를 할 수 있다. #include #include using namespace std; int main() { string out; string strInput = "Hello world hello C++"; stringstream s_stream.. 2021. 8. 29. 세그먼트 트리 (Segment tree) 세그먼트 트리 (Segment tree) 정의 세그먼트 트리 (Segment tree) 란, 1차원 배열의 값들을 포화 이진 트리를 활용하여 Bottom-up 을 통해 효율적으로 저장 및 탐색하는 자료구조 이다. 이 트리의 리프 노드들은 순서대로 배열의 원소들에 해당이 되며, 내부 노드들은 아래 두 자식 노드에 해당이 되는 배열의 원소들을 합한 범위의 원소들에 대한 연산 값을 나타낸다. 트리 구현 트리의 각 노드들은 배열에서 트리에 해당되는 구간의 원소들의 합의 값을 가지고 있다. 설명 세그먼트 트리는 Bottom-up 방식으로 구현이 된다. 이를 위해선, 리프 노드들을 배열의 원소들로 우선적으로 초기화를 시켜준다. 리프노드의 시작 노드는 배열의 개수보다 큰 2의 제곱수 들 중 최소값이다. 즉 위 트리에.. 2021. 8. 3. 힙[Heap], 삽입 및 삭제 힙 (Heap), 삽입 및 삭제 정의 최대힙/최소힙 ( Link : 2021.07.21 - [C++ Algorithm/ETC] - 힙 [Heap], 최대힙/최소힙 ) 에서 임의의 값을 삽입, 삭제할 때 O(logN) 의 시간복잡도로 해결을 할 수 있다. 이러한 1차원 array 에서는 임의의 값을 삽입하거나 삭제를 할 때 마다 O(N)의 시간이 소요가 되어 굉장히 비효율적이다. 최대힙/최소힙을 사용한다면 이는 이진트리로 이루어졌기 때문에 이 작업들이 O(logN)의 소요시간을 가진다. 삽입 최대힙/최소힙 에서 Data 의 삽입은 현재 Node중 가장 마지막 Node에 우선 연결이 된다. 힙(Heap)은 완전이진트리를 활용한 자료구조 이기에 삽입을 할 때 기존 Node 와 Swap을 하여 두지 않는 이상 .. 2021. 7. 22. 힙 [Heap], 최대힙/최소힙 힙 (Heap), 최대힙/최소힙 정의 힙(Heap) 이란 완전이진트리(Perfect Binary Tree) 를 응용한 자료구조이다. 완전이진트리는 아래와 같은 Binary Tree를 의미한다. 완전이진트리는, 위처럼 마지막 레벨을 제외하면 모두 포화상태이며 마지막 레벨에 해당되는 노드들은 모두 좌측으로 쏠려있는 Binary Tree 이다. 이를 이용해서 힙(Heap)이라는 자료구조에 접근을 할 수 있다. 예를 들어 만약 최소힙을 생성하게 되면, Parent node 는 항상 Child node 보다 작거나 같은 값을 가지게 된다. 설명 힙(Heap)은 일반적으로 어떠한 수의 배열에 있어서 최소값과 최대값을 구할 때 쓰인다. 최소값을 구할 때 쓰이는 힙(Heap)은 최소힙(Min Heap) 이라고 불리고 .. 2021. 7. 21. C++ PriorityQueue Container Priority Queue Container Priority Queue 란? 우선순위 queue 를 구현한 template class 이다. 기존의 queue container 에 오름차순, 내림차순을 사용하여 우선순위를 부여 한 것이다. header file 에 있다. Queue container 설명 Link : 2021.02.09 - [C++ Header/#include ] - Queue container 형식 template template class priority_queue 생성자 std::priority_queue pq; // default container type : vector, default 정렬기준 : less std::priority_queue pq; // default 정렬기준 .. 2021. 7. 6. Bitmask (2), "자주 사용되는 형태" Bitmask (2), "자주 사용되는 형태" 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 int nth_bit_on(int n) { return 1 2021. 2. 25. Bitmask (1), "Bit operator" Bitmask (1), "Bit operator" OR operator ( A | B ) 두 비트중 하나라도 1 이면 1 이다. ex) 0 0 1 1 ⑵ | 0 1 0 1 ⑵ = 0 1 1 1 ⑵ AND operator ( A & B ) 두 비트 다 1 이어야 1 이다. 0 0 1 1 ⑵ & 0 1 0 1 ⑵ = 0 0 0 1 ⑵ XOR operator ( A ^ B ) 두 비트가 같으면 1, 다르면 0 이다. 0 0 1 1 ⑵ | 0 1 0 1 ⑵ = 1 0 0 1 ⑵ NOR operator ( ~ A ) 모든 비트가 반전된다. ~ 0 0 1 1 ⑵ = 1 1 0 0 ⑵ SHIFT operator ( A > i ) A 를 i 비트만큼 이동시킨다. int i = 3; 1 0 1 1 ⑵ i = 1 ⑵ = .. 2021. 2. 9. lower_bound, upper_bound lower_bound & upper_bound std::lower_bound - cppreference.com std::upper_bound - cppreference.com Definition lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용 upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용 How to use Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다. lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound.. 2021. 2. 4. C++ Queue Container // Queue Container What is Queue Container? 선입선출(FIFO : First - In, First - Out)의 원리에 따라 객체의 삽입 및 삭제를 수행하는 자료의 저장 공간이다. ※ 선입선출 이란? 말 그대로 저장 공간에 먼저 들어간 데이터의 값이 먼저 나오는 형태를 말한다. 비유를 하자면, 휴지심같이 위아래가 뚫린 원기동 모양의 통이 있다고 할때 이 원통 위로 계속해서 테니스 공을 넣으면 원통의 아래 부분으로 공이 빠져나올 것이다. 또한 먼저 넣은 테니스 공이 아래로 먼저 나올것이다. 이러한 원리라고 생각하면 된다. How to use queue의 선언 #include // queue 헤더파일 내에 있다. using namepsace std; // queue는 std.. 2020. 12. 18. 이전 1 다음 728x90
