TIL (Today I Learned)/알고리즘3 [알고리즘] Big O #1 Big O Big O는 코드가 얼마나 효율적으로 실행되는지 수학적으로 비교하는 방법. 동일한 작동을 하는 코드 A와 코드 B가 있다고 생각해 보자. 코드 A는 15초 동안 실행되고, 코드 B는 1분 동안 실행 된다면, 우리는 코드 A가 더 낫다고 생각할 것이다. 이것이 시간 복잡도이다. 하지만, 시간 복잡도는 시간으로 측정하지 않는다. 무슨 소리예요, 방금 15초와 1분을 비교했잖아요? 하실 것이다. 왜냐면 방금 시간을 측정한 컴퓨터보다 성능이 더 좋은 컴퓨터로 B코드를 실행하면 15초보다 빠르게 실행될 수도 있기 때문이다. 따라서, 무언가를 완료하는 데 걸리는 작업 수로 측정하는 것이 더욱 정확하다. 시간 복잡도 외에도 공간 복잡도를 측정해야 한다. 코드 A는 매우 빠르게 실행되지만 상대적으로 실.. 2023. 3. 16. [알고리즘] RB Tree삭제 동작 원리 #2 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드 블랙 트리 삭제 방식 0. 삭제 전 RB 트리 속성 만족한 상태 1. 삭제 방식은 일반적인 BST와 동일 2. 삭제 후 RB 트리 속성 위반 여부 확인 - 어떻게 확인할 수 있는가 3. RB트리 속성을 위반했다면 재조정 4. RB 트리 속성을 다시 만족 RB.. 2022. 11. 26. [알고리즘] RB Tree개념과 삽입 동작 원리 #1 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드블랙 트리 기본 개념과 특징 1. 레드블랙 트리 개념 1. 이진 탐색 트리(BST)의 한 종류 2. 스스로 균형 잡는 트리 3. BST의 worst case의 단점을 개선 : worst case = 한 방향으로 편향된 이진탐색 트리 > O(N) 4. 모든 노드.. 2022. 11. 26. 이전 1 다음
