S4) Unit 11. [자료구조/알고리즘] Algorithm with Math & 정규표현식

📣  순열과 조합

𝟭. 순열

✔️ 서로 다른 n개의 원소를 가지는 집합에서 어떤 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 나열하는 것

➰ 조합과 달리 순서도 따져서 부분집합을 만든다.

➰ nPr = n! / (n-r)!

➰ 3P2 = 3 * 2 = 6

𝟮. 조합

✔️ 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것

➰ 순서는 따지지 않는다.

➰ nCr = nPr / r!

➰ 3C2 = 3 * 2 / 2 * 1 = 3

 

🚨 순열과 조합 모두 N이 원소의 총개수이고 R이 뽑는 개수라고 할 때, 순열과 조합은 반드시 R <= N을 만족해야 한다.

---

📣  GCD와 LCM(최대공약수와 최소공배수)

𝟭. GCD(Greatest Common Divisor)

✔️ 최대공약수 :  두 수 이상의 여러 공약수 중 최대인 수

✔️ 공약수 : 두 수 이상의 여러 수 중 공통된 약수

 

𝟮. LCM(Lowest Common Multiple)

✔️ 최소공배수 : 여러 공배수 중 최소인 수

✔️ 공배수 : 두 수 이상의 여러 수 중 공통된 배수

 

𝟯. 최대공약수와 최소공배수를 구하는 방식

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

Q. 12와 18의 최대공약수와 최소공배수

A. 12 = 2 * 2 * 3

18 = 2 * 3 * 3

겹치는 부분인 2 * 3 = 6이 최대공약수, 2 * 3을 중심으로 남은 2와 3을 곱해 나오는 수인 36이 최소공배수

 

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

➰ 2와 3이 12와 18의 공약수임을 알고 있으므로, 2와 3으로 12와 18이 나누어지지 않을 때까지 나누고, 남은 값을 곱해주면 된다.

 

✔️ 유클리드 호제법 : 최대공약수와 관련이 깊은 공식으로, a와 b(a > b)가 있을 때 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와r의 최대공약수와 같다는 이론 => b를 r로 나눈 r'을 구하고, 다시 r을 r'로 나누는 과정을 반복해서, 나머지가 0이 될때 나누는 수가 a와 b의 최대공약수이다.

Q. 81과 15의 최대공약수는?

A. 81 / 15 = 5 + 6

15 / 6 = 2 + 3

6 / 3 = 2 + 0

나머지가 0이 나온 3이 최대공약수이다.

---

📣  멱집합

𝟭. 멱집합

✔️ 어떤 집합이 있을 때, 이 집합의 모든 부분집합

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

 

𝟮. 멱집합을 구하는 방법

Q. 집합 {1, 2, 3}의 멱집합을 구해라

A.

