오늘 배운 것

• Algorithm with Math : 순열, 조합
• Algorithm with Math : 멱집합
• 정규표현식

Algorithm with Math : 순열, 조합

순열

정의

서로 다른 n개의 무언가 중 r개를 골라 순서를 고려해 나열한 경우의 수
순서를 생각하며 나열하는 것이 중요하다.

순열이라는 의미의 영어 Permutation의 첫 글자인 P를 따서 nPr로 표시한다.

계산

예시 문제

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

접근 방법
1. n개의 숫자 중 1~k개를 뽑아 순열을 생성한다.
2. 각 순열을 정수로 변환하고 해당 정수가 중복되지 않도록 하여 소수인지 검사한다.
3. 소수이면 개수를 센다

조합

정의

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 고를 때 n개에서 r개를 택하는 조합이라 한다.
순서를 생각하지 않는 것이 중요하다.

조합이라는 의미의 영어 Combination의 첫 글자인 C를 따서 nCr로 표시한다.

계산

예시 문제

문제
왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다.
일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것입니다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다.
백설 공주는 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈습니다.
아홉 난쟁이의 키를 줬을 때, 원래 백설 공주를 돕는 일곱 난쟁이를 찾는 방법은 무엇인가요?

접근 방법
일곱 난쟁이의 키의 합이 100이라고 주어졌기 때문에,
9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고 그 합이 100이 되는 경우를 찾는다.

Algorithm with Math : 멱집합

정의

어떠한 집합의 모든 부분집합을 멱집합이라고 부른다.
집합 {1, 2, 3}이 있다고 했을 때
멱집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이고 개수는 8개이다.

모든 부분집합을 나열하는 방법

단계를 나누는 기준
가장 앞 원소(혹은 임의의 집합 원소)의 유무로 단계를 구분한다.

멱집합을 구하는 단계를 잘 살펴보면 순환 구조를 확인할 수 있다.
임의의 원소를 제외하며 집합을 작은 단위로 줄여 나가는 방법이다 (재귀)

정규표현식

정의

문자열에서 특정한 문자를 찾아내는 도구이다.
정규표현식은 특정한 규칙을 갖는 문자열로 이루어진 표현식이며,
정규표현식에서 특수문자는 각각의 고유한 규칙을 갖고 있다.
이러한 규칙들을 조합하여 원하는 패턴을 만들고, 특정 문자열에서 해당 패턴과 대응하는 문자를 찾을 수 있다.

정규표현식의 규칙

정규표현식 사용하기

정규표현식은 두가지 방법으로 사용할 수 있다.

리터럴 패턴
정규표현식 규칙을 슬래시(/)로 감싸 사용한다.
슬래시 안에 들어온 문자열이 찾고자 하는 문자열이다.

let pattern = /c/;

생성자 함수 호출 패턴
RegExp 객체의 생성자 함수를 호출하여 사용한다.

let pattern = new RegExp('c');

new를 이용하여 정규 표현식 객체를 생성하고, 찾고자 하는 문자열을 인자로 넣는다.

정규표현식 내장 메소드

RegExp 객체의 메소드
exec()
원하는 정보를 뽑아내고자 할 때 사용한다.
검색의 대상이 찾고자 하는 문자열에 대한 정보를 가지고 있다면, 이를 배열로 반환한다.
찾는 문자열이 없다면 null을 반환한다.

let pattern = /c/
pattern.exec('i am a trainee developer')

test()
찾고자 하는 문자열이 대상에 포함되어 있는 지 여부를 boolean으로 리턴한다.

let pattern = /c/;
pattern.test('coding is funny. but hard')

String 객체의 메소드
match()
RegExp.exec()와 동일한 기능을 수행한다.

let pattern = /c/;
let str = 'i am so hungry';
str.match(pattern);

replace()
검색 후 바꾸기를 수행한다.
첫번째 인자로는 정규표현식을 받고, 두번째 인자로는 치환하려는 문자열을 받는다.
문자열에서 찾고자 하는 대상을 검색하여 입력받은 문자열로 치환한 뒤 변경된 값을 리턴한다.

let pattern /c/;
let str = 'codestates'
str.replace(pattern, 'C')
// c를 C로 바꾸는 명령. 'Codestates'가 반환된다.

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

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

search()
정규표현식을 인자로 받아 가장 처음 매칭되는 부분 문자열의 위치를 반환한다.
매칭되는 문자열이 없으면 -1을 반환한다.

