LeetCode/NeetCode

[DP: 0 / 1 Knapsack] 474. Ones and Zeroes ★★★★★

hyunkookim 2025. 4. 13. 05:56

474. Ones and Zeroes

 

https://youtu.be/miZ3qV04b1g

 

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보다 더 이해가 쉬울 수 있어.