목록2020/09/12 (2)
차근차근
0. 제목 백준 9251 LCS BOJ 9251 LCS 파이썬 9251 LCS Python 9251 LCS 1. 문제 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 풀이 두 문자열의 길이를 조금씩 늘려 가며 확인하여 공통 부분 수열의 최대 길이를 계산한다. 두 문자열을 X, Y라고 할 때 X[i-1] = Y[i-1] 이면 dp[i] = dp[i-1][j-1] + 1, X[i-1] != Y[i-1] 이면 dp..
0. 제목 백준 11053 가장 긴 증가하는 부분 수열 BOJ 11053 가장 긴 증가하는 부분 수열 파이썬 11053 가장 긴 증가하는 부분 수열 Python 11053 가장 긴 증가하는 부분 수열 1. 문제 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 dp[i] : i 번째 원소까지의 가장 긴 증가하는 부분 수열의 길이 가장 먼저 dp의 원소들을 1로 초기화 시켜..