dp23 [Python] 백준 2225번 : 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 항상 절차대로 접근하면 된다. DP에는 i개의 숫자로 숫자 n을 만드는 경우의 수를 저장한다. DP[0]에는 0부터 숫자를 사용할 수 있으므로 몇 개의 숫자를 쓰던 경우의 수는 1이다. 표를 통해서 이해해 보자. 2를 2개로 만드는 경우는 (0, 2), (1, 1), (2, 0) 3가지이다. 이 경우는 (0을 한 개만 사용) * (2를 한 개만 사용) + (2를 한 개만 사용) * (0를 한 개만 사용) + (1을 한 개만 사용) * (1를 한 개만 사용) 이렇게 3가지로 볼 수 있다. 숫자 .. 2022. 7. 21. [Python] 백준 2294번 : 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 💡 문제 풀이 DP 문제이다! DP 문제는 항상 3가지를 고려해준다. 1. 어떤 값을 memoization 할지 2. 어떻게 점화식을 세울지 3. 초기값을 어떤 값으로 둘지 이번 DP 배열에는 n을 만드는데 최소 동전 개수를 넣어주었다. 동전의 가치가 i 보다 크면 DP[i]와 DP[i-c] + 1을 비교해서 더 작은 값으로 최신화를 한다. 더 작은 값으로 최신화하기.. 2022. 7. 19. [Python] 백준 2293번 : 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡 문제 풀이 DP 문제이다! 역시 점화식만 고민하면 되는 문제이다. 주어진 코인을 기준으로 연산을 실행하고 이전 경우를 따지면서 계산해주면 된다. 문제를 예로 들면, 1을 기준으로 시작한다. 2는 1을 만드는 방법에서 1만 추가해준 것이다. 또, 3은 2를 만드는 방법에서 1만 추가해준 것이다. 즉, 1원이 기준일 때는 경우의 수가 변화가 없다. 1만 추가하면 되기 때문이다. 2를 기준으로 잡았을.. 2022. 7. 18. [Python] 백준 14501번 : 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 전형적인 DP 문제이다. DP 문제를 해결할 때에는 점화식이 중요하다. 이 문제는 점화식 자체는 단순하다. DP[i]는 i 번째 날에 최대 금액이다. 점화식은 일을 받았을 때, 일을 해결한 날의 DP 값과 받기 전 날 DP 값과 받은 일의 금액의 합을 비교해야 한다. 이 문제는 몇 가지 센스를 요구한다고 생각하는데 첫 번째는 DP 리스트의 크기이다. 최대 걸리는 기간은 5일이므로 DP는 n+5 크기를 가져야 한다. 두 번째는 상담 처리에 대한 것이다. n일에 3일이 걸리는 일을 시작했을 때, n+3일째에 새로운 일을 받을 .. 2022. 6. 21. [알고리즘] 배낭 채우기 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위의 문제는 대표적인 배낭 채우기 문제이다. 찾아보니 배낭 채우기 문제는 두 가지 유형으로 나뉜다고 한다. 물건(보석)을 자를 수 있을 때의 "Fractional Knapsack"과 자를 수 없을 때의 "0-1 Knapsack Problem"로 나뉜다고 한다. 자를 수 있는 경우는 보통 그리디 알고리즘으로 해결한다고 한다. 이 글에서 다루는, 그리고 보통 많이 다루는 배낭 채우기 알고리즘은 자를 수 없는 경우이다. 배낭 채우기 문제를 푸는 방법은 여러 가지가 있다. 모든 .. 2021. 11. 24. [C++] 백준 1912번 : 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 연속합을 구하는 문제이기 때문에 경우는 단순하게 2가지 경우로 나뉜다. 1. i번째 더한 값이 최대인 경우 2. i-1번째까지 더한 값보다 i번째 값이 더 큰 경우 배열 DP[i]는 i번째 연속합을 저장한다. DP[i]는 2가지 경우에 따라 DP[i-1] + arr[i]값과 arr[i]값만 비교해주면 된다. 느낀 점 처음에 DP[i]의 값에 대해서 잘못 생각해서 많이 헤매었다. i번째까지 존재하는.. 2021. 6. 25. 이전 1 2 3 4 다음
