1. Hash의 기본 개념 key와 value를 이용해 특정 데이터인 value를 고유 인덱스인 key로 관리하는 자료구조입니다. 내부적으로 배열을 사용해 데이터를 저장하기 때문에 빠른 검색 속도를 가지고 있습니다. 특별한 알고리즘(Hash Function)을 이용해 데이터와 관련한 고유의 숫자를 만들어 인덱스로 활용합니다. 특정 데이터가 저장되는 인덱스는 해당 데이터의 고유한 위치이기 때문에 삽입, 삭제 시 데이터의 이동이 없습니다. 2. Hash의 구조 Hash Table을 이용해 데이터를 저장합니다. Hash Code / value 객체에 대응하는 고유의 정수값을 Hash Code라고 합니다. 데이터는 Hash Function을 거쳐 value에 저장되는데 이때 key(index) 값이 Hash C..

BST(Binary Search Tree)에서 높이를 log n으로 지향해 조금 더 균형 잡힌 트리로 만드는 기법입니다. - BST 조건을 만족하는 트리 구조 - 시간복잡도 O(log n) 1. Red-black Tree의 활용 자바 Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있습니다. Map에서 HashMap의 Separate Chaining(충돌 처리 기법 중 하나, LinkedList로 Hash 충돌을 해결하는 방법)에서 사용됩니다. (Hash 충돌 기법에 대해서 더 알아보기 -> https://junboom.tistory.com/27) 2. Red-black Tree의 조건 - 모든 root 노드와 leaf 노드는 black의 색을 가집니다. - red의 색을..

QuickSort는 주어진 array를 분할 정복하고, pivot을 설정해 pivot과 비교하며 정렬하는 방법입니다. pivot 설정은 개발자에 따라 다르게 설정할 수 있지만, 보통은 중앙값을 pivot으로 설정합니다. 분할 정복을 하기 때문에 최소, 평균 시간복잡도가 O(n*log n)이지만, pivot과 비교되는 값이 항상 조건에 충족되어 pivot을 지속해서 바꿔주어야 하는 경우(최악의 경우) O(n^2)이 됩니다. 기존의 array에서 값을 변경하기 때문에 공간복잡도는 1입니다. 자바와 벡터를 이용해 QuickSort를 구현해 보겠습니다. Java 코드 import java.util.Vector; public class QuickSort { static void quickSort(Vector v,..

합병 정렬은 주어진 array를 지속적으로 쪼개어 최소 array에서 값을 비교해 다시 합치고 정렬하는 방식으로 최소, 최대, 평균 시간 복잡도가 O(n*log n)으로 비교적 가장 빠른 정렬 방법입니다. 쪼개진 array를 정렬하여 저장하기 위한 별도의 copy array가 필요하기 때문에 공간복잡도는 n입니다. 자바와 벡터를 이용해 합병 정렬을 구현해 보겠습니다. Java 코드 package sort; import java.util.Vector; public class MergeSort { static void merge(Vector v, int s, int e, int m) { Vector ret = new Vector(); int i = s; int j = m + 1; while (i