PS/알고리즘
n sqrt n에 특수한 조건의 배낭 문제 해결하기
이 글에서 다룰 문제는 아래와 같다. 1. \(N\)개의 물건의 가치 \(v_1, v_2, ..., v_n\)이 주어진다. \(W=\sum_{i=1}^N v_i\)로 정의한다. 2. 각 물건을 선택한 여부를 \(x_1, x_2, ..., x_n\)으로 정의한다. 3. \(\sum_{i=1}^N {v_ix_i} \sim O(N)\)을 만족한다. 4. \((\sum_{i=1}^N {v_ix_i})(W - \sum_{i=1}^N {v_ix_i})\)를 최대화 해야 된다. 문제를 다시 말하자면 각 물건을 두 그룹으로 나누고, 두 그룹의 속한 물건의 합의 곱을 최대화하는 문제이다. 이 문제의 naive한 풀이는 배낭 문제처럼 \(O(NW)\)에 해결할 수 있다. 한 그룹의 합이 \(X\)가 될 수 있는 여부를 알..
인접행렬의 제곱
1. 인접 행렬의 제곱? 그래프 관련 문제를 풀 때, 그래프를 표현하는 방법은 인접 행렬과 인접리스트가 있다. 하지만 인접 행렬은 \(O(V^2)\)의 공간복잡도를 가지기 때문에 \(O(V+E)\)의 공간복잡도를 가지는 인접리스트를 많이 쓴다. 이전에 BOJ 1533 길의 개수를 풀 때 알게된 사실인데, 가중치가 없는 인접 행렬을 \(N\)제곱하면 어떤 \(U−>V\)를 \(N\)번만에 가는 경우의 수로 계산될 수 있다는 사실을 알게 되었다. 어떤 \(A, B, C\)인 정점이 주어지고, 연결관계를 나타낸 인접행렬로 이 사실을 한번 알아보자. $$\begin{pmatrix} A->A & A->B & A->C \\ B->A & B->B & B->C \\ C->A & C->B & C->C\end{pmatri..