<i,j> 데이터 집합일때 빠르게 조회하기
<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) {
}
}