Tree
-
[C++] 카카오 코딩테스트 < 길 찾기 게임 > 문제풀이백준 문제풀이/etc 2020. 2. 9. 16:30
풀이 바로 본론으로 갑시다. 여기로 가시면 문제를 풀어보실 수 있습니다. 문제를 읽어보니 전무로 승진한 라이언이 사원들을 위해서 무언가 엄청 분석하고 있습니다. 하지만, 문제에서 요구하는 것은 간단합니다. 기본적인 트리를 구현하고 전위순회와 후위 순회를 수행해라. 트리 구현이 필수적인 경우엔 반드시 필요한 요소만을 구현할 필요가 있습니다. 기본적으로 자료구조에서 배운 트리는 Value 값만을 갖고 왼쪽 자식, 오른쪽 자식을 구별합니다. 저는 이 문제를 해결하기 위해 TreeNode 의 멤버 변수로 x, y, value 를 사용했습니다. y 는 상대적인 depth 를 의미합니다. x 는 크기를 비교하는 key 값이 됩니다. value는 실질적으로 답이 되는 값입니다. Tree 의 구현은 자료구조 개념과 같..
-
[알고리즘] 레드-블랙트리(Red-BlackTree) -Insert프로그래밍/알고리즘 2019. 4. 8. 23:20
이진탐색트리(BST)를 기반으로 구성된 자료구조입니다. BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 개념설명 : 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서..