TECH/Algorithm
-
왜 unbalanced binary search tree는 나쁠까?TECH/Algorithm 2021. 9. 20. 13:03
Why an unbalanced binary search tress is bad? 일반적으로 binary search tree는 조회(lookup), 삽입(insert), 삭제(delete)에 O(logN)이 소요되는 자료구조 이다. 하지만, 아래 그림과 같이 이진 검색 트리가 한 쪽으로 편항될 경우, 사실상 링크드 리스트와 다를게 없게 된다. 따라서 조회(lookup), 삽입(insert), 삭제(delete)에 O(N)이 소요되어 성능의 저하가 발생한다.
-
Stack과 Queue 구현, 배열과 링크드 리스트 중 어떤 것을 이용할까?TECH/Algorithm 2021. 9. 14. 20:50
Summary Stack : 둘 다 가능 Queue: 리스트를 이용하는 것이 일반적. Stack & Queue Stack Array와 LinkedList 모두 구현 가능하다. Array 장점 메모리에 연속적으로 할당되는 특징 덕분에 캐시 지역성을 이용한 더 빠른 접근이 가능하다. 단점 사이즈가 제한되어 있다. 고정 크기 배열 경우 사이즈를 늘리기가 불가능하고, 유동 크기 배열의 경우 사이즈가 한계에 다다르면 어레이를 (일반적으로) 두배 크기로 늘리고, 기존의 요소들을 모두 복사해야하는 작업이 필요하다. LinkedList 장점 사이즈에 제한 받지 않는다. 단점 배열과 달리 요소가 연속적으로 할당되지 않아 비교적 느리다. 포인터를 위한 추가적인 메모리 공간이 필요하다. Queue LinkedList로 구현..