728x90 C, C++/Data structure7 인오더, 프리오더, 포스트오더 (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. 세그먼트 트리 (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. 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. 이전 1 다음 728x90
