20220215 APS 응용, 조합, 탐욕기법

조합(Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합
• 조합의 수식
  • nCr = n! / (n-r)! r!
  • nCr = n-1Cr-1 + n-1Cr, nC0=1

조합을 생성하는 방법

1. 반복문을 통한 조합 생성
2. 재귀 호출을 이용한 조합 생성
3. NextPermutation을 활용
   • 원소 크기와 같은 크기의 int 배열 P를 생성하여 r개 크기 만큼 뒤에서 0이 아닌 값으로 초기화 (ex, 1로 초기화)
   • nextPermutation 알고리즘 한 번 수행시마다 조합이 생성됨
   • P 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 것

부분 집합(Subset)

• 집합에 포함된 원소들을 선택
• 원소들의 그룹에서 최적의 부분 집합을 찾는 것
• N개의 원소를 포함한 집합
  • 자기 자신과 공집합을 포함한 모든 부분집합(Power set)의 개수는 2^n개
  • 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

부분 집합 생성 방법

1. 반복문을 통한 부분집합 생성
2. 재귀 호출을 이용해 생성 : Visited를 이용
3. 바이너리 카운팅을 통한 사전적 순서로 생성

바이너리 카운팅 (Binary Counting)

• 원소 수에 해당하는 N개의 비트열을 이용
• n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미

탐욕 기법(Greedy Algorithm)

• 최적해를 구하는데 사용되는 근시안적인 방법
• 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은 해를 찾는 문제
• 여러 경우 중에서 하나를 선택할때 마다 그 순간에 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적으로 해답을 만들었다고해서 그것이 최적이라는 보장은 없음
• 한번 선택된 것은 번복하지 않음 → 단순하며, 제한적인 문제들에 적용됨

분할 정복 기법(Divide and Conquer)

설계 전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나누다
• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다
• 통합(Combine) : (필요하다면) 해결된 해답을 모은다

이진 검색(Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행
  • 목적 키를 찾을 떄까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 함
• 검색 과정

1. 자료의 중앙에 있는 원소를 선택
2. 중앙 원소의 값과 찾는 목표 값을 비교
3. 중앙 원소의 값과 목표 값이 일치하면 탐색을 종료
4. 목표값이 중앙 원소값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 크다면 자료의 오른쪽 반에서 새로 검색을 수행
5. 찾는 값을 찾을 때까지 위의 과정을 반복