Algorithm/Study (2) 썸네일형 리스트형 단절점 얼마 전에 후배에게 단절점과 SCC에 대한 질문을 받았는데 공부한지 오래되기도 했고 정리하는 시간이 필요할 거 같아서 글로 남기기로 하였다! 단절점은 우선 무향 그래프(Undirected Graph)에서 정의되는 개념이다. 단절점이란, 해당 정점을 그래프에서 지웠을 때 그래프의 전체 컴포넌트 수가 늘어나는 정점을 의미한다. 더 쉽고 풀어서 말해보자면 이쪽과 저쪽을 (혹은 그 이상을) 연결하는 점을 의미한다. 연결성을 중요하게 생각하는 상황에서(라우터의 연결을 나타낸 그래프 같은 거?) 단절점은 정말 중요한 점이다. 해당 정점에 (더 자세하게는 단절점에 연결된 간선이) 문제가 생긴다면 전체적인 연결 자체에 문제가 생긴다는 말이니까. 그렇다면 이 단절점은 어떻게 구할까? 제일 쉽고, 제일 빨리 생각나는 방법.. Red-Black Tree 1. 설명 Dictionary ADT(Abstract Data Type; 추상 자료형)를 구현하는 방법은 여러 가지가 있다. 그중 하나인 Binary Search Tree(이하 BST)는 평균 O(logN)의 삽입, 삭제, 탐색 시간을 가지지만, 최악의 경우 O(N)의 시간 복잡도를 가진다. 이렇게 최악인 경우는 BST에서 원소들이 한 방향으로만 쏠리게 되면 생기게 된다. Best인 케이스는 Tree가 Complete Binary Tree이겠지만 현실은 그렇게 호락호락하지 않다. 그래서 편하게 BST로 구현하고 Worst가 O(N)인 상황을 기도로 피하기에는 여러 가지 애로사항들이 많다. Red-Black Tree는 BST가 가진 문제들을 해결해 줄 수 있다. Wikipedia에는 Red-Black Tr.. 이전 1 다음
