AncomWiki

Minimum Sum 문제 (동적계획법 + 비트마스크)

Properties1
descriptionn x n 행렬에서 각 행에서 정확히 하나의 원소를 선택하여 합이 최소가 되게 하는 문제. 열의 선택 여부를 비트마스크로 표현하여 상태 공간의 중복을 제거하고, 동적계획법(DP)을 통해 최적의 최소 합을 계산한다. 시간 복잡도는 O(n * 2^n) 수준이다.

7 min read

Minimum Sum 문제 (동적계획법 + 비트마스크)

Source

  • Evernote/Inbox/문제해결을 위한 창의적 알고리즘 Minimum Sum (고급, p200).md

Summary

n x n 행렬에서 각 행에서 정확히 하나의 원소를 선택하여 합이 최소가 되게 하는 문제. 열의 선택 여부를 비트마스크로 표현하여 상태 공간의 중복을 제거하고, 동적계획법(DP)을 통해 최적의 최소 합을 계산한다. 시간 복잡도는 O(n * 2^n) 수준이다.

Key Points

  • 문제 유형: n x n 행렬에서 행마다 한 개씩 선택하여 총합 최소화
  • 핵심 기법: 비트마스크(Bitmask)를 이용한 상태 표현 및 동적계획법(DP)
  • 상태 정의: 현재 행(row)과 사용된 열의 집합(bitmask)을 상태로 사용
  • 구현 특징: 메모이제이션을 위해 DP 테이블(DT)을 활용하며, 방문하지 않은 상태는 INF로 초기화 후 재귀 호출
  • 참고: 원문은 Java 코드 예시 제공, 시간 복잡도 표기 오류 가능성 있음(코드상 O(n*2^n)에 가까움)

그래프 뷰