조합의 정의 조합은 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 말한다. 앞서 살펴본 순열과의 차이점은 순서를 고려하지 않는다는 점이다. 수학적 증명을 통한 조합 구하기 순열이 nPr = n개에서 r개를 선택한 후 순서대로 나열하는 것인데 여기서 n개에서 r개를 선택하는 것이 순열이고 이 r개를 다시 나열하는 것이 nPr이다. 따라서 nCr은 다음과 같이 구할 수 있다. 위 식을 처리하기 쉬운 재귀 방식으로 변경해보자. 위 식을 잘 살펴보면 nCr은 보다 낮은 단계인 n-1Cr-1과 n-1Cr의 합이다. 여기서 r이 선택할 요소의 개수이다. 즉 n개에서 r개를 뽑는 방법은 어떤 요소 하나를 고려했을 때 그 요소를 뽑았을 때의 조합과 그 요소를 뽑지 않았을 때의 조합의 합이된다. 조합의 과정 ..

다음으로 알아볼 순열 작성 방식은 next permutation을 이용하는 방법이다. next permutation은 말 그대로 사전 순으로 다음의 순열을 찾는 과정이다. 다음 순열이란 만약 요소가 {1,2,3}일 때 이것의 다음은 {1,3,2}, 다시 {1,3,2}의 다음은 {2,1,3} --> {2,3,1} --> {3,1,2} --> {3,2,1}로 전개되는 것을 말한다. 어떻게 이과정이 진행되는지 살펴보자. 진행 과정 next permutation을 찾는 과정은 몇 가지 절차를 거쳐서 이뤄진다. {3, 5, 1, 9, 7}로 이뤄진 배열의 다음 순열을 찾아보자. step 1: src[i]< src[i+1] 즉 다음 요소보다 작은 요소 중 가장 마지막 요소를 찾는다. 다음 그림을 보면 현재 위 조건..

순열은 앞서 살펴봤던 visited를 이용하는 방식이외에도 여러 가지 방식으로 작성이 가능하다. 여기서는 swap 을 이용해서 순열을 구하는 방식에 대해 살펴보자. 기본적인 컨셉은 아래와 같다. - swap: 요소와 요소의 위치를 서로 변경한다. - depth: 선택할 수 있는 요소의 범위를 조절한다. 진행 과정 먼저 최초의 배열 {A, B, C, D}가 있고 depth 0에서 swap 되는 단계는 다음과 같을 것이다. 물론 depth0-1인 BACD는 depth0-0 인 ABCD에 대한 모든 하위 depth가 종료된 후 진행될것이다. 이제 depth0-0의 하위인 depth1의 동작을 살펴보자. 첫 번째 자리는 A로 고정된 상태에서 나머지 요소들이 swap 대상이 된다. 이제 depth1-0이 종료되면..

앞선 포스트에서 살펴봤듯이 순열을 구현하기 위해 필요한 개념은 3가지이다. 1. 순서대로 나열 - 반복문을 통해 순차적으로 접근한다. 2. 중복을 허용하지 않음 - 이미 사용한 요소가 무엇인지 저장해놓는다. 이를 위해 visited라는 이름의 배열을 사용한다. 3. 재귀를 통한 접근 - 선택해야할 요소들을 하나씩 줄여가면서 자신 호출 4개의 원소를 가진 배열을 만들고 여기서 3개를 선택해서 나열하는 경우의 수를 조사해보자. private static char[] src = {'A', 'B', 'C', 'D'}; 기본적인 코드의 흐름은 다음과 같다. 코드에 대한 설명은 주석으로 대체한다. /** * 순열을 만들고 출력하는 메서드 * @param r 선택할 요소의 개수 * @param current 현재 선..

순열의 정의 순열(Permutation)이란 n개의 원소에서 r개를 중복을 허용하지 않고 선택해서 순서대로 늘어놓은 것을 말하며 nPr이라고 표기한다. 순열의 전개 과정 4개의 원소 {1,2,3,4}에서 3개를 선택해서 순서대로 나열하는 방법에 대해 생각해보자. 맨 처음은 4개의 원소가 모두 올 수 있다. 그 다음은 각 경우에 대해 중복을 허용하지 않으므로 1st에서 선택되지 않은 3녀석이 각각 올 수 있다. 즉 4*3 가지가 가능하다. 여기서 1-4와 4-1은 당연히 다르다. 우리는 순서대로 나열하고 있다는 점이 중요하다.(만약 순서가 상관 없이 뽑기만 진행한다면 조합이 된다.) 동일한 절차를 거치면 우리가 원하는 순열을 얻을 수 있다. 드디어 모든 절차가 끝났고 4개의 원소에서 중복 없이 3개를 선택..