알고리즘!/Dynamic Programming33 [C] 11659: 구간 합 구하기 4 그냥 bruteforce하게 이중 for문을 이용해서 푼다면 시간초과가 나온다. 이때 구간 합을 이용하여야 하는데 i번째까지 합을 dp[i]에 저장하였다가 합을 구해야하는 구간에 대해서 result=dp[b]-dp[a-1]; 를 통해 구하면 된다. DP라고 보기에는 애매할 수도 있으나 중복되는 부분 문제를 줄일 수 있다는 점에서 의의가 있는 것 같다. 이건 꼭 알아야한다! 구간 합을 이용하면 시간복잡도를 n^2에서 n으로 획기적으로 줄일 수 있다! #include int arr[100001]; int dp[100001]; int main(void) { int n,m; scanf("%d %d",&n,&m); for(int i=1;i 2023. 8. 21. [C] 2293: 동전 1 시간이 엄청 오래걸려서 풀었다.. 일단 맨 처음에는 재귀함수를 이용한 Top-Down 방식으로 풀려고 노력했는데 예외처리를 해줘도 지수적으로 증가하기 때문에 자꾸 시간초과가 났다. 여기서 주의해야할 점은 각각의 코인의 가치에 따라서 dp를 따로 생각해야한다는 점이다. 결국 마지막에는 하나로 모아 풀어야하지만 처음에 생각은 따로따로 해야한다는 점인데 그 결과 구현을 하자면 dp[i]+=dp[i-price[j]]; 가 된다 1. j번째 동전을 포함하지 않은 상태에서 i의 가치를 표현하기 위해서는 j-1번쨰 동전까지만을 이용하여 만들 수 있는 경우의 수를 구하면 되기 때문에 dp[i]+=dp[i]...가 된다. 2. j번째 동전을 포함한 상태라는 뜻은 결국 가치가 i-price[j]가 되는 경우의 수를 구하면.. 2023. 8. 21. [C] 1929: 소수 구하기 사실 이 문제가 Dynamic Programming로 푸는 것은 아니다. DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을 i+1번째를 구할 때 이용하는 것이다. 사실 이걸 그대로 사용하고 있지는 않다. 다만 DP에 쓰이는 방법 일부를 사용하고 있다. i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면 그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다. 즉 Bottom-up 방식으로 생각해서 구현하면 된다. #include int dp[1000001]; int main(void) { int m,n; scanf("%d %d",&m,&n); for(int i=2;i=m && i 2023. 8. 10. [C] 1003: 피보나치 함수 피보나치!!하면 바로 Dynamic Programming으로 풀어야겠다는 생각이 들어야한다! 가장 대표적이면서 기본적인 DP 문제가 피보나치랑 이항계수 관련된 문제이기 때문이다 예시와 같이 피보나치 함수를 f(n)부터 구한다면 호출의 개수가 n이 조금만 증가해도 기하급수적으로 늘어난다. 그렇기 때문에 f(0)과 f(1) 부터 배열에 저장하면서 f(n)을 구해야만 효율적으로 호출할 수 있다. 이 문제에서도 n이 1,2,3...증가할 수록 호출하는 f(0)과 f(1)의 개수가 피보나치 수열의 점화식을 따른다. 그렇기 때문에 이것을 배열에 미리 저장한 후 테스트케이스가 주어지면 불러오면 되는것이다 #include int arr[500001]; int fibo_0[41]; int fibo_1[41]; int m.. 2023. 8. 3. 이전 1 2 3 4 5 6 7 8 9 다음