DP

[백준 9252번 'LCS 2']https://www.acmicpc.net/problem/9252 [접근 방식]LCS(Longest Common Subsequence), "최장 공통 부분 수열" 은 '대상 문자열들의  문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열'을 의미한다.위 문제의 예제1을 보면,"ACAYKP" , "CAPCAK" 이렇게 두개의 문자열의 LCS 를 구하고자 한다. "ACAYKP""CAPCAK" LCS = "ACAK" 이다.꼭 연속된 문자가 아니더라도, 순서대로 공통된 문자들의 집합의 가장 긴 사례를 구하는 것이 "최장 공통 부분 수열" 이다. LCS에 대한 자세한 설명은 https://buly.kr/7mAqbah 를 참고. 문제 해결 키워드는 "LCS"를 "DP"를 이용하여 ..

[백준 2565번 '전깃줄']https://www.acmicpc.net/problem/2565 [접근 방식]스스로 해결하지 못한 문제. 다이나믹 프로그래밍과 최장 증가 부분 수열을 사용하여 해결하는 문제이다.전기줄들을 A위치를 기준으로 오름차순 정렬한다.정렬된 전기줄들의 B위치 배열에서 최장 증가 부분 수열의 최대 길이를 구한다. 전체 전기줄 개수에서 최대 길이를 빼면, 제거해야 하는 전기줄의 개수가 도출된다. 여기서 중요 포인트는, 최장 증가 부분 수열을 다이나믹 프로그래밍을 통해 구현하는 것이다.length 배열의 정의 : length[i] 를 끝으로(포함) 하는 최장 증가 부분 수열의 길이따라서 인덱스 k의 원소를 포함하는 최장 증가 부분 수열의 길이를 DP를 이용하여 구한다.인덱스 k 원소가 가장..