Hello backEnd

문제 설명1. 몇개의 노드가 주어질지 입력2. 순서대로 노드가 주어진다.3. 어떤 노드를 지울지 알려준다.4. 그 노드랑 이 노드의 모든 자식노드를 지원 후 남은 자식노드 갯수 구하기풀이 과정1. 처음에는 그냥 어떤 노드의 자식들을 모두 보관하게 하고 그 노드를 기준으로 자식을 확인해가면서 삭제해줬다.2. 그리고 ans는 처음에 모든 자식없는 노드들을 확인해서 만들어줬다.3. 리프노드 도달시 하나씩 뺴줘서 처리했다.4. 이랬더니 중간에 틀렸는데, 이유를 생각해보니 어떤 노드의 부모가 그 노드만을 자식으로 가진다면 문제가 될 것 같았다.(O-O-O 이렇게 돼있으면 안됨)5. 여러 방법이 있었겠지만... 나는 그냥 그 노드의 부모를 갖는 Map을 하나 더 만들어서 부모 찾고 자식이 하나뿐이면 더해주는 식으..

TreeSet!! public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable {}TreeSet의 구조를 살펴보면 다음과 같다. 이는 AbstractSet, NavigableSet인터페이스를 구현하여 사용하고 있다. TreeSet은 이름처럼 Tree와 같은 구조를 가지고 원소들을 저장한다. 특징을 나열하자면 중복 불가 원소의 순서 보존되지 않음 집어넣은대로 들어가는게 아니라 알아서 트리 구조로 정렬시킨다. 요소를 오름차순으로 정렬한다. Thread-safe하지 않다. Red-Black-Tree TreeSet은 내부적으로 Red-Black-Tree를 사용하고 있다. 이게 뭘까...? Red-B..

Red-Black-Tree!! 얘는 일종의 자기 균형 이진탐색 트리이다. 이진탐색트리란 자신의 왼쪽 서브 트리에는 현재 노드보다 작은 것, 오른쪽 서브 트리에는 큰 것만을 가질 수 있다. 이 덕분에 이진탐색트리에서는 조회를 할 때에 O(log n)의 시간 복잡도를 갖는다. 그런데 만약 요런 식으로 조회하면 O(n)의 시간 복잡도를 갖는다. Red-Black-Tree 알고리즘은 이런 문제를 해결하기 위해 도입되었다. 트리의 속성 모든 노드는 Red 혹은 Black이다. root node는 Black!!! 모든 nil노드는 Black!!! nil노드? go언어에서 null을 nil로 써넣는데 존재하지 않음을 의미하는 노드이다. 자녀가 없을 때에 자녀를 nil노드로 표기 이 nil노드는 값이 있는 노드와 동등..