본문 바로가기

Algorithm7

BackTracking 3 1) 문제 풀이 방법 a. 문제 정의 a. 문제 정의 1) 직원들의 키를 선택/선택X (조합)하여 만들수있는 M을 만들때, 최소 직원의 수 i. 조합/순열, 2진, 멀티플을 확인 ii. 1번 토대로 문제의 그래프를 그려 보기 b. 문제의 복잡도를 계산한다.  i. 2의N승, 3의N승….  c. 메모이제이션 고려 i. 상향식 메모이제이션 1) 루트 노드에서 현재 노드까지 누적된 파라메터의 정답 값을 메모이제이션 하는 경우. ii. 하양식 메모이제이션 1) 현재 노드에서 리프노드까지 리턴되는 값을 계산하여 여 메모이제이션 하는 경우. 1) Dp 메모이제이션 2) 비트마스킹 메모이제이션 iii. 점화식 설정 § dp[i][j] = 구하려는 값 § 함수의 파라메터를 사용하여 dp 파라메터를 결정. □ 함수의 파.. 2024. 6. 15.
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.

티스토리툴바