"JavaScript".search(/script/); // -1 대소문자를 구분한다
"JavaScript".search(/Script/); // 4
"codestates".search(/ode/); // 1

flag

플래그는 추가적인 검색 옵션의 역할을 한다.
각자 혹은 함께 사용하는 것이 모두 가능하며, 순서에 구분이 없다.
i
i를 붙이면 대소문자를 구분하지 않는다.

let withi = /c/i;
let withouti = /c/;
"Codestates".match(withi); // ['C']
"Codestates".match(withouti); // null

g
검색된 모든 결과를 리턴한다.

let withg = /c/g;
let withoutg = /c/;
"coolcodestates".match(withg); // ['c', 'c']
"coolcodestates".match(withoutg); // ['c'] g 가 없으면 첫 번째 검색 결과만 반환

m
다중 행을 검색한다.

let str = `1st : cool
2nd : code
3rd : states`;
str.match(/c/gm)
// 3개의 행을 검색하여 모든 c 를 반환합니다.
// ['c', 'c']
str.match(/c/m)
// m은 다중행을 검색하게 해 주지만, g 를 빼고 검색하면 검색 대상을 찾는 순간 검색을 멈추기 때문에
// 첫 행의 ['c'] 만 리턴합니다.

정규표현식 패턴

^ 줄(Line)의 시작에서 일치 /^abc/
$ 줄(Line)의 끝에서 일치 /xyz$/
. (특수기호, 띄어쓰기를 포함한) 임의의 한 문자
a|b a or b 와 일치, 인덱스가 작은 것을 우선 반환
* 0회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {0,} 와 동일
*? 0회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일
+ 1회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {1,} 와 동일
+? 1회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일
{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]/ 와 동일
[^] []안의 문자열 앞에 ^이 쓰이면, []안에 없는 문자를 검색함

Anchors

^
문자열의 처음을 의미하며, 문자열에서 ^ 뒤에 붙은 단어로 시작하는 부분을 찾는다.
일치하는 부분이 있더라도, 그 부분이 문자열의 시작부분이 아니면 null 을 리턴한다.

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

$
문자열의 끝을 의미하며, 문자열에서 $앞의 표현식으로 끝나는 부분을 찾는다.
^와 비슷하지만 ^는 문자열의 시작을 찾는 반면, $는 문자열의 마지막 부분을 찾는다.
마찬가지로 일치하는 부분이 있더라도, 그 부분이 문자열의 끝부분이 아니면 null 을 리턴한다.

"coding is fun".match(/un$/); // ['un']
"coding is fun".match(/is$/); // null
"coding is fun".match(/^coding is fun$/);
// 문자열을 ^ 와 $ 로 감싸주면 그 사이에 들어간 문자열과 정확하게 일치하는 부분을 찾습니다
// ["coding is fun"]

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"]

{}
{}는 *, *?, +, +? 의 확장판으로 생각할 수 있다.
*, *?, +, +? 가 '0개 이상' 또는 '1개 이상' 검색이 전부였던 반면,
{}는 직접 숫자를 넣어서 연속되는 개수를 설정할 수 있다.

"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
| 는 or 조건으로 검색하여 | 의 왼쪽 또는 오른쪽의 검색 결과를 반환한다.

"Cc Oo Dd Ee".match(/O|D/g); // ["O", "D"]
"Cc Oo Dd Ee".match(/c|e/g); // ["c", "e"]
"Cc Oo Dd Ee".match(/D|e/g); // ["D", "e"]
"Ccc Ooo DDd EEeee".match(/D+|e+/g); // + 는 1번 이상 반복을 의미하기 때문에
// ["DD", "eee"] 를 반환합니다.

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

[abc] // a or b or c 를 검색합니다. or(|) Operator 로 작성한 a|b|c 와 동일하게 작동합니다.
[a-c] // [abc] 와 동일합니다. - 로 검색 구간을 설정할 수 있습니다.

"Ccc Ooo DDd EEeee".match(/[CD]+/g); // [] 에 + 등의 기호를 함께 사용할 수도 있습니다.
// C or D 가 한번 이상 반복된 문자열을 반복 검색하기 때문에
// ["C", "DD"] 가 반환됩니다.

"Ccc Ooo DDd EEeee".match(/[co]+/g); // ["cc", "oo"]
"Ccc Ooo DDd EEeee".match(/[c-o]+/g); // - 때문에 c ~ o 구간을 검색하여
// ["cc", "oo", "d", "eee"] 가 반환됩니다.

