20260519-backtracking2: 백트래킹 알고리즘 구현 및 테스트

이번 커밋은 5월 19일에 이루어졌으며, 두 개의 파이썬 파일을 통해 백트래킹 알고리즘의 두 가지 다른 예시를 구현하고 테스트했습니다. leetcode_131_problem.py는 회문 분할 문제를, 5.7.knapsack0-1bt_problem.py는 0/1 배낭 문제를 백트래킹 기법으로 해결하는 코드를 담고 있습니다.

요약

이번 작업에서는 백트래킹 알고리즘을 활용하여 두 가지 문제를 해결하는 파이썬 코드를 작성했습니다. 첫 번째는 문자열을 회문으로 분할하는 leetcode_131_problem.py이며, 두 번째는 0/1 배낭 문제에 대한 백트래킹 기반 분기 한정법을 구현한 5.7.knapsack0-1bt_problem.py입니다. 각 파일에는 문제 해결 과정에 대한 상세한 설명과 테스트 케이스가 포함되어 있습니다.

배경 및 목적

이 작업의 주된 목적은 알고리즘 학습의 일환으로 백트래킹(Backtracking) 알고리즘을 깊이 이해하고 실제로 구현하는 것이었습니다. 특히, 서로 다른 두 가지 문제에 백트래킹을 적용함으로써 알고리즘의 일반성과 응용 가능성을 탐구하고자 했습니다.

구현 내용

총 342라인의 코드가 추가되었습니다.

leetcode_131_problem.py

이 파일은 주어진 문자열을 모든 가능한 회문(palindrome) 부분 문자열의 조합으로 분할하는 문제를 해결합니다.

• 주요 변경사항:
  • partition 함수를 구현하여 문자열 s를 입력받아 가능한 모든 회문 분할 리스트를 반환합니다.
  • is_palindrome 헬퍼 함수를 사용하여 부분 문자열이 회문인지 검사합니다.
  • backtrack 함수는 재귀적으로 가능한 분할을 탐색하며, 회문인 부분 문자열을 찾으면 path에 추가하고 다음 탐색을 진행합니다.
  • res.append(list(path))를 사용하여 path의 현재 상태를 복사하여 결과 리스트에 저장합니다.
  • path.pop()을 사용하여 백트래킹을 수행하며 이전 상태로 복원합니다.
  • 디버그 모드(DEBUG = True)를 위한 출력문과 Mermaid 다이어그램을 포함하여 알고리즘의 동작 방식을 시각적으로 이해할 수 있도록 했습니다.
• 변경된 파일 목록: Week10_problem/leetcode_131_problem.py
• 추가/삭제 라인 수: 추가 183라인, 삭제 0라인
• 핵심 코드 설명:

  def partition(s: str) -> List[List[str]]:
      res = [] # 결과를 담을 리스트
      def is_palindrome(sub: str) -> bool:
          return sub == sub[::-1] # 부분 문자열이 회문인지 검사
  
      def backtrack(start: int, path: List[str]):
          if start == len(s): # 모든 문자를 처리했다면 현재 path는 완전한 회문 조각(정답)
              res.append(list(path)) # 정답이면 res 저장
              return
  
          # 다음 분할 위치(end)를 start+1 .. len(s)까지 이동시키며
          # s[start:end]가 palindrome인지 확인하고, 맞으면 재귀로 진행
          for end in range(start + 1, len(s) + 1):
              sub = s[start:end] # 현재 고려하는 조각
              if is_palindrome(sub): # 이 조각은 회문인가?
                  path.append(sub)        # 회문이면 조각을 회문 조각 리스트에 추가
                  backtrack(end, path)    # 다음 분할로 분기 (end를 다음 start로 입력)
                  path.pop()              # 재귀 종료 후 백트래킹
      
      backtrack(0, []) # 초기 호출: 시작 인덱스 0, 빈 경로
      return res
  

5.7.knapsack0-1bt_problem.py

이 파일은 0/1 배낭 문제를 백트래킹과 분기 한정법(branch and bound)을 사용하여 해결합니다.

