CS/자료구조

Hash 자료구조와 해시 충돌

Hash Table 이란 Hash Table은 데이터를 key-value 형식으로 보관하여 검색 · 삽입 · 삭제를 O(1) 시간 복잡도로 수행할 수 있는 자료구조이다. Hash Table은 key 값을 통해 데이터를 다루기 때문에, key 값은 고유해야한다. 이러한 고유한 key 값을 만드는 작업은 해시 함수가 담당하는데, 대표적으로는 key 값의 ASCII 값을 합하여 만드는 간단한 방법이 있다. 이러한 해시 함수가 key를 만드는 과정에서, 의도하지 않게 우연히 key 값이 일치하는 경우가 발생할 수 있는데 💡 이를 해시 충돌이라고 한다. 해시 충돌이 발생하면, key 값이 중복되어 데이터가 사라질 수 있다. 따라서 해시 충돌이 발생하면 대처해야한다. 대표적인 방법으로는 체인법 (Seperate C..

병합 정렬 (Merge Sort) 을 구현해보자

정렬을 할 수 있는 방법은 여러가지가 있다. 대표적으로 다음과 같은 방법이 있다. 💡 정렬의 종류와 방식 1. 버블 정렬 : 2개의 원소를 계속 비교해나가며 값이 큰 원소가 앞에 있는 경우 위치를 교환한다. 제일 큰 값(오름차순의 경우)을 제일 뒤로 보내어 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 만약 한번 순회했을 때 두 원소간 위치가 변한 적이 없다면 순회를 빠져나가는 방식으로 최적화를 할 수 있다. 2. 선택 정렬 : 원소들을 순회하여 가장 작은 값을 찾은 뒤(선택), 제일 앞 원소와 위치를 바꿈으로서 작은 값이 계속 앞으로 이동하면서 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 3. 삽입 정렬 : 2번째 원소부터 시작해서 N번째 원소까지 N-1까지의 ..

Linked List 구현해보기

리스트에는 연속하는 메모리 공간에 저장되어 있는 ArrayList와 각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 연결되는 LinkedList가 있다. 각 자료구조의 특징은 다음과 같다. 1️⃣ ArrayList 1. 데이터가 연속적으로 나열되어 있어, 특정 인덱스의 데이터에 접근하는 경우 O(1) 로 접근할 수 있다. 2. 선형 탐색의 경우 O(n), 정렬되어 있을 때 이분탐색의 경우 O(logN) 으로 접근할 수 있다. 3. 중간 위치에 데이터를 삽입 · 삭제 하는 경우, 나머지 원소들의 위치를 옮겨야 하기 때문에 O(N) 이다. 2️⃣ LinkedList 1. 특정 인덱스에 위치한 원소에 접근하는 경우에, 순회를 해서 찾아야 하므로 O(N) 이다. 2. 단일 연결 리스트의 경우, 시작 부분..