N-Queen

1889 : N Queen

백트래킹을 부를때 마다 

2차원 배열이 굳이 없어도

이미 배치한 위치를 저장할 배열만 있어도 

promissing(

배치한 위치값을 저장하고 있다면 우리가 알 수 있다. -> row0부터 순서대로 내려올것이므로 column값만 저장하면된다.

 

1824 : 스도쿠

bitmasking에 배열을 왜씀... 속도를 위해선 비트 연산

 

1247. [S/W 문제해결 응용] 3일차 - 최적 경로

맨하탄 distance : 맨하탄은 계획도시이기 때문에 단순히 x, y좌표의 차로 계산할 수 있다. 별도로 주어지지 않으면 피타고라스를 이용하는것이 맞다.

 

a- b사이의 거리를 반복해서 계산해야하면, 미리 계산해서 값을 저장해 놓으면 성능향상을 이끌어 낼 수 있다.

-> memoization

 

가지치기가 없는 backtracking 은 단순한 Permutation보다 성능이 안좋다. make_candidate, process_solution함수가 계속해서 Call되기 때문이다.

+ make_candidate는 후보해들이 있는 배열을 만들기 때문이다.

이렇게 보면 backtracking은 비효율적인 알고리즘으로 보인다.

bitmasking을 포함되었는지 안포함되었는지는 bit연산자를 사용하는게 좋다.

BackTrack(int bit){

	if(bit& (1<<i)== 0){
		...
	}
}

Make_Candidate를 간단한 연산으로 대체할 수 있다면 꼭 바꾸는게 좋다.

 

1. 동일한 연산을 비트연산으로 치환할 수 있다면 꼭 비트연산으로 치환하는게 좋다.

2. 함수로 빈도수가 많이 불렀던 부분을 inline화 하면 더 성능향상을 이끌어 낼 수 있다.

3. 반복되는 연산은 memoizatio을 활용하면 성능향상을 이끌어낼 수 있다.

하지만 처음부터 모든 이 방법을 활용하지말고 기본코드를 점진적으로 성능개선작업을 하는게 맞다.