[Advanced] SW 문제해결 응용 - 구현 - 완전검색

1. 완전 검색 - 최적해 문제

많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것

• 완전 검색 알고리즘 → 중복 제거 → 개선된 알고리즘
• 완전 검색 알고리즘 → 분할정복, 동적 계획법
• ex) 베이비진 문제

 

2. 조합적 문제 - 경우의 수 문제

순열 : 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

• 다수 문제들이 순서화된 요소들의 집합에서 최선의 경우를 찾는 것
  • 순회 외판원 문제 (Traveling Salesperson Problem)
    방문할 도시가 n개라면 가능한 모든 경로는 n! 만큼 존재 → 12이상부터 폭발적 증가!
    

    

존슨-트로터 알고리즘 : 교환을 통해 순열 생성

 

조합 : 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

• 재귀 호출을 이용한 조합 생성 알고리즘
  

  

 

 

부분집합 : 최적의 답이 전체 값들의 부분 집합인 알고리즘들이 존재 

• 바이너리 카운팅(Binary Counting)
  • 원소를 각각의 binary로 생각해서 푸는 기법
• ex) 배낭 문제, N개의 원소를 포함한 집합