본문 바로가기

백준/동적프로그래밍49

백준 1699 c++ "제곱수의 합" -PlusUltraCode- https://www.acmicpc.net/problem/1699 [필자 사고]동적 프로그래밍을 이용해 푼 문제이다.필자는 처음에 제곱수를 어떻게 표현할지 고믾이였다.2중 for문 방식을 이용하였고 첫번째 for문은 dp값을 갱신할 목적 두번째 for문은 k*k로 제곱수를 통해 dp값을 갱신할 목적으로 사용했다.처음 필자는 두번째 for문에서 k의 초기값을 1로설정 안하고 i로 설정해서 한참 애를 먹었다.아래는 코드 상세한 해설이다.[코드 해설] 2. 시간 복잡도 분석이중 반복문을 사용하므로 최악의 경우 시간 복잡도는 **O(N√N)**이 된다.바깥 반복문: i가 1부터 N까지 반복 → O(N)안쪽 반복문: k^2이 i 이하일 때까지 반복 → O(√N)따라서 최악의 경우에도 효율적인 방법으로 문제를 해결.. 2025. 2. 10.
백준 11055 c++ "가장 큰 증가하는 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11055  [필자 사고]가장 긴 부분수열을 체킹하는 방법 => 동적프로그래밍이다.필자는 이 문제를 풀기 전에 가장 긴 부분수열의 갯수를 구하는 문제를 풀었다.해당 문제와 알고리즘이 비슷하지만 그대는 갯수를 구하는거고 현재는 합을 구하는 문제이다.상세한 코드 설명은 아래에 적어 놓겠다.필자가 이 문제를 풀면서 놓친 부분은 dp를 초기화 할때 arr의 모든 idx값으로 초기화 하는게 아니라0으로 초기화 했다는 문제다.생각해보니 개개인이 가장 큰 숫자일 수 있기 때문에 dp자체를 초기화 할때 arr의 인덱스로 초기화 해야 된다는것을 알게됐다.[코드 해설]1. 입력 처리 (Input 함수)사용자로부터 정수 N을 입력받아 배열의 크기를 결정한다. 이후, .. 2025. 2. 10.
백준 1003 c++ "피보나치 함수" -PlusUltraCode- https://www.acmicpc.net/problem/1003 [필자 사고]동적 프로그래밍 bottom-up 방식으로 푼 문제이다.필자는 pair 을 이용하여 첫번째 인덱스에는 0의 갯수를 두번째 인덱스에는 1의 개숫를 bottom-up 방식으로 늘려갔다. 점화식은 아래 코드해설 부분에 설명해 놓았다.[코드 해설][소스 코드]#include #include #include using namespace std;vector> dp;void Make_DP() { dp.resize(41); dp[0] = { 1,0 }; dp[1] = { 0,1 }; dp[2] = { 1,1 }; for (int i = 3; i > N; cout > T; Make_DP(); while (T--) { Game_Start();.. 2025. 2. 9.
백준 9095 c++ "1, 2, 3 더하기" -PlusUltraCode- https://www.acmicpc.net/problem/9095[필자 사고]동적 프로그래밍을 이용하여 문제를 해결했다.처음에는 어떻게 접근할지 막막했지만 1,2,3이라는 숫자를 보고 힌트를 얻었다.dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 이라는 점화식을 새워 봤는데 실제 갯수와 일치한느 모습을 볼 수 있었다.왜 이런가 곰곰히 생각해 봤는데 dp[i-3] 입장에서는 과거의 1,2,3으로 이루어져있고 여기에 3이라는 숫자만 더 언져지만 된다.다른 두개의 dp들도 동일한 과정이다.아래는 상세한 코드해설이다. [코드 해설][소스 코드]#include #include #include using namespace std;int N;vector dp;void Make_DP() { dp[1] .. 2025. 2. 9.

티스토리툴바