TIL. Algorithm 2

김은서·2022년 10월 17일

TIL

목록 보기

46/49

순열과 조합

순열

순열(順列, permutation):

서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며,
이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같음.

여기 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있습니다.
만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 이번에는 순서에 상관있게 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까요?

총 6개의 부분집합이 나올 수 있을 것입니다.
왜냐하면 순열은 조합과 달리 순서도 따져서 부분집합을 만들기 때문입니다.
즉 사과가 뒤로 가는 경우와 사과가 앞으로 가는 경우를 다르게 보고 각기 하나의 경우의 수로 치는 것입니다.
그래서 {사과 오렌지} {오렌지 사과}가 다른 집합으로 취급될 수 있는 것입니다.

순열의 식은 이렇게 표현됩니다.

순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현합니다.
여기서도 n은 원소의 총 개수를 의미하고,
r은 그중 뽑는 개수를 의미합니다.

여기서 중요한 것은,
앞서 설명했듯이 순열 또한 중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다는 것입니다.

한 번 3P2의 값을 식을 통해 확인해보도록 하겠습니다.

이렇게 식을 통해 확인해 보았을 때도 6개의 부분조합이 도출이 됨을 알 수 있었습니다.
이어서 살펴본 조합의 식은 순열의 개념 또한 이용이 됩니다.

조합

조합(組合, combination):

서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며,
이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같습니다.

여기 또 다시 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있습니다.
만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 순서에 상관없는 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까요?

총 3개의 부분집합이 나올 수 있을 것입니다.
왜냐하면 조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이기 때문입니다.
즉 사과가 뒤로 가든, 앞으로 가든 상관 없이 그저 사과 1개와 오렌지 1개가 있으면 하나의 경우의 수로 치는 것입니다.

조합의 식은 이렇게 표현합니다.

조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현합니다.

여기서 n은 원소의 총 개수를 의미하고,
r은 그중 뽑는 개수를 의미합니다.

여기서 중요한 것은,
앞서 설명했듯이 조합은 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다는 것입니다.
과일이 3개가 있는데 4개, 5개를 뽑으라는 것처럼, 없는 것들을 뽑으라는 말과 똑같기 때문에 R은 최대 N개까지만 뽑을 수 있습니다.

한 번 3C2의 값을 식을 통해 확인해보도록 하겠습니다.

이렇게 식을 통해 확인해 보았을 때도 3개의 부분조합이 도출이 됨을 알 수 있었습니다.

이렇게 순열과 조합의 개념에 대해 살펴보았습니다.
해당 개념을 알고 있으면 순열과 조합에 관련된 알고리즘을 접할 때 조금 더 쉽게 이해할 수 있습니다.

GCD와 LCM

GCD

최대공약수(Greatest Common Divisor, GCD):

두 수 이상의 여러 공약수 중 최대인 수.

공약수(Common Divisor)

최대공약수의 개념 중 공약수는 두 수 이상의 여러 수 중 공통된 약수를 의미합니다.
여기서 약수(Divisor)는 어떤 수를 나누어떨어지게 하는 수를 의미합니다.

여기 6과 9 두 수가 있습니다.
미리 표기했듯이 6의 약수는 1, 2, 3, 6이고, 9의 약수는 1, 3, 9입니다.
이 중 공통된 약수는 1, 3으로 공약수라고 표현합니다.

여기서 최대공약수를 찾아보겠습니다.

여러 개의 공약수 중 최대인 수가 바로 최대공약수이므로,
6과 9의 최대공약수는 3임을 알 수 있습니다.

LCM

최소공배수(Lowest Common Multiple, LCM):

두 수 이상의 여러 공배수 중 최소인 수를 가리킵니다.

공배수(Common Multiple)

최소공배수의 개념 중 공배수는 두 수 이상의 여러 수 중 공통된 배수를 의미합니다.

