알고리즘 문제 풀이 공부 _ 1

알고리즘 공부하는데 뭔가 아리까리한 것들을 작성해본다.

쉽게 까먹고 그리고 유용한 함수들도 작성한다.

 

그리고 좀 문제도 좀 적고 길어지면 2편이나 3편을 돌아와야지 ㅎ

 

 

아스키 코드

첫번째 라인이 넘버.

마지막 빨간색이 가르키는 단

 

소,대 문자 

아스키 코드를 활용해서 +32 로 할수 있지만 함수로 바로 할 수 있다.

tolower, toupper

    char str = tolower('A');
    cout << str; // a

 

 

소수 알고리즘

N의 소수를 구하려면 N의 절반값까지 다 나눠서 나머지가 0인 애들만 모아서 계산해야 하는데, 이러면 시간복잡도가 O(N/2)으로 숫자가 커질수록 복잡해질 수 있다.

그래서 약수를 구할때 규칙이 있고, 이 규칙은 N의 제곱근을 중심으로 좌측에 있는 수들은 우측에 있는 수와 짝을 이룬다는 규칙이다.

자세한건 다른 블로그 찾아보고 ㅋㅋㅋ

bool CheckPrime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) { //i가 n의 약수라면 소수가 아니므로 false return
			return false;
		}
	}
	//2 ~ n-1까지 약수가 없다면 소수이므로, true return
	return true;
}

 

 

DFS (이진트리 깊이우선 탐색)

int n, ch[100];
void DFS(int L){
	int i;
	if(탈출 조건){
		...
	}
	else{
		ch[L]=1;
		DFS(L+1);
		ch[L]=0;
	}
}

 

 

BFS (이진트리 넓이 우선 탐색)

int ch[10001], d[3]={1, -1, 5};


	Q.push(s);
	while(!Q.empty()){
		x=Q.front();
		Q.pop();
        ... 조건 수행
	}