Computer Science/자료구조3 Array(배열)과 List(리스트) 차이 Array (배열) 특징 메모리 상에 데이터가 연속적으로 저장된다 같은 성질을 갖는 항목들의 집합 크기가 고정적이다. 랜덤 접근이 가능하다. 장점 인덱스가 있어 탐색의 경우 시간 복잡도는 O(1)이다. 단점 맨 앞이나 중간에 삽입이나 삭제시 그 뒤(오른쪽)에 있는 값들을 한쪽으로 한칸씩 옮겨야 하기 때문에 시간복잡도는 O(n)이다. (삭제나 삽입시 재배열이 필요하다) 배열 생성시 크기를 정해야하며, 추후에 변경하기 힘들다 배열을 사용할 때 읽기가 빈번하게 일어나는 경우 List (리스트) 특징 메모리 상에 데이터가 비연속적으로 저장된다. 크기가 가변적이다. 장점 메모리 공간을 미리 확보할 필요가 없다. 단점 읽기 시 시간 복잡도는 O(n)이다 리스트를 사용할 때 삽입과 삭제가 빈번하게 일어날 경우 추가적.. 2023. 5. 13. [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 사용 용도 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 특징 힙(heap)을 이용한 구현 방법 루트 노드엔 우선순위가 높은 값이 들어간다. 힙에서는 항상 루트 노드를 제거한다. 힙은 완전 이진 트리 형태로 구성되어있다. import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) heap = [] for i in range(n, 0, -1): heappush(heap, i) print('-' * 15, 'heappop', '-' * 15) for i in ra.. 2023. 5. 10. [자료 구조] 자료 구조 시간 복잡도 자료 구조(data structure) 효율적으로 데이터를 관리하고, 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 자료구조 평균 시간 복잡도 자료 구조 접근 탐색 삽입 삭제 배열 (array) O(1) O(n) O(n) O(n) 스택 (stack) O(n) O(n) O(1) O(1) 큐 (queue) O(n) O(n) O(1) O(1) 이중 연결 리스트 (doublylinked list) O(n) O(n) O(1) O(1) 해시 테이블 (hash table) O(1) O(1) O(1) O(1) 이진 탐색 트리 (BST) O(log n) O(log n) O(log n) O(log n) AVL 트리 O(log n) O(log n) O(log n) O(log n) 레드 블랙 트리 O(log n) O(lo.. 2023. 3. 19. 이전 1 다음