길이가 K인 증가하는 부분 수열의 개수를 구하는 다이나믹 프로그래밍

6506번: 엘 도라도 주어진 배열에서 길이가 K인 증가하는 부분 수열의 개수를 찾는 문제 [1,2,3,4,5,6,7]에서 [2,4,6]은 증가하는 부분 수열이지만 [4,1,2]는 부분 수열이 아니다. ----------------------------------------------------------------------------------------------------------------- dp[i][x] = i번째 원소까지 봤을때, 길이가 x인 증가하는 부분 수열의 개수라고 정의해서, O(N^3)에 가장 긴 증가하는 부분 수열의 길이를 구하듯이 구해봤는데 틀리더라고 어디선가 꼬인건지 근데 dp[i][x] = "마지막 원소가 i번째 원소이면서" 길이가 x인 증가하는 부분 수열의 개수 라고 정..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 11.
• textsms

배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수 주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다. 이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가? --------------------------------------------------------------------------------------------------------------------------------------------------------------- 어떤 수로 바꾸는가?에 대한 문제는 되지 않는다  1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다. 그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가? 주어진 배열..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 24.
• textsms

가장 긴 증가 부분수열 실제 수열을 구하는 역추적 방법

1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 26.
• textsms

다이나믹 프로그래밍 - 최장 증가 수열(LIS)을 찾는 알고리즘 배우기

1. 문제 어떤 수열이 왼쪽에서 오른쪽으로 순서대로 나열된다. 3,2,6,4,5,1.... 만약 이러한 나열된 순서를 유지하면서, 크기가 점진적으로 커지면서, 가장 긴 부분수열은 어떻게 찾을 수 있을까 이러한 부분수열은 연속적으로 고를 필요는 없다. 예를 들어 위 수열에서 3,4,5는 크기가 점점 커지는 부분수열이다. 2. 완전 검색 단순하게 완전 탐색을 수행해서 찾아낼 수도 있다 주어진 수열의 모든 부분집합을 구한다. 부분집합의 원소들이 증가하는 수열인지 검사한다. 증가하는 수열일때, 부분수열의 길이의 최댓값을 갱신한다. 당연히, 부분집합의 크기가 긴 것부터 조사하면, 처음으로 찾게되는 증가수열이 가장 긴 증가수열일 것이다. #완전탐색으로 최장증가 부분수열 찾기 s = [3,2,6,4,5,1] n = ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 20.
• textsms