여기서 배수(Multiple)는 하나의 수에 정수를 곱한 수입니다.

반대로 말해서, 배수는 그 수에 의해 나누어 떨어지는 수라고 볼 수 있습니다.

여기 12와 18 두 수가 있습니다.

두 수의 공배수는 이런 식으로 해당 수의 배수를 나열해 겹쳐지는 수를 찾는 방식으로 구할 수 있을 것입니다.

공배수의 경우 배수이기 때문에 무수히 많으므로 가장 큰 공배수는 구할 수 없습니다.

그러므로 최소공배수를 찾아야 하는데, 여기서 최소 공배수는 36임을 알 수 있습니다.

GCD와 LCM을 구하는 방식

구하는 방식에는 여러 방식이 있습니다.

가장 작은 수들의 곱으로 나타내며 구하는 방식과,

공약수로 나누어보며 최대공약수와 최소공배수를 구하는 방법이 있습니다.

그리고 마지막에는 알고리즘 문제에서 가장 많이 쓰이는 유클리드 호제법을 알아보도록 하겠습니다.

가장 작은 수들의 곱으로 나타내며 구하는 법

여기 다시 12와 18이 있습니다.

12와 18을 가장 작은 수의 곱으로 나타내봅니다.

여기서 겹치는 부분인 2와 3을 곱한 수인 6이 최대공약수이고,

6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수가 됩니다.

공약수로 나누어보며 구하는 법

이번에는 공약수로 나누어보며 최대공약수와 최소공배수를 구하는 법을 알아보겠습니다.

우리는 이미 2와 3이 공약수임을 알고 있습니다.

해당 공약수들로 12와 18을 더이상 나눌 수 없는 수까지 나눕니다.

여기서 나누는 데에 사용된 수인 2와 3을 곱하면 6이 나오고, 이 6은 최대공약수가 됩니다.

그리고 나누는 데에 사용된 수와 더 이상 나눌 수 없는 수들을 곱하게 되면 36이 나오고,
이 수는 최소공배수가 됩니다.

유클리드 호제법

어떤 방식으로 구하는지 알아봤으므로, 이번에는 여러분들이 GCD와 LCM 개념이 쓰이는 문제를 풀 때 가장 많이 쓰이는 유클리드 호제법에 대해 알아보도록 하겠습니다.

유클리드 호제법을 알고 있게 되면 최대공약수와 최소공배수를 구하는 모든 문제에 일단 적용해보고 시작할 수 있게 됩니다.

유클리드 호제법은 최대공약수와 관련이 깊은 공식입니다.

2개의 자연수 a와 b가 있을 때,

a를 b로 나눈 나머지를 r이라 하면

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론입니다.

이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고,

다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게 됩니다.

해당 수식을 보며 다시 이해해보도록 하겠습니다.

여기 2개의 자연수 a와 b가 있습니다.

단 a가 b보다 커야 한다는 조건(절대적 조건)이 있습니다.

왜냐하면 나누었을 때 음수가 나오면 안 되기 때문입니다.

이제 a와 b를 나누었을 때 q와 r이 나옵니다.
q는 몫(Quotient)을 의미하고,
r은 나머지(Rest)를 의미한다고 생각하시면 됩니다.

여기서 다시 b를 r로 나눕니다.

그러면 다시 몫인 q와 나머지인 r’가 나올 것이고,

r을 다시 r’와 나누게 되면 언젠가 몫인 q와 나머지인 r이 0이 되는 상황이 도출이 됩니다.

이 때 나누는 수인 r’가 바로 최대공약수라는 의미입니다.

이번에는 실제 자연수를 이용해 확인해보도록 하겠습니다.

여기 81과 15가 있습니다.
같은 방식으로 쭉 나눴을 때, 마지막 나눗셈에서 나누는 수인 3이 최대공약수임을 확인할 수 있습니다.
이런 식으로 유클리드 호제법을 이용하게 되면 최대공약수를 쉽게 구할 수 있게 되고,
최대공약수를 구할 수 있게 되면 최소공배수는 자연스럽게 구할 수 있게 됩니다.

