공부기록/Algorithm

Complexity Big-oh Notation시간 복잡도에 대해 설명해주세요. O() 로 표기되는 빅 오 표기법은 최악의 경우에서의 성능을 나타냅니다. 시간/공간복잡도에 대해 설명해주세요. 알고리즘이 얼마나 효율적인지 판단하는 척도입니다. 각각 특정 크기의 입력(n)을 기준으로 연산 시간 또는 메모리 사용량이 얼마나 되는지 객관적으로 판단하는 데 쓰입니다. 두 복잡도 모두 빅오 표기법을 사용하여 표현할 수 있습니다. O() 로 표기되는 빅 오 표기법은 최악의 경우에서의 성능을 나타냅니다. 시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간의 양을 의미하고, 입력된 데이터의 크기와 실행 시간 간의 비례 관계를 나타내는 지표입니다. 공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리의 양을 나..

https://www.youtube.com/watch?v=wpaRL-WZn7c&t=410s AVL tree BBST(균형이진트리)의 가장 엄격한 형태의 트리 중 하나로 균형 요소(balance factor)를 1개 이하로 유지한다. 이 균형 요소는 트리의 높이(height)가 노드의 개수에 대해 로그함수적으로 상대적임을 보장한다.(Balance factor guarantees the tree's height to be logarithmic relative to the number of nodes.) Balance Factor 균형 요소 [**] BF란? BF는 balanced Factor의 줄임말로, 왼쪽의 하위 트리의 높이에서 오른쪽의 하위 트리의 높이를 뺀 값을 뜻한다. BF 계산과 균형 판별 중요한..

이진 탐색 트리 Binary Search Tree (BST) 노드 기반 이진 탐색 트리 데이터 구조로 다음 속성을 가진다. 노드의 왼쪽 하위 트리에는 해당 노드의 key보다 적은 값을 가진 노드만 포함한다.(즉, 왼쪽 자식 노드부터는 본 노드보다는 작은 값을 가진다.) 노드의 오른쪽 하위 트리에는 해당 노드의 key보다 큰 값을 가진 노드만 포함한다. 왼쪽과 오른쪽 하위 트리 또한 반드시 이진 탐색 트리여야만 한다. 이러한 속성 덕분에 검색하기 유용하고, 덕분에 이진 ‘탐색’ 트리 라는 이름이 붙었다. 루트에서 시작되어 크고 작음을 비교하며 이동하면 되기에, 이 트리는 비교 횟수가 적은 요소를 검색하는 데 유용하다. 탐색 시간은 트리의 높이에 달렸다. Nodes of BST 이진 탐색 트리의 각 노드는 ..