소근소근

백준 13711 LCS4 https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://steptoprogrammer.tistory.com/60 [백준 BOJ 17218 glod5 - 비밀번호 만들기] Longest Common String (LCS) C++ 백준 17218 https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기..

백준 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 어떤 수열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 출력하는 문제이다. dp[N] 배열을 선언하고, dp[N]에는 N번째 수를 마지막 원소를 갖는 가장 긴 증가하는 부분수열(lis)의 길이를 저장한다. O(N^2)으로 푼다. 이중 포문을 돌면서, 현재 수보다 1 작..