[TIL] Day75 #알고리즘 #순열 #조합 #GCD #LCM #멱집합 #정규표현식

Beanxx·2022년 8월 11일
0

TIL

목록 보기
75/120
post-thumbnail

2022.08.11(Thurs)

[TIL] Day75
[SEB FE] Day76

☑️ Algorithm with Math

📎 순열 & 조합

🔷 순열 (permutation)

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

스크린샷 2022-08-11 오전 11 04 54

✋ 중복 허용 ❌ → r ≤ n

// result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수
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();

🔷 조합 (combination)

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

스크린샷 2022-08-11 오전 11 09 56

✋ 중복 허용 ❌ → r ≤ n

// result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수
function combinationLoop() {
  let lookup = ['A', 'B', 'C', 'D', 'E'];
  let result = [];

  console.log(lookup);

	// 반복 조건이 순열과 다름 (한번 조합한 요소는 다시 조합 X)
  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

🔷 GCD(Greatest Common Divisor)

: 최대공약수로써, 두 수 이상의 여러 공약수 중 최대인 수를 가리킴

🔸 공약수(Common Divisor)
: 두 수 이상의 여러 수 중 공통된 약수(어떤 수를 나누어 떨어지게 하는 수)

🔷 LCM(Lowest Common Multiple)

: 최소공배수로써, 두 수 이상의 여러 공배수 중 최소인 수를 가리킴

🔸 공배수(Common Divisor)
: 두 수 이상의 여러 수 중 공통된 배수(하나의 수에 정수를 곱한 수 ⇒ 그 수에 의해 나누어 떨어지는 수)

🟣 GCD & LCM 구하는 방식

  1. 가장 작은 수들의 곱으로 나타내어 구하는 방법
    : 겹치는 부분이 최소공약수 / 이에 나머지를 곱한 수가 최소공배수
  2. 공약수로 나누어 최대공약수 & 최소공배수를 구하는 방법
    : 공약수로 두 수를 더이상 나눌 수 없을 때까지 나눔
    → 나누는데 사용된 수가 최대공약수 / 이에 더이상 나눌 수 없는 수들을 곱하면 최소공배수
  3. 유클리드 호제법
    : a / b = q + r 식에서 a&b의 최대공약수 = b&r의 최대공약수 성립하는 이론
    👉 b / r = q + r’r / r’ … 과정 반복
    ⇒ 나머지가 0이 되었을 때 나누는 수(r’)가 a & b의 최대공약수
    ✋ a > b 전제조건 존재 (why? 나누었을 때 음수가 나오면 안되기 때문)
     // 유클리드 호제법을 이용하여 최대공약수를 구하는 로직
     function gcd(a, b){
     	// 모든 자연수를 0으로 나누게 되면 리턴되는 값이 Infinity
     	// so, 조건을 b !== 0 로 설정
     	// => b가 0이 될 때까지 반복
     	while(b !== 0){
     		let r = a % b;
     		a = b;
     		b = r;
     	}
     	return a;
     }
     // 유클리드 호제법을 이용해 최소공배수를 구하는 로직
     function lcm(a, b){
     	return a * (b / gcd(a, b));
     }


📎 멱집합

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

  • 원소가 있는지, 없는지 고려하므로 집합 요소가 n개일 때 모든 부분집합 개수는 2^n
  • 순환 구조: 임의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법 (ex-재귀에 응용 가능)
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);


☑️ 정규표현식

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

  • 리터럴 패턴: 슬래시(/)로 감싸서 사용 (슬래시 안의 문자열 = 찾고자 하는 문자열)
    // pattern 변수를 이용하여 'c'를 찾을 수 있음
    let pattern = /c/;
  • 생성자 함수 호출 패턴: RegExp 객체의 생성자 함수를 호출하여 사용

📎 정규식 패턴

정규식 패턴설명
^Line 시작에서 일치 /^abc/
$Line 끝에서 일치 /xyz$/
*0회 이상 연속 반복되는 문자와 가능한 많이 일치. = {0, }
+1회 이상 연속 반복되는 문자와 가능한 많이 일치. = {1, }
+?1회 이상 연속 반복되는 문자와 가능한 적게 일치. = {1}
{3}숫자 3개 연속 일치
{3, 5}3개 이상 5개 이하 연속 일치
[a-z]a~z 사이의 문자 구간에 일치 (영소문자)
[A-Z]A~Z 사이의 문자 구간에 일치 (영대문자)
[0-9]0~9 사이의 문자 구간에 일치 (숫자)
\d숫자 검색. = /[0-9]/
\D숫자가 아닌 문자 검색. = /[^0-9]/
\w영어 대소문자, 숫자, _ 검색. = /[A-Za-z0-9]/
\W영어 대소문자, 숫자, _가 아닌 문자 검색. = /[^A-Za-z0-9]/
[^][]안에 없는 문자 검색

📎 RegExp 객체 메소드

🔸 exec(): execution. 원하는 정보를 뽑아내고자 할 때 사용

  • 검색 대상이 찾고자 하는 문자열에 대한 정보를 가지고 있다면 이를 배열로 반환하며, 찾는 문자열이 없다면 null 반환
let pattern = /c/; // 찾고자 하는 문자열
pattern.exec('coding'); // 검색하려는 대상 전달

// ['c']

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

let pattern = /c/;
pattern.test('coding');

// true

📎 String 객체 메소드

🔸 match(): 정규 표현식을 인자로 받아 주어진 문자열과 일치된 결과를 배열로 반환 / 없으면 null

let pattern = /c/;
let str = 'coding';
str.match(pattern); // str 안에 pattern이 포함되어 있으므로 ['c'] 반환
// = RegExp.exec();

