본문 바로가기

분류 전체보기119

BackTracking 1 백트랙킹 (브루투 포스) - 모든 경우의 수를 다 탐색해 본다. 1) 그래프 그려 보기 ○ 조합 문제. § 물건들이 N개, 순서와 상관없고 물건을 뽑았을때 특정 값을 구하는 경우. □ 특정 값이란 가치의 최대, 최소, 구하는 방법의 개수 등.. § 물건을 선택하거나, 선택하지 않거나 모든 조합의 경우의 수를 전부 탐색. § 유형 1> 이진 형태 □ 복잡도 ® N □ 그래프 □ 코드.DFS(int index, int cnt) { if (cnt > M) return; // 가지치기 if (index == N) // 종료조건, 리프노드 { if (cnt == M) { // 정답갱신 } return; } DFS(index + 1, cnt + 1); // index + 1 번째 물.. 2024. 6. 15.
Dynamic Programing 4 DP 냅색 응용 • 숙달 되면 1차원 냅색으로 구현하자. (2차원 x) • DP 아이템 줄이기 (물건 중복 안되는 경우) ○ 물건과 물건의 개수가 주어질 경우, 물건을 개수 만큼 추가하여 물건 리스트를 재정의하자!!! § Ex) (물건, count) {(2,3), (3,2)} ==> (2, 2, 2, 3, 3) ==> 5개의 물건. ○ 물건 * 물건 count가 클 경우 N * M >= 1억 이상 되는 경우 § 물건 이진형태로 그룹핑 해서 물건리스트를 재구성 하자. □ 모든 수는 2진수로 만들수 있음. □ Ex) 물건, 무게 : 4, 아이템 개수 : 12 경우, 물건을 다 추가하게 되면 (4, 4, ….)  ® 만들수 있는 무게 (12개) : 4, 8, 12, 16, 20, 24, 28, 32, 36, .. 2024. 6. 15.
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.

티스토리툴바