Sevity Blog

마운트 여부 및 location 확인하기

df -h

mount하기

sudo mount 192.168.0.1:/volume1/mynas /nas/mynas

앞에가 원격nas위치, 뒤에가 local 위치

-t nfs 옵션을 주는 경우가 있는데 필요한 것인지?

nas의 io상태 확인하기

iostat -mnh

만약 설치되어 있지 않으면 sudo yum install sysstat

계정 로그인 시도 시 패스워드 불일치로 잠겼을때

1. 계정의 틀린 패스워드 입력 횟수 확인 및 마지막 시도 시간 확인

pam_tally2 -u 계정명

2. 계정 패스워드 잠김 해제

pam_tally2 -u 계정명 --reset

출처: https://siron89.tistory.com/14 [siron89]

여기보면 설명 잘 돼있다.

crontab -e 하면 내용 볼 수 있다. (에디트도 아마 가능?)

*　　　　　　*　　　　　　*　　　　　　*　　　　　　*
분(0-59)　　시간(0-23)　　일(1-31)　　월(1-12)　　　요일(0-7)

실행주기는 위처럼 되고.. 9시에서 15시까지 매시간 5분째 마다 실행하고 싶으면

5 9-15 * * * 이렇게 하면 된다.

git remote -v 하면 repository url 확인 가능

git remote set-url origin 신규url 하면 repository변경 가능(ip가 바꼈다던가 할 때)

tag관련

git tag 하면 현재 달린 tag들 확인가능

git show v1.4 하면 태그 세부 정보 확인가능

git tag -a v1.4 -m "my version 1.4"  하면 버전 달고 메시지 쓸 수 있음

git tag -a v1.4 9fceb02 -m "my version 1.4" 하면 예전 commit에 대해서도 tag달 수 있음

git push origin --tags 이렇게 명시적으로 tag를 따로 push해줘야만 서버에 반영됨에 주의

git checkout v1.4 하면 해당 tag로 체크아웃 가능(근데 detached HEAD 상태가 된다)

git reflog 하면 detached 된 상태를 로그 히스토리 형태로 볼 수 있다.

git log --graph --decorate $(git rev-list -g --all) 하면 현재 HEAD가 어딘지 graph로도 볼 수 있다.

git checkout - 하면 detached 상태에서 원래 HEAD상태로 돌아간다. (tag 체크아웃은 풀린다)

git checkout -b version14 v1.4 하면 브랜치 만들면서 체크아웃 가능 

생성

아래 명령어로 id를 생성한다. (useradd는 low level utility로 home directory 자동 생성이 안될 수 있다.근데 CentOS에서는 둘이 동일하다.)

adduser 유저id

passwd 유저id

변경

특정 그룹에 넣기(adduser로 그냥 생성하면 id와 같은 이름의 group이 생성되면서 거기 들어갔던 것 같다)

adduser -G 그룹이름 유저id

sudo권한 부여

/etc/sudoers 열어서 root 밑에 유저id 추가

삭제

userdel -r 유저id (-r옵션을 주어야 홈디렉토리까지 삭제됨에 주의, deluser라는 것도 있지만 redhat계열은 없다고 한다. 따라서 CentOS에도 없음)

groupdel 그룹이름(user생성시 같은 이름의 그룹이름이 생성되었을 수 있기 때문에 해주는 것)

조회

특정 유저id가 속한 그룹들 조회(여러 그룹에 들어가 있을 수 있다.)

groups 유저id

여기 참조했습니다.

기본개념

git branch를 아무런 옵션 없이 실행하면 (local) branch 목록을 보여준다.

git branch -r 하면 원격 branch 목록을 보여준다.

git branch -d my_branch 하면 로컬에서 해당 branch를 삭제한다.

git push origin :my_branch 하면 원격에서도 삭제한다.

근데 이렇게 해도 git branch -r에서 계속 보인다면 git fetch --all --prune 하면 갱신된다.

아래 그림 좋아서 가져옴

단, 아래 그림에서는 Index(=stage)에서 workspace로 돌리는 명령어가 checkout으로 되어 있는데,

git 2.23부터는 "git restore --staged <file>" 이런식으로 restore를 써야함

위 그림에서 index = stage

git pull과 git fetch차이

fetch는 원격 저장소의 변경 사항을 가져오지만 로컬 저장소와의 병합은 수동으로 수행해야 하며,
pull은 변경 사항을 가져오고 자동으로 병합한다.
즉 git pull = git fetch + git merge

