Algorithm 21장 - 알고리즘 유형 (2)

Algorithm

순열과 조합

순열

• 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
• 순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현한다.
• 여기서 n은 원소의 총개수를 의미하고, r은 그중 뽑는 개수를 의미한다.
• 여기서 중요한 것은, 순열은 중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다는 것이다.

조합

• 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
• -조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이다.
• 조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현한다.
• 여기서 n은 원소의 총개수를 의미하고, r은 그중 뽑는 개수를 의미한다.
• 조합 또한 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다는 것이다.
• 과일이 3개가 있는데 4개, 5개를 뽑으라는 것처럼, 없는 것들을 뽑으라는 말과 똑같기 때문에 R은 최대 N개까지만 뽑을 수 있다.

GCD와 LCM

GCD 최대 공약수

LCM 최소 공배수

GCD와 LCM을 구하는 방식

• 여기 다시 12와 18이 있다.
• 12와 18을 가장 작은 수의 곱으로 나타낸다.
• 여기서 겹치는 부분인 2와 3을 곱한 수인 6이 최대공약수이고, 6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수가 된다.
• 우리는 이미 2와 3이 공약수임을 알고 있다.
• 해당 공약수들로 12와 18을 더 이상 나눌 수 없는 수까지 나눈다.
• 여기서 나누는 데에 사용된 수인 2와 3을 곱하면 6이 나오고, 이 6은 최대공약수가 된다.
• 그리고 나누는 데에 사용된 수와 더 이상 나눌 수 없는 수들을 곱하게 되면 36이 나오고, 이 수는 최소공배수가 된다.

유클리드 호제법

• 유클리드 호제법은 최대공약수와 관련이 깊은 공식이다.
• 2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론이다.
• 이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게 된다.
• 단 a가 b보다 커야 한다는 조건(절대적 조건)이 있습니다. 왜냐하면 나누었을 때 음수가 나오면 안 되기 때문이다.
• 이제 a와 b를 나누었을 때 q와 r이 나온다.
• q는 몫(Quotient)을 의미하고, r은 나머지(Rest)를 의미한다.
• 여기서 다시 b를 r로 나눈다.
• 그러면 다시 몫인 q와 나머지인 r’가 나올 것이고, r을 다시 r’와 나누게 되면 언젠가 몫인 q와 나머지인 r이 0이 되는 상황이 도출된다.
• 이때 나누는 수인 r’가 바로 최대공약수라는 의미이다.

멱집합

• 집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개이다.
• 그리고 이 모든 부분집합을 통틀어 멱집합이라고 한다.
• 이렇게 어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합 이라고 한다.
• Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.
  • Step B: 2를 제외한 {3}의 부분집합을 나열합니다.
    • Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}
    • Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}
  • Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.
    • Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}
• Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.
  • Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열합니다.
    • Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}
    • Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}

예시

카드뽑기

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

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

모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지합니다.

해당 조건을 만족하려면, 다음과 같은 방법으로 경우의 수를 구합니다.

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

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

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

5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
일반식 : nPr = n! / (n - r)!
5! = 5 X (5 - 1) X (5 - 2) X (5 - 3) X (5 - 4) = 5 X 4 X 3 X 2 X 1 = 120
그렇다면, 순열의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까요?

예) [A, B, C], [A, B, D], [A, B, E], [A, C, B] ... 등

// 반복문 코드

function permutationLoop() {
  // 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
  // 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ["A", "B", "C", "D", "E"];

  let result = [];

  for (let i = 0; i < lookup.length; i++) {
    for (let j = 0; j < lookup.length; j++) {
      for (let k = 0; k < lookup.length; k++) {
        if (i === j || j === k || k === i) continue;
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }

  return result;
}

permutationLoop();

• 반복문의 개수 === 요소를 뽑는 개수
  • 5개의 요소 중 3개를 뽑는 조건 : 하나의 반복문당 5 개의 요소(lookup.length)를 순회하고, 반복문을 3번 중첩하여 3개의 요소를 뽑는다.
  • 조금 더 풀어서 쓰자면 이러한 식이 된다.

• 중복된 요소는 제거

  • 같은 인덱스를 선택하는 것은, 중복된 요소를 선택한다는 것과 같다.
  • 하지만 순열은 중복된 요소를 허용하지 않기 때문에, result에 넣기 전에, 동일한 인덱스인지 검사하고, 동일하다면 삽입하지 않고 다음으로 넘어간다.
  • AAA부터 EEE까지 전부 만드는 코드이지만, 마지막에 중복 요소를 제거함으로써 순열이 완성된다.
• case 2. 순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수

2번 조건에서 모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 합니다.

다음과 같은 방법으로 경우의 수를 구합니다.

순열로 구할 수 있는 경우를 찾습니다.
순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눕니다.
먼저, 조합은 순열과 달리 순서를 고려하지 않습니다. 만약 순열처럼 순서를 생각하여 경우의 수를 센다면, 조합으로써 올바르지 않을 겁니다.

예를 들어 순열에서는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급합니다. 다시 말해 순열에서처럼 순서를 생각하여 선택하면, 중복된 경우가 6배 발생합니다.

여기서 나온 여섯 가지 경우의 수는 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 입니다.

5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10
일반식: nCr = n! / (r! * (n - r)!)
그렇다면, 조합의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까요?

예) [A, B, C], [A, B, D]\, [A, B, E], [B, C, D] ... 등

// 반복문 코드

function combinationLoop() {
  // 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
  // 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ["A", "B", "C", "D", "E"];
  let result = [];

  console.log(lookup);

  for (let i = 0; i < lookup.length; i++) {
    for (let j = i + 1; j < lookup.length; j++) {
      for (let k = j + 1; k < lookup.length; k++) {
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }

  return result;
}

combinationLoop();

• 순열과 마찬가지로 result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수다.
• 순열과 다른 점은, 반복의 조건에 있다. (i = 0, j = i + 1, k = j + 1)
• 한 번 조합한 요소는 다시 조합하지 않는다.
• 하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음, 그 요소를 반복에 포함하지 않고 다음 요소부터 시작한다.

반복문으로 순열과 조합을 나타낼 수 있지만, 개수가 늘어나면 반복문의 수도 늘어난다는 단점과 뽑아야 되는 개수가 n개처럼 변수로 들어왔을 때 대응이 어렵다는 단점이 있기 때문에 재귀를 사용해서 풀어야 하는 경우가 많다.