20260526-분기한정법 실습

이번 커밋은 알고리즘 스터디의 일환으로, 분기한정법(Branch and Bound)을 활용하여 0-1 배낭 문제와 관련된 두 가지 알고리즘(BFS, BestFS)을 구현하고, LeetCode의 최소 경로 합 문제를 해결하는 데 집중했습니다.

요약

이번 커밋은 20260526-분기한정법 실습이라는 메시지로 총 4개의 파일을 수정했습니다. Claude-흐름 사고방식 이해하기.txt 파일은 분기한정법 알고리즘의 개념 이해를 돕기 위해 Claude AI와의 대화 내용을 정리한 것이며, Week11_problem/6.2.knapsack.0-1.bb_bestfs_problem.py와 Week11_problem/6.1.knapsack.0-1.bb_bfs_problem.py 파일은 각각 Best-First Search와 Breadth-First Search를 이용한 0-1 배낭 문제의 분기한정법 구현입니다. 또한, Week11_problem/leetcode_64_problem.py 파일은 LeetCode 64번 문제인 최소 경로 합을 BFS로 해결하는 코드를 담고 있습니다. 총 1029 라인이 추가되었습니다.

배경 및 목적

알고리즘 스터디의 11주차 주제인 분기한정법을 깊이 이해하고 실제 문제에 적용하기 위해 이 작업이 필요했습니다. 특히, 0-1 배낭 문제는 탐욕 알고리즘으로는 최적해를 보장할 수 없으므로, 분기한정법과 같은 완전 탐색 기반의 접근 방식이 요구됩니다. 또한, BFS와 BestFS의 탐색 전략 차이를 비교하고, LeetCode의 실제 문제를 통해 알고리즘 적용 능력을 향상시키는 것이 목적입니다.

구현 내용

Claude-흐름 사고방식 이해하기.txt

이 파일에는 Claude AI와 0-1 배낭 문제의 분기한정법(BestFS) 및 외판원 문제의 상태공간트리 탐색에 대한 대화 내용이 기록되어 있습니다. BestFS의 탐색 전략, bound 계산 방식, pruning 조건, 그리고 외판원 문제에서의 Dijkstra와의 차이점, bound 계산 시 제외되는 조건 등에 대한 질문과 답변이 포함되어 있습니다. 이 대화는 알고리즘의 개념적 이해를 돕는 역할을 합니다.

Week11_problem/6.2.knapsack.0-1.bb_bestfs_problem.py (BestFS 0-1 배낭 문제)

• 주요 변경사항: 0-1 배낭 문제를 Best-First Search를 사용하여 해결하는 알고리즘을 구현했습니다. 우선순위 큐(heapq)를 사용하여 bound 값이 가장 높은 노드부터 탐색합니다.
• 변경된 파일: Week11_problem/6.2.knapsack.0-1.bb_bestfs_problem.py
• 추가 라인: 147
• 삭제 라인: 0
• 핵심 코드 설명:
  • Node 클래스는 현재 아이템 레벨, 누적 무게, 누적 이익, 그리고 계산된 bound 값을 저장합니다.
  • boundof 함수는 현재 노드에서 얻을 수 있는 최대 이익의 상한을 계산합니다. 현재 이익에 남은 아이템들을 분수 배낭 방식으로 채웠을 때의 최대 이익을 더합니다.
  • knapsack3 함수는 BestFS 알고리즘을 구현합니다. 우선순위 큐에 노드를 삽입할 때 -bound를 사용하여 bound 값이 가장 높은 노드가 먼저 나오도록 합니다. maxprofit 변수를 통해 현재까지 찾은 최적 이익을 갱신하며, bound 값이 maxprofit보다 작은 노드는 탐색에서 제외(pruning)합니다.

Week11_problem/6.1.knapsack.0-1.bb_bfs_problem.py (BFS 0-1 배낭 문제)

• 주요 변경사항: 0-1 배낭 문제를 Breadth-First Search를 사용하여 해결하는 알고리즘을 구현했습니다. 일반적인 큐를 사용하여 레벨 순서대로 탐색합니다.
• 변경된 파일: Week11_problem/6.1.knapsack.0-1.bb_bfs_problem.py
• 추가 라인: 136
• 삭제 라인: 0
• 핵심 코드 설명:
  • Node 클래스는 BestFS와 동일하게 level, weight, profit, bound를 저장합니다.
  • boundof 함수 역시 BestFS와 동일하게 상한을 계산합니다.
  • knapsack2 함수는 BFS 알고리즘을 구현합니다. 큐(deque)를 사용하여 노드를 레벨 순서대로 탐색하며, bound 값이 maxprofit보다 큰 경우에만 큐에 삽입합니다. BFS는 BestFS에 비해 bound 값을 우선순위로 고려하지 않으므로 탐색 범위가 더 넓을 수 있습니다.

