66. 조합, 중복조합, 순열, 중복순열 뼈대 알고리즘

1. 개요

조합, 중복조합, 순열, 중복순열 알고리즘은 모든 경우를 나열하는 알고리즘이다.

모든 경우를 나열하기에 작은 범위의 문제에 대해서 완전 탐색 알고리즘에 적합하다.

또한 각각의 경우에 해당하는 모든 데이터 Set을 가지고 있기 때문에 조건에 만족하는 모든 경우를 출력할 때 필요하다.

또는 앞서 포스팅한 knapsack problem(배낭 문제)처럼 각각의 가치와 무게에 대한 경우에 따라서

문제가 설정한 최고 효율적인 방법이나 값을 찾는데 도움이 된다.

이 포스팅에서는 현재 각각의 뼈대가 알고리즘이 흩어져있는데, 이를 복습 겸 코드 작성하여 모든 뼈대를 종합해서 정리했다.

재귀 방식으로 움직이기 때문에 큰 문제는 해결하지 못한다.

만약 문제가 작고, 완전 탐색을 한다고 하여도 성능에 크게 문제가 없고, 또한 각각의 경우를 출력해야 한다면 이 

나열하기 알고리즘의 대표인 '조합, 중복조합, 순열, 중복순열' 알고리즘을 잘 고려하자.

조합이나 중복조합 그리고 중복순열 알고리즘은 쉽게 직관적으로 코드를 보면 이해할 수 있지만,

순열 알고리즘만큼은 조금 머릿속에서 쉽게 쉽게 이해가 안갔다.

오직 순열 알고리즘만 미리 초기화한 배열을 사용한다.

또한 Swap 함수나 또는 사전 순으로 출력을 위한 Right_Rotate()와 Left_Rotate()를 사용한다.

즉, 미리 입력해둔 배열 속 데이터를 이리저리 순서만 바꿔서 출력하고 다시 원래 상태로 되돌린다.

순열 알고리즘의 재귀 방법은 이렇다.

현재 단계에서, 배열의 첫 번째 원소, 두 번째 원소, 세 번째 원소 ... 마지막 원소를 맨 처음 원소와 교환한 후(처음만 결정)

다음 단계에서 나머지 뒷 부분의 순열 알고리즘을 작성한다.

예시)

-> 0 결정 - 1, 2의 순열

0, 1 2의 순열      -> 1 결정 - 0, 2의 순열 

                       -> 2 결정 - 0, 1의 순열

2. 문제

조합, 중복조합, 순열, 중복순열 뼈대 알고리즘을 모두 작성하시오.

3. 코드 및 출력

3-1) 조합

3-2) 중복조합

3-3) 순열

3-4) 중복순열

3-5) 메인

3-6) m: 3, n: 2 출력

3-7) m: 3, n: 3 출력

4. 정리

모든 경우를 다 나열하여 알고싶을 때나 또는 작은 부분에 대한 완전 탐색을 위할 때 이 알고리즘을 사용한다.

완전 탐색 알고리즘은 모든 알고리즘의 기본이니까 언제나 시작은 이 나열 알고리즘을 적용할 수 있는지 검사부터 하자.

계속 공부!