1️⃣ 1을 제외한 {2, 3}의 부분집합을 나열한다.

     2️⃣ 2를 제외한 {3}의 부분집합을 나열한다.

        3️⃣ 3을 제외한 {}의 부분집합을 나열한다 => {}

        3️⃣ {}의 모든 부분집합에 {3}을 추가한 집합들을 나열한다 => {3}

     2️⃣ {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열한다.  

        3️⃣ {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열한다. => {2}, {2, 3}

 

1️⃣  {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한다.

     2️⃣ {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한다.

        3️⃣ {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열한다. => {1}, {1, 3}

        3️⃣ {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열한다. => {1, 2}, {1, 2, 3}

---

📣  Algorithm with Math 예제

𝟭. 순열과 조합 : 카드 문제

Q. [A, B, C, D, E]로 이뤄진 5장의 카드가 있고, 이 5장의 카드 중 3장을 선택하여 나열하려고 한다.

이때, 다음의 조건을 각각 만족하는 경우를 찾아야 한다.

1. 순서를 생각하며 3장을 선택한다.

2. 순서를 생각하지 않고 3장을 선택한다.

 

A. 1은 순열, 2는 조합 문제이다.

1️⃣ 순열의 경우

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

➰ 첫번째 카드를 선택하는 방법 5가지, 두번째 카드를 선택하는 방법 4가지, 세번째 카드를 선택하는 방법 3가지 => 5 * 4 * 3 = 60가지

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();

 

2️⃣ 조합의 경우

➰ 3장을 하나의 그룹으로 선택해야 한다 => 순서를 고려하지 않기 때문에 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A] 는 모두 한가지 경우로 취급하므로 [A, B, C] 자체를 하나의 그룹으로 생각해서 한가지 경우라고 생각해야한다.

➰ 순열의 결과를 한 그룹에서 나올 수 있는 6가지 경우로 나눈 것이 조합의 결과이다.

➰ 60 / 6 = 10

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();

 

🚨 순열과 조합은 반복문이 아닌 '재귀'를 사용하는 경우가 많다.

 

𝟮. GCD와 LCM : 유클리드 호제법을 이용해 최대공약수와 최소공배수 구하기

1️⃣ 최대공약수

function gcd(a, b){
	while(b !== 0){
    // 나머지가 0이 될 때까지 반복
		let r = a % b;
        // r 은 첫번째 수와 두번째 수를 나눈 나머지
		a = b;
        // 첫번째 나눠질 수는 두번째 수가 되고
		b = r;
        // 두번째 수는 두 수를 나눈 나머지가 된다.
	}
	return a;
}

 

2️⃣ 최소공배수

function lcm(a, b){
	return a * (b / gcd(a, b));
    // 유클리드 호제법을 이용해서 최대공약수를 구하고, 
    // 최대공약수를 이용해서 최소공배수를 구한다.
}

 

𝟯. 멱집합 - Power Set

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);

---

📣  정규표현식

𝟭. 정규 표현식

✔️ 문자열에서 특정한 규칙에 따른 문자열 집합을 표현하기 위해 사용되는 형식언어

➰ 특정한 규칙을 갖는 문자열로 이루어진 표현식으로, 특수 문자는 각각의 고유 규칙을 갖고 있다.

 

𝟮. 정규 표현식 예시

✔️ 이메일 유효성 검사

const email = 'kimcoding@codestates.com';
let result = '올바릅니다.';

// 1. 정규표현식 사용
let regExp = /^[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*.[a-zA-Z]{2,3}$/i;

if(regExp.test(email) === false) result = '올바르지 않습니다.';
result; // '올바르지 않습니다.'

-----------------------------------------------------------------------------

// 2. 정규표현식이 아닌 경우, 이메일 아이디가 영문 소문자인지 확인하는 코드
let idx = email.indexOf('@');
if(idx === -1) result = '영문 소문자가 아닙니다.';

let ID = email.slice(0,idx);

ID.split('').forEach(e => {
	e = e.charCodeAt(0);
	if(e < 97 || e > 122){
	result = '영문 소문자가 아닙니다.';
	}
});

result; // '올바릅니다.'

 

𝟯. 정규 표현식 패턴

^	줄(Line)의 시작에서 일치 /^abc/
$	줄(Line)의 끝에서 일치 /xyz$/
.	(특수기호, 띄어쓰기를 포함한) 임의의 한 문자
a|b	a or b 와 일치, 인덱스가 작은 것을 우선 반환
*	0회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {0,} 와 동일
*?	0회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일
+	1회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {1,} 와 동일
+?	1회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {1} 와 동일
{3}	숫자 3개 연속 일치
{3, }	3개 이상 연속 일치
{3, 5}	3개 이상 5개 이하 연속 일치
()	캡쳐(capture)할 그룹
[a-z]	a부터 z 사이의 문자 구간에 일치(영어 소문자)
[A-Z]	A부터 Z 사이의 문자 구간에 일치(영어 대문자)
[0-9]	0부터 9 사이의 문자 구간에 일치(숫자)
\	escape 문자. 특수 기호 앞에 \를 붙이면 정규식 패턴이 아닌, 기호 자체로 인식
\d	숫자를 검색함. /[0-9]/와 동일
\D	숫자가 아닌 문자를 검색함. /[^0-9]/와 동일
\w	영어대소문자, 숫자, (underscore)를 검색함. /[A-Za-z0-9]/ 와 동일
\W	영어대소문자, 숫자, (underscore)가 아닌 문자를 검색함. /[^A-Za-z0-9]/ 와 동일
[^]	[]안의 문자열 앞에 ^이 쓰이면, []안에 없는 문자를 검색함

 

𝟰. 정규 표현식 사용하기

Q. 문자열 str 이 주어질 때, str의 길이가 5 또는 7이면서 숫자(0~9)로만 구성되어 있는지를 확인해 주는 함수를 작성해라.

결과는 Boolean으로 리턴된다. 예를 들어 str가 c2021이면 false, 20212이면 true를 리턴한다.

// 정규표현식 사용
function solution(str) {
    return /^\d{5}$|^\d{7}$/.test(str);
}

 

𝟱. 정규 표현식의 실례

✔️ JS에서 정규표현식은 객체로, 내장 메소드를 가지고 있다.

 

1️⃣ RegExp 객체의 메소드

✔️ exec() : 원하는 정보를 뽑아내고자 할 때 사용한다.

➰ 검색의 대상이 찾고자 하는 문자열에 대한 정보를 가지고 있다면 이를 배열로 반환하며, 찾는 문자열이 없다면 null을 반환한다.

 

✔️ test() : 찾고자 하는 문자열이 대상 안에 있는지의 여부를 boolean 으로 리턴한다.

 

2️⃣ String 객체의 메소드

✔️ match() : RegExp.exec() 와 비슷한 기능을 하며, 정규 표현식을 인자로 받아 주어진 문자열과 일치된 결과를 배열로 반환한다.

➰ 일치되는 결과가 없으면 null을 리턴한다.

 

✔️ replace() : '검색 후 바꾸기'를 수행한다.

➰ 첫 번째 인자로는 정규표현식을 받고, 두 번째 인자로는 치환하려는 문자열을 받는다.

➰ 자열에서 찾고자 하는 대상을 검색해서 이를 치환하려는 문자열로 변경 후 변경된 값을 리턴한다.

 

✔️ split() : 주어진 인자를 구분자로 삼아, 문자열을 부분 문자열로 나누어 그 결과를 배열로 반환한다.

 

✔️ search() : 정규표현식을 인자로 받아 가장 처음 매칭되는 부분 문자열의 위치를 반환한다.

➰ 매칭되는 문자열이 없으면 -1을 반환한다.

 

3️⃣ flag

✔️ 정규표현식은 플래그를 설정해 줄 수 있으며, 플래그는 추가적인 검색 옵션의 역할을 한다.

➰ 플래그들은 각자 혹은 함께 사용하는 것이 모두 가능하며, 순서에 구분이 없다.

 

✔️ i를 붙이면 대소문자를 구분하지 않는다.

✔️ g를 붙이면 검색된 모든 결과를 리턴한다.

✔️ m을 붙이면 다중행을 검색한다.

 

4️⃣ 정규식 패턴(표현식)

✔️ 정규표현식에 다양한 특수기호를 함께 사용하면 문자열을 다룰 때에 더 많은 옵션을 설정할 수 있다.

 

✔️ Anchors: ^ and $

➰ ^ : 문자열의 처음을 의미하며, 문자열에서 ^뒤에 붙은 단어로 시작하는 부분을 찾는다.

    ㄴ 일치하는 부분이 있더라도, 그 부분이 문자열의 시작 부분이 아니면 null을 리턴한다.

➰ $ : 문자열의 끝을 의미하며, 문자열에서 $앞의 표현식으로 끝나는 부분을 찾는다.

    ㄴ 일치하는 부분이 있더라도, 그 부분이 문자열의 끝부분이 아니면 null을 리턴한다.

 

✔️ Quantifiers: *, +, ? and {}

➰ * : 바로 앞의 문자가 0번 이상 나타나는 경우를 검색한다.

    ㄴ /ode*/g 을 사용하게 되면 "od" 가 들어가면서 그 뒤에 "e"가 0번 이상 포함된 모든 문자열을 리턴한다.

➰ + : + 바로 앞의 문자가 1번 이상 나타나는 경우를 검색한다.

➰ ? : ? 앞의 문자가 0번 혹은 1번 나타나는 경우만 검색한다.

    ㄴ ?는 * 혹은 + 와 함께 쓰는 것도 가능하며, 함께 사용하였을 경우 *?는 0번, +?는 1번인 문자열만 리턴한다.

➰ {} : 직접 숫자를 넣어서 연속되는 개수를 설정할 수 있다.

    ㄴ {2}는 2개, {2, }는 2개 이상, {2, 5}는 2개 이상 5개 이하를 의미한다.

 

✔️ OR operator

➰ | 는 or 조건으로 검색하여 | 의 왼쪽 또는 오른쪽의 검색 결과를 반환한다.

 

✔️ Bracket Operator : []

➰ 대괄호 [] 안에 명시된 값을 검색한다.

 

✔️ Character classes 

➰ \d : d 는 digit 을 의미하며 0 ~ 9 사이의 숫자 하나를 검색한다. [0-9] 와 동일

➰ \D : not Digit 을 의미하며, 숫자가 아닌 문자 하나를 검색한다. [^0-9] 와 동일

➰ \w : 알파벳 대소문자, 숫자, _(underbar) 중 하나를 검색한다. [a-zA-Z0-9_]와 동일

➰ \W : 알파벳 대소문자, 숫자, _ (underbar)가 아닌 문자 하나를 검색한다. [^a-zA-Z0-9_]와 동일

 

✔️ Grouping and capturing

➰ 그룹화 : 표현식의 일부를 ()로 묶어주면 그 안의 내용을 하나로 그룹화할 수 있다.

➰ 캡쳐 : () 로 그룹화한다고 하였고, 이를 캡처한다 라고 한다.

co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]

ㄴ () 로 "co"를 캡처

ㄴ 캡처한 "co" 는 일단 당장 사용하지 않고, + 가 "co"의 1회 이상 연속 반복을 검색

ㄴ 이렇게 캡처 이외 표현식이 모두 작동하고 나면, 캡처해 두었던 "co"를 검색

 

✔️ non-capturing

➰ (?:)로 사용하면 그룹은 만들지만 캡처는 하지 않는다.

 

✔️ lookahead

➰ 검색하려는 문자열에 (?=여기) 에 일치하는 문자가 있어야 (?=여기) 앞의 문자열을 반환한다.

 

✔️ negated lookahead

➰ (?!) 는 (?=) 의 부정