공지

알고리즘문제 풀면서 알게된 내용

happilee12 2017. 10. 22. 01:44
반응형


+ 알게된 내용 추가

- thisTurn이 문자 'x'또는 'o'일 경우, 그 반대의 문자를 얻고 싶을 때는 'x'+'o'-thisTurn

- int& a = b; a의 주소를 b의 주소와 같도록 만듬 a references b, a값을 바꾸면 b값도 바뀜. int& cacheRef = cache[bijection()];

- memset(target, value, sizeof(target)); sizeof함수를 이용할 것. 헤더는  <cstring

- 이항계수 구하기

const int M = 1000000100; // k의 최대 값 +1.
void calcComination(){
    memset(combination, 0, sizeof(combination));
    FOR(i, 201){
        combination[i][0] = combination[i][i] = 1;
        for(int j=1; j<i; j++)
            combination[i][j] = min(M, combination[i-1][j] + combination[i-1][j-1]);
    }
}
- binary search

- double형에서 +무한대 값 : #define INF std::numeric_limits<double>::infinity();

- 2진수 출력 bitset<32>(target)

- 소수 n번째 자리까지 출력 cout.precision(n);

- cout << fixed << setprecision(2); // 소수점 2째자리까지 출력 cout.precision(2)할 때 안되던데 이걸로는 됨

- 구조체 선언 typedef typedef vector<vector<long long>> matrix;

- long long int 선언 long long mod = 1000000007LL;

- 연산자 재정의 matrix operator * (const matrix &a, const matrix &b){

- 행렬연산 알고리즘

    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j++){
            for(int k = 0 ; k < n ; k ++){
                c[i][j] += a[i][k]*b[k][j];
            }
        }
}

- 행렬 거듭제곱 빠르게 알고리즘 O(lgN)

  

matrix ans = {{1, 0}, {0, 1}};
    while (n > 0) {
        if (n % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        n /= 2;
    }


- 비트마스크가 int범위를 넘어가도록 초기화 하는 경우  long long int full = (1LL<<n)-1;

- 비트마스크 사용시 자릿수 헷갈림 주의!! (보통 역으로 들어감)

- 비트마스크에서 1의 갯수 세기
int numOfOne(int a){ //************비스마스크에서 1의 갯수 세기
    int count = 0;
    while(a){

        count += a&1;

        a = a>>1;

    }

    return count;

}


- 두 좌표 사이의 거리 계산

#include <cmath>

double calcDist(pair<double, double> point1, pair<double, double> point2){
    double ret;
    ret = sqrt(pow(point1.first-point2.first, 2)+pow(point1.second-point2.second,2));
    return ret;
}

- optimize 함수는 범위를 줄여나가는 함수이다. decision(low) && !dicision(high)가 될 때 까지!!!!




** 벡터 관련

- 벡터 parameter 넘길 때 
int countSafe(vector<vector<int>> cmap, vector<pair<int, int>> spread) { // ******** 벡터 parameter넘길 때 & 없으면 값복사 있으면 참조

-vector<pair<int, int>> 를 특정 인덱스로 정렬 

bool compare(const pair<int, int>&i, const pair<int, int>&j) { return i.second < j.second; }

- 벡터에서 pop_front 

int pop_front(vector<int> &a){
int ret = a.front();
a.erase(a.begin());
return ret;
}

- 벡터에서 sort

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

- 벡터에서 i번째 인덱스에 삽입

a.insert(a.begin()+i, value);

- 벡터 초기화 쉽게 matrix c(n, vector<long long>(n));

c라는 메트릭스를 새로 선언하고, 안에 길이 n짜리 벡터를 넣는데 이 각각 벡터들은 또 길이 n짜리 long long 벡터 초기화 되어있음

다른예시   vector <long long> v(n,0) 벡터 v는 길이 n짜리 long long 벡터이며 각각 원소들은 0으로 초기화 되어있음.

-벡터의 중복 제거
sort(rotations.begin(), rotations.end());
rotations.erase(unique(rotations.begin(), rotations.end()), rotations.end());


- lower_bound, upper_bound

auto l = lower_bound(a.begin(), a.end(), number);

auto r = upper_bound(a.begin(), a.end(), number);


- equal_range

auto p = equal_range(a.begin(), a.end(), number);

p.second - p.first



** 큐

#include <queue> queue<int> q; // int형 queue 선언 
q.push(0); //맨 뒤에 0 
int here = q.front(); // 맨 앞의 값 가져오기 
q.pop(); // 맨 앞의 값 지우기

**multiset

#include <set>

multiset<int> s;

s.insert(x);

s.count(x)



- 보드판의 회전 : rotBoard[i][j] = board[n-j-1][i];

-ㅁㄴㅇ


반응형