언제 사용하나? 순위(대소)가 중요한 알고리즘에서 입력값의 개수보다 입력값의 범위가 클 때 사용. 예) 좌표의 범위는 약 40억이 넘지만 최대 입력값은 백만이다. 만약 좌표가 앞부분에 몰려있다면 나머지 부분은 불필요한 공간이라 탐색하지 않아도 된다. 좌표 압축을 통해 원하는 범위만 탐색할 수 있게 된다면 시간적,공간적으로 효율적이다. #define _CRT_SECURE_NO_WARNINGS //경고 제거 #include #include #include int main() { int N,input; std::vector x1,x2; //int 범위: -20억 ~ 20억 정도 scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &input); x1.pus..

이진 탐색으로 원소를 탐색한다. 사용 조건: 탐색을 진행할 배열 혹은 벡터는 오름차순으로 정렬된 상태여야 한다. 찾으려는 key값보다 같거나 큰 숫자가 몇 번째에서 처음 등장하는 찾기 위해 사용 algorithm 헤더파일에 있다. 반환형은 iterator이므로 몇 번째 인덱스인지 알고 싶다면 첫번째 주소를 가리키는 배열의 이름을 빼줘야 한다. int arr[6] ={1,2,3,4,5,6}; std::lower_bound(arr,arr+6,6) - arr; // 5반환 std::vector arr={1,2,3,4,5,6,}; std::lower_bound(arr.begin(),arr.end(),6)-arr.begin(); //5반환 찾으려는 key값을 초과하는 숫자가 몇 번째에서 처음 등장하는지 찾기 위해..

erase함수와 unique 함수를 사용하여 제거한다. 1. unique 함수 algorithm 헤더파일에 존재한다. 중복되는 원소들은 제거해 나가며 앞에서부터 원소들로 벡터를 구성한다. unique 함수만 사용하면 중복된 원소들이 제거되지만 뒤의 인덱스엔 기존 원소들이 그대로 있기 때문에 erase 함수와 같이 사용해야 한다. n개의 원소에 대한 unique 함수의 시간복잡도는 O(n)이다. std::v.unique(v.begin(),v.end()); 2. erase 함수 std::v.erase(v.begin()+5); //5번째 인덱스를 지우고 싶을 때 3. unique함수와 erase 함수를 같이 사용하기 std::v.erase(unique(v.begin(),v.end()), v.end()); 코테..

#define _CRT_SECURE_NO_WARNINGS //경고 제거 #include #include class person { public: int age; char name[101]; int id;//가입한 순서를 저장할 변수 (나이가 같을 때 정렬조건을 위해 필요) }; int compare(const void* arg1, const void* arg2) { person* a = (person*)arg1; //전달받은 매개변수를 저장할 객체 만들기 person* b = (person*)arg2; if (a->age > b->age) return 1; else if (a->age age) return -1; else { if (a->id > b->id) return 1; else retur..

#define _CRT_SECURE_NO_WARNINGS //경고 제거 #include #include //qsort 함수 사용 #include /*strlen(문자열의 길이 반환 함수),strcmp(문자열 비교 함수: 같다면 0반환, 다르다면 -앞에 문자열이 사전 상 뒤에 있다면 양수 반환, 뒤에 문자열이 사전 상 뒤에 있다면 음수 반환*/ int compare(const void* arg1, const void* arg2) { //오름차순으로 정렬위한 비교 함수 만들기 if (strlen((const char*)arg1) st..

2차원 배열을 여러개 생성하고 싶다면 구조체를 사용하기 typedef struct plain{ int x; int y; }; int main(){ plain* arr=new plain[5]; //구조체 5개 생성= 2차원 배열 5개 생성 ... }