길이가 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

크기가 1씩 증가하는 가장 긴 증가하는 부분수열의 길이를 구하는 다이나믹 프로그래밍

15966번: 군계일학 주어진 배열에서 ai = a1 + (i-1)을 만족하는 부분 수열 a의 길이의 최댓값을 구하는 문제 -------------------------------------------------------------------------------------------------------------------------------------------------- 그런데 가장 긴 증가하는 부분 수열을 찾는거니까 O(N^2)인가? 근데 N이 10만인데? 그러면 O(N)에 찾을 수 있다는건가? 한참 고민했다.. 갑자기 번뜩이는?아이디어가 떠올랐다 먼저 핵심은 ai = a1 + (i-1)을 만족하는 수열은 무엇을 의미하는가? a1 = 1이면 a2 = 2, a3 = 3,.... a1 = 2이..

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

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

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

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