✅ 오늘의 학습 키워드
- 냅색 문제 (Knapsack Problem)
- Meet in the Middle 알고리즘
- 이분 탐색 (Binary Search)
- 부분집합 합 (Subset Sum)
✍️ 공부한 내용 본인의 언어로 정리하기
오늘은 백준 1450번 냅색문제를 풀었습니다. 이 문제는 배낭에 담을 수 있는 물건의 최대 무게가 주어졌을 때, 물건의 부분집합을 찾아 가방에 담을 수 있는 모든 방법을 구하는 문제입니다. 이 문제는 냅색 문제 (Knapsack Problem)의 변형 문제로, 주어진 물건들을 여러 가지 방법으로 조합하여 가능한 합이 최대 무게 이하인 경우의 수를 구하는 문제입니다.
일반적으로 냅색 문제는 동적 계획법 (Dynamic Programming)을 사용하여 해결하지만, 물건의 개수가 많아지면 시간 복잡도가 급격하게 증가합니다. 이를 해결하기 위해 Meet in the Middle 알고리즘을 사용했습니다. 이 알고리즘은 물건 목록을 두 개의 부분집합으로 나눈 후, 각 부분에서 가능한 부분합을 구하고 이를 이분 탐색을 통해 효율적으로 결합하는 방식입니다.
🧠 오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
처음에 문제를 풀 때, 동적 계획법을 사용해 풀려고 했지만, 물건의 개수와 가방의 무게가 크기 때문에 시간 복잡도가 너무 커져서 접근이 어려웠습니다. 그래서 Meet in the Middle 알고리즘을 적용해 보았습니다.
어떻게 해결했는지
문제를 두 개의 부분집합으로 나누고, 각 부분에서 가능한 부분합을 구한 뒤, 이를 이분 탐색을 통해 두 부분합의 합이 최대 무게 이하인 경우의 수를 계산했습니다.
이분 탐색을 사용하여 한 부분합에 대해 다른 부분합이 최대 무게를 넘지 않는 경우를 효율적으로 찾을 수 있었습니다.
무엇을 새롭게 알았는지
Meet in the Middle 알고리즘을 활용하여 부분합을 분리하고, 이를 이분 탐색으로 결합하는 방식이 매우 효율적이라는 것을 알게 되었습니다.
또한, 이분 탐색을 사용하여 조건을 만족하는 조합의 수를 빠르게 찾는 방법을 배웠습니다.
내일 학습할 것은 무엇인지
내일은 동적 계획법을 응용하여 다른 배낭 문제를 풀어보고, 이분 탐색을 더 연습해 볼 예정입니다.
📝 작성 코드
import sys
from itertools import combinations
from bisect import bisect_right
input = sys.stdin.read
data = input().split()
N = int(data[0])
C = int(data[1])
weights = list(map(int, data[2:]))
# 물건을 두 그룹으로 나누기
half = N // 2
left_weights = weights[:half]
right_weights = weights[half:]
# 부분합 계산 함수
def get_subsums(weights):
subsums = []
for i in range(len(weights) + 1):
for comb in combinations(weights, i):
subsums.append(sum(comb))
return subsums
# 왼쪽과 오른쪽 부분합 계산
left_subsums = get_subsums(left_weights)
right_subsums = get_subsums(right_weights)
# 오른쪽 부분합 정렬
right_subsums.sort()
# 가능한 조합의 수 계산
count = 0
for left_sum in left_subsums:
if left_sum <= C:
# C - left_sum 이하의 right_subsums 원소 개수 찾기
idx = bisect_right(right_subsums, C - left_sum)
count += idx
print(count)#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
