대충공부한거적어두는블로그

- 두 수의 GCD를 구해주는 GCD 함수를 정의하고 int GCD(int x, int y) { while(true) { if(x>y) { x = x%y; if(x==0) return y; } else { y = y%x; if(y==0) return x; } } } - 연속한 데이터끼리 GCD를 구한다, 반복적으로 적용하기 위해 cyclic하게 동작할 수 있는 Queue 자료형 활용 - Queue에 데이터가 한 개 남는다면 그것이 GCD 일 것. (최적화: GCD 리턴값 1이면 바로 break) queue q; // data int x1, x2, gcd; while(true) { x1 = q.front(); q.pop(); if(q.empty()) { gcd = x1; break; } x2 = q.fro..

user input 숫자인지 문자인지 - stoi(), stol(), stod() 등의 함수 에러처리로 파악한다 bool check_number(string s) { try { stoi(s); } catch (const invalid_argument& e) { // 숫자 형태 아닐 때 return false; } catch (const out_of_range& e) { // 표현 가능 범위 넘었을 때 return false; } return true; } in python? - unsigned 정수에 한해 isdigit() 함수를 사용 가능하다 ("123"은 true, "25kim6"은 false) for _ in range(m): tmp = input() if tmp.isdigit(): print(l[..

main에 최적화를 위한 두 줄 추가하고 시작하면 시간 초과 잘 안 난다 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); } 벡터 내에 특정 element 있는지 이진 탐색으로 확인하는 방법 - lower_bound를 사용해 삽입될 위치 포인터를 리턴받은다음 v.end() 아니고 해당 주소에 element 있는지 확인하면됨 sort(v.begin(), v.end()); for(int i=0; i> s; vector::iterator it = lower_bound(v.begin(), v.end(), s); if(it != v.end() && *it == s) cnt++; } python bisect...

pair 자료형 - utility 헤더 선언 필요, 그런데 및 헤더에 포함되어 있어 별도 선언 필요 x vector v; int N, x, y; cin >> N; while(N--) { cin >> x >> y; v.push_back(make_pair(x,y)); } cf) python이었으면? 배열을 원소로 가지는 배열을 생성하면 되겠지 vector 정렬 - compare 함수를 별도로 정의하여 sorting 기준 명시 - compare 함수 파라미터로 const + &(참조, Referece) 조합 사용 // 상수성, 메모리 절약 bool compare(const pair& p1, const pair& p2) { if(p1.first == p2.first) return p1.second < p2.se..

Merge Sort - 주의할 점은 (l,m-1),(m,r) 로 나누면 (k,k+1) => (k,k-1),(k,k+1) 무한루프 되므로 안 됨. (l, m) (m+1,r) 로 나누자 #include using namespace std; int N, arr[1000000], arr2[1000000]; void mergeSort(int l, int r) { if(l>=r) return; int m = (l+r)/2; // 각 chunk 정렬 mergeSort(l, m); mergeSort(m+1, r); // 두 chunk 합치기 int ptr1 = l, ptr2 = m+1, ptr = l; while(ptr1

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.