[알고리즘 C++] 위키

후이재·2020년 8월 28일
3
post-thumbnail

include

#include<iostream>  // 기본이쥬
#include<vector>    // vector

// STL
#include<algorithm> // sort등 알고리즘 라이브러리
#include<set>       // STL set
#include<stack>     // STL stack
#include<queue>     // STL queue

// header file
#include<limits.h>  // 최대, 최소값 상수 INT_MIN

//
#include <stdlib.h> 
#include <math.h>   // math(abs, sqr, pow 등)

// string
#include <string>    // 문자열
#include <ssstream>  // 문자열 입력

#include <string.h>  // memset(arr, 0, sizeof(arr))사용가능

+ using namespace std;

define

#defind abs(x) x<0 ? -x:x  // abs 함수 define

기본 제공 함수

min(a, b);   // 최솟값
max(a, b);   // 최댓값

반복문

for (auto tree : trees){}    // trees벡터든 뭐든을 tree별로 해당 구문을 반복

배열

int num[10];                 // static 자연수가 들어가야 함
int num[100][100] = {0};     // 전체 초기화
sizeof(num)/sizeof(num[0]);  // 전체 크기에서 방 한칸을 나눠주기
memset(visit, false, sizeof(visit)); // false로 초기화, string.h 헤더 필요

동적 배열

int *num = new int[length];      // 주솟값에 할당
int *num = new int[3]{1, 2, 3};  // 값 명시
_msize(num)/sizeof(*num);        // 동적할당된 메모리는 heap영역에 저장되므로

비트연산

AND(&): 둘 다 1일 경우 1
OR(|): 둘 중 하나라도 1일 경우 1
NOT(~): 1이면 0, 0이면 1
XOR(^): 같으면 0, 다르면 1
L_shift(<<): 정수일 경우 2배
R_shift(>>): 정수일 경우 1/2배

문자열

string str = "hello"; // 선언
str.size();           // 크기
str.substr(0, 3);     // 0번째 인덱스로부터 3개까지

str.find("he");       // 문자열에서 he찾기, 찾으면 인덱스, 못찾으면 string::npos
str.find("he", 3);    // 인덱스 3번부터 찾기

str.erase(i, 2);      // i에서부터 2개 지우기

// string 의 경우
transform(str.begin(), str.end(), str.begin(), ::tolower); // 대문자는 toupper

// char 의 경우
str[i] = toupper(str[i]); // 대문자로 
str[i] = tolower(str[i]); // 소문자로

#include <sstream>
stringstream ss("huijae0816 huijae");   // input을 cin에 넣은것처럼 처리
ss>> id;                                // huijae0817저장
ss>> name;                              // huijae저장

string(1, 'A' + i);     // 한 글자의 char를 string으로 바꾸는 방법

상수

** include limits.h

INT_MIN
INT_MAX

💜 사랑해요 STL

STL 벡터

** 벡터는 원하는 자료형을 넣어서 쓸 수 있는 템플릿

vector<vector<int>> v; // 그렇기 때문에 이렇게도 선언이 가능하지!
vector<vector<int>> v(6, vector<int>(3, 0)) // 이렇게 크기 초기화 가능
v[0][1];               // 이런 식으로 안쪽 vector에 접근 할 수 있다

vector<int> vec;       // 선언
vector<int> vec2(vec); // 복사 생성
vector<int> vec(20);   // 크기 지정
vector<int> vec(20, 1);// 크기 20, 1로 초기화

vec[0];                // 0번째 접근
vec.push_back(0);      // 맨 끝에 0 삽입
vec.pop_back();        // 맨 끝 원소 삭제
vec.begin();           // 시작 값
vec.end();             // 끝 값

vec.back();            // 마지막 원소 참조
vec.front();           // 첫번째 원소 참조

vec.clear();           // 모두 삭제
vec.erase(vec.begin()+k);          // k번째 삭제
vec.erase(vec.begin(), vec.end()); // iter사이 삭제
vec.empty();           // 비어있으면 true리턴

vec.size();            // 원소 개수
vec.capacity;          // 전체 할당된 공간

vec.insert(2, 3, 4);   // 2의 위치에 3개의 4를 넣기
vec.insert(vec.end(), vec2.begin(). vec2.end()); // 두개의 벡터 연결

lower_bound(vec.begin(), vec.end(), num); // algorithm 의 lower_bound사용

STL set

set<T> str_set;                 // 원하는 자료형으로 생성 가능!

set<string> str_set(v.begin(), v.end());

str_set.insert("hey");  // 반횐되는 pair에서 second값이 성공 실패 여부 
str_set.find("hello");  // 해당 element 검색, iterator 반환 (!= str_set.end()이면 찾은 것)
str_set.count("hello"); // 해당 element 개수 반환
str_set.erase(str_set.begin())  // 해당 iter 삭제

set<string>::iterator iter = str_set.begin(); 
string str = *iter.begin();   // iter != str_set.end()까지 iter++;하면 됨

STL multiset

** multiset은 insert한 원소를 자동으로 정렬해주는 기특한 container

multiset<int> ms ; 

ms.insert(9); // 추가
int count = ms.count(9);  // 9의 개수 출력

