본문 바로가기

Computer Science/자료구조4

[자료구조] Array, ArrayList, LinkedList 차이 (시간복잡도, 각각 언제 써야할까?) 목차 Array ArrayList LinkedList Array, ArrayList, LinekdList 시간복잡도 Array, ArrayList, LinedList 언제 써야 할까? 1. Array 배열은 선언 시에 배열의 크기가 결정되고, 이후 변경하지 못해 고정적이다. 인덱스라는 데이터의 논리적 위치와 디스크에 저장되는 물리적 위치가 동일하며, 인덱스를 알고 있다면 빠르게 접근할 수 있다. (특징) 크기가 고정적 논리적 위치와 물리적 위치가 동일 조회 시 인덱스를 알고 있다면 O(1)의 시간복잡도를 가짐 데이터의 개수가 제한되어 있고, 조회가 빈번한 경우에 배열을 사용 (장점) 캐시에 데이터가 존재할 가능성이 큼 조회 속도가 빠름 (단점) 배열의 크기가 한정되어 있음 2. ArrayList Arra.. 2024. 4. 2.
[자료구조] 해시 테이블이란? (해시 함수, 해시 충돌과 해결 방법, 자바에서 HashMap과 HashTable) 목차 해시 테이블이란? 해시 함수 해시 충돌과 해결 방법 Seperate Chaining 방식 Open Address 방식 Resizing (테이블 크기 재할당) 자바에서 HashMap, HashTable 1. 해시테이블이란? 해시 테이블은 key-value 형태로, 각각의 key 값에 해시 함수를 적용해 배열의 인덱스를 생성하고, 인덱스에 데이터를 저장하거나 검색할 수 있는 자료구조이다. 해시 테이블은 내부적으로 배열을 이용하고 있고 key를 통해 배열의 인덱스에 접근할 수 있기 때문에, 속도가 매우 빠르다는 장점을 가지고 있다. 하지만 해시 함수에 의존하고 있기 때문에, 충돌이 일어나지 않고 빠르게 해시를 만들어내는 해시 함수의 역할이 중요하다. (특징) 삽입, 삭제, 검색 모두 평균적으로 O(1)의.. 2024. 3. 13.
[자료구조] 스택, 큐, 힙 차이 (+ 배열과 연결 리스트를 이용한 구현 차이) 목차 스택 개념과 활용 큐 개념과 활용 힙 개념과 활용 배열과 연결리스트를 이용한 구현 차이 1. 스택 스택은 LIFO 방식의 자료구조로, 나중에 들어온 원소가 가장 먼저 제거된다. 리스트의 한쪽 끝에서 삽입, 삭제가 이뤄지며, 가장 마지막으로 실행한 동작을 가져와야 할 때 사용된다. 스택에서 가장 위쪽에 있는 값을 top이라고 하며, 원소 삽입, 삭제 시에 top을 가리키는 값이 변화된다. (사용 예시) 웹사이트 방문 기록 ctrl+z 실행 취소 함수 호출 (관련 함수 - 자바) push(x) : 스택의 가장 위쪽에 x라는 원소 삽입 pop() : 스택의 가장 위쪽에 원소 삭제 peek() : 스택의 가장 위쪽에 원소 읽기 isEmpty() : 스택이 비어있으면 true, 비어있지 않으면 false 반.. 2024. 3. 6.
[자료구조] 트리 개념과 종류 (이진 탐색 트리, 트리 응용) 목차 트리란? 트리 종류 편향 트리 (Skew Tree) 이진 트리 (Binary Tree) 완전 이진 트리 (Complete Binary Tree) 포화 이진 트리 (Perfect Binary Tree) 전 이진 트리 (Full Binary Tree) 이진 탐색 트리 (Binary Search Tree, BST) 트리 응용 1. 트리란? 트리는 데이터의 계층적 구조를 노드로 표현한 자료구조이다. 가장 상위 노드를 루트 노드라고 부르며, 하나의 루트 노드를 기준으로 가지처럼 뻗어져 나가는 형태를 지닌다. (특징) 트리는 그래프의 한 종류이며, 최소 연결 트리라고도 부른다. 노드와 노드를 연결하는 간선으로 구성되며, 노드 N개인 트리는 항상 N-1개의 간선을 갖는다. 노드 사이의 경로에는 순환하는 사이클이.. 2024. 3. 1.

티스토리툴바