알고리즘) 과제4,3번(dp,dc)

 

W vs j

반복문 안에서 **W(전체 용량)**를 쓰시면 안 되고, **j(현재 루프의 임시 용량)**를 쓰셔야 합니다.

• 이유: DP 테이블은 '가방 용량이 1일 때, 2일 때, 3일 때...'를 차례대로 구해서 P[n][W]까지 가는 과정입니다. 그런데 코드 안에 W를 써버리면, 중간 과정(작은 용량일 때의 최적값)을 건너뛰고 마지막 용량만 보게 되어 엉뚱한 값이 나옵니다

 

 

① "이미 계산했는지" 확인하는 과정이 빠졌습니다.

메모이제이션의 존재 이유는 "한 번 계산한 건 다시 안 하겠다"는 것입니다. 함수 맨 윗부분에 **"이미 p2[n][W]에 값이 있으면 계산하지 말고 바로 리턴해!"**라는 코드가 있어야 합니다.

② w[n] > W일 때도 저장해야 합니다.

현재 코드에서는 아이템이 무거울 때 그냥 바로 리턴해버립니다. 이렇게 되면 나중에 똑같은 상황이 왔을 때 또 계산하게 됩니다. 이 결과도 p2[n][W]에 적어줘야 합니다.

 

 

 

 

 

p2[n-1][W]라고 배열에 직접 접근하면 그 칸이 아직 -1인 상태일 수 있어서 엉뚱한 결과가 나옵니다.

반드시 **Knapsack(n-1, W)**를 호출해야 합니다.

 

배열에 직접 접근하는 방식"은 동적 프로그래밍(반복문) 방식이고, 지금 짜고 계신 코드는 재귀(분할 정복) 방식이라서 그렇습니다

 

    // 3. 재귀적으로 계산하기
    if (w[n] > W) {
        // 현재 아이템이 너무 무거워서 못 담는 경우
        p2[n][W] = Knapsack(n - 1, W);
    } <<

 

 

 

 

p2[n][W] = ... 이렇게 바로 값을 넣으려고 하면 재귀의 장점이 사라집니다. **"이미 계산했는지 확인"**하는 절차와 **"계산 후 저장"**하는 절차가 분리되어야 합니다.

<조건문으로 

 

1. 배열은 몇 개 필요한가요?

보통 3종류의 배열이 필요합니다.

1. 입력 데이터 배열 (1차원 2개):
   • int[] w: 각 아이템의 무게 (weight)
   • int[] p: 각 아이템의 가치 (profit)
2. 결과 저장용 배열 (2차원 1개 - 메모이제이션용):
   • int[][] p2: 계산된 결과를 저장하는 표. 

 

 

 

 

1,2번 경우도 있네

 

 

 

일반적으로 메모이제이션(Memoization)을 사용할 때 저장하는 시점은 딱 한 문장으로 요약할 수 있습니다.

**"정답을 return 하기 직전"**입니다.

 

 

 

가장 쉬운 출발점은 **"문제의 질문을 그대로 배열의 값으로 만드는 것"**입니다.

• 4번 문제: "1을 만드는 최소 연산 횟수를 구하라"
  • → dp[i] = 숫자 i를 1로 만드는 최소 연산 횟수

 

 

"변하는 수(변수)"가 몇 개인가 보세요 (차원 결정)

문제가 진행되면서 상태를 결정짓는 요인이 몇 개인지 파악하면 배열의 차원이 정해집니다.

• 1차원 배열: 고려할 게 "현재 숫자" 하나뿐일 때
  • 예: 4번 문제 (현재 숫자 만 알면 됨)
  • XX
• 2차원 배열: 위치(좌표)나 두 가지 조건을 동시에 따져야 할 때
  • 예: 3번 문제 (삼각형의 '행'과 '열' 위치를 알아야 함)
  • 예: 배낭 문제 (몇 번째 물건인지 + 남은 무게)

 

 

 

 

 

 

+1 (연산 횟수 추가) 누락

findMin을 하실 때 이전 단계의 값만 가져오고 있습니다.

• 문제점: arr[i] = arr[i/2]가 아니라, arr[i] = arr[i/2] + 1이 되어야 합니다.
• 이유: arr[i/2]는 i/2를 1로 만드는 데 걸린 횟수이고, 거기서 i로 오기 위해 나누기 연산을 "한 번 더" 수행했기 때문입니다. 모든 경로에 +1이 붙어야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

왜 이전 코드에서는 초기화가 필요 없었나?

제가 드린 코드는 원본 배열인 triangle을 그대로 덮어쓰기 때문입니다.