multiset<int>::iterator iter;

for(iter = ms.begin();iter != ms.end();iter++) // 순차접근
	cout<<*iter<<" ";
    
iter = ms.insert(9);   // 9가 삽입된 위치 출력
iter = ms.lower_bound(9); // 9가 있다면 9, 없다면 9보다큰 최소값
iter = ms.upper_bound(11);  // 11이 있거나 없거나 11보다큰 최소값

ms.erase(ms.begin()); // 시작 삭제
ms.erase(ms.end()-1); // 마지막 삭제

STL map

map<string, int> str_map;
str_map["key"] = 1;         // 수정, 없을경우 insert
int valut = str_map["key"]; // 가져오기

str_map.erase("key");      // 해당 키 삭제

str_map["in"]                           // 이미 있을 경우 false 반환
str_map.find("in") != str_map.end()     // 안에있는지 체크

auto iter = str_map.insert(make_pair("hi", 1));            // iterator 반환
if(iter.second != false) {}                                // second 가 value

for(iter = str_map.begin();iter != str_map.end();iter++){  // 반복문 수행
	int value = iter->second;
}

STL stack

stack<T> st(vec.begin(), vec.end()); // 원하는 자료형으로 생성 가능!

st.push();   // 원소 추가 (앞)
st.pop();    // 원소 삭제 (뒤)

st.top();    // 원소의 top 원소 반환
st.empty();  // 비어있는지여부 bool반환
st.size();   // stack 사이즈 반환

STL queue

queue<T> qu(vec.begin(), vec.end()); // 이런식으로 초기화 가능!!

qu.push(); // 원소 추가 (뒤)
qu.pop();  // 원소 삭제 (앞)

qu.front(); // 맨앞 원소 반환
qu.back();  // 맨뒤 원소 반환
qu.empty();  // 비어있는지여부 bool반환
qu.size();   // queue 사이즈 반환

priority queue

priority_queue<int, vector<int>, greater<int>> pq(vec.begin(), vec.end()); // greater<int>, less<int> // gerater이 오름차순
pq.top();                                          // top을 사용해야함
pq.empty();

pair

queue<pair<int, int>> q;
q.push(make_pair(i, j));
q.front().first;          // 첫번째 값
q.front().second;         // 두번째 값

STL algorithm

sort(시작, 종료, compare함수);        // 정렬해준다 compare함수의 반환값에 따라 정렬(quick sort)
stable_sort(시작, 종료, compare함수); // stable하게 정렬해준다(merge sort)

reverse(시작, 종료);           // 뒤집어준다. string도 가능
*max_element(시작, 종료);      // 시작~ 종료 사이의 큰 값
*min_element(시작, 종료);      // 시작~ 종료 사이의 작은 값

next_permutation(시작, 종료);  // 시작~ 종료까지에서 다음 순열 구해줌 ㅋㅋㅋㅋㅋ
unique(vec.begin(), vec.end()) // 중복되는 값을 뒤로 밀어넣어준다. 반환값은 중복값들의 첫번째 주소
erase(unique(vec.begin(), vec.end()), vec.end()) // 하면, 중복값을 모두 제거할 수 있다.

자주 쓰는 함수

int GCD(int a, int b){         // 최대공약수
    if(a == 0) return b;
    return GCD(b % a, a);
}

int LCM(int a, int b){         // 최소공배수
    return a * b / GCD(a,b);
}
int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); } // 컴팩드 버전
int lcm(int x, int y) { return x * y / gcd(x, y); }

int fibonacci(int num)        // 피보나치
{
    return num < 2 ? 1 : jumpCase(num - 2) + jumpCase(num - 1);
}

bool compare(string s1, string s2){ // 알아서 2개씩 꺼내서 비교함
    return s1 < s2;                 // 내림차순 정렬
    //return s1 > s2;               // 오름차순 정렬 // 사전식
}
bool numComp(string str1, string str2) { return num1 < num2; } // 숫자 오름차순
bool headComp(string str1, string str2) { return str1.compare(str2) < 0; } // 문자열 오름차순 // 사전식


void quad_eqn(double a, double b, double c) // 2차 방정식의 근 구하기
{
     double d, x, y;
     d=b*b-4*a*c;
     if(d>0)
     {
         x=(-b-sqrt(b*b-4*a*c))/2*a;
         y=(-b+sqrt(b*b-4*a*c))/2*a;
     }
     else if(d==0)
     {
         x=b/(-2*a);
     }
}

vector<string> strtok(string str, char delim = ' '){ // strtok
	vector<string> ret;
	int prev=0;
	for(int i=0;i<str.size();i++){
		if(str[i]==delim){
			ret.push_back(str.substr(prev,i-prev));
			prev=i+1;
		}
	}
	if(str.size()!=prev)
		ret.push_back(str.substr(prev,str.size()-prev));
	return ret;
}

출력

"124"[a];   // 문자열 에서 인덱스 a인 부분 출력 ㅎㄷ ㄷ

형변환

to_string(20);  // int string으로
'9' -'0';       // 숫자로된 char int로
stoi("1234");   // 숫자로된 string int로

자료형 크기

profile
공부를 위한 벨로그

0개의 댓글