읽기쓰기 저장소가 다른 경우가 있을수 있다.

git branch -v 해보면 fetch와 push저장소가 나오는데, 보안등의 이유로 각각 다른 설정을 사용할수도 있다.(실제 그런 경우를 본적은 없다)

$ git remote -v
origin  git@github.com:sevity/online_judge.git (fetch)
origin  git@github.com:sevity/online_judge.git (push)

git branch 전략

판정하고자 하는 n의 범위가 클 때는 아래 is_prime() 함수를 사용

bool is_prime(long long n)
{
      if (n<2) return false;

       for(long long it=2;it*it<=n;it++)
             if(n%it==0)  return false;

       return true;
}

좀 더 빠른 함수를 원하면 아래 버전도 있다. 그러나 둘다 시간복잡도는 O(sqrt(N))으로 동일하다. 경험적으로는 3배정도 상수배로 아래 함수가 위 함수보다 빠르다.

bool is_prime(ll n)
{
    // 코너케이스 검사
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // 이 부분은 아래 루프에서 가운데 5개 숫자를 건너뛸 수 있도록 하는 검사입니다
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    // 소수의 개념을 사용합니다.
    // 소수는 (6*n + 1) 또는 (6*n - 1)의 형태로 표현될 수 있으므로
    // 6의 모든 배수에 대해 검사해야 하며,
    // 소수는 항상 6의 배수보다 1 더 크거나 1 더 작습니다.
  
    /* 
       1. 여기서 i는 5 + 6K의 형태이며, 여기서 K는 0 이상입니다.
       2. i+1, i+3, i+5는 짝수 (6 + 6K)입니다. N은 짝수가 아닙니다.
       3. N%2와 N%3 검사가 이전 단계에서 완료되었기 때문입니다.
       4. 따라서 i+1, i+3, i+5는 N의 약수가 될 수 없습니다.
       5. i+4는 9 + 6K 형태로, 3의 배수입니다. 
       6. N은 3의 배수가 아니므로, i+4는 N의 약수가 될 수 없습니다.
       따라서 N이 i나 i+2의 약수인지만 확인합니다.
    */
    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

아래 밀러-라빈 소수판정법을 쓰면 n의 범위가 클 때, 위의 최적화된 코드 보다도 대략 20배정도 빠른 성능을 얻을 수 있고, 확률적 방법이긴 하지만, 실용적인 범위내에서는 다 맞는 결과를 도출한다. 시간복잡도는 O(k * log(n)^3)정도 된다.(k=3)

n<4,759,123,141일 경우 아래 코드는 정확히 동작하며 더 큰 범위에 대해서는 추가 처리가 필요하다(unsigned int를 long long등으로 바꿔주고 2,7,61 부분을 늘려줘야 한다, 참고로 unsigned int의 범위는 0부터 4,294,967,295까지로 위 범위안에 들어간다.)

bool is_prime(unsigned int n) {
	if (n < 2) return 0;
	if (n % 2 == 0) {
		if (n == 2) return 1;
		else return 0;
	}
	int s = __builtin_ctz(n - 1);
	for (unsigned long long a: {2, 7, 61}) {
		if (a >= n) continue;
		int d = (n - 1) >> s;
		unsigned long long now = 1;
		while (d != 0) {
			if (d & 1) now = (now * a) % n;
			a = (a * a) % n;
			d >>= 1;
		}
		if (now == 1) goto success;
		for (int i = 0; i < s; ++i) {
			if (now == n - 1) goto success;
			now = (now * now) % n;
		}
		return 0;
		success:;
	}
	return 1;
}

에라토스테네스의 채(sieve)

vector<bool> sieve(int max)
{
    vector<bool> p(max+1, true);
    p[0] = p[1]=false;
    for(int i=2;i*i<=max;i++)
        for(int j=2;i*j<=max;j++)
            p[i*j]=false;
    return p;
}

소인수 분해

t%i 부분에서 소수가 아니어서 문제가 될 것 같지만, 합성수의 경우 소수로 먼저 나눠떨어진 이후에 접근되어 괜찮음

소수 배열 생성기

소수로 이루어진 배열이 필요하면 위의 함수를 쓰면 된다. 예를 들어 이 문제의 답안에 쓰일 수 있다.

근데, 신기하게도, 아래처럼 먼저 체로 거르고 벡터에 담는게 두배정도 빠르다.

vector bool로 바꾸면서 또 두배 빨라짐

아래처럼 바꾸니까, 또 위에서 3배 빨라졌다 (총 12배 ㄷ)

문제는 여기 참조

브루트포스 $O(N)$

$O(\sqrt{N})$

특정 수 하나의 약수를 구하는게 아니라, 여러수의 약수를 동시에 구할때는 에라토스테네스의 채처럼 접근해야 복잡도가 훨씬 작아짐을 발견했다. 이 문제를 풀면서 발견할 수 있었고, 아래 코드는 해당 문제의 답변이기도 하다.

stl queue와 동일하게 #include <queue>를 해주고 다음처럼 코딩하면..

5,2,1 순으로 표시된다.

queue에 넣는 순서가 아니라 값 기준으로 정렬되면서 들어가는 것이다.

queue와의 API적인 차이점은 front()대신 top()이 쓰인다는 점

이렇게 되는데는 max heap과 관련이 있다.

내림차순이 아닌 오름차순으로 정렬하려면 다음처럼 queue선언을 바꿔주면 된다.

필요이상으로 복잡해진점은 그냥 그러려니 하고 넘어가자--;; C++은 이런 측면으론 결함언어이다.

만약 큐에 들어가는 값이 0보다 크다는것이 보장된다면 위처럼 복잡한 선언을 해주는대신 음수값을 넣어주는 방법도 있다.

이걸 쓸경우 queue하나에 넣고 빼는데 O(log N)으로 생각하면 된다.

즉 N루프안에 priority_queue연산을 넣어도 O(N log N)정도에 돌릴 수 있다는 이야기

O(N^2)가 안될때 고려해볼 만 하다.

관련문제 리스트

코드포스 Playlist

사용자정의 정렬함수 사용

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

bool compareJobs(const pair<int, int>& a, const pair<int, int>& b) {
    if(a.first == b.first)
        return a.second > b.second; // 요청 시각이 빠른 게 우선 (최소 힙이므로 > 사용)
    return a.first > b.first;
}

int main() {
    // decltype(&compareJobs) 를 이용하여 comparator의 타입을 지정
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        decltype(&compareJobs)
    > pq(&compareJobs);

    pq.push({10, 0});
    pq.push({5, 1});
    pq.push({15, 2});

    while (!pq.empty()) {
        auto top = pq.top();
        cout << "소요시간: " << top.first << ", 요청 시각: " << top.second << "\n";
        pq.pop();
    }
    return 0;
}

decltype을 적어줘야 하는것 빼고는 std::sort의 비교함수와 비슷한 느낌으로 쓸 수 있다.

근데 이거 2가지 치명적인 주의사항이 있네;

첫번째는, 아래 빨간색 부분을 실수하기 쉽다는거다. &안붙여도 실행은 되는데 null오류가 나고, pq뒤에 괄호를 생략하거나 &를 생략해도 마찬가지다;;

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&compareJobs)> pq(&compareJobs);

