반응형
1. 해시
개념
- 키(key)를 이용해 값(value)에 빠르게 접근할 수 있도록 도와주는 자료구조이다.
목적
- 주된 목적은 임의의 데이터를 "키-값" 쌍으로 저장하고, 주어진 키를 통해 빠르게 해당 값을 찾을 수 있도록 하는 것이다.
구조
- 해시 테이블은 배열(혹은 버킷)의 형태로 구성되며, 각 배열의 인덱스는 해시 함수를 통해 결정된다.
해시 함수
- 임의의 입력(키)을 고정된 크기의 정수(해시 값)로 변환하는 함수로, 이 값이 배열의 인덱스로 사용된다.
시간 복잡도 및 성능
- 평균 시간 복잡도
- 검색, 삽입, 삭제 : 보통 O(1)
- 최악의 경우
- 모든 키가 하나의 버킷에 몰리는 경우 O(n) → 좋은 해시 함수를 선택하고 적절한 해시 테이블 크기를 유지하면 이런 상황은 매우 드묾
- 로드 팩터 (Load Factor)
- 로드 팩터는 해시 테이블에 저장된 항목의 수를 전체 버킷 수로 나눈 값이다.
- 이 값이 높아지면 충돌이 증가할 가능성이 높다. 이를 관리하기 위해 일정 임계값을 넘으면 해시 테이블의 크기를 늘리고 재해싱을 진행한다.
해시 알고리즘의 응용
- 데이터베이스 인덱스 : 대용량 데이터를 빠르게 검색하기 위해 해시 인덱스를 사용한다.
- 캐시 메모리 : 자주 사용되는 데이터를 저장하고 빠르게 접근하기 위해 해시 자료구조를 활용한다.
- 집합 자료구조 : 중복된 원소를 허용하지 않고, 원소의 포함 여부를 빠르게 확인할 때 사용한다.
- 문자열 검색 : 일부 알고리즘은 해시 값을 이용해 문자열 내에서 패턴을 빠르게 찾는다.
문제 유형
- 빈도수 계산 : 배열의 값들을 키로 하여 그 등장 횟수를 값으로 저장하는 방식은 전형적인 사례
- 중복 제거와 종류의 수 세기 : 해시맵을 이용하면 중복을 쉽게 제거하고, 서로 다른 요소의 개수를 효율적으로 구할 수 있음
- 시간 복잡도 : 해시를 사용하면 각 요소에 대한 삽입, 탐색, 갱신이 평균적으로 O(1)의 시간 복잡도를 가지기 때문에, 전체 문제를 O(N) 시간에 해결할 수 있음
2. 정렬
개념
- 데이터 집합을 오름차순, 내림차순 또는 사용자 정의 기준에 따라 순서대로 배열하는 일련의 절차
- 종류
- 비교 기반 정렬 알고리즘 : 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬
- 비교를 사용하지 않는 정렬 알고리즘 : 카운팅 정렬, 기수 정렬, 버킷 정렬
목적
- 데이터 처리 효율화 : 정렬을 통해 검색, 이진 탐색, 중복 제거 등 후속 작업을 보다 효율적으로 수행할 수 있음
- 데이터 시각화 및 분석 : 정렬된 데이터를 통해 패턴, 경향 등을 쉽게 파악할 수 있으며 데이터 시각화에도 유리함
- 시스템 최적화 : 메모리 접근 패턴을 개선하거나 캐시 효율을 높이는 등 시스템 성능 최적화에 기여
시간 복잡도 및 성능
- 버블 정렬, 선택 정렬, 삽입 정렬 : O(n²)
- 병합 정렬 : O(n log n)
- 퀵 정렬 : O(n log n), 최악의 경우 O(n²)
- 힙 정렬 : O(n log n)
문제 유형
- 비교 기반 정렬 : 데이터 간의 대소 관계를 비교하여 정렬 (ex. 버블, 삽입, 선택, 퀵, 병합, 힙 정렬)
- 비교 비기반 정렬 : 데이터의 분포나 특정 키 값을 이용하여 정렬 (ex. 카운팅, 기수, 버킷)
버블 정렬
- 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법
- 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다
- 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다
- 마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 형식을 띈다
선택 정렬
- 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
- 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다
병합 정렬
- 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식
- 이 과정은 재귀적으로 구현된다
- 숫자들을 반으로 나누는 데 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는데 각각 O(n)의 시간이 걸린다
실행 시간 빠른 순서 : 병합 > 선택 > 버블
728x90
댓글