▸JAVA/알고리즘 및 자료구조3

• 

  부분집합_재귀함수_조합 구하기 (JAVA) [ 조합 (Combination) ] n개의 원소 중 r개의 원소를 꺼내는 경우의 수 순서가 유효하지 않기 때문에 중복을 허용하지 않음 (순열은 순서가 유효하므로 중복 허용) 경우의 수 : nPr / r! = n! / r! * (n-r)! 표기법 : nCr 순열과 달리 순서가 필요없어서 중복을 허용하지 않는 것을 조합이라고 합니다. {1,2,3}과 {3,2,1}은 같은 것으로 간주합니다. 예를 들어 {1,2,3} 중 2개를 곱해서 나올 수 있는 숫자를 구하라고 한다면 "{1,2} = 2", "{2,1} =2" 이기 때문에 순서에 상관 없이 원소의 종류만 맞으면 됩니다. 이전 글의 순열 코드를 약간 수정해 조합이 되었기 때문에 순열의 원리를 이해하면 금방 이해를 할 수 있습니다. 순열 코드는 백준 알고리즘.. ▸JAVA/알고리즘 및 자료구조 2020. 4. 17.

• 

  부분집합_재귀함수_순열 구하기 (JAVA) [ 순열 (Permutation) ] n개의 원소 중 r개의 원소를 꺼내는 경우의 수 순서가 유효하기 때문에 원소의 중복을 허용함 (조합은 순서가 유효하지 않아 중복 불허) 경우의 수 : n! / (n-r)! 의 갯수를 가짐 표기법 : nPr 순서가 있도록 모든 경우의 수를 뽑아내는 것을 순열이라고 합니다. 부분집합 중 {1, 2, 3}과 {3,2,1}은 엄연히 다른 것으로 인식합니다. 예를 들어 {1,2,3} 중 2개를 조합해 만들 수 있는 모든 숫자를 구하라고 한다면 순열을 이용해야 합니다. 두 숫자를 붙이는 것은 순서에 따라 다르니까요. 일단 최대한 직관적으로 작성 후 백준 알고리즘 문제를 통해 검증을 완료한 코드입니다. * 전체 코드 package pojoPrj; import java.util.A.. ▸JAVA/알고리즘 및 자료구조 2020. 4. 17.

• 

  부분집합_재귀함수_멱집합 구하기 (JAVA) [ 멱집합(powerset) ] 공집합을 포함해 모든 부분집합을 가진 집합 (중복 없음) 어떠한 집합의 부분집합을 산출하는 로직은 여러 가지가 있습니다. 그 중 모든 부분집합(멱집합)을 가장 쉽게 구할 수 있는 재귀함수 사용법입니다. 원소 순서에 상관없이 중복을 허용하지 않기 때문에 rCr의 조합과 동일한 결과입니다. 아래 3개짜리 배열이 하나 있다고 해보겠습니다. * 집합 : { a, b, c } 먼저 가장 앞에 있는 "a"의 기준에서 생각해봅니다. "a"는 부분집합에 있을 수도 있고 없을 수도 있습니다. 따라서 "a"가 있건 없건 부분집합을 구하기 위해서는 { b, c }의 부분집합 정보가 필요합니다. 피보나치 수열과 같이 큰 문제를 해결하기 위해 작은 정보가 필요한 경우입니다. 그럼 이번엔 { b,.. ▸JAVA/알고리즘 및 자료구조 2020. 4. 14.