밤이 블로그

* 조합 (Combination) : 서로 다른 n개에서 r개를 뽑는 것을 n개에서 r개를 택하는 조합이라 하고 이 조합의 수를 nCr로 나타낸다. : 조합은 배열을 생각하지 않으므로(순서X) 선택하여 배열하는 순열의 수를 배열의 수로 나눈 값이라고 생각해도 무방하다. 문제. 4개의 원소(0~3)에서 2개를 뽑는 모든 경우의 수를 출력하시오. (Java) 풀이.Combination을 구현하려면 어떻게 해야 할까? nCr = n-1Cr + n-1Cr-1위 식은 아래와 같이 이해할 수 있다. A,B,C,D,E 5명 중 3명을 뽑는 경우, 5C3이 경우는 A를 기준으로 나눌 수 있다. 1) A가 이미 정해진 경우 : A, x, x : 나머지 4명중 2명을 뽑아야 함. 4C22) A가 제외된 경우 : x, x,..

* 순열 (Permutation) : 서로 다른 n개의 원소에서 r개를 중복을 허용하지 않고 선택하여 순서 있게 늘어 놓은 것을 nPr로 표시한다 문제. { 1, 2, 3, 4 } arr 배열의 4개의 원소에서 3개를 중복을 허용하지 않고 선택하여 순서 있게 나열하는 모든 경우의 수를 출력하시오. (Java) 풀이.Permutation을 구현하려면 어떻게 해야 할까? 아래 그림을 보고 힌트를 얻어보자. 재귀(Recursive) - dfs를 이용하여 풀 수 있을 것 같다. int[] arr = { 1, 2, 3, 4 }; 1) arr[0] → arr[1] → arr[2] → arr[3] 순서로 진행하자. 2) 첫 번째로, arr[0]의 값은 [0], [1], [2], [3]과 swap될 수 있다.3) 두 ..