Unit11 - [자료구조/알고리즘]
시간 복잡도
Big-O 표기법
O(1) : 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.
O(n):입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
O(log n): O(1) 다음으로 빠른 시간 복잡도
BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)
비유: up & down
O(n2): 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
O(2n):Big-O 표기법 중 가장 느린 시간 복잡도
ex)피보나치 수열
공간 복잡도(Space Complexity)
프로로그램이 필요로 하는 메모리 공간을 산출
Algorithm의 유형
Greedy Algorithm
Greedy Algorithm 문제 해결 단계
선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
Algorithm 구현
완전 탐색(brute force):가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식, 매 순간 최적의 선택을 찾는 방식
ex) Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS
시뮬레이션(simulation):문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습
Dynamic Programming(DP, 동적 계획법):모든 경우의 수를 조합해 최적의 해법
하나의 문제는 단 한 번만 풀도록 하는 알고리즘
- Overlapping Sub-problems : 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용
ex) 피보나치 수열
작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.
- Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용한다.
작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수있다.
ex) A->D 최단경로 ( A->B->C->D)
A->C 최단경로 ( A->B->C)
A->B 최단경로 ( A->B)
Algorithm 유형 예제
Brute Force Algorithm:모든 값을 대입하는 방법
지능형 전략 x
무차별 대입 방법을 나타내는 알고리즘
두가지 경우 사용
- 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때
- 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
Brute Force Algorithm의 한계
문제의 복잡도에 매우 민감하다.
순차 검색 알고리즘 (Sequential Search)
- 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.
function SequentialSearch2(arr, k) {
// 검색 키 K를 사용하여 순차 검색을 구현
// 입력: n개의 요소를 갖는 배열 A와 검색 키 K
// 출력: K 값과 같은 요소 인덱스 또는 요소가 없을 때 -1
let n = arr.length; // 현재의 배열 개수를 n에 할당합니다.
arr[n] = k; // 검색 키를 arr n 인덱스에 할당합니다.
let i = 0; // while 반복문의 초깃값을 지정하고
while (arr[i] !== k) { // 배열의 값이 k와 같지 않을 때까지 반복합니다.
i = i + 1; // k와 같지 않을 때 i를 +1 합니다.
}
if (i < n) { // i가 k를 할당하기 전의 배열개수보다 적다면(배열 안에 k 값이 있다면)
return i; // i를 반환합니다.
} else {
return -1; // -1을 반환합니다.
}
}문자열 매칭 알고리즘 (Brute-Force String Matching)
길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
function BruteForceStringMatch(arr, patternArr) {
// Brute Force 문자열 매칭을 구현합니다.
// 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P
// 출력: 일치하는 문자열이 있으면 첫 번째 인덱스를 반환합니다. 검색에 실패한 경우 -1을 반환합니다.
let n = arr.length;
let m = patternArr.length;
for (let i = 0; i <= n - m; i++) {
// 전체 요소 개수에서 패턴 개수를 뺀 만큼만 반복합니다. 그 수가 마지막 비교 요소이기 때문입니다.
// i 반복문은 패턴과 비교의 위치를 잡는 반복문입니다.
let j = 0;
// j는 전체와 패턴의 요소 하나하나를 비교하는 반복문입니다.
while (j < m && patternArr[j] === arr[i + j]) {
// j가 패턴의 개수보다 커지면 안 되기 때문에 개수만큼만 반복합니다.
// 패턴에서는 j 인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
// 같을 때 j에 +1 합니다.
j = j + 1;
}
if (j === m) {
// j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미입니다.
// 이때의 비교했던 위치를 반환합니다.
return i;
}
}
return -1;
}
선택 정렬 알고리즘 (Selection Sort)
전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘
function SelectionSort(arr) {
// 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
// 입력: 정렬 할 수 있는 요소의 배열 A
// 출력: 오름차순으로 정렬된 배열
for (let i = 0; i < arr.length - 1; i++) {
// 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다.
// 현재 값 위치에 가장 작은 값을 넣을 것입니다.
let min = i;
// 현재 인덱스를 최솟값의 인덱스를 나타내는 변수에 할당합니다.
for (let j = i + 1; j < arr.length; j++) {
// 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소와 비교하는 반복문을 구성합니다.
if (arr[j] < arr[min]) {
// j 인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
min = j;
// j 인덱스를 최소를 나타내는 인덱스로 할당합니다.
}
}
// 반복문이 끝났을 때(모든 비교가 끝났을 때)
// min에는 최솟값의 인덱스가 들어있습니다.
// i 값과 최솟값을 바꿔서 할당합니다.
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
// 모든 반복문이 끝나면 정렬된 배열을 반환합니다.
return arr;
}
그외 알고리즘
- 버블 정렬 알고리즘 - Bubble Sort
- Tree 자료 구조의 완전 탐색 알고리즘 - Exhausive Search (BFS, DFS)
- 동적 프로그래밍 - DP(Dynamic Programing)
Dynamic Programming - 피보나치 수열과 타일링
Fibonacci
Recursion + Memoization
Memoization의 정의: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용
결과를 저장하는 방법을 Memoization이라고 한다.
Iteration + Tabulation
Tabulation의 정의: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 리스트(도표)에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법
2x1 타일링
2x1 일때 |
2x2 일때 || =
갈이가 3개인 이상부터
2x3 일때 ||| ,|= , =|
n=2일때 || + | 세로 타일 1개를 추가하는 경우
n=3일때 | + = , = + | 가로 타일 2개를 추가하는 경우의 수
2x4 일때 |||| , ==|| , ||== , =||| , |||=
memo[4] = memo[3] + memo [2]
n=3일때 ||| + | , ||=+| , =|| + | 세로 타일 1개를 추가하는 경우
n=2일때 =+ =|| , ||=+=
function tiling2x1(n) {
let memo = [0, 1, 2];
for (let i = 3; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
};
순열(nPr)
서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것
순열은 조합과 달리 순서도 따져서 부분집합을 만든다.
조합(nCr)
조합(組合, combination)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것
조합은 순서에 상관없이 원소를 선택해 부분집합을 만든다.
GCD와 LCM
GCD: 최대공약수(Greatest Common Divisor, GCD)는 두 수 이상의 여러 공약수 중 최대인 수
최대공약수의 개념 중 공약수는 두 수 이상의 여러 수 중 공통된 약수를 의미
약수(Divisor)는 어떤 수를 나누어떨어지게 하는 수를 의미
여러 개의 공약수 중 최대인 수가 최대공약수
LCM: 최소공배수(Lowest Common Multiple, LCM)는 두 수 이상의 여러 공배수 중 최소인 수
최소공배수의 개념 중 공배수는 두 수 이상의 여러 수 중 공통된 배수를 의미
배수(Multiple)는 하나의 수에 정수를 곱한 수 , 반대로 말해서 배수는 그 수에 의해 나누어 떨어지는 수
여러개의 공배수 중 최소인수가 최소공배수
GCD와 LCM을 구하는 방식
2 | 12 18
-------------------
3 | 6 9
___________
2 3
GCD :6
LCM: 36
유클리드 호제법
최대공약수와 관련이 깊은 공식
두 개의 양의 정수 a와 b (a>b)가 주어졌을 때, a를 b로 나눈 나머지를 r이라고 합니다. 그런 다음, b를 r로 나눈 나머지를 구하고, 이를 b 대신 새로운 값으로 대체합니다. 이 과정을 반복하면서, 어떤 시점에서 r이 0이 되면, 그 때의 b가 a와 b의 최대공약수가 된다.
gcd(a,b) = gcd(b,r)
a/b = q+ rb/r = q + r^2r/r^2= q + 0
r^2가 최대공약수
멱집합
모든 부분집합을 멱집합이라고 한다.
순열과 조합
문제: 카드 뽑기
1.순서를 생각하며 3장을 선택할 때의 모든 경우의 수
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();순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수
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();문제: 소수 찾기
n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성
각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사
소수라면 개수를 센다.
문제: 일곱 난쟁이
명의 난쟁이를 순서를 생각하지 않고, 난쟁이 7명의 키를 합했을 때 100이 되는 경우
GCD와 LCM
유클리드 호제법을 이용해 최대공약수를 구하는 로직
function gcd(a, b){
while(b !== 0){
let r = a % b;
a = b;
b = r;
}
return a;
}유클리드 호제법을 이용해 최소공배수를 구하는 로직
function lcm(a, b){
return a * (b / gcd(a, b));
}문제: Mask States
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있다.
이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취한다.
이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요?
LCM(60, 75, 90)은 900
A 900/60 =15번 135개
B 900/75 = 12번 180개
C 900/90 = 10번 250개
A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개
Power Set
let inputSet = ['a', 'b', 'c'];
function powerSet (arr) {
const result = [];
function recursion (subset, start) {
//subset(현재까지의 부분집합
result.push(subset);
//subset을 result 배열에 추가
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);recursion([...subset, arr[i]], i+1)은 subset 배열과 arr[i]를 이어붙인 새로운 배열 [...subset, arr[i]]을 인자로 하여 recursion 함수를 호출한다.
이렇게 하면 subset 배열에 arr[i]가 포함된 부분집합을 생성할 수 있다.
반면에 recursion(subset.concat(arr[i]), i+1)은 subset 배열과 arr[i]를 이어붙인 새로운 배열 subset.concat(arr[i])을 인자로 하여 recursion 함수를 호출한다. 이렇게 하면 arr[i]가 이미 subset 배열에 포함된 상태에서 arr[i]를 추가한 부분집합을 생성한다.
정규 표현식
문자열에서 특정한 규칙에 따른 문자열 집합을 표현하기 위해 사용되는 형식 언어
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. 정규표현식 사용x
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; // '올바릅니다.'RegExp 객체의 메소드
exex()
하는 정보를 뽑아내고자 할 때 사용
let pattern = /s/;
pattern.exec('software')
//['s'] 로 반환test()
let pattern = /s/;
pattern.test('software');
//true 반환String 객체의 메소드
match()
let pattern = /s/;
let str = 'software';
str.match(pattern);
//['s'] 를 반환replace()
let pattern = /c/;
let str = 'software';
str.replace(pattern, 'S');
//Softwaresplit()
123,456,789".split(",") // ["123", "456", "789"]
"12304560789".split("0") // ["123", "456", "789"]search()
"SoftWare".search(/ware/); // -1
"SoftWare".search(/Ware/); // 4
"SoftWare".search(/oft/); // 1
//가장 처음 매칭되는 부분 문자열의 위치를 반환
flag
i를 붙이면 대소문자를 구분하지 않는다.
let withi = /w/i;
let withouti = /w/;
"SoftWare".match(withi); // ['W']
"SoftWare".match(withouti); // nullg를 붙이면 검색된 모든 결과를 리턴
let withg = /w/g;
let withoutg = /w/;
"sosoftware".match(withg); // ['s', 's']
"sosoftware".match(withoutg); // ['s'] g 가 없으면 첫 번째 검색 결과만 반환m을 붙이면 다중행을 검색
let str = `1st : so
2nd : soft
3rd : ware`;
str.match(/c/gm)
// 3개의 행을 검색하여 모든 s 를 반환
// ['s', 's']
str.match(/s/m)
// m은 다중행을 검색하게 해 주지만, g 를 빼고 검색하면 검색 대상을 찾는 순간 검색을 멈춘다.
// 첫 행의 ['s'] 만 리턴
정규식 패턴(표현식)
Anchors : ^ and $
^는 문자열의 처음을 의미
"software is eazy".match(/^so/); // ['so']
"software is eazy".match(/^eazy/); // null$는 문자열의 끝을 의미
"software is eazy".match(/zy$/); // ['zy']
"software is eazy".match(/is$/); // null
"software is eazy".match(/^"software is eazy"$/);Quantifiers : *, +, ? and {}
*는 * 의 바로 앞의 문자가 0번 이상 나타나는 경우를 검색
"so sot softt soff sofing softtttt softinging".match(/oft*/g);
// ["oftt", "of", "ofttttt", "oft", "oft"]+ 바로 앞의 문자가 1번 이상 나타나는 경우를 검색
"so sot softt soff sofing softtttt softinging".match(/oft*/g);
// ["oftt", "softtttt", "oft"]? 앞의 문자가 0번 혹은 1번 나타나는 경우만 검색
"so sot softt soff sofing softtttt softinging".match(/oft*/g);
//["oftt","ofttttt","oft"]->0번 또는 1번
"co cod code codee coding codeeeeee codingding".match(/oft*?/g);
// ["oftt", "of", "ofttttt", "oft", "oft"] -> 0번
"co cod code codee coding codeeeeee codingding".match(/ofe+?/g);
// ["oftt", "softtttt", "oft"]{}는 직접 숫자를 넣어서 연속되는 개수를 설정
"so sot softt soff sofing softtttt softinging".match(/oft{2}/g
// 2개 t
// ["oftt"]
"so sot softt soff sofing softtttt softinging"".match(/oft{2,}/g);
// 2개 이상 t
// ["oftt", "ofttttt"]
"co cod code codee coding codeeeeee codingding".match(/oft{2,5}/g);
// 2개 이상 5개 이하의 t
// ["oftt", "ofttttt"]OR operator
"Aa Bb Cc Dd".match(/A|D/g); // ["A", "D"]
"Aa Bb Cc Dd".match(/a|d/g); // ["a", "d"]
"Aa Bb Cc Dd".match(/A|d/g); // ["A", "d"]
"Aaa Bb Cc DDd".match(/a+|D+/g); // + 는 1번 이상 반복
// ["aa", "DD"] 를 반환합니다Bracket Operator - []
[abc] // a or b or 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);
// [] 안에 ^ 를 사용하면 부정을 나타내기 때문에 [] 안에 없는 값을 검색합니다.
// ["$#67", "@9"]Character classes
\d 와 \D
\d 의 d 는 digit 을 의미하며 0 ~ 9 사이의 숫자 하나를 검색=>[0-9]
\D 는 not Digit 을 의미하며, 숫자가 아닌 문자 하나를 검색=>[^0-9]
\w 와 \W
\w 는 알파벳 대소문자, 숫자, _(underbar) 중 하나를 검색=>[a-zA-Z0-9_]
\W 는 알파벳 대소문자, 숫자, _ (underbar)가 아닌 문자 하나를 검색=>[^a-zA-Z0-9_]
Grouping and capturing
()
let so = 'soso';
let sooo = 'sooosooo';
so.match(/(so)+/);
//["soso", "so", index: 0, input: "soso", groups: undefined]
sooo.match(/(so)+/);
// ["so", "so", index: 0, input: "sooosooo", groups: undefined]
캡처
so.match(/(so)+/);
//["soso", "so", index: 0, input: "soso", groups: undefined]- () 로 "so"를 캡처
- 캡처한 "so" 는 당장 사용하지 않고, + 가 "so"의 1회 이상 연속 반복을 검색
- 이렇게 캡처 이외 표현식이 모두 작동하고 나면, 캡처해 두었던 "so"를 검색
문자열 대체 시 캡처된 값 참조
non-capturing
(?:)로 사용하면 그룹은 만들지만 캡처는 하지 않는다.
so.match(/(?:so)+/);
//["soso", index: 0, input: "soso", groups: undefined]lookahead
(?=) 는 검색하려는 문자열에 (?=여기) 에 일치하는 문자가 있어야 (?=여기) 앞의 문자열을 반환
"abcde".match(/ab(?=e)/);
// abcd 가 e 앞에 있기 때문에 ["abcd"] 를 반환
"abcde".match(/ab(?=e)/);
// e 의 앞은 "abcd" 이기 때문에 null을 반환negated lookahead
(?!) 는 (?=) 의 부정
"abcde".match(/abcd(?!e)/); // null
"abcde".match(/ab(?!e)/); // ["ab"]