"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Za-z]+/g); 
// a~z 또는 A~Z 에서 한번 이상 반복되는 문자열을 반복 검색하기 때문에
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"] 를 반환합니다.
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Z]+/gi);
// flag i 는 대소문자를 구분하지 않기 때문에 위와 동일한 결과를 반환합니다.
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"]

"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[0-9]+/g);
// 숫자도 검색 가능합니다.
// ["12", "54"]

"aAbB$#67Xz@9".match(/[^a-zA-Z]+/g);
// [] 안에 ^ 를 사용하면 anchor 로써의 문자열의 처음을 찾는것이 아닌 
// 부정을 나타내기 때문에 [] 안에 없는 값을 검색합니다.
// ["$#67", "@9"]

Character classes
\d & \D
\d 의 d 는 digit 을 의미하며 0 ~ 9 사이의 숫자 하나를 검색한다. [0-9] 와 동일하다.
\D 는 not Digit 을 의미하며, 숫자가 아닌 문자 하나를 검색합니다. [^0-9] 와 동일하다.

"abc34".match(/\d/); // ["3"]
"abc34".match(/[0-9]/) // ["3"]
"abc34".match(/\d/g); // ["3", "4"]
"abc34".match(/[0-9]/g) // ["3", "4"]
"abc34".match(/\D/); // ["a"]
"abc34".match(/[^0-9]/); // ["a"]
"abc34".match(/\D/g); // ["a", "b", "c"]
"abc34".match(/[^0-9]/g); // ["a", "b", "c"]

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

"ab3_@A.Kr".match(/\w/); //["a"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/) // ["a"]
"ab3_@A.Kr".match(/\w/g); //["a", "b", "3", "_", "A", "K", "r"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/g) // ["a", "b", "3", "_", "A", "K", "r"]

"ab3_@A.Kr".match(/\W/); // ["@"]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/); // ["@"]
"ab3_@A.Kr".match(/\W/g); // ["@", "."]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/g); // ["@", "."]

Grouping and capturing
()
()는 그룹으로 묶는다는 의미 이외에도 다른 몇가지 의미가 더 있다.

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

let co = 'coco';
let cooo = 'cooocooo';

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

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

co+ 는 "c"를 검색하고 + 가 "o"를 1회 이상 연속으로 반복되는 문자를 검색해 주기 때문에 "cooo"가 반환되었다.
하지만 (co)+ 는 "c" 와 "o" 를 그룹화하여 "co"를 단위로 1회 이상 반복을 검색하기 때문에 "coco"가 반환되었다.
여기서 특이한 점은 일치하는 문자열로 반환된 결과가 2개 이다.

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

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

1. () 로 "co"를 캡쳐
2. 캡쳐한 "co" 는 일단 당장 사용하지 않고, + 가 "co"의 1회 이상 연속 반복을 검색
3. 이렇게 캡쳐 이외 표현식이 모두 작동하고 나면, 캡쳐해 두었던 "co"를 검색

따라서 2번 과정에 의해 "coco" 가 반환되고, 3번에 의해 "co"가 반환되는 것.

문자열 대체 시 캡쳐된 값 참조
캡쳐된 값은 replace() 메소드를 사용하여 문자 치환 시 참조 패턴으로 사용될 수 있다.
아래 예시를 보면, 우선 첫 번째 (\w+) 가 code 를 캡쳐하고,
두 번째 (\w+) 가 states 를 캡쳐한다.
(/(\w+)\ 와 (\w+)/\사이의 . 은 . 앞에 역슬래시가 사용되었기 때문에
'임의의 한 문자'가 아닌 기호로써의 온점 . 을 의미한다.
각 캡쳐된 값은 첫 번째는 $1 이 참조, 두 번째는 $2 이 참조하기 때문에
이 참조된 값을 "$2.$1" 이 대체하게 되어 code 와 states 가 뒤바뀐 "states.code" 가 반환된다.

"code.states".replace(/(\w+)\.(\w+)/, "$2.$1"); //states.code

non-capturing
() 를 사용하면 그룹화와 캡쳐를 한다. 하지만 (?:)로 사용하면 그룹은 만들지만 캡쳐는 하지 않는다.

let co = 'coco';

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

co.match(/(?:co)+/); 
// ["coco", index: 0, input: "coco", groups: undefined]
// 위 "캡쳐" 예시의 결과값과 비교해 보시기 바랍니다.

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"]