🍑동적 프로그래밍 동적 프로그래밍은 Dynamic Programming 즉, DP라고 불리는 알고리즘 기법이다. 복잡한 문제를 점화식으로 만들어 분할 정복할 때, 반복문 또는 재귀를 사용할 수 있는데 이 과정에서 계산의 결과 값을 저장해두어 중복되는 계산을 하지 않도록 만들어준다. 이는 점화식 이렇게 결과 값을 저장해두는 것을 메모이제이션이라고 하는데, 보통 배열의 형태로 수행된다. DP 과정 전체 문제를 부분 문제로 단순화한다. 1번의 과정에서 점화식을 도출한다. 점화식을 이용하여 배열로 간단히 해결할 수 있는지 생각한다. bottom-up top-down 없다면 재귀함수를 만들고 메모이제이션한다. 메모이제이션 방식은 보통 배열이다. 전체 문제를 해결한다. 대표 문제 피보나치 수열 구하기 피보나치 수열..

합친 LIS https://www.algospot.com/judge/problem/read/JLIS 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. 두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '..

https://www.algospot.com/judge/problem/read/LIS 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라. 어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C..