28.01_Algorithm with Math_순열/조합_22.09.29

Algorithm with Math

>주요 등장 개념

• 순열/조합
• GCD/LCM(최대공약수, 최소공배수)
• 멱집합

//알고리즘에 등장하는 수학 개념은 많이 쳐줘봐야 고등 수학이다. 쫄지 말자

순열/조합

>순열

: n 개 중 m 개를 선택할 때, 순서를 고려하여 뽑는 경우의 수

: 똑같은 요소를 뽑지 않는 모든 경우의 수로도 볼 수 있음.

: P라고 표현, Permutation

>순열 일반식

nPr = n! / (n-r)!

n! : 모든 경우의 수(순서가 있을 경우)
(n-r)! : r개를 뽑기 위해 나머지 경우의 수를 제거하는 식

>코드 표현

public static ArrayList<String[]> permutationLoop() {
    String[] alphaCard = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();
    //순열 특징1: 0부터 끝까지 반복(0부터 해야 다시 뽑힐 수 있음.)
    for (int i = 0; i < alphaCard.length; i++) {
      for (int j = 0; j < alphaCard.length; j++) {
        for (int k = 0; k < alphaCard.length; k++) {
        //순열 특징2: 똑같은 카드일 때는 제거( 5*4*3 을 표현)
          if (i == j || j == k || k == i) continue;
            String[] input = new String[]{alphaCard[i], alphaCard[j], alphaCard[k]};
            result.add(input);
        }
      }
    }
  return result;
}

>조합

: n 개 중 m 개를 선택할 때, 순서를 고려하지 않고 뽑는 경우의 수

: 순열로 뽑은 경우의 수에서 중복을 제거한 것으로도 볼 수 있음.

: C라고 표현, Combination

>조합 일반식

nCr = n! / ((n-r)!*r!)

n! / (n-r)! : 순열의 경우의 수

1/r! : 순열에서 순서를 고려하지 않는 경우 생기는 중복 경우의 수

>코드 표현

public static ArrayList<String[]> combination() {
  String[] lookup = new String[]{"A", "B", "C", "D", "E"};
  ArrayList<String[]> result = new ArrayList<>();
  //조합 특징1: 반복문의 시작이 이전 반복문 시작+1 이다.
  //이전 요소가 다시 뽑힐 필요가 없기 때문
  for(int i = 0; i < lookup.length; i++) {
    for(int j = i + 1; j < lookup.length; j++) {
      for(int k = j + 1; k < lookup.length; k++) {
        String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
		result.add(input);
      }
    }
  }
  return result;
}

>순열/조합의 한계

• 반복문의 수

: 중복된 반복문의 수가 많아 효율이 떨어진다.

• 뽑아야할 갯수가 미지수일때

: 뽑아야할 갯수의 추가는 곧 반복문의 중첩 수의 추가이기 때문에 해당 요소가 미지수이면 코드 작성이 까다로워진다.

>순열/조합의 한계 극복

: 때문에 순열/조합 문제는 재귀 함수로 많이 푼다.

>재귀함수 코드 표현

: 추가 작성

 

>소수 찾기

: 추가 작성

>일곱 난쟁이

: 추가 작성