개념

시간복잡도

- 대략 1억번 계산에 1초

- 버블정렬: O(n*n)

- 선택정렬: O(n*n)

- 삽입정렬: O(n*n)

 

 

// 개념: pow(밑, 제곱승) , 헤더#include <cmath>
// 개념: abs(숫자) :절댓값 , 헤더:#include <cmath>

 

##sort 정렬

: 퀵 정렬을 구현 

sort(v.begin(), v.end());

sort(v.begin(), v.end(),compare);//사용자 정의 함수 사용

sort(v.begin(), v.end(),greater<자료형>()); //내림차순 (Descending order)

sort(v.begin(), v.end(),less<자료형>());//오름차순 (default = Ascending order)

 

## stable 정렬

// : stable_sort() : 입력된 순서를 유지하면서 정렬하는것

 

# 최댓값 구하기 max_element 

//: max_element(dp, dp + n): max_element(시작주소,끝주소) 최대값의 주소를 반환

 

 

##map

//  map<string,int> m; : 균형잡힌 이진트리 형식으로 pair<key,value> 객체로 저장 
// map 구조체 탐색 : 
// 1. key값으로 탐색 :m[clothes[i][1]] +=1;
// 2. auto 로 자동으로 pair객체 인색해서 탐색 : for(auto iter: m){iter.second};

 

 

##큐

1.큐 초기화

- 큐는 clear() 가 없어서 빈큐를 넣어야 한다.

q = queue<int>(); //빈 큐를 넣어서 큐를 초기화

 

 

#문자열

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring> // memset 헤더
#include <string>
using namespace std;
 
string s;
 
int main() {
    ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류
    cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
    
 
    //#문자열
 
    string s = "abcdefg";
 
    // 입력
    string a;
    cin >> a; // 공백 미포함 입력 
    cin.ignore(); // getchar() 와 같은 역할 , getline 입력시 엔터 미포함 되도록 사용
    getline(cin, a); // 공백포함 입력 
 
    //string.size() , string.length()
    // 문자열 길이 반환
    s.size();
    s.length();
 
    // 추가
    s = s + "abc";
    s.append("abc");
 
    //string.find()
    //string.find(문자열) : 반환값= 찾는 문자열의 시작 위치 , 없으면 string::npos 라는 제일 큰 임이의 수 반환
    // npos 는 (int)s.find(i) 로 하면 문자 없을 씨 -1 로 됨
    cout << (int)s.find('c') << '\n';
    cout << (int)s.find('abc') << '\n';
 
    // string.replace()
    // 개념: 문자열.replace(시작인덱스 idx,길이len,대입 문자열) : idx부터 idx+len까지 문자열 대입 
    // 개념: 문자열.replace(시작주소,끝주소,문자열) : 시작부터 끝직전 주소만 업데이트
    s.replace(1, 2, "ss"); cout << s << '\n';
 
    // string.erase()
    // 개념: 문자열.erase(주소) : 해당 주소만 삭제
    // 개념: 문자열.erase(시작주소, 끝주소) : 해당 주소범위 삭제
    s.erase(s.begin() + 2); cout << s << '\n';
    s.erase(s.begin(), s.end() - 3); cout << s << '\n';
 
    // string.substr()
    // s.substr(시작인덱스, 끝 인덱스); : (]해당범위 문자열 추출, 범위벗어나면 npos반환
    cout << s.substr(1, s.size()) << '\n';
 
    // toupper() tolower(), 
    // 개념: toupper(문자) 대문자로 변환, tolower(문자), 소문자로 변환
    // 헤더#include <string>
    cout << toupper(s[0]) << '\n';
    cout << tolower(s[1]) << '\n';
    return 0;
}

# 벡터 find()
// 개념: find(배열.begin(),배열.end(),찾는 값) : 찾고자 하는 것의 위치 반환,없으면 end()반환 , 헤더#include 

 

# 벡터

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // memset 헤더
using namespace std;
 
 
int main(){
    ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류
    cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
    
    vector<int> a;
    for (int i = 0; i < 10; i++) {
        a.push_back(i);
    }
    // max_element()
    // :최대 값 iterator 반환
    // 최대값의 위치와 , 최대값 구할 때 사용
    // algorithm 헤더
    cout << *max_element(a.begin(), a.end()) << '\n'; // 해당 원소 값
    cout << max_element(a.begin(), a.end())-a.begin()+1 << '\n'; // 최대 원소 iterator반환
 
    // find()
    // 찾고자 하는 값 주소 iterator 반환
    find(a.begin(), a.end(), 2); // 찾는 값 위치
    *find(a.begin(), a.end(), 2); // 찾는 값 
    return 0;
}
 
 
 
 

#완전탐색 순열

##include <algorithm> 헤더

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool cmp(const int a, const int b) {
    return a > b;
}
 
int main() {
    vector<int> v;
    int arr1[100000];
    vector<int> arr2[100000];
    int n = 100000;
 
    //sort
    //첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
    sort(arr1, arr1 + n);
    sort(arr2.begin(), arr2.end());
    //비교 함수도 만들어서 같이 넘겨줄 수 있다.
    sort(arr1, arr1 + n, cmp);
 
    //stable_sort
    //:순서를 유지하며 조건 정렬
    stable_sort(arr1, arr1 + n);
    stable_sort(arr2.begin(), arr2.end());
    //비교 함수도 만들어서 같이 넘겨줄 수 있다.
    stable_sort(arr1, arr1 + n, cmp);
 
 
 
 
    //next_permutation
    //첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
    //구간내의 원소들의 다음 순열을 생성하고 true를 리턴한다.
    //다음 순열이 없다면 false를 리턴한다.
    //구간내의 원소들은 정렬되어 있어야한다.
    int arr[10];
    for (int i = 0; i < 10; i++)
        arr[i] = i;
    do {
        for (int i = 0; i < 10; i++)
            printf("%d ", arr[i]);
        printf("\n");
    } while (next_permutaion(arr, arr + 10));
 
 
    // nth_element
    // :전체 수 중 n번째 까지만 정렬
    nth_element(v.begin(), v.begin() + 3, v.end()); // 3 번째 까지만 정렬
    nth_element(v.begin(), v.begin() + 3, v.end(),greater<int>()); // 3번째 까지 내림차순
 
 
    return 0;
}

 

#이진탐색

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // memset 헤더
#include <string>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류
    cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
    
    vector<int> a;
 
    // binary_search()
    // 이진탐색으로 찾는값의 유무 bool 반환
    int cnt = 0;
    if (binary_search(a.begin(), a.end(), 2)) { cnt++; }
    
    //lower_bound()
    //lower_bound(a.begin(), a.end(), num); 찾는 값의 시작 주소 반환 , 
    lower_bound(a.begin(), a.end(), 1);
 
    //upper_bound()
    //upper_bound(a.begin(), a.end(), num); 찾는 값의 마지막 주소 반환
    upper_bound(a.begin(), a.end(), 2);
 
    // lower_bound,upper_bound 조합
    // 찾는 숫자들의 갯수를 구할 때 정렬 후 차 구함
    sort(a.begin(), a.end());
    upper_bound(a.begin(), a.end(), 1) - lower_bound(a.begin(), a.end(), 1);
 
    return 0;
}