• 주요 변경사항:
  • knapsack 함수는 재귀적으로 아이템을 포함하거나 포함하지 않는 경우를 탐색합니다.
  • promising 함수는 현재 노드에서의 이익 상한(upper bound)을 계산하여 더 이상 탐색할 가치가 없는 분기는 가지치기(pruning)합니다.
  • maxprofit과 bestset 변수를 사용하여 현재까지 발견된 최댓값 이익과 해당 아이템 집합을 관리합니다.
  • include 배열은 현재 탐색 경로에서 선택된 아이템들을 추적합니다.
  • 배낭 문제는 1-based 인덱스를 사용하도록 w와 p 배열에 더미 0을 추가했습니다.
  • 다양한 테스트 케이스를 통해 knapsack_solver 함수의 정확성을 검증합니다.
• 변경된 파일 목록: Week10_problem/5.7.knapsack0-1bt_problem.py
• 추가/삭제 라인 수: 추가 159라인, 삭제 0라인
• 핵심 코드 설명:

  def promising(i, weight, profit):
      # ... (이익 상한 계산 로직)
      return bound > maxprofit # 상한이 현재 최댓값보다 크면 유망
  
  def knapsack(i, weight, profit):
      global n, W, w, p, bestset, include, maxprofit
  
      # 현재 노드가 유효한 해인지 확인 및 최적해 갱신
      if weight <= W and profit > maxprofit:
          maxprofit = profit
          for k in range(1, n + 1):
              bestset[k] = include[k]
  
      # 이 노드가 유망한지 검사하고 분기 진행
      if promising(i, weight, profit):
          if i + 1 <= n:
              # (분기 A) 다음 아이템을 포함
              include[i + 1] = 1
              knapsack(i + 1, weight + w[i + 1], profit + p[i + 1])
              include[i + 1] = 0 # 백트래킹
  
              # (분기 B) 다음 아이템을 포함하지 않음
              knapsack(i + 1, weight, profit)
  

기술적 의사결정

이번 작업에서는 별도의 기술 또는 라이브러리 선택이 없었으며, 순수 파이썬 기능과 표준 자료구조를 활용하여 알고리즘을 구현했습니다.

배운 점 및 개선점

• 배운 점:
  • 백트래킹 알고리즘의 기본적인 탐색 원리와 재귀적 구조를 이해했습니다.
  • 회문 분할 문제에서는 부분 문자열을 효율적으로 검사하는 방법과 재귀 호출 시 path의 상태를 올바르게 관리하는 것이 중요함을 배웠습니다.
  • 0/1 배낭 문제에서는 분기 한정법을 통해 탐색 공간을 효과적으로 줄일 수 있음을 알게 되었습니다. promising 함수의 역할이 탐색 효율성을 크게 향상시킨다는 것을 확인했습니다.
  • 1-based 인덱스 사용이 특정 알고리즘 구현 시 편리할 수 있음을 경험했습니다.
• 개선점:
  • leetcode_131_problem.py에서 회문 검사를 매번 수행하는 대신, 동적 계획법(DP)을 활용하여 미리 회문 여부를 테이블에 저장해두면 성능을 더욱 향상시킬 수 있습니다.
  • 5.7.knapsack0-1bt_problem.py에서 아이템을 미리 이익-무게 비율 순으로 정렬하면 promising 함수의 계산이 더 효율적일 수 있으며, 더 빠른 최적해를 찾을 가능성이 높아집니다.
• 다음 단계 계획:
  • leetcode_131_problem.py에 DP를 적용한 회문 검사 방식을 구현합니다.
  • 5.7.knapsack0-1bt_problem.py에 아이템 정렬을 추가하여 성능을 최적화합니다.
  • 다른 유형의 백트래킹 문제(예: N-Queens, 부분집합 합)를 추가로 구현하고 학습합니다.

참고 자료

• LeetCode 131. Palindrome Partitioning
• 알고리즘 관련 교재 및 강의 자료 (CSE304-2026-1-Algorithms)