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

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

알고리즘 배낭문제

가장 흔한 문제인 배낭문제는 다양한 문제 풀이법이 있습니다. 먼저 가장 쉽게 재귀로 풀어보겠습니다. 재귀는 내가 이재품을 살때와 안살때를 재귀함수로 구현해주면됩니다. 일단 간단하게 배낭크기를 10으로 잡고 5개의 물건이 있다고 보면됩니다. 간단한 코드는 위와같다. 하지만 위의 코드는 계산했음에도 불구하고 계산할려는 특징이 있어 메모리로 계산을 했는지 안했는지 추가해야합니다. 이를 가지치기라고 하는데 다음에 설명하고 메모리DP를 풀겠습니다. dp로 답을 구하는법은 소개 더보기 알고리즘 배낭문제[…]