알고리즘 설계 패러다임 - 05 조합 탐색

UMI·2024년 2월 16일

05 조합 탐색 (Combinatorial Search)

Optimal substructure가 성립한다
⇔ 지금까지 어떤 경로로 이 부분 문제에 도달했건, 남은 부분 문제도 항상 최적으로 풀어야 함
⇒ 과거에 대한 모든 정보를 가지고 끝에 가봐야지만 결론을 낼 수 있었던 일반적인 재귀 함수와는 달리, 현재와 관련된 정보만 가지고도 최적화 문제를 풀 수 있는 것 → Parameter에서 경로 vector 뺄 수 있고 따라서 Return 값도 앞으로에 대한 것만 취급 → Parameter 내용이 줄어듬에 따라 memoization이 가능해짐
최적화 문제 동적 계획법 레시피 (Optimal substructure 성립할 때)
1. 모든 답을 만들어보고 그 중 최적의 값을 반환하는 완전 탐색 함수 작성
2. 전체에 대한 값을 반환하는게 아니라, 앞으로 남은 선택들에 해당하는 값만을 반환하도록 함수 구조 수정
3. Parameter에 이전의 선택에 대한 정보 최소화
  ← 원래 Parameter의 활용 지점 확인 후 모두 replace
4. 가능하다면 Parameter 더 간략화
  → 부분 문제들이 더 많이 중복되는 효과
  ← Parameter로 들어가는 것들과 일대일 대응시킬 수 있는 것 생각
최적화 문제 DP → 함수가 아예 최적화된 값을 반환하게끔 해줌

경우의 수 or 확률 계산하기 레시피
1. 모든 답을 직접 다 만들어서 세어보는 완전 탐색 재귀 함수 작성
  ← 이미 Return 값은 앞으로와 관련된 값
  ← 다음으로 가능한 모든 갈래가 다 포함되는지 확인
2. 필요한 정보만 남기고 Parameter 최대한 간략화
  ← 전체 경로 vector를 Parameter로 주고 받을 때는 끝까지 가서 마지막 선택까지 한 후 조건을 확인 ⇒ 전체 경로가 아니라 그에 대한 간략화된 정보 조각을 받도록 Parameter부가 변경되었기 때문에 한조각에 대한 선택을 할 때마다 해당 조건을 확인할 수 있도록 해야함
  ← 원래 Parameter의 활용 지점 확인 후 모두 replace
  → memoization이 가능해짐
점화식이 떠오르면 그냥 바로 구현해도 됨 (다음으로 가능한 모든 갈래가 다 포함되는지만 확인해주기)
가끔 계산의 방향을 바꾸는 옵션도 고려해보기
- func(x) ⇐ func(x+1) ... ~ ⇒to⇒ func(x) ⇐ func(x-1) ... ~
Overflow 주의 !!!

부분 문제가 너무 복잡하거나 개수가 너무 많을 때
→ 문제를 좀 더 분석해서 답이 항상 어떤 구조를 가짐을 알아내고 그를 활용하기 (ex. 양자화 문제, 실험데이터 복구 문제)
기존의 문제를 변형한 형태의 문제
→ 비슷한 형태의 부분 문제 정의를 써서 풀 수 있는 경우 (ex. JLIS)
→ 직접적으로 풀기보단 기존 문제의 해법을 이용하면 더 쉽게 풀 수 있는 경우 (ex. 비대칭 타일)

海