백준/동적프로그래밍49 백준 2225 c++ "합분해" -PlusUltraCode- https://www.acmicpc.net/problem/2225 [필자 사고]동적프로그래밍 문제이다.이 문제를 해결하기 위해서는 일단 해봐야 된다.종이를 가져와서 N= 1 일때 K=1일때 갯수 N , K (1, 2) 일때 갯수 ----계속 해 나아가면 규칙성을 발견할 수 있다.dp[i][k] = dp[i-1][k] + dp[i][k-1] 의 점화식을 세울 수 있다. 역시 동적프로그래밍 문제는 직접 종이들고 경우의수를 만들어야 한다는걸 느낀 문제이다. 이래는 자세한 해설이다.[코드 해설]1. 입력 처리 (Input 함수)Input() 함수는 사용자로부터 두 개의 정수 NNN과 KKK를 입력받고, 이를 바탕으로 2차원 dp 벡터를 초기화하는 역할을 한다.dp 벡터는 크기가 (N+1)×(K+1)(N+1) \.. 2025. 2. 26. 백준 2294 c++ "동전 2" -PlusUltraCode- https://www.acmicpc.net/problem/2294 [필자 사고]필자는 처음에 이 문제를 접근할 때 2차원 DP를 생각했었다.dp[i][n] 이라고 할 때 값어치 n은 동전의 값을 정했었다. 문제를 해결하지 못하였고 다른 분들의 코드를 참고할 결과 1차원 DP를 이용하여 풀 수 있었다.coin을 이용하여 현재 idx - coin 의 dp값이 0이 아니면 min으로 최소값비교한느 형식으로 문제를 풀 수있었다.이 문제를 풀면서 느낀점은 DP문제는 직접 처은 경우의 수를 직접 세어서 점화식을 찾아야 될거 같다.[코드 해설]1. 입력 처리 (Input 함수)Input() 함수는 사용자로부터 동전의 개수 NNN과 목표 금액 KKK를 입력받고, 이를 바탕으로 필요한 벡터를 초기화하는 역할을 한다.co.. 2025. 2. 26. 백준 15990 c++ "1, 2, 3 더하기 5" -PlusUltraCode- https://www.acmicpc.net/problem/15990 [필자 사고]동적 프로그래밍 문제이다. 처음 이 문제를 봤을 때 당황했던 점은 연속된 수는 불가능 하다는 점이다.연속된 숫자가 가능하면 동적프로그래밍 계단 문제와 비슷한 알고리즘으로 풀 수 있는데 아쉬웠다.그런 다음 생각한 사고 방식이 이전에 사용한 숫자를 기록할 수단이 필요 했다는 점이다.그래서 필자는 2차원 방식을 생각을 했고 DP[N][3] 식으로 1,2,3을 닮을 공간을 마련해줬다.그런 다음 점화식은 dp[i][1] = dp[i-1][2] + dp[i-1][3] 형태로 구현했다. 현재 1이라는 숫자를 넣을거니깐 i-1칸으로 간뒤 이전값이 2와 3인 dp들의 값을 더하는 방식이다.위와 같은방법을 1,2,3을 반복하면 해당 문제를 .. 2025. 2. 21. 백준 12852 c++ "1로 만들기 2" -PlusUltraCode- https://www.acmicpc.net/problem/12852 [필자 사고]그래프 탐색으로도 풀 수있지만 필자는 동적프로그래밍을 이용하여 풀었다.이 문제를 풀면서 오랜만에 부모추적 알고리즘을 사용했다.매번 최소화 되는 지점마다 이전 idx의 위치를 현재 idx에 기록을 하게 되면 나중에 부모추적을 할 수 있게 된다. 또한 top-down 보단 bottom-up을 하는게 문제를 푸는게 훨씬 수월함을 느꼈다. [코드 해설]2. 유효한 숫자 검사 (isInside 함수)isInside(num) 함수는 num 값이 N 이하인지 확인한다.num ≤ N 이면 true 반환그렇지 않으면 false 반환이 검사는 N을 초과하는 연산을 방지하는 역할을 한다.3. 최소 연산 횟수 및 부모 노드 업데이트 (findMi.. 2025. 2. 17. 이전 1 2 3 4 5 6 7 8 ··· 13 다음