Week11_problem/leetcode_64_problem.py (LeetCode 64번 문제)

• 주요 변경사항: LeetCode 64번 문제인 "Minimum Path Sum"을 BFS를 사용하여 해결하는 코드를 작성했습니다. 격자에서 시작점부터 도착점까지의 최소 경로 합을 찾는 문제입니다.
• 변경된 파일: Week11_problem/leetcode_64_problem.py
• 추가 라인: 104
• 삭제 라인: 0
• 핵심 코드 설명:
  • minPathSum 함수는 BFS를 활용하여 최소 경로를 탐색합니다.
  • 큐에는 현재 위치 (행, 열)와 해당 위치까지의 누적 합을 저장합니다.
  • visited 딕셔너리를 사용하여 이미 방문한 칸에 대해 더 나쁜 경로로 재방문하는 것을 방지합니다.
  • 오른쪽과 아래쪽으로 이동 가능한 경우, 새 누적 합을 계산하고 visited에 기록된 값보다 작거나 min_path_sum보다 작은 경우에만 큐에 추가합니다.

기술적 의사결정

• 0-1 배낭 문제 해결 방식:
  • BFS vs BestFS: 두 알고리즘 모두 분기한정법의 틀 안에서 구현되었지만, 탐색 전략에서 차이를 보입니다. BFS는 레벨 순서대로 탐색하며, BestFS는 bound 값이 가장 높은 노드부터 우선적으로 탐색합니다. BestFS가 일반적으로 더 효율적인 탐색을 수행할 수 있습니다.
  • Bound 함수 구현: bound 함수는 가능한 최대 이익의 상한을 추정하는 핵심 요소입니다. 현재까지의 이익에 남은 아이템들을 분수 배낭 방식으로 채울 수 있는 최대 이익을 더하는 방식으로 구현했습니다. 이는 최적해를 찾기 위한 필수적인 전제 조건입니다.
• LeetCode 64번 문제 해결 방식:
  • BFS 사용: 이 문제는 최단 경로 탐색 문제의 성격을 가지므로 BFS가 적합합니다. 각 칸으로 이동할 때마다 누적 합을 갱신하며, visited 맵을 통해 동일한 칸에 대해 더 큰 누적 합으로 다시 방문하는 것을 방지하여 효율성을 높였습니다.
  • visited 맵 활용: visited 맵은 단순히 방문 여부만을 기록하는 것이 아니라, 해당 칸에 도달한 최소 누적 합을 기록합니다. 이를 통해 불필요한 재탐색을 방지하고, 더 효율적인 경로를 우선적으로 탐색하게 됩니다.

배운 점 및 개선점

• 분기한정법의 이해: BFS와 BestFS를 직접 구현하면서 분기한정법의 원리, 특히 bound 계산과 pruning의 중요성을 체감했습니다. bound 값이 높을수록 탐색 범위가 넓어지고, 낮을수록 pruning이 많이 되어 효율적이라는 것을 알게 되었습니다.
• 탐색 알고리즘 비교: BFS와 BestFS의 구현을 통해 탐색 공간을 어떻게 관리하는지에 따라 알고리즘의 성능이 달라짐을 확인했습니다. BestFS가 bound를 활용하여 더 유망한 경로를 우선 탐색하는 것이 인상 깊었습니다.
• Claude AI 활용: Claude AI와의 대화를 통해 알고리즘의 개념적인 부분을 시각적 예시와 함께 깊이 이해할 수 있었습니다. 특히, bound의 의미와 pruning 조건, 외판원 문제에서의 bound 계산 방식 등 복잡한 개념들을 명확하게 정리할 수 있었습니다.
• 개선점:
  • 0-1 배낭 문제에서 bound 계산 시 fractional knapsack 부분을 조금 더 최적화할 수 있는지 검토할 필요가 있습니다.
  • LeetCode 64번 문제는 DP(Dynamic Programming)로도 해결 가능하며, DP 방식과 BFS 방식의 성능을 비교 분석하면 더 많은 인사이트를 얻을 수 있을 것입니다.
• 다음 단계 계획:
  • 외판원 문제(Traveling Salesperson Problem)에 대한 분기한정법 구현을 진행합니다.
  • 분기한정법을 적용한 다른 문제들을 탐색하고 해결합니다.
  • DP와 분기한정법 등 다양한 알고리즘의 시간 복잡도 및 공간 복잡도를 비교 분석하는 내용을 추가합니다.

참고 자료

• Claude AI와의 대화 내용 (Claude-흐름 사고방식 이해하기.txt)
• LeetCode 64번 문제 설명 페이지 (https://leetcode.com/problems/minimum-path-sum/description/)