본문 바로가기

CS/자료구조15

[자료구조] Singly Linked List *** 개인이 공부한 내용들을 간략하게 정리하고 참고하기 위한 포스팅입니다. 설명에 실수가 있을 수 있습니다. 지적해 주시면 정말 감사하겠습니다. *** Array의 단점 1. 고정된 길이를 가지고 있는 자료구조이기 때문에, 동적으로 resizing할 일이 생길 수 있다. 이 경우 새로운 array를 만들고 > element들을 복사하고 > 새로 생성한 array로 reference를 재설정해 줘야 하기 때문에 비효율적이다. 2. 앞 쪽 index에 새로운 값을 추가하려는 경우, 그 뒷쪽 값들을 전부 다 한 칸씩 밀어 줘야 하기 때문에 비효율적이다. 예를 들어 1, 2, 3, 4, 5가 저장된 array가 있고 0th index에 6을 저장하려는 경우, {6,1,2,3,4,5}를 만들기 위해 1,2,3,.. 2023. 7. 29.
[자료구조] 배열(Array) *** 개인이 공부한 내용들을 간략하게 정리하고 참고하기 위한 포스팅입니다. 설명에 실수가 있을 수 있습니다. 지적해 주시면 정말 감사하겠습니다. *** 정의 : 연속된 정수로 인덱싱된 같은 type의 원소들의 집합. 1. Add 1-1) sorted array : 순서를 유지하기 위해 shifting을 통해 공간을 만들어야 하므로, time complexity는 O(n)이다. 1-2) unsorted array: array의 끝에 원소를 더하면 되므로 time Complexity는 O(1)이다. 2. Remove 1-1) sorted array: shifting을 통해 삭제된 공간을 메워 줘야 하므로, time Complexity는 O(n)이다. 1-2) (삭제할 index가 주어졌다는 가정 하에) 삭.. 2023. 7. 26.
[자료구조] Map 정의) (Key, Value) 값을 저장하는 자료구조. 파이썬의 dictionary가 Map 자료구조이다. Priority Queue의 key가 연속된 수(consecutive numerics)여야 하는 것과 달리, Map은 다양한 Key를 사용할 수 있다. 구현 및 시간복잡도) 1. Unsorted DLL을 이용. - Insertion: O(1) - Deletion: O(n) - Searching: O(n) 2022. 11. 11.

티스토리툴바