멱집합

집합 {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}

원소가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합의 요소가 n 개일 때 모든 부분집합의 개수는 2n개 입니다.

예를 들어 집합의 원소가 4개라면 모든 부분집합의 개수는 24, 집합의 원소가 5개라면 25가 됩니다.

간단히 {1, 2, 3}의 모든 부분집합을 구하는 단계는 다소 복잡해 보일 수 있습니다.
그러나 이 단계를 자세히 보면, 어디서 많이 본 듯한 패턴이지 않나요?

이 순서는, 트리구조와 비슷한 형태라는 사실을 떠올릴 수 있습니다.

멱집합 문제는 트리 문제는 아닙니다. 그림은 이해를 돕기 위해 사용되었습니다.

멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인할 수 있습니다.

여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다.

따라서, 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있습니다.
예를 들어 PowerSet 이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet 함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여 해결할 수 있습니다.

문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.

순열과 조합 - 순열과 조합을 이용한 문제들

시작하기 전에 알아두어야 할 용어

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

문제: 카드 뽑기

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

순서를 생각하며 3장을 선택합니다.
순서를 생각하지 않고 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();

result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수입니다.

반복문 3개로 구성된 이 순열 코드는 전혀 어렵지 않습니다.

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

// 반복문 1개당 1개의 요소를 뽑습니다.

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

중복된 요소는 제거
- 같은 인덱스를 선택하는 것은, 중복된 요소를 선택한다는 것과 같습니다. 하지만 순열은 중복된 요소를 허용하지 않기 때문에, result에 넣기 전에, 동일한 인덱스인지 검사하고, 동일하다면 삽입하지 않고 다음으로 넘어갑니다.
- AAA부터 EEE까지 전부 만드는 코드이지만, 마지막에 중복 요소를 제거함으로써 순열이 완성됩니다.

결과

/* 
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
  [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
  [ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
  [ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
  [ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
  [ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
  [ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
  [ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
  [ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
  [ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
  [ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
  [ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
  [ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
  [ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
  [ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
  [ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
  [ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
  [ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
  [ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]
*/

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)
- 한 번 조합한 요소는 다시 조합하지 않습니다. 하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음, 그 요소를 반복에 포함하지 않고 다음 요소부터 시작합니다.

결과

/*
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ], [ 'A', 'D', 'E' ],
  [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ], [ 'B', 'D', 'E' ], 
	[ 'C', 'D', 'E' ]
]
*/

보시다시피 반복문으로 순열과 조합을 만들어낼 수는 있습니다. 하지만, 분명한 한계점이 존재합니다.

개수가 늘어나면 반복문의 수도 늘어난다.
- 만약, 11개의 요소 중 10개를 뽑아야 한다면, 10중 반복문을 구현해야 합니다. 이는 굉장히 비효율적일 뿐더러 보기 좋은(쉬운) 코드에 부합하지도 않습니다.
뽑아야 되는 개수가 n개처럼 변수로 들어왔을 때 대응이 어렵다.
- 요소 개수를 변수로 받는 건 요소.length를 사용하여 대응할 수 있지만, 뽑아야 되는 개수도 변수로 받게 된다면 몇 개의 반복문을 설정해야 하는지, 설정은 어떻게 하는지 굉장히 까다로워질 것입니다.

📌 그렇기에 순열과 조합은 재귀를 사용하여 풀이하는 경우가 많습니다. 재귀를 사용한 순열과 조합 코드 제작을 직접 시도해 보세요.

문제: 소수 찾기

한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다.
흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
종이에 기록된 모든 숫자가 배열로 주어진다면,
이 종잇조각으로 만들 수 있는 소수는 몇 개인가요?

