Counting sort는 정렬 알고리즘중 하나로, 키 값의 범위가 제한된 정수 일때 매우 효율적인 방법, 다른 비교 기반 정렬 알고리즘과 달리, 비교를 하지 않고 숫자의 발생 횟수를 카운트하여 정렬을 수행한다. 시간 복잡도가 O(n+k)이다. 데이터크기와 데이터 값의 범위에 비례합니다.
카운팅소트에 동작원리
1.
입력데이터값 범위를 미리 알어두어야 한다. 예를 들어 0에서 100사이의 정수만을 다룬다면, 해당범위에 맞춰 알고리즘이 동작
2.
각 데이터가 몇번씩 등장했는지 기록하는 카운트 배열을 만듭니다.
3.
카운트 배열을 통해 해당 숫자보다 작은 숫자가 몇개 있는지 계산합니다.
4.
원래 배열의 숫자를 하나씩 꺼내면서 정렬된 위치에 배치합니다.
[5, 2, 2, 1, 2]
1단계 : 정렬할 값들을 count 배열에 저장한다.
2단계 : 누적합을 구해준다.
누적합을 구하는 이유
신기하게도 정렬할 값들이 result 배열에 들어 갈수 있는 LastIndex가 결정된다.
숫자 5는 result[5 - 1]에 들어가면 된다.
숫자 2는 result[4-1]에 들어가면 된다.
숫자 1은 reulst[1-1]에 들어가면 딘다.
(index에 -1을 해주면 result[0]부터 채울수 있다.)
3단계 누적합을 이용하여 정렬 결과 저장
정렬할 값을 하나씩 탐색하면서, 제 위치에다가 값을 저장 한다.
#include <iostream>
#include <queue>
int main()
{
int arr[5] = { 5,2,2,1,2 };
int bucket[6] = { };
int result[5] = { };
//1. bucket에 arr의 값을 넣어준다.
for (size_t i = 0; i < 5; i++)
bucket[arr[i]]++;
//2. bucket의 값을 누적시킨다.
for (size_t i = 1; i < 6; i++)
bucket[i] += bucket[i - 1];
//3. result에 bucket의 값을 넣어준다.
for (size_t i = 0; i < 5; i++)
{
int index = bucket[arr[i]] - 1;
result[index] = arr[i];
bucket[arr[i]]--;
}
return 0;
}
C++
복사
unordered_map<key, value>
c++ 에서 제공하는 해시테이블 기반의 컨테이너입니다. 이 컨테이너는 키값과 데이터값 쌍으로 이루어져있다.
키를 기준으로 인덱스에 접근하기 때문에 데이터를 검색, 삽입할떄 빠른속도로 사용 할수 있다.
1.
해기 기반 : 내부적으로 해시함수를 사용해서 키를 계산하기 때문에, 평균 시간 복잡도가 삽입, 삭제, 검색 전부 O(1)이다.
2.
키의 순서 보장이 되지 않는다. 삽입되는 순서가 유지되지 않는다. 내부적으로 해시테이블에 저장되기떄문에, 순서가 무작위이다.
3.
중복되는 키값을 허용 않는다. 각 키는 고유해야 하며, 중복된 값을 사용하면 그냥 덮어 씌어진다
4.
시간복잡도 는 O(1)이다. 그치만 해시 충돌이 많아질 경우 O(n)까지도 늘어날수도 있다.
#include <iostream>
#include <unordered_map>
int main()
{
std::unordered_map<std::string, int> age_map;
// 삽입
age_map["Alice"] = 25;
//age_map.insert(std::make_pair("Bob", 30));
age_map["Bob"] = 30;
age_map["Charlie"] = 22;
// 값 접근
std::cout << "Alice's age: " << age_map["Alice"] << std::endl;
// 존재 여부 확인
if (age_map.find("Bob") != age_map.end())
{
std::cout << "Bob is in the map." << std::endl;
}
//if (age_map["Candy"] > 0)
//{
// std::cout << "Bob is in the map." << std::endl;
//}
// 삭제
age_map.erase("Charlie");
// 전체 순회
//for (std::pair<const std::string, int>& pair : age_map)
//{
// std::cout << pair.first << ": " << pair.second << std::endl;
//}
for (const auto& pair : age_map)
{
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
C++
복사
주요 함수
•
insert(): 새 키-값 쌍을 삽입합니다.
•
find(): 키를 찾아서 해당 키에 대한 이터레이터를 반환합니다. 없으면 end()를 반환합니다.
•
erase(): 주어진 키를 삭제합니다.
•
[]: 키를 통해 값을 삽입하거나, 값을 반환합니다.
unordered_map은 순서를 신경 쓰지 않고 빠르게 키를 기반으로 데이터를 조회하고자 할 때 매우 유용한 컨테이너입니다.
