자료구조와 시간복잡도에 관한 무작위 정리
-
큐와 우선순위 큐의 시간복잡도차이
우선순위 큐 구현시 리스트, 힙자료구조 사용 가능 데이터 N개일때, 리스트기반시 최악의 경우 복잡도는 O(N^2), 힙은 O(NlogN) 데이터 갯수가 많아질수록 복잡도는 기하급수적으로 증가.
-
리스트와 딕셔너리의 차이점
list : 순서 존재, index 존재, mutable, index지정하여 값변경 가능 , 존재확인하는 in연산자는 하나씩 스캔후 반환하여 오래걸린다(성능 낮음) tuple : 순서 존재, index존재, immutable, immutable,같이 저장시 list보다 적은용량(수정 필요없고 간단한형태는 tuple이 좋다) unpacking(튜플의 값 차례대로 변수에 대입 가능 a,b = b, a가 그예임. 하나씩 안넣어도됨) dictionary : key와 value로 구성, 중복불가, 순서x, 크기와 무관하게 in 연산 속도 일정(key값만 찾으니까) set : key값으로만 구성, 중복불가, 순서 X
-
큐와 리스크의 시간복잡도차이, 큐를 쓰는 이유
deque가 속도가 훨씬 빠르다. list는 O(n), deque는 O(1)이다. append,remove,push,pop 등 연산 많을수록 좋다. Max length도 정할수 있음. deque는 양쪽에서 요소의 추가삭제 list는 fixed size memory blocks(array), 고정된 사이즈의 메모리를 갖는 array임. 첫번째 원소 삭제시 모든원소 앞으로 이동해야함. stack: 무조건 순차적 처리, 구조가 단순하여 구현쉽고 데이터저장,읽기 속도 우수. 하지만 저장 개수 정해야함(재귀함수 호출 개수): 공간낭비 발생우려
-
스택과 큐가 지원하는 operation
stack : push.item,pop.item queue : enqueue, dequeue
-
Heapq 를 쓰지 않을때와 썼을때의 차이
heap : complete Binary tree를 기본으로 가지는 자료구조 최댓값,최솟값 찾아내는 연산 빠르게 하기위해 시간복잡도는 O(logN) -> 삽입,삭제의 시간복잡도 list , sorted,pop을 이용하면 O(nlogn)으로 큼.
최대힙: root가 최대,부모의 노드가 자식노드의 값과 같거나 더큼, 최소힙 : root가 최소,부모의 노드가 자식노드의 값과 작거나 더작음 이진탐색트리 : 부모노드의 값보다 작으면 왼쪽,크면 오른쪽 자식(힙은 이런 규칙이 없다.) 최소힙 기준으로 삽입과 삭제의 과정
insert : 왼쪽에서 오른쪽순서로 완전이진트리를 구성하며 데이터 삽입 -> 입력된 데이터와 부모 노드 비교 -> 부모보다 작다면 서로의 자리를 변경 -> 이전 2단계를 부모보다 클때까지 반복. delete : 루트노드 삭제 -> 트리의 말단에서 가장 오른쪽에 있는 노드를 루트로 승격 -> 루트노드가된 데이터와 두 자식노드의 값을 비교하여 가장 작은 값과 위치 변경
heapq사용시 직접 힙을 구현하지 않아도 된다. 직접구현과 시간복잡도 차이 심하다, 트리는 원소에 한번에 접근이 가능함, 배열을 사용하여 트리 구현시 메모리고정할당방식이라는 배열의 특성상 불편한점 많음
-
순열 permutation을 사용하지 않고 재귀함수로 구현
재귀를 이용한 순열의 시간복잡도는 O(n!) 재귀 사용하지 않은 itertools.permutation 은 O(n*n!) 더높지만 데이터 클때 더 효율적인 이유 : 최적화(메모리, 시간) 재귀는 기본적으로 부하가 많이걸린다. 특정상황에는 쓰는게 좋지만.
