LeetCode/NeetCode
[DP: 0 / 1 Knapsack] 474. Ones and Zeroes ★★★★★
hyunkookim
2025. 4. 13. 05:56
strs 셋들 중에.. 0이 m 개수, 1이 n 개 가지는 substr 셋의 최대 개수를 return하라는 거 같은데 맞아?
응, 정확히 이해했어! 문제 요약해 줄게:
🔍 문제 요약:
- strs는 0과 1로 구성된 문자열 리스트야.
- 각 문자열을 하나의 "아이템"처럼 생각하고, 이들 중에서 몇 개를 선택할지 결정해야 해.
- 단, 선택된 문자열들 속에 포함된 0의 총 합(개수)이 m 이하여야 하고, 1의 총 합(개수)이 n 이하여야 해.
- 그런 조건을 만족하는 부분집합의 최대 크기(문자열 개수)를 구하는 문제야.
예시로 다시 보면:
python
복사편집
strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
- "10" → 0이 1개, 1이 1개
- "0001" → 0이 3개, 1이 1개
- "111001" → 0이 2개, 1이 4개 ← ✖ (1이 너무 많음)
- "1" → 1이 1개
- "0" → 0이 1개
- 예를 들어 "10", "0001", "1", "0"를 고르면:
- 총 0의 개수: 1 + 3 + 0 + 1 = 5 (OK)
- 총 1의 개수: 1 + 1 + 1 + 0 = 3 (OK) → ✅ 조건 만족, 4개 선택함
✅ 핵심:
- 제한된 수(m개의 0, n개의 1) 안에서
- 최대한 많은 문자열을 골라야 함
💡 접근 방식:
- 3차원 배낭 문제 (3D Knapsack Problem) 이라고 생각하면 쉬워.
- 문자열을 하나씩 선택할지 말지를 결정하면서,
- 현재까지 사용한 0과 1의 수를 관리하는 방식이야.
✅ dp[i][j] 정의 (정확한 표현)
dp[i][j] 는
"i개의 0, j개의 1을 사용할 수 있을 때,
strs 리스트 안에서 선택할 수 있는 문자열 부분집합의 최대 개수" 를 의미한다.
✅ Bottom-up DP
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# dp[i][j]는 i개의 0과 j개의 1을 사용해서 선택할 수 있는 strs의 부분집합의 최대 문자열 개수
dp = [[0] * (n + 1) for _ in range(m + 1)]
# strs에 있는 각 문자열 s에 대해서 처리
for s in strs:
zeros = s.count('0') # 문자열 s에서 0의 개수
ones = s.count('1') # 문자열 s에서 1의 개수
# 뒤에서부터 순회하는 이유:
# 이전 상태의 dp 값을 덮어쓰지 않기 위해 (0-1 Knapsack 방식)
for i in range(m, zeros - 1, -1): # 0을 최대 m개까지 사용할 수 있음
for j in range(n, ones - 1, -1): # 1을 최대 n개까지 사용할 수 있음
# 현재 문자열 s를 선택하지 않는 경우: dp[i][j]
# 현재 문자열 s를 선택하는 경우: dp[i - zeros][j - ones] + 1
# 이때, +1 은 현재 문자열 선택
# 현재 문자열에 0이 zeros 개, 1이 ones 개 있으므로,
# 그전에, 0이 i - zeros개, 1이 j - ones개로 구성된 부분집합의 최대 개수인
# dp[i - zeros][j - ones] 와 더해줘야 함
# 두 가지 중 더 큰 값을 선택해서 dp[i][j]에 저장
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
# 최종적으로 m개의 0, n개의 1을 사용해서 선택 가능한 부분집합의 최대 문자열 개수를 반환
return dp[m][n]
🧠 핵심 요약 (정리용)
개념 | 의미 |
dp[i][j] | i개의 0, j개의 1을 사용해서 만들 수 있는 부분집합의 최대 크기 (strs 안의 문자열 개수 기준) |
dp[i - zeros][j - ones] + 1 | 지금 문자열 s를 추가해서 만드는 새로운 부분집합의 크기 |
max(dp[i][j], ...) | 선택했을 때와 안 했을 때 중 더 좋은 선택을 반영 |
✅ 먼저 핵심만 요약하면:
dp[m][n]부터 순회하면서 덮어쓰는 이유는,
기존 상태(이 문자열을 포함하지 않은 상태)를 유지하면서,
새로운 상태(이 문자열을 포함한 상태)를 계산하기 위함이야.
🧠 깊이 있는 설명:
상황 예시:
strs = ["10"]
s = "10" → zeros = 1, ones = 1
m = 5, n = 3
dp[i][j] 업데이트식:
for i in range(m, zeros - 1, -1):
for j in range(n, ones - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
예를 들어 i=5, j=3일 때:
dp[5][3] = max(dp[5][3], dp[4][2] + 1)
👉 dp[4][2]는 지금 문자열 "10"이 아직 반영되지 않은 상태의 값이야.
그래서 "10"을 한 번만 반영해서 +1 해주는 거지.
🔁 반대로 앞에서부터 순회하면 어떤 문제가?
만약 아래처럼 i=0부터 시작하면:
for i in range(zeros, m + 1):
for j in range(ones, n + 1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
dp[i - zeros][j - ones]가 이미 "10"을 반영한 상태일 수 있어.
→ 그럼 같은 문자열을 여러 번 중복 선택한 것처럼 돼버림!
이건 0-1 Knapsack (각 아이템 1번만 사용 가능) 문제에서 절대 하면 안 되는 실수야.
📌 결론
- dp[m][n]이 제일 먼저 순회되지만,
그때 사용하는 값 dp[m - zeros][n - ones]는 아직 이전 상태이므로 안전해. - 뒤에서부터 순회하니까 한 문자열이 여러 번 반영되는 걸 방지할 수 있어.
✅Bottom-up DP: defaultdict(int)를 사용해서 공간을 더 유연하게 관리
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# dp[(z, o)]는 0을 z개, 1을 o개 사용해서 만들 수 있는 부분집합의 최대 문자열 개수
from collections import defaultdict
dp = defaultdict(int)
# 각 문자열 s를 순회
for s in strs:
mCnt, nCnt = s.count("0"), s.count("1") # 현재 문자열의 0과 1 개수
# 이중 for문은 뒤에서부터 순회함 → 동일 문자열 중복 선택을 막기 위해 (0-1 knapsack 패턴)
for z in range(m, mCnt - 1, -1): # 남은 0의 개수 z: m부터 mCnt까지
for o in range(n, nCnt - 1, -1): # 남은 1의 개수 o: n부터 nCnt까지
# 현재 문자열을 선택하지 않은 상태: dp[(z, o)]
# 현재 문자열을 선택한 상태: 1 + dp[(z - mCnt, o - nCnt)]
# 두 경우 중 더 큰 값을 선택해서 갱신
dp[(z, o)] = max(1 + dp[(z - mCnt, o - nCnt)], dp[(z, o)])
# 최종적으로 0을 m개, 1을 n개까지 써서 만들 수 있는 최대 부분집합의 크기
return dp[(m, n)]
🔍 이 코드의 장점:
특징설명
defaultdict(int) | 초기값이 0이라서 dp 테이블 선언이 간단해짐 |
뒤에서부터 순회 | 같은 문자열을 여러 번 선택하지 않게 보장 |
더 간결한 코드 | 2차원 배열보다 메모리를 덜 사용할 수도 있음 |
🧠 핵심 동작 방식
- dp[(z, o)]: 0을 z개, 1을 o개 썼을 때 선택 가능한 최대 문자열 수
- dp[(z - mCnt, o - nCnt)]: 현재 문자열을 선택하기 전에 가능한 상태
- +1: 현재 문자열도 선택하므로 1 증가
✅ Top-down DFS + Memoization 방식
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# 메모이제이션을 위한 딕셔너리 선언 (중복 계산 방지용)
# key: (현재 인덱스, 남은 0 개수, 남은 1 개수)
# value: 해당 상태에서 만들 수 있는 최대 문자열 개수
dp = {}
# dfs(i, m, n): strs[i:] 범위에서
# 0은 m개, 1은 n개까지 사용 가능할 때 선택할 수 있는 최대 문자열 개수를 반환
def dfs(i, m, n):
# 종료 조건: 모든 문자열을 다 봤으면 더 이상 선택할 수 없으므로 0 반환
if i == len(strs):
return 0
# 이미 계산한 상태라면 캐시된 값을 바로 반환
if (i, m, n) in dp:
return dp[(i, m, n)]
# 현재 문자열에서 0과 1의 개수 세기
mCnt = strs[i].count("0")
nCnt = strs[i].count("1")
# 1. 현재 문자열을 선택하지 않는 경우
# 다음 문자열로 이동하지만 남은 m, n은 그대로
dp[(i, m, n)] = dfs(i + 1, m, n)
# 2. 현재 문자열을 선택할 수 있다면 (남은 m, n 안에 들어갈 경우)
if mCnt <= m and nCnt <= n:
# 현재 문자열 선택 + 다음 문자열로 이동 (남은 0,1 개수도 줄임)
dp[(i, m, n)] = max(
dp[(i, m, n)],
1 + dfs(i + 1, m - mCnt, n - nCnt)
)
# 현재 상태에서 만들 수 있는 최대 부분집합 크기 반환
return dp[(i, m, n)]
# 첫 번째 문자열부터 시작, 0은 최대 m개, 1은 최대 n개 사용 가능
return dfs(0, m, n)
📌 핵심 요약
- dfs(i, m, n)는 strs[i:]부터 볼 때,
0은 m개, 1은 n개까지 사용할 수 있는 상황에서
만들 수 있는 부분집합의 최대 크기를 반환하는 재귀 함수야. - 선택 or 선택하지 않음을 모두 고려해서 더 좋은 쪽을 선택함.
- 이미 계산한 (i, m, n) 상태는 dp에 저장해서
중복 호출을 피함 (메모이제이션)
이 방식은 Top-down이라 직관적이고,
경우에 따라 Bottom-up DP보다 더 이해가 쉬울 수 있어.