본문 바로가기

전체 글92

BackTracking 2 1) DP 메모이제이션 - 정의 - 노드 탐색시, Dp 값을 미리 구해놓은 값이 있으면 탐색하지 않고 해당 값을 이용하여 탐색의 수를 줄인다. ○ 가지치기 차이 § ans 갱신을 하지 않고도, 노드 리턴할 수 있음. 1-1) 상향식 백트랙킹 메모이제이션 - 루트 노드에서 현재 노드까지 누적된 파라메터의 정답 값을 메모이제이션 하는 경우. § 가지치기 식으로 사용 ○ 정답갱신을 리프노드에서 하기 때문에 자식 노드들의 값을 비교할 수 없음. - 구현 방식 ○- 최적화 종류 ○ 가지치기 § 최소값 가지치기 § 정답에 가까운 답을 빨리 찾을수록 가지치기 효율 좋음. ○ 상향식 DP 메모이제이션 § 현재 함수까지 누적된 파라메터 값만 사용하여 앞으로 탐색을 할지 말지를 결정 (중간값) □ Dp[i][j] = 구하.. 2024. 6. 15.
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.

티스토리툴바