Algorithm의 개념2

 

목차

 

 

 

 

 

 

📌  Algorithm의 개념

 

 

문제를 해결하는 최선의 선택

 

 

📍순열과 조합

 

순열

 

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

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

 

순열의 식

 

P - Permutation n - 원소의 총개수 r -  그 중 뽑은 개수

순열은 중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다.

 

 

 

조합

 

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

순서에 상관없이 원소를 선택해 부분집합을 만든다.

 

 

조합의 식

 

C - Combination n - 원소의 총개수 r -  그 중 뽑은 개수

조합 또한 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다

 

 

 

📍 GCD,  LCM

 

 

최대공약수와 최소공배수

 

 

🔗 GCD(Greatest Common Divisior)

 

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

💁🏼‍♂️ 공약수란? 두 수 이상의 여러 수 중 공통된 약수를 의미

예를 들어, 6과 9의 최대공약수는? 3이다.

 

 

 

🔗 LCM(Lowest Common Multiple)

 

최소 공약수 : 두 수 이상의 여러 공배수 중 최소의 수

💁🏼‍♂️ 공배수란? 두 수 이상의 여러 수 중 공통된 배수를 의미

예를 들어, 12와 18의 최소공배수는 36이다.

 

 

🔗 GCD와 LCM을 구하는 방식

 

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

 

 

2와 3을 곱한 수인 6이 최대공약수이고, 6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수이다.

 

 

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

 

 

2와 3이 공약수이므로 2와 3을 곱하면 6인 최대공약수, 더 이상 나눌 수 없는 수들의 총 곱인 36이 최소공배수이다.

 

 

유클리드 호제법

 

가장 많이 사용되는 유형, 최대공약수와 관련이 깊은 공식이다.

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론

이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게 된다.

 

 

 

📍 멱집합

 

집합의 모든 부분집합을 멱집합이라 한다.

 

 

---

• 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}

 

 

멱집합을 찾는 과정 모식도

 

 

📍 정규표현식

 

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

 

 

이메일 유효성 검사

 

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; // '올바릅니다.'

 

휴대전화 번호 유효성 검사

 

let regExp = /^01([0|1|6|7|8|9]?)-?([0-9]{3,4})-?([0-9]{4})$/;

 

 

🔗  리터럴 패턴

 

정규표현식 규칙을 슬래시(/)로 감싸 사용

슬래시 안에 들어온 문자열이 찾고자 하는 문자열이며, 컴퓨터에게 '슬래시 사이에 있는 문자열을 찾고 싶어!'라고 명령을 내리는 것

 

let pattern = /c/;
// 'c 를 찾을 거야!' 라고 컴퓨터에게 명령을 내리는 것
// 찾고 싶은 c를 pattern 이라는 변수에 담아놨기 때문에 이 변수를 이용하여 c 를 찾을 수 있다.

 

🔗  생성자 함수 호출 패턴

 

RegExp 객체의 생성자 함수를 호출하여 사용

 

 

정규식	패턴설명
^	줄(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]/ 와 동일
[^]	[]안의 문자열 앞에 ^이 쓰이면, []안에 없는 문자를 검색함