이 문제에는 순열이 숨어 있습니다. 만약 이 사실을 알아차린다면, 문제를 보다 쉽게 해결할 수 있습니다. 순열을 이용한다면, 다음과 같이 전략을 세울 수 있습니다.

n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성합니다.
각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사합니다.
소수라면 개수를 셉니다.
숫자는 순서에 의해 전혀 다른 값이 될 수 있습니다. 예를 들어 123과 321은 전혀 다른 숫자입니다. 만약 이 문제를 조합으로 접근하게 된다면, 123과 321은 같은 경우로 취급합니다. 따라서, 순서를 고려하지 않고 k 개를 뽑아내는 조합으로는 이 문제를 해결할 수 없습니다.

문제: 일곱 난쟁이

왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다.
하루일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉" 명이었던 겁니다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다.
(뛰어난 수학적 직관력을 가지고 있던) 백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다.
아홉 난쟁이 각각의 키가 주어질 때,
원래 백설 공주와 평화롭게 생활하던 일곱 난쟁이를 찾는 방법은 무엇인가요?

위 문제는 조합을 이용해서 일곱 난쟁이를 찾을 수 있습니다.
모든 일곱 난쟁이의 키를 합했을 때 100이 된다고 주어졌기 때문에, 9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고, 난쟁이 7명의 키를 합했을 때 100이 되는 경우를 찾으면 됩니다.

위 두 문제와 같이 순열과 조합을 활용하는 문제는,
문제를 먼저 이해하고 지문 속에서 힌트를 얻어 활용할 수 있어야 합니다.

GCD와 LCM - GCD와 LCM을 이용한 문제들

시작하기 전에 기억해두어야 할 용어

약수: 어떤 수를 나누어떨어지게 하는 수
배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수
공약수: 둘 이상의 수의 공통인 약수
공배수: 둘 이상의 수의 공통인 배수
최대공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
최소공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

유클리드 호제법을 이용한 공식

유클리드 호제법을 이용해 최대공약수를 구하는 로직

function gcd(a, b){
	while(b !== 0){
		let r = a % b;
		a = b;
		b = r;
	}
	return a;
}

해당 함수 gcd 는 유클리드 호제법을 적용한 로직입니다.
함수 선언을 한 뒤 a와 b를 매개변수로 받고 있으며, 그 안에 while문으로 이루어진 중심 로직이 있습니다.
while문은 b는 0이 아니어야 함을 조건으로 받고 있는데, 왜 0이 아니어야 하냐면 모든 자연수를 0으로 나누게 되면 리턴되는 값이 Infinity이기 때문입니다.
값이 무한대로 나오면 안 되기 때문에 해당 조건을 걸어둠으로써 값이 제대로 나오지 않는 상황을 방지합니다.

해당 조건을 지키며 b가 0이 될 때까지 계속 while문은 돌아갑니다.
변수 r 은 a와 b의 나머지가 할당이 되어 있는 그 밑으로 a는 b로 재할당을 시키고,
b는 r로 재할당을 시키고 있습니다.
그리고 마지막으로 리턴하는 값은 a로, 이 a를 리턴하는 이유는 while문이 돌아가면서 나누는 수를 재할당을 하기 때문입니다.

유클리드 호제법을 이용해 최소공배수를 구하는 로직

function lcm(a, b){
	return a * (b / gcd(a, b));
}

해당 함수 lcm 은 마찬가지로 a와 b를 매개변수로 받고 있으며, 리턴되는 값으로 a에 b를 최대공약수로 나눈 값을 곱하고 있습니다.
여기서 최대공약수의 값은 위에서 만들었던 함수 gcd를 이용해 구할 수 있습니다.
최소공배수는 최대공약수를 이용해서 만들어지는 수입니다.
그러므로 최대공약수를 만들 줄 알면 최소공배수 또한 만들 수 있게 됩니다.

GCD와 LCM의 개념이 적용된 문제

문제: Mask States

