수댕의 개발일지

알고리즘 공부를 하기 위해 코테를 풀다보니 List와 Set의 시간복잡도 차이에 놓치고 있는 부분이 생겼다. List vs Set 시간 복잡도 기능ListSet추가 (Add)O(1)O(1)제거 (Remove)O(n)O(1)탐색 (Serch)O(n)O(1)정렬 (Sort)O(n logn)-  여기서 내가 놓친 것은 "remove"이다. List는 순서가 있는 자료구조이고, Set는 순서가 없는 자료구조이다. 그렇기 때문에 List에서 제거를 할때는 탐색을 통해 해당 값을 찾고, 제거한다. 하지만 Set은 내부적으로 해시 테이블의 구조로 이루어져있다. 그래서 제거하는데 시간복잡도가 O(1)이 걸린다. Set이 해시 테이블 기반으로 구현되어있다고?set에 대해 조금 더 자세히 살펴보기 위해 해시 테이블을 생각..

1 .List python -> dynamic array : 연속적 시간 복잡도 Dynamic array access / update O(1) insert_back amortized O(1) delete_back O(1) insert_at O(n) delete_at O(n) 2. LinkedList, Doubly LinkedList LinkedList : Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조, 비연속적 -> Node는 데이터 값(value), 주소값(next)로 구성 시간 복잡도 Linked List access / update O(n) insert_front O(1) insert_at O(n) insert_back O(n) | O(1) remove_front O(1) rem..