혼자서 공부하는 블로그

관련 문제: 백준 11051번 - 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 C(N, K)를 10007로 나눈 나머지를 구한다. 풀이: DP(N, K) = 이항 계수 C(N, K) 이 경우 DP(N, K) = DP(N-1, K-1) + DP(N-1, K) 해설: 1) "DP(N, K) = DP(N-1, K-1) + DP(N-1, K)"의 의미 기본적인 이항 계수의 성질 중 하나인 C(n, r) = C(n-1, r-1) + C(n-1, r)을 DP로 바꿔 쓴 것이다. 사실 이 성질을 몰..

관련 문제: 백준 9251번 - LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 주어진 두 수열의 공통 부분 수열 중 가장 긴 것을 찾는다. 예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK이다. 풀이: DP(i, j) = 수열 1의 앞에서부터 i개 원소들로 이루어진 부분수열과 수열 2의 앞에서부터 j개 원소들로 이루어진 부분수열 간의 LCS 길이 이 경우 DP(i, j) = { DP(..

관련 문제: 백준 11053번 - 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 주어진 수열에서 가장 긴 증가하는 부분수열을 찾는 것이다. 예를 들어 {10, 20, 10, 30, 20, 50}의 LIS는 {10, 20, 30, 50}이다. 풀이: DP(i) = i번째 원소를 반드시 맨 끝에 포함할 때 LIS의 길이 이 경우 DP(i) ..

관련 문제: 백준 12865번 - 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 물건의 무게(W)와 가치(V)가 주어질 때, 정해진 무게 안으로 물건을 택하면서 얻을 수 있는 최대 가치를 구하는 것이다. 풀이: DP(i, W) = i번째 물건까지 있고 무게 제한이 W일 때의 최대 가치 이 경우 DP(i, W) = { DP(i-1, W) (if Wi > W) max[..