긴가민가2

• 

  210713 NP vs P Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등 Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘) 알고리즘에서 핵심적인 문제 : Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름 Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential 이.. 미가공 필기(알고리즘) 2021. 7. 13.

• 

  210701 레드 블랙 트리(Red-Black Tree) 레드 블랙 트리(Red-Black Tree) 모든 노드는 블랙 노드이거나 레드노드이다 루트는 블랙노드이다 모든 리프 노드는 블랙노드이다 (*리프 노드 : child가 없는 노드) 레드 노드의 child들은 모두 블랙 노드이다 임의의 노드에 대해 그 노드부터 후손 리프 노드까지의 경로에는 같은 수의 블랙노드가 있다 균형 이진 탐색 트리 => 탐색시간 O(log n) 키의 개수 n, 리프의 개수 L 이라고 하였을 때, 전체 노드의 수 = n + L = 전체 edge 수 +1 = 2n +1 L= n+1 레드 블랙 트리 평균 높이 : 원래 트리의 높이를 h, 새로운 트리의 높이를 h' 라 하면 h' >= h/2 검색 연산들은 이진검색 트리와 동일. 삽입, 삭제는 Rotation을 이용하여 수행하다 회전(Rota.. 미가공 필기(알고리즘) 2021. 7. 5.