Algorithm7 Dynamic Programing 3 냅색 DP 푸는 방식 1) 냅색 문제 확인 a. (0/1 문제) 더 이상 쪼갤수 없는 N개의 물건들을 조합을 해서, 특정 수 M값을 만들었을때, 선택된 물건들의 값을 구하여라. i. 물건들의 값 : 최대가치, 최소가치, 개수, 만들수 있는 수인지 아닌지( 1 or 0 ) ii. 만들려는 수 : 총 가방의 무게, 확인하고 싶은 구슬의 무게, Limits iii. 0/1 문제 - 선택하거나 선택하지 않거나 문제 - 선택하는 것들을 여러가지 경우로 나눌수 있으면 조건에 따라 Dp Update 복수개. □ 조건에 따라 적재되는 예제들..- 선택하는 것들을 여러가지 경우로 쪼갤수 없으면 dp 파라메터로 추가.b. 물건을 쪼갤수 없고, 가방에 넣을 수 있으면 냅색. i. 물건을 쪼갤수 있거나, 하나만 들어갈수.. 2024. 6. 15. Dynamic Programing 2 유형 3) 값을 만들수 있는지 없는지, 개수 구하기 문제 1) 1학년 https://www.acmicpc.net/problem/55571. 복잡도 확인하기 - N * M 2. DP 문제유형 - 특정한 경우 경우의 개수 구하기 3. 부분문제 정의하기 - V[i] = 숫자들. - Dp[i][j] = i번째 수까지 고려하고, j 수를 만드는 개수. - 하양식 • 이전 DP 값. ○ i 번째 수를 더하는 경우, 이전 dp § dp[i-1][j - v[i]] ○ I 번째 수를 빼는 경우 dp 값, 이전 dp § dp[i-1][j + v[i]] • 연산 ○ += 4. DP 설계 D[0][v[0]] = 1; for (int i=1; i for (int j=0; j if (.. 2024. 6. 15. Dynamic Programing 1 문제의 예제와 풀이방법은 문어박사 youtube를 참조해서 작성함. DP 문제 풀이 순서 1) 복잡도 확인하기 1-1) DP 메모이제이션 - N - 복잡도 계산하는 방법은 조건 마다 다르다. § 이진(2의N승), 삼진(3의N승), 사진(4의N승) - 복잡도를 계산하면 엄청 크지만, 중복이 그만큼 많이 되는 경우 가능. 1-2) 일반 DP - N(아이템 개수) * M(조건 크기) 1-3) 냅색DP - 최대 N = 10만, M = 100 - N이 큰 경우는 알고리즘을 통해 줄이자. • 복잡도 종류 - 메모리 : N * M bytes - 중첩 For 문 : N * M 2) DP 유형 판별하자. - 풀어본 유형은 바로 점화식을 세울수 있음. 2-1) 이전 or 이후 dp값을 참조하여 값을 계산하는 경우. ○ .. 2024. 6. 15. 이전 1 2 다음
