데이터 집합일때 빠르게 조회하기

<i,j>와 <j,i> 같을시 이 문제를 순열문제로 볼수있겠지만 한번더 생각하면 그래프문제로 풀수도 있다.

예로 동일한 원이 3개가 있는데 이를 각가 충돌처리한다고 생각해보자.

출돌체크하기위해서는 한 객체와 따른 객체를 비교를해야하는데

가지고 있는 모든 원에 대해 충돌체크하면 아래와 같은 코드가 발생한다.

for(int i=0;i<n;++i){
	for(int j=0;i<n;++j){
			
	}
}

하지만 이걸 배열 그래프로 표현하게 되면 아래와 같은 식이 나오게 된다.

위 그림을 보면 알겠지만 대각선을 기준으로 대칭이기 때문에 대칭인것만 충돌체크를 하면 빠르게 조회할수있다.

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
		}
	}

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다