두번째는 priority_queue의 경우 desc정렬이 기본이라 기본정렬의 기호가 반대라는 것이다;;;

std::sort인 경우일때 비해서 아래 괄호 방향을 거꾸로 해줘야 한다.

bool compare2(const vector<int>& a, const vector<int>& b) {
  return a[1] > b[1]; // 오름차순을 원하는건데 괄호방향이 std비교함수와 반대임
}

LCS관련 백준문제를 참고 하자.

재귀풀이

memoize 하지 않으면 O(2^n)복잡도라 n이 20 이상일 경우 TLE 나기 쉽다.

재귀+Memoization = (Recursive DP)

위의 소스코드에 memoize만 추가해준 코드로 왠만한 문제는 이정도 선에서 푸는게 가장 쉽다.

iterative DP

for문으로 푸는 것에 관심있다면, 조금 덜 직관적일 수 있으며, 아래처럼

dp[i][j] = i,j번째 문자열까지의 lcs 로 놓고.. 테이블을 그려놓고 규칙을 발견해서 푸는게 좋다.

숫자가 증가하는 모서리 부분을 보면 dp[i][j] = 1 + dp[i-1][j-1] 규칙을 찾을 수 있고,

숫자가 증가하는 모서리가 아닌 기타 부분을 보면 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 규칙을 찾을 수 있다.