20260526 : 0-1 배낭 문제, 브랜치 앤 바운드 알고리즘 실습
0-1 배낭 문제 해결을 위한 브랜치 앤 바운드 알고리즘 구현 코드에 대한 상세 주석을 추가했습니다. 'add underscores' 커밋은 2026년 5월 26일에 이루어졌으며, 코드의 가독성과 이해도를 높이는 데 집중했습니다.
2026-1-Algorithm-assignments: 0-1 배낭 문제 브랜치 앤 바운드 알고리즘 주석 개선
0-1 배낭 문제 해결을 위한 브랜치 앤 바운드 알고리즘 구현 코드에 대한 상세 주석을 추가했습니다. 'add underscores' 커밋은 2026년 5월 26일에 이루어졌으며, 코드의 가독성과 이해도를 높이는 데 집중했습니다.
요약
이번 커밋은 Week11_problem 폴더 내의 두 파일, 6.1.knapsack.0-1.bb_bfs_problem.py와 6.2.knapsack.0-1.bb_bestfs_problem.py에서 발생한 변경 사항을 포함합니다. 총 34라인이 추가되고 12라인이 삭제되었습니다. 주요 변경 내용은 두 파일 모두에서 boundof 함수와 knapsack 함수의 파라미터 의미, 그리고 코드 내의 주석을 개선하여 알고리즘의 동작 방식을 더 명확하게 설명하는 것입니다.
배경 및 목적
기존 브랜치 앤 바운드 알고리즘 구현 코드는 기능적으로는 정상 동작했으나, 알고리즘의 각 단계별 의미와 사용되는 변수들의 역할을 이해하기 어렵다는 점이 있었습니다. 특히 boundof 함수의 역할이나 knapsack 함수 내에서 노드를 확장하고 큐(또는 힙)에 삽입하는 로직에 대한 명확한 설명이 부족했습니다. 따라서 코드의 유지보수성과 다른 개발자들이 코드를 이해하고 활용하는 데 도움을 주기 위해 상세한 주석을 추가하는 것이 필요했습니다.
구현 내용
이번 커밋은 주로 코드의 주석을 추가하고 일부 단어를 변경하여 가독성을 높이는 데 초점을 맞췄습니다.
주요 변경사항 상세 설명
boundof함수: 함수의 파라미터(u,n,W,w,p)에 대한 의미를 명확하게 정의하는 주석을 추가했습니다. 또한, 상한 계산 로직에서 '분수 배낭 방식'으로 일부만 반영하는 부분과, 계산된 상한 값을 반환하는 부분에 대한 설명을 명확히 했습니다.knapsack함수 (BFS 및 Best-First Search): 함수의 파라미터(n,W,w,p)에 대한 의미를 명확히 정의하는 주석을 추가했습니다. 또한, 노드를 확장하고 큐(또는 힙)에 삽입하는 로직에 대한 설명을 "상한이 현재 최적보다 크면 힙에 삽입"과 같이 더 구체적으로 명시했습니다. 일부 설명에서 '상한 계산은 현재 누적 이익에서 시작'이라는 부분을 더 명확하게 표현했습니다.
변경된 파일 목록
Week11_problem/6.1.knapsack.0-1.bb_bfs_problem.pyWeek11_problem/6.2.knapsack.0-1.bb_bestfs_problem.py
추가/삭제된 코드 라인 수
- 총 추가 라인: 34
- 총 삭제 라인: 12
핵심 코드 설명
Week11_problem/6.2.knapsack.0-1.bb_bestfs_problem.py의 boundof 함수 변경 예시:
def boundof(u, n, W, w, p):
# 파라미터 의미
# u: 현재 상태 노드(현재까지의 level/weight/profit 정보를 가짐)
# n: 전체 아이템 개수
# W: 배낭의 최대 허용 무게
# w: 아이템 무게 배열(1번 인덱스부터 실제 아이템)
# p: 아이템 이익(가치) 배열(1번 인덱스부터 실제 아이템)
# 이미 용량을 넘겼다면 유효하지 않으므로 상한을 0으로 반환
if u.weight >= W:
return 0
else:
# "상한 계산은 현재 누적 이익에서 시작"
profit_bound = u.profit
# 다음으로 고려할 아이템 인덱스
j = u.level + 1
# 현재까지 누적된 무게
total_weight = u.weight
# 남은 용량이 있을 때까지 아이템을 통째로 담음
while j <= n and total_weight + w[j] <= W:
total_weight += w[j]
profit_bound += p[j]
# 다음 아이템으로 이동
j += 1
# 더 이상 통째로 못 담는 첫 아이템은 "분수 배낭 방식"으로 일부만 반영
if j <= n:
profit_bound += (W - total_weight) * (p[j] / w[j])
# "이 노드에서 가능한 최대 총이익 상한" 반환
return profit_bound
위 코드는 boundof 함수의 각 파라미터에 대한 설명과 계산 로직에 대한 설명을 명확히 하고 있습니다.
Week11_problem/6.1.knapsack.0-1.bb_bfs_problem.py의 knapsack2 함수 변경 예시:
def knapsack2(n, W, w, p):
# 파라미터 의미
# n: 전체 아이템 개수
# W: 배낭의 최대 허용 무게
# w: 아이템 무게 배열(편의상 w[0]=0, 실제 아이템은 w[1]~w[n])
# p: 아이템 이익 배열(편의상 p[0]=0, 실제 아이템은 p[1]~p[n])
global count
# BFS 탐색을 위한 큐
queue = [] # Initialize Queue
# 루트 노드 생성 (아무것도 선택하지 않은 상태)
v = Node(-1, 0, 0) # level, weight, profit
v.bound = boundof(v, n, W, w, p)
queue.append(v)
# 최종 최대 이익 초기화
maxprofit = 0
# 큐가 빌 때까지 반복
while queue:
# 큐에서 가장 앞에 있는 노드(가장 먼저 추가된 노드)를 꺼냄
v = queue.pop(0)
# 현재 노드의 레벨이 마지막 레벨 전이고,
# 상한이 현재까지 찾은 최대 이익보다 크면 자식 노드를 생성하여 탐색
if v.level < n and v.bound > maxprofit:
# 왼쪽 자식: 다음 아이템을 선택한 경우
# Level을 1 증가시키고, 해당 아이템의 무게와 이익을 더함
u = Node(v.level + 1, v.weight + w[v.level + 1], v.profit + p[v.level + 1])
# 유효한 무게이고 이익이 현재 최대 이익보다 좋으면 최적 이익 갱신
if u.weight <= W and u.profit > maxprofit:
maxprofit = u.profit
# 왼쪽 자식의 상한 계산
u.bound = boundof(u, n, W, w, p)
# "상한이 여전히 희망적이면 큐에 넣어 나중에 확장"
if u.bound > maxprofit:
queue.append(u)
# 오른쪽 자식: 다음 아이템을 "선택하지 않음" 경우
# Level만 1 증가시키고, 무게와 이익은 그대로 유지
u = Node(v.level + 1, v.weight, v.profit)
# 오른쪽 자식의 상한 계산
u.bound = boundof(u, n, W, w, p)
# "상한이 현재 최적보다 크면 큐에 삽입"
if u.bound > maxprofit:
queue.append(u)
# "최종 최대 이익 반환"
return maxprofit
위 코드는 BFS 탐색에서 노드를 큐에 추가하고 확장하는 과정을 설명하는 주석을 추가했습니다.
기술적 의사결정
이번 커밋에서는 새로운 기술이나 라이브러리 도입이 없었습니다. 기존 Python 코드의 주석을 개선하는 작업에 집중했습니다.
배운 점 및 개선점
- 배운 점: 코드에 상세한 주석을 추가하는 작업이 얼마나 중요한지 다시 한번 느꼈습니다. 단순히 코드가 동작하는 것을 넘어, 그 원리를 이해하고 설명하는 과정에서 알고리즘에 대한 이해도가 깊어졌습니다.
- 개선점: 앞으로도 구현하는 알고리즘에 대해 각 변수, 함수, 주요 로직에 대한 상세한 주석을 습관화해야겠습니다. 특히, 복잡한 알고리즘일수록 주석의 역할이 커진다는 것을 인지하고 있습니다.
- 다음 단계 계획: 다음 단계로는 추가된 주석을 바탕으로 각 알고리즘의 성능을 측정하고, 다른 최적화 기법을 적용하는 것을 고려할 수 있습니다.
참고 자료
- (해당 커밋에서 특별히 참고한 외부 자료는 없습니다.)