정렬
데이터를 순서대로 나열하는 방법
정렬 종류
- 버블 정렬
- 두 인접한 데이터의 크기를 비교해 정렬하는 방법.
- 시간 복잡도 (엔제곱)
- 선택 정렬
- 선택해서 정렬한다.
- 시간 복잡도 (엔제곱)
- 삽입 정렬
- 선택 정렬이 전체에서 최솟값을 "선택"하는 거 였다면, 삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식!
-
병합 정렬 - merge
- 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘
-
병합 정렬 - mergeSort
- 분할 정복의 개념 적용, 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
스택
한 쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조(Last In First Out)
push(data): 맨 앞에 데이터 넣기
pop(): 맨 앞에 데이터 뽑기
peek(): 맨 앞에 데이터 보기
isEmpty(): 스텍이 비어있는지 안 비어있는지 여부 반환해주기
데이터를 넣고 뽑는 걸 자주하는 자료구조!!
시간 복잡도: 오의 엔제곱
큐
한 쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺼 수 있는 선형구조(First In First Out)
순서대로 처리되어야 하는 일에 쓰인다.
enqueue(data): 맨 뒤에 데이터 추가하기
dequeue(): 맨 앞에 데이터 뽑기
peek(): 맨 앞에 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
데이터 넣고 뽑는 걸 자주하는 자료구조!!
큐는 스택과 다르게 끝과 시작의 노드를 전부 가지고 있어야 한다.
해쉬
해쉬 테이블이란?
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
👉키를 통해 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다. 키에 대해서 검색하면 바로 값을 조회할 수 있는 아주 유용한 자료구조다.
내부적으로는 배열을 사용하여 인덱스를 찾기위해 해쉬함수라는걸 이용한다.❗
해쉬함수는 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수다.
해쉬 테이블은 시간은 극대화할 수 있되 공간을 대신 사용하는 자료구조다.
