[SCCC] #2 재귀함수, 순열, 비트마스크

재귀함수

• 재귀호출
  - 자신과 동일한 일을 하는 부하 직원에게 작업을 요청하고 그 결과물을 돌려받는 과정
  - 부하 직원의 결과물이 항상 올바르다고 빋고 작업을 수행하면 됨
  - = 수학적 귀납법
• 주의사항
  - 종료 조건이 있어야 함
  - 재귀 호출 과정에 사이클이 없어야 함 ( a -> b -> c -> a -> ... )
  - 종료 조건에 가까워지는 방향으로 설계

순열

• std::next_permutation(begin, end)
  • 사전 순으로 다음 순열을 구하는 함수
  • 다음 순열이 없으면 false, 있으면 true 반환

int arr[5] = {0, 1, 2, 3, 4};
std::next_permutation(arr, arr+5);
  // arr = {0, 1, 2, 4, 3} 로 바뀜

int arr[4] = {1, 1, 2, 2};
std::next_permutation(arr, arr+4);
  // arr = {1, 2, 1, 2} 로 바뀜. 중복 원소 있어도 상관 없음

• do while 문을 이용하면 모든 순열을 확인할 수 있음

비트마스크

• 배열 A의 모든 부분 집합을 구하는 방법
  • 재귀함수
  • 비트마스크