HashTable이란?? (Key, Value)로 데이터를 저장하는 자료 구조 Key를 hash function에 넣으면 고유의 값이 나오게 된다. 이 고유의 값을 index로 활용해서 검색 저장하는 테이블을 HashTable이라 합니다. 이상적인 조건하에 HashTable의 장점은 검색, 삭제, 삽입 모두 O(1)이라는 점이다. (이상적인 조건은 아래에 적겠습니다.) 하지만 단점도 존재한다. - 일반적인 배열에 비해서 저장공간이 많이 필요한다. - Hash 충돌에 대한 별도의 자료구조가 필요하다. - 순차적인 값들을 정렬 혹은 값들이 필요할 때는 배열에 비해 비효율적이다. Hash 충돌 Hash 충돌이 일어나지 않는 것이 HashTable에서 가장 이상적인 상황이다. 그럼 Hash 충돌에 대해서 알아보..

O(n^2) 버블 정렬 0번가 1번 / 1번과 2번 / 3번과 4번 계속 비교하며 가장 큰 수를 우측으로 이동시킨다. 다시 0번 부터 n - 1 까지 2번째로 큰 수를 우측으로 이동시킨다. 왜 버블인가? - 원소들이 거품처럼 올라오는 것처럼 보여서 버블 정렬 선택 정렬 전체를 훑어서 가장 작은 수를 처음에 넣는다. 다시 전체를 훑어서 그 다음으로 작은 수를 그 다음에 넣는다. 마지막까지 수행해서 모든 수를 정렬한다. 왜 선택 정렬인가? - 위치를 선택해서 어울리는 수를 찾는 거라서 선택 정렬 삽입 정렬 정렬된 배열을 점차 늘려가는 방향으로 배열한다. 0 ~ k 번째까지 정렬된 배열이고 k + 1 번째 수를 정렬해야한다면 0 ~ k 사이에서 k + 1 번째 수의 위치를 찾아 삽입한다. 왜 삽입 정렬인가? ..