동적 계획법13 최장 공통 부분 수열 (LCS, Longest Common Subsequence) 과 역추적 최장 공통 부분 수열 (LCS, Longest Common Subsequence)문제는 잘알려진 Well-Known 알고리즘으로 간단한 규칙을 통해 구할 수 있습니다. A와 B 문장에서 LCS를 구하기 위한 배열 DP[i][j]는 A의 i번째 문자열과 B의 j번째 문자열까지 최대 LCS 길이라고 정의를 하고 DP 배열을 아래와 같이 초기화 합니다. 이제 2중 포문으로 A[i]와 B[j] 하나씩 비교하면서 DP 배열을 채워줘야합니다. 만약 A[i]와 B[j]가 같은 경우 DP[i][j]를 일단 LCS 길이를 1 늘려줍니다. 만약 A[i]와 B[j]가 다르다면 LCS 길이는 이전에 구한 LCS중 가장 큰 길이로 채워집니다. 만약 TSET의 첫 T와 TEST의 마지막 T가 만나는 경우를 살펴보겠습니다. 이 경.. 2020. 8. 6. [BOJ] 백준 17367번: 공교육 도박 https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 � www.acmicpc.net 주사위를 N번을 던져서 나온 최근 3개의 값으로 상금의 기대값을 구하는 문제입니다. 앞에서 몇번을 던져서 뭐가 나오든 신경을 쓸 필요없이 최근 3개의 눈을 기반으로 던질 수 있는 경우를 고려하면 쉽게 풀 수 있습니다. 만약 최근 3개가 5 3 4의 눈이 나왔다면, 현재 상금과 한번 더 던졌을때 다음에 올 눈 1~6에서의 기대값을 계속 구해가면서 더이상 던질 수 없을때 까지 반복하면 됩니다. #in.. 2020. 7. 23. [ 0/1 Knapsack] 배낭 냅색 알고리즘 냅색 문제(Knapsack Problem)는 물건들의 무게 w와 가치 v가 주어지고 배낭의 용량 c가 주어질때 배낭에 넣은 물건들의 가치의 합이 최대 몇인지 구하는 문제입니다. 0/1 냅색은 물건을 쪼개어 담을 수 없는 문제입니다. 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에서 최대 가치의 합 dp[_w]을 구해가자! 입니다. i번째 물건의 무게와 가치를 각각 arr[i][0], arr[i][1]이.. 2020. 7. 3. [BOJ] 백준 2225번: 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0~N까지 정수 K개를 더하여 N을 만드는 경우의 수를 구하는 문제입니다. 이를 식으로 나타내면 아래와 같습니다. 각 a의 값은 0 이상이므로 중복 순열의 식으로 구할 수 있습니다. #include #include #include #include #include #include #include #include #define MOD (1000000000) using namespace std; int n, m; int ncr[401][401] = { 0, }; int main() { ios_base::sync_with_stdi.. 2020. 6. 29. 이전 1 2 3 4 다음
