알고리즘
해시(Hash) 란?
1. 개념 해시 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다. 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다 → 해시 태이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있다. → 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 실행할 수 있다. 해시함수 위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수(알고리즘) 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일..
C++ 알고리즘 문제풀이하며 자주 쓰이는 라이브러리, 함수 정리
비정기적으로 업데이트 합니다. #include unique(시작 주소, 종료 주소); - 중복제거 return 값 : 중복 제거하고 난 후의 끝 주소 주의 사항 : sort후 사용해야 올바르게 수행이 가능함!! 참고 자료 응용 : erase(unique(v.begin(), v.end()) , v.end()); --> erase함수를 이용하여 중복 된 항목들을 모두 지워 줄 수가 있다. find(시작 주소, 종료 주소,값); - 값 찾기 return 값 :값이 있다면, 찾고자 하는 값의 주소 /값이 없다면, 종료 주소 주의 사항 : #include의 find()와는 다르다. 참고 자료 min_element(시작 주소, 종료 주소); / max_element(시작 주소, 종료 주소); : 최소 / 최대값 찾..
불안정 정렬 sort, 안정정력 stable_sort
안정 정렬와 불안정 정렬 지금까지 계속 sort를 써오면서 해당 값에 대해서 순서가 유지되는지 여부를 거의 신경써본적이 없었고 (순서는 당연히 유지되는줄 알았다), 동일한 값에 대해 기존의 순서가 유지되는 정렬을 해본적이 없어서 잘 몰랐는데, sort 함수를 활용한 정렬은 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있다. 아래의 이미지에 잘 나와있는데, stable 같은 경우에는 순서가 확실히 유지되는 반면, not stable 같은 경우에는 같은 값에 대해서 순서가 뒤바뀔 수 있다. C++의 sort 와 stable sort c++의 경우 algorithm 헤더에서 sort 함수와 stable_sort 함수를 둘다 지원하고 있으며, sort 함수의 경우 내부적으로 퀵 정렬로, stable_sort 함수..