CS 공부/알고리즘
해시(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 함수..
Greedy Algorithm (그리디 알고리즘, 탐욕법) 개념 정리 & 문제 추천
앞으로 코딩테스트를 준비하며 공부하는 알고리즘 유형에 대해서 정리를 해보고, 관련된 문제들을 정리해보려고 한다. 1. 그리디 알고리즘이란? 그리디 알고리즘이란 말그대로 Greedy(탐욕)이라는 이름 그대로 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 일반적인 그리디 알고리즘은 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. → 그리디 알고리즘의 해법은 정당성 분석, 최적의 해를 구할 수 있는지 검토하는 것이 중요하다. 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만, 코딩테스트는 그리디 알고리즘을 활용해서 만들어질 수 있도록 문제를 출제하므로 OK 인것. 2. 그리디 알고리즘 예시 (이코테 내용 정리) 가장 대표적인 예..