무한 배낭 문제 unbounded knapsack에 대한 또 다른 핵심 고찰(dp[i] = min(dp[i], dp[i-k*w[j]] + k*v[j]) = min(dp[i], dp[i-w[j]] + v[j]))

1. 무한 배낭 문제(unbounded knapsack) 일반적인 배낭 문제는 무게가 제한된 배낭에 특정 물건을 최대 가치로 담는 방법을 찾는 문제인데, 각각의 물건은 최대 하나씩만 담을 수 있다 https://deepdata.tistory.com/474 배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건deepdata.tistory.com   근데 각 물건을 무한히 담을 수 있는 경우, 그러한 문제를 unbounded knapsack 무한 배낭 문제라고 부른다  알고보니 이미 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 27.
• textsms

원형 배열에서의 다이나믹 프로그래밍 기본

https://school.programmers.co.kr/learn/courses/30/lessons/12971?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  원형으로 연결된 배열에서, i번째 원소를 선택했을때, 서로 인접한 i-1번, i+1번 원소를 선택할 수 없다. 이런 경우 n개의 원소 중 적절히 선택하여 최댓값을 구하는 문제 원형으로 연결되어 있기 때문에, 1번 원소를 선택하는 경우 2번 원소와 n번 원소를 선택할 수 없다 마찬가지로 n번 원소를 선택하는 경우 1번 원소와 n-1번 원소를 선택할 수 없다. -------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 24.
• textsms

최소 편집 거리(edit distance)를 구하는 알고리즘

1. 문제 두 문자열 S1, S2가 주어질때, 다음과 같은 3가지 연산을 임의의 횟수만큼 실행할 수 있다. 1) 임의의 위치에 원하는 문자 하나를 삽입 예: banana >>> banacna 2) 임의의 위치에 있는 문자 하나를 삭제 예: banana >>> banna 3) 임의의 위치에 있는 문자 하나를 원하는 문자로 대체 예: banana >>> canana  2. 재귀를 이용한 해법 문자열의 왼쪽이나 오른쪽 끝에서부터 한문자씩 처리한다. 왼쪽부터 처리해서, 첫번째 문자가 서로 일치하는 경우, 나머지 문자에 대해 재귀적으로 처리 첫번째 문자가 서로 일치하지 않는다면, 여기에 3가지 작업으로 삽입, 제거, 대체 작업을 수행할 수 있다. 그리고 나머지 부분에 대해 재귀적으로 계산  첫번째 문자가 일치하면..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 11.
• textsms

재귀적으로 점화식 세우는 다이나믹 프로그래밍 연습1

6096번: Bulls and Cows 총 n마리의 암소와 황소를 한줄로 세울때, 두 마리의 황소 사이에 최소 k마리의 암소가 있도록 줄을 세운다고 할 때, 그러한 방법의 수를 5000011로 나눈 나머지를 구한다. 이때 각 소는 구분할 수 없어서 서로 다르게 세워진 경우만 다른 경우의 수로 센다 n  2마리 황소 사이에 k마리 암소 세우고.. 어떻게 순열 돌리고 흠... dp[i][j]를 i마리 소 세우는데 마지막에 황소가 오는 경우가 j = 0, 아닌 경우가 j = 1인데  마지막에 황소가 온다고 하더라도 그 전 정보를 알수가 없으니 이건 흠... --------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 11. 23.
• textsms

정확히 배낭의 크기만큼 담아야하는 독특한 배낭 문제

13910번: 개업 (acmicpc.net) n그릇의 요리를 해야하는데 가지고 있는 도구 크기들이 주어질때,  주어진 도구를 사용할때는 정확히 해당 크기만큼 요리해야한다면 n그릇을 만들기 위해 최소 몇번 요리해야하는지 예를 들어 1그릇, 3그릇용 도구가 주어지면 3그릇용 도구로 2그릇을 요리하지는 않고,  1그릇용 도구만 사용하여 1그릇만 요리할 수도 있고 1그릇, 3그릇 도구를 동시에 써서 4그릇을 요리할 수도 있다 또한 4그릇을 만들어야할때, 5그릇을 만들지 않는다  배낭문제처럼 dp[i] = i그릇 요리를 만들기 위해 해야하는 최소 요리 수 0그릇 요리에는 당연히 0번이면 되니까 dp[0] = 0 i = 1,2,3,...,n에 대하여 j번째 도구를 사용할때, k = j+1,j+2,...,m-1번째 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 10. 1.
• textsms

선택한 원소의 인접한 원소는 선택할 수 없을 때 원소 합을 최대로 선택하는 방법

7265번: Herbamedžiai (acmicpc.net)  배열에서 i번째 원소를 선택하면 i-1번째, i+1번째 원소는 선택할 수 없을때, 선택할 수 있는 원소의 최대 합을 구한다면 n이 최대 10만이라 O(N)에는 해결해줘야한다 $O(N^{2})$ 아니면 못할것 같지만 놀랍게도 O(N)에 되더라고 DP[i] = i번째 원소까지 봤을때 선택한 원소들의 최대합 만약 i번째 원소를 선택하지 않는다면? dp[i] = dp[i-1]로 그대로 가져오면 된다 만약 i번째 원소를 선택한다면? i-1번째 원소는 선택할 수 없으므로, dp[i-2]에다가 i번째 원소 선택 A[i]를 더해주면 된다 dp[i] = dp[i-2] + A[i] 여기서 둘 중 더 큰 값을 고르면 된다 dp[i] = max(dp[i-1], d..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 8. 10.
• textsms