용어정리

• 순열 : 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.
• 조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.
• ! (factorial, 팩토리얼) : n! 은 n에서부터 1씩 감소하여 1까지의 모든 정수의 곱. (n 보다 작거나 같은 모든 양의 정수의 곱.) 팩토리얼에서, 0!과 1!은 모두 1이다.
  Ex) 5! = 5 x 4 x 3 x 2 x 1

---

문제 - 카드 뽑기

A, B, C, D, E로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.

1. 순서를 생각하며 3장을 선택하는 경우
2. 순서를 생각하지 않고 3장을 선택하는 경우

case 1. 순서를 생각하며 3장을 선택할 때의 모든 경우의 수 : 순열

• 흐름 : 모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지한다.

첫번째 나열하는 카드를 선택하는 방법은 다섯 가지.
첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법은 네 가지.
두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법은 세 가지.
따라서 5 X 4 X 3 = 60 가지의 방법이 있다.

이렇게 n 개 중에서 일부만을 선택하여 나열하는 것을 순열 이라고 한다. 순열은 순서를 지키면서 나열해야 한다.

예를 들어 카드를 3장 뽑을 때, [A, B, D]와 [A, D, B] 두 경우 모두 A, B, 그리고 D라는 같은 카드를 3장 선택했지만, 나열하는 순서가 다르므로 서로 다른 경우로 구분해야 한다.

순열은 Permutation 의 약자 P 로 표현한다.

---

5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60

일반식 : nPr = n! / (n - r)!

// 반복문 코드

public static ArrayList<String[]> permutationLoop() {
  // 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
  // 문제 안에 포함되어 있을 경우 아래와 같이 직접 배열 요소 입력해서 사용한다.
    String[] lookup = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();

    for (int i = 0; i < lookup.length; i++) {
      for (int j = 0; j < lookup.length; j++) {
        for (int k = 0; k < lookup.length; k++) {
          if (i == j || j == k || k == i) continue;
            String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
            result.add(input);
        }
      }
    }
  return result;
}

case 2. 순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수 - 조합

• 흐름 : 3장의 카드를 하나의 그룹으로 선택해야 한다.

다음과 같은 방법으로 진행한다.

1. 순열로 구할 수 있는 경우를 찾는다.
2. 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.

예를 들어 순열에서는 {A, B, C}, {A, C, B}, {B, A, C}, {B, C, A}, {C, A, B}, {C, B, A} 의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급한다.

여기서 나온 여섯 가지 경우의 수는 3장의 카드를 순서를 생각하여 나열한 모든 경우의 수다.

3장의 카드를 순열 공식에 적용하면 3! / (3-3)! = (3 X 2 X 1) / 1 = 6 이다. 순서를 생각하느라 중복된 부분이 발생한 순열의 모든 가짓수를, 중복된 6가지로 나누어 주면 조합의 모든 경우의 수를 얻을 수 있다.

따라서 (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10 이다.

조합은 Combination 의 약자 C 로 표현한다.

5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 : 5C3 = 5! / (3! * 2!) = 10

일반식 : nCr = n! / (r! * (n - r)!)

// 반복문 코드

public static ArrayList<String[]> combinationLoop() {
	// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 아래와 같이 요소를 직접 적어서 사용한다.
  String[] lookup = new String[]{"A", "B", "C", "D", "E"};
  ArrayList<String[]> result = new ArrayList<>();

  for(int i = 0; i < lookup.length; i++) { // 중복을 허용하지 않기 때문에 i = 0
    for(int j = i + 1; j < lookup.length; j++) { // j = i +1 
      for(int k = j + 1; k < lookup.length; k++) { // k = j + 1 인덱스가 1씩 증가한다. 
        String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
				result.add(input);
      }
    }
  }

  return result;
}

소수 찾기

// 소수 = 1과 자기 자신만 약수로 가지는 수 
// 소수 확인 = 임의의 수 n % 2 == 0 이면 소수가 아님
public boolean isPrime(int number) {
    for(int i = 2; i < number; i++) {
      if(number % i == 0) return false;
    }
    return true;

---

// Math.sqrt를 사용해서 제곱근으로 비교하여 소수 판별이 가능하다
public boolean isPrime(int number) {
    for(int i = 2; i <= Math.sqrt(number); i++) {
      if(number % i == 0) return false;
    }
    return true;
  }