서로 중복되지 않는 숫자로 이루어진 리스트 nums가 주어졌을 때, 부분 집합 내의 모든 쌍 (i, j)에 대해 i % j = 0 또는 j % i = 0을 만족하는 가장 큰 부분 집합을 찾아야 합니다. 즉, 부분 집합 안의 어떤 두 요소를 골라도 한 요소가 다른 요소로 나누어떨어져야 합니다. 우리의 목표는 이러한 부분 집합의 크기를 구하는 것입니다.
예를 들어 입력이 nums = [3, 6, 12, 24, 26, 39]라면 출력은 4가 됩니다. 가장 큰 유효한 부분 집합은 [3, 6, 12, 24]이기 때문입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 리스트를 오름차순으로 정렬합니다. 정렬하면 어떤 요소의 약수는 항상 그 요소보다 앞쪽에 위치하게 되므로, 각 요소를 기준으로 자신보다 작은 요소들만 확인하면 됩니다.
dp[i]는 i번째 요소를 마지막 원소로 포함하는 유효한 부분 집합의 최대 크기를 의미하며, 초기값은 모두 1(자기 자신만 포함)입니다.- 각 인덱스 i에 대해, i보다 앞선 모든 j를 검사하면서
nums[i] % nums[j] == 0인 경우dp[i] = max(dp[i], dp[j] + 1)로 갱신합니다. - dp 배열 전체에서 최댓값이 곧 정답이 됩니다.
알고리즘 단계
- 리스트
nums의 크기만큼 1로 채워진 dp 배열을 생성합니다. nums를 오름차순으로 정렬합니다.- n := len(nums)로 설정하고, n <= 1이면 n을 그대로 반환합니다.
- ans := 0으로 초기화합니다.
- i를 1부터 n-1까지 반복하며:
- j를 0부터 i-1까지 반복하며,
nums[i]가nums[j]로 나누어떨어지면 dp[i]를max(dp[i], dp[j] + 1)로 갱신합니다.
- j를 0부터 i-1까지 반복하며,
- ans를
max(ans, dp[i])로 갱신합니다. - 모든 반복이 끝나면 ans를 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 구현 방법을 확인할 수 있습니다.
class Solution: def solve(self, nums): dp = [1] * len(nums) nums.sort() n = len(nums) if n <= 1: return n ans = 0 for i in range(1, n): for j in range(0, i): if nums[i] % nums[j] == 0: dp[i] = max(dp[i], dp[j] + 1) ans = max(ans, dp[i]) return ans ob = Solution() nums = [3, 6, 12, 24, 26, 39] print(ob.solve(nums))
입력
[3, 6, 12, 24, 26, 39]
출력
4
시간 복잡도 분석
정렬에 O(n log n), 이중 반복문에 O(n²)이 소요되므로 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 dp 배열 사용으로 O(n)입니다. 이 알고리즘은 LeetCode의 'Largest Divisible Subset' 문제와 유사한 유형으로, 배수 관계 문제를 동적 계획법으로 해결하는 대표적인 예시입니다.