알고리즘 - 프로그래밍 기법

나머지 연산

(a+b) mod m = (a mod m + b mod m) mod m

(a-b) mod m = (a mod m - b mod m) mod m

(a*b) mod m = (a mod m * b mod m) mod m

재귀적 알고리즘

부분집합 생성하기

void search(int x){
	if(k==n+1){
		//부분집합 처리
	}
	else{
		subset.push_back(k);
		search(k+1);
		subset.pop_back();
		search(k+1);
	}
}

순열 생성하기

void search(){
	if(permutation.size()==n){
		//순열처리
	}
	else{
		for(int i=1;i<=n;i++){
			if(check[i]) continue;
			check[i]=true;
			permutation.push_back(i);
			search();
			check[i]=false;
			permutation.pop_back();
		}
	}
}

퇴각검색

수정예정

비트연산

x « k 왼쪽 시프트 연산은 정수의 오른쪽에 비트 0을 k개 덧붙이는 연산이다.

x » k 오른쪽 시프트 연산은 정수의 오른쪽 비트 k개를 제거하는 연산이다.

왼쪽 시프트는 x에 2^k를 곱하는 것과 같다.

오른쪽 시프트는 x에 2^k로 나눈 후 정수로 내림 한 것과 같다.

회고

백트레킹 부분을 좀 더 보강해야하고, 비트마스킹에 대한 흐름을 이해하게 되었다. 이번 장에서는 딱히 자세하게 정리할 부분이 없기에 빠르게 넘어가도록 하겠다.