정현우 / 4기 1주차 / 2문제

[cookingTorch]

문제명 : 최소 편집

시간 복잡도 : O(N^2) , 공간 복잡도 : O(N)

1. 풀이 과정

- 92 ms
- DP
- dp[i][j]
- = B의 i 번째, A의 j 번째 문자까지의 prefix로 계산된 최소 편집 횟수
- dp[0][i] = i, dp[i][0] = i
- B[i] == A[j]이면
-   dp[i][j] = dp[i - 1][j - 1]
- B[i] != A[j]이면
-   dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
- dp[i]가 dp[i - 1]까지만 참조하므로 배열 두 개로 재사용

---

문제명 : 카우버거 알바생

시간 복잡도 : O(NMK) , 공간 복잡도 : O(MK)

1. 풀이 과정

- 116 ms
- Knapsack
- 용량 (M, K) 가방에
- 무게 (x, y), 가치 1인 N 가지 짐들로 만들 수 있는 최대 가치
- Knapsack 뒤에서부터 탐색 : dp 1차원 줄이기
- dp[i][j] = 용량 (i, j)에 현재까지의 짐들로 만들 수 있는 최대 가치
- dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1)

---