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

<i,j>와 <j,i> 같을시 이 문제를 순열문제로 볼수있겠지만 한번더 생각하면 그래프문제로 풀수도 있다. 예로 동일한 원이 3개가 있는데 이를 각가 충돌처리한다고 생각해보자. 출돌체크하기위해서는 한 객체와 따른 객체를 비교를해야하는데 가지고 있는 모든 원에 대해 충돌체크하면 아래와 같은 코드가 발생한다. 하지만 이걸 배열 그래프로 표현하게 되면 아래와 같은 식이 나오게 된다. 위 그림을 보면 알겠지만 대각선을 기준으로 대칭이기 소개 더보기 <i,j> 데이터 집합일때 빠르게 조회하기[…]

2231 문제 분해합 풀이

생성자 M이 N을 만들수 있다. N이 주어질경우 M을 찾아라 하지만 주어진건 N이기때문에 이를 딱히 찾을 방도가 없다. 그렇기 때문에 이문제는 무차별 대입으로 풀어야한다. 여기서 빅오를 줄일 방법이 존재하는데 M은 N보다 작다는 점이다. 왜냐하면 M은 N의 분해합을 하기때문에 작을수가 없다. 소스는 다음과 같다.   1 2 3 4 5 6 7 8 9 10 11 12 소개 더보기 2231 문제 분해합 풀이[…]

2309 문제 일곱 난쟁이문제 풀이

깊이 우선탐색처럼보이지만 다른 방법으로도 쉽게 풀수 있다. 조합을 이용하는 것이다. 가짜를 뽑는경우의 수를보면 9c2이니 총 가지의수는 (9*8)/(2*1) 이 나오게 된다. 여기서 중요할점은 가짜를 제외하고 뽑을경우 총합이 100이 되면 가짜가 자동으로 나오게된다. 아래는 그 코드이다.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 소개 더보기 2309 문제 일곱 난쟁이문제 풀이[…]