블로그 옮겼습니다

개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..

\(2\leq{N}\leq{50}\)\(0\leq{A[i]}\leq{N-1}\)N개의 원소로 이루어진 벡터 A가 주어진다. 벡터의 값들은 0과 N-1 사이값이며 중복되지않는다.\(0\leq{K}\leq{N-2}\)인 N-1가지의 K에 대해 각각 한번씩 swap(A[K], A[K+1]) 을 해야만 한다.그렇다면 이 swap을 하는 순서에 따라서 주어진 벡터의 결과값이 달라질 것이다.그렇다면 주어진 벡터가 0,1, ..., N-2, N-1 과 같은 형태로 오름차순 정렬되도록 하는 swap 순서는 총 몇가지가 있는지를구하는 문제이다. 이 문제는 DP로 풀 수가 있다. \(dp[i][j]\,:\,[i,\,j]\) 의 구간을 오름 차순 정렬하는 방법의 수오름 차순 정렬이라는 것은 [i, j] 구간에 어떤 수들이 ..

1234memset(d,0,sizeof(d)); for (i=0;i