그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 접근 처음에는 LCS가 무조건 이어진 문자열 이어야 한다고 생각해서 이어진 문자열에 대한 코드를 작성했다. 악랄하게도 주어진 예제도 그렇게 이해하고 풀 수 있는 예제였다 ㅠ 예제 입력 abc abc ac 예제 출력 2 a, b가 떨어져있더라도 그냥 띄어서 개수를 셀 수 있다는 것이다.. 위와 같은 반례가 있기 때문에 다르게 다 풀고서 처음부터 다시 접근했다. 해결 기본적으로 DP로 풀어야한다는 감이 온다. (a..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 오랜만에 눈물의 AC를 받은 문제이다. LCS의 길이를 구하는 것 까지는 설명을 듣고 이해할 수 있었다. 하지만 실제 LCS를 구하는 방법에서 막혀서 시간이 걸렸다. 다음과 같은 순서로 LCS를 구하는 문제에 접근했다. 1. string2차원 배열을 만들고, DP 배열을 채울 때 string 배열도 DP가 채워짐에 따라서 똑같이 채우는 방법. 하지만..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제를 핵심만 남겨서 해석해보자면 다음과 같다. "정렬되지 않은 정수 배열이 주어질 때 연속적으로 증가하는 가장 큰 정수 배열의 길이를 구하여라" 이는 흔히 LIS (Longest Increasing Subsequence), 즉 최장 증가 부분 수열이라 불리는 문제이다. 다음과 같은 논리로 위와 같은 문제를 DP로 풀 수 있다. 먼저, DP 배열은 다음과 같이 선언한다. DP[지금 탐색 중인 상자의 번호]..