2022.08.11(Thurs)
[TIL] Day75
[SEB FE] Day76
☑️ Algorithm with Math
📎 순열 & 조합
🔷 순열 (permutation)
: 서로 다른 n개 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개 원소를 선택하거나 나열하는 것
👉 조합과 같이 n개 원소로 이루어진 집합에서 r개 원소로 이루어진 부분집합을 만드는 것과 같음
✋ 중복 허용 ❌ → 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개 원소로 이루어진 부분집합을 만드는 것과 같음
✋ 중복 허용 ❌ → 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 구하는 방식
- 가장 작은 수들의 곱으로 나타내어 구하는 방법
: 겹치는 부분이 최소공약수 / 이에 나머지를 곱한 수가 최소공배수 - 공약수로 나누어 최대공약수 & 최소공배수를 구하는 방법
: 공약수로 두 수를 더이상 나눌 수 없을 때까지 나눔
→ 나누는데 사용된 수가 최대공약수 / 이에 더이상 나눌 수 없는 수들을 곱하면 최소공배수 유클리드 호제법
: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"]