방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다.
이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다.
각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다.
이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다.
이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요?
(휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

풀이 방법은 다양합니다. 그러나 이 문제에서 최소 공배수를 떠올릴 수 있다면, 더 쉽고 빠르게 문제를 해결할 수 있습니다.

세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 됩니다.
따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로, 앞서 학습했던 최소공배수의 개념을 알아야 합니다.

결과적으로, LCM(60, 75, 90)은 900입니다.
(LCM; Least Common Multiple, 최소 공배수)

A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 900/60 = 15 번 작업하고, 15번 X 9개 = 135개의 마스크를 만들어 냅니다.
B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개,
C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 만들어 냅니다.

따라서, A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개가 됩니다.

최소공배수를 쉽게 알아내는 법은 앞서 소개한 유클리드 호제법을 사용하는 것입니다.
세 수의 최소 공배수를 구하는 방식은 첫 번째 수와 두 번째 수의 최소 공배수를 구한 뒤, 그 값과 세 번째 수의 최소 공배수를 구하는 형식입니다.

멱집합 - Power Set

Power Set

집합 S가 있을 때, Power Set인 P(S)는 집합 S의 거듭제곱 집합으로, S의 모든 부분 집합의 집합을 의미합니다.

예를 들어 S가 {a, b, c} 으로 요소가 3개일 때,

P(S)는 {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}} 으로 요소가 8개임을 알 수 있습니다.

즉 S에 n개의 요소가 있다면 P(S)에는 2^n의 요소가 있음을 의미합니다.

Example

Set = [a, b, c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter        Subset
     000               Empty set
		 001                   a
     010                   b
     011                   ab
     100                   c
     101                   ac
     110                   bc
     111                   abc

이제 알고리즘 로직을 보도록 하겠습니다.

Input : Set[], set_size

1. 모든 집합의 크기를 가져옵니다. power_set_size = pow(2, set_size)
1. 0에서부터 power_set_size까지의 반복문 실행
- i = 0에서 set_size까지 크기를 지정해 반복문을 돌립니다. 그리고 집합에서 i번째 요소에 해당하는 하위 집합을 출력합니다.
- 하위 집합을 구하면 개행을 통해 집합을 구분합니다.

주어진 집합 S에 대해 거듭제곱 집합은 0과 2^n-1 사이의 모든 이진수를 생성하여 찾을 수 있습니다. 여기서 n은 집합의 크기입니다.
예를 들어 집합 S {x, y, z}에 대해 0부터 2^3-1까지의 모든 이진수를 생성하고, 생성된 각 숫자에대해 해당 숫자의 집합 비트를 고려하여 해당 집합을 찾을 수 있습니다.

아래는 위에서 소개한 접근 방식을 구현한 것입니다.

let inputSet = ['a', 'b', 'c'];

function powerSet (arr) {
	const result = [];

	function recursion (subset, start) {
		result.push(subset);

		for(let i = start; i < arr.length; i++){
			recursion([...subset, arr[i]], i+1);
			//이렇게도 구현할 수 있습니다.
			recursion(subset.concat(arr[i]), i+1);
		}
	}

	recursion([], 0);

	return result;
}

poserSet(inputSet);

Output

[
  [],
  [ 'a' ],
  [ 'a', 'b' ],
  [ 'a', 'b', 'c' ],
  [ 'a', 'c' ],
  [ 'b' ],
  [ 'b', 'c' ],
  [ 'c' ]
]

위의 powerSet 로직은 재귀함수를 이용하여 구현한 것입니다.
재귀함수에 부분집합을 만들기 위한 빈배열과 시작할 숫자를 지정합니다.
이어 숫자가 커지게끔 하면서 중심 로직인 반복문을 돌려 부분집합을 만든 뒤, 최종적으로 배열 result에 push합니다.

김은서

이전 포스트

TIL. Algorithm

다음 포스트