// ['c']

🔸 replace(): 검색 후 바꾸기 수행 (1번째 인자-정규 표현식, 2번째 인자-치환하려는 문자열)

  • 문자열에서 찾고자 하는 대상을 검색해서 이를 치환하려는 문자열로 변경 후 변경된 값 리턴
let pattern = /c/;
let str = 'coding';
str.replace(pattern, 'C');

// 'Coding'

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

"123, 456, 789".split(","); // ["123", "456", "789"]

🔸 search(): 정규표현식을 인자로 받아 가장 처음 매칭 문자열 위치 반환 / 없으면 -1 반환

"coding".search(/odi/); // 1
"coding".search(/Ding/); // -1 (대소문자 구분)

📎 flag

🔸 i: 대소문자 구분 X

let withi = /c/i; // 대소문자 구분 x
let withouti = /c/;

"Coding".match(withi); // ['C'];
"Coding".match(withouti); // null

🔸 g: 검색된 모든 결과 리턴

let withg = /c/g;
let withoutg = /c/;

"coolcoding".match(withg); // ['c', 'c'];
"coolcoding".match(withoutg); // ['c'] (첫번째 검색 결과만 반환)

🔸 m: 다중행 검색

let str = `1st : cool
2nd : coding
3rd : happy`;

str.match(/c/gm); // 3개의 모든 행을 검색하여 모든 c를 반환
// ['c', 'c']

str.match(/c/m) // 다중행 검색 but, 검색 대상을 찾는 순간 검색 멈춤
// ['c'] (첫 행만 반환)

📎 정규식 패턴(표현식)

🔷 Anchors

🔸 ^: 문자열의 처음을 의미 (일치하는 부분이 있어도, 그 부분이 문자열 시작 부분이 아니면 null)

'coding is cool'.match(/^co/); // ['co']
'coding is cool'.match(/^cool/); // null

🔸 $: 문자열 끝 의미 (일치하는 부분이 있어도, 그 부분이 문자열 끝 부분이 아니면 null)

'coding is cool'.match(/ol$/); // ['ol']
'coding is cool'.match(/is$/); // null
'coding is cool'.match(/^coding is cool$/); // ['coding is cool']

🔷 Quantifiers

🔸 *: * 바로 앞 문자가 0번 이상 나타나는 경우 검색

// /ode*/g: 'od'가 들어가면서 그 뒤에 'e'가 0번 이상 포함된 모든 문자열 리턴
"co cod code codee coding codeeeeee codingding".match(/ode*/g);
// ["od", "ode", "odee", "od", "odeeeeee", "od"]

🔸 +: + 바로 앞 문자가 1번 이상 나타나는 경우 검색

"co cod code codee coding codeeeeee codingding".match(/ode+/g);
// ["ode", "odee", "odeeeeee"]

🔸 ?: ? 앞의 문자가 0번/1번 나타나는 경우만 검색

"co cod code codee coding codeeeeee codingding".match(/ode?/g);
// ["od", "ode", "ode", "od", "ode", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode*?/g);
// ["od", "od", "od", "od", "od", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode+?/g);
// ["ode", "ode", "ode"]

🔸 {}: 직접 숫자를 넣어서 연속되는 개수 설정 가능

"co cod code codee coding codeeeeee codingding".match(/ode{2}/g);
// 2개의 "e"를 포함한 문자열 검색
// ["odee", "odee"]

"co cod code codee coding codeeeeee codingding".match(/ode{2,}/g);
// 2개 이상의 "e"를 포함한 문자열 검색
// ["odee", "odeeeeee"]

"co cod code codee coding codeeeeee codingding".match(/ode{2,5}/g);
// 2개 이상 5개 이하의 "e"를 포함한 문자열 검색
// ["odee", "odeeeee"]

🔷 OR operator

"Cc Oo Dd Ee".match(/O|D/g); // ["O", "D"]
"Ccc Ooo DDd EEeee".match(/D+|e+/g); 
// + 는 1번 이상 반복 의미 => ["DD", "eee"]

🔷 Bracket Operator - [] : 대괄호 안에 명시된 값 검색

[abc] // a or b or c 검색
[a-c] // = [abc]

// c or o가 1번 이상 반복된 문자열 반복 검색
"Ccc Ooo DDd EEeee".match(/[co]+/g); // ["cc", "oo"]

🔷 Character classes

🔸 \d: digit. 0~9 사이 숫자 하나 검색 (= [0-9])

🔸 \D: not Digit. 숫자가 아닌 문자 하나 검색 (= [^0-9])

🔸 \w: 알파벳 대소문자, 숫자, 중 하나 검색 (= [a-zA-Z0-9])

🔸 \W: 알파벳 대소문자, 숫자, 가 아닌 문자 하나 검색 (= [^a-zA-Z0-9])

🔷 Grouping & Capturing

🔸 ()

  • 그룹화: () 안의 내용을 하나로 그룹화할 수 있음
  • 캡처
    co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]

🔷 non-capturing - (?:): 그룹은 만들지만 캡처는 하지 않음

🔷 lookahead - (?=): 검색하려는 문자열에 일치하는 문자가 있어야 기호 앞의 문자열 반환

"abcde".match(/ab(?=c)/);
// ab가 c 앞에 있기 때문에 ["ab"] 반환

"abcde".match(/ab(?=d)/);
// d 의 앞은 "abc" 이기 때문에 null 반환

🔷 negated lookahead: (?!) = (?=) 부정

"abcde".match(/ab(?!c)/); // null
"abcde".match(/ab(?!d)/); // ["ab"]
profile
FE developer

0개의 댓글