2022.08.10(Wed)
[TIL] Day74
[SEB FE] Day75
: 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법
👉 input 값을 통해 output 값을 얻기 위한 계산 과정
Input
): 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 함.Output
): 알고리즘은 실행이 되면 적어도 1가지 이상의 결과를 반드시 출력해야 함.Finiteness
): 알고리즘은 유한한 명령어 수행 후, 유한한 시간 내에 종료해야 함. ⇒ 실행된 후엔 반드시 종료되어야 함Definiteness
): 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해선 안됨.Efficiency
): 알고리즘은 가능한 한 효율적이어야 함. (시간&공간 복잡도 ⬇️ ⇒ 효율적 알고리즘)입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
효율적인 알고리즘을 구현한다
👉 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성
Big-O
(빅-오) - 최악의 경우 (가장 자주 사용!)Big-Ω
(빅-오메가) - 최선의 경우Big-θ
(빅-세타) - 중간(평균)의 경우🔸 O(1)
constant complexity
: 입력값이 증가하더라도 시간이 늘어나지 않음
👉 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미
function O_1_algorithm(arr, index) {
return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2
🔸 O(n)
linear complexity
: 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}
✋ 입력값 1 증가 → 실행시간 2초씩 증가해도 O(2n)이 아닌 O(n)으로 표기
ㄴ🤷♀️ why? 입력값이 커지면 커질수록 계수 의미가 점점 퇴색 → 10배 증가해도 O(n)으로 표기!
🔸 O(log n)
logarithmic complexity
ex)BST
값 탐색 - 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬
🔸 O(n^2)
quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}
function another_O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
// do something for 1 second
}
}
}
}
✋ n^5과 n^10 모두 O(n^2)로 표기 (n이 커질수록 지수가 주는 영향력 점점 퇴색되기 때문)
🔸 O(2^n)
exponential complexity
Big-O 표기법 중 가장 느린 시간 복잡도를 가짐
// 재귀로 구현하는 피보나치 수열
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
➰ 데이터 크기에 따른 시간 복잡도
데이터 크기 제한 | 예상되는 시간 복잡도 |
---|---|
n ≤ 1,000,000 | O(n) / O(logn) |
n ≤ 10,000 | O(n^2) |
n ≤ 500 | O(n^3) |
알고리즘이 수행되는 데에 필요한 메모리 총량
👉 프로그램이 필요로 하는 메모리 공간을 산출하는 것
➰ 프로그램이 요구하는 공간 =
고정적인 공간
(데이터 양과 무관하게 항상 요구되는 공간)
➕ 가변적 공간
(처리할 데이터 양에 따라 다르게 요구되는 공간 → 프로그램 성능에 큰 영향을 줌)
// 재귀함수로 구현된 factorial 함수
function factorial(n) {
if(n === 1) {
return n;
}
return n*factorial(n-1);
}
// 1까지 호출할 경우 n~1까지 스택에 쌓임 -> 공간 복잡도: O(n)
선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
👉 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식
Selection Procedure
): 현재 상태에서의 최적의 해답 선택Feasibility Check
): 선택된 해가 문제 조건을 만족하는지 검사Solution Check
): 문제가 해결되었는지 검사 & IF 해결 X → 선택 절차로 돌아가 과정 반복🔸 탐욕 알고리즘 특징
Greedy Choice Property
): 앞의 선택이 이후의 선택에 영향을 주지 않음Optimal Substructure
): 문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성됨✋ 위의 2가지 조건을 만족하는 특정한 상황이 아니면 최적의 해를 보장하지 못함
// Greedy Algorithm - 거스름돈
function keepTheChange(input) {
// 거스름돈
// 1000엔을 지불했다는 가정 존재
let change = Number(1000 - input);
let count = 0;
// 잔돈으로 줄 동전 단위를 배열에 저장
const joiCoins = [500, 100, 50, 10, 5, 1];
// 위의 배열 크기만큼 반복
for (let i = 0; i < joiCoins.length; i++) {
// 거스름돈이 0원이 되면 순회 멈춤
if (change === 0) {
break;
}
// 쓰인 잔돈 개수 카운팅
count += Math.floor(Number(change / joiCoins[i]));
// 나머지 재할당
change %= joiCoins[i];
}
return count;
}
console.log(keepTheChange(380)); // 4
console.log(keepTheChange(1)); // 15
🔹 완전 탐색
: 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식
Brute Force Algorithm
(무차별 대입): 모든 가능성을 시도하여 문제를 해결하는 방법프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때 사용
문제를 해결하는 여러 솔루션이 있고, 각 솔루션을 확인해야 할 때 사용
🔸 순차 검색 알고리즘(Sequential Search)
: 배열 안에 특정 값이 존재하는지 검색할 때 index 0~ 마지막 index까지 차례대로 검색
function SequentialSearch(arr, k) {
// 검색 키 k를 사용하여 순차 검색 구현
// Input: n개의 요소를 갖는 배열 arr와 검색 키 k
// Output: K값과 같은 요소 인덱스 / 요소가 없을 때 -1
let n = arr.length; // 배열 개수 n에 할당
arr[n] = k; // 검색 키 k를 arr의 n index에 할당 (arr 마지막 요소로 k 추가)
let i = 0;
// 배열 arr 값이 k와 같지 않을 때까지 반복 => k와 같으면 반복 stop
while (arr[i] !== k) {
i++; // k와 같지않으면 i++
}
// k를 배열 arr에 할당하기 전의 배열 개수보다 적다면 (배열 내에 k값이 이미 존재한다면)
if (i < n) {
return i; // i(k가 있는 index) 반환
} else {
return -1; // 배열 내에 k가 없다면 -1 반환
}
}
console.log(SequentialSearch([7, 2, 9, 5, 3, 8, 9], 8));
🔸 문자열 매칭 알고리즘(Brute-Force String Matching)
: 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지 검색
function BruteForceStringMatch(arr, patternArr) {
// Brute Force 문자열 매칭 구현
// Input: n개의 문자 텍스트를 나타내는 배열 arr, m개의 문자 패턴을 나타내는 배열 patternArr
// Output: 일치하는 문자열이 있으면 첫번째 인덱스를 반환 / 검색에 실패한 경우 -1 반환
let n = arr.length;
let m = patternArr.length;
// i - 패턴과 비교의 위치를 잡는 반복문
// 전체 요소 개수 - 패턴개수 만큼 반복 => 그 수가 마지막 비교요소이므로!
for (let i = 0; i < n - m; i++) {
let j = 0;
// j - 전체와 패턴의 요소 하나하나를 비교하는 반복문
// j가 패턴 개수보다 커지기 전까지 반복
while (j < m && patternArr[j] === arr[i + j]) {
// patternArr[j] === arr[i+j] <- 만족하면 즉, 같아지면 j++;
j++;
}
// 패턴 문자열과 완전히 같은 부분이 존재함을 의미
if (j === m) {
return i; // 비교했던 위치 즉, 패턴 일치 시작 index 반환
}
}
return -1; // 일치하는 패턴이 없으면 -1 반환
}
console.log(
BruteForceStringMatch(
["A", "B", "C", "D", "B", "D", "B", "C", "C", "D", "B", "D", "A"],
["C", "D", "B", "D"]
)
); // 2
🔸 선택 정렬 알고리즘 (Selection Sort)
: 전체 배열 검색 → 현재 요소와 비교 → 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소를 교환하는 정렬 알고리즘
function SelectionSort(arr) {
// 주어진 배열을 Selection Sort로 오름차순 정렬
// Input: 정렬 가능한 요소의 배열 arr
// Output: 오름차순으로 정렬된 배열
// 배열 arr의 index 0 ~ 마지막 index까지 반복
for (let i = 0; i < arr.length - 1; i++) {
// 현재 index를 최소값 index를 나타내는 변수에 할당
let min = i;
// i 이후의 배열요소과 비교하는 반복문
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// j index를 최소값의 index로 재할당
min = j;
}
}
// 모든 비교가 끝난 후, min에는 최소값의 index가 할당되어 있음.
// i값과 최소값을 바꿔서 할당해줌.
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
// 정렬된 배열 반환
return arr;
}
console.log(SelectionSort([9, 4, 8, 3, 1, 5]));
// [ 1, 3, 4, 5, 8, 9 ]
🔹 Simulation
: 모든 과정과 조건 제시 → 그 과정을 거친 결과가 무엇인지 확인하는 유형
👉 문제에서 요구하는 복잡한 구현 요구사항을 코드로 옮겨, 마치 시뮬레이션하는 것과 같은 구현 방식
: 모든 경우의 수를 조합하여 최적의 해법을 찾음
👉 주어진 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제 해결
👉 하위 문제 계산 후 그 해결책을 저장하고, 나중에 동일 하위 문제를 만날 경우 저장된 해결책 적용 → 계산 횟수 줄임
🧙 하나의 문제는 단 한 번만 풀도록 하는 알고리즘!!
✋ 이 때 결과를 저장하는 방법 ⇒memoization
✋ DP는 아래의 2가지 가정이 만족하는 조건에서 사용 가능!
Overlapping Sub-problems
Optimal Substructure
🔸 Fibonacci
Recursion
+ Memoization
(= Top-down
방식)Memoization
: 이전에 계산한 값을 메모리에 저장함으로써 동일 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
function fibMemo(n, memo = []) { // []: 하위 문제 결과값을 저장하는데 사용
// 이미 해결한 하위 문제인지 찾아보기
// memo[n]을 이전에 계산하여 이미 존재한다면 저장되어 있는 값을 그대로 사용
if(memo[n] !== undefined) {
return memo[n];
}
if(n <= 2) {
return 1;
}
// undefined라면 즉, 첨 계산하는 수라면 재귀로 결괏값을 도출하여 변수에 할당
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 추후 동일 문제를 만났을 때 사용하기 위해 return 전에 memo에 저장
memo[n] = res;
return res;
}
// memorization 사용한 피보나치 문제의 시간 복잡도: O(N)
// 그냥 재귀 함수로만 풀었을 때의 시간 복잡도: O(2^N)
Iteration
+ Tabulation
(= Bottom-up 방식)
Tabulation
: 제일 작은 값부터 구하여 리스트에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술function fibTab(n) {
if(n <= 2) {
return 1;
}
// n = 1 & 2일 때의 값을 미리 배열에 저장
// 피보나치 수열은 1부터 시작이지만 index는 0부터 시작이므로
// 0번째 index엔 dummy data = 0 삽입
let fibNum = [0, 1, 1];
// n >= 3 부턴 앞서 배열에 저장해놓은 값 이용
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
}
return fibNum[n];
}
➕ Chrome 개발자 도구에서 함수 실행 시간 측정해보기
var t0 = performance.now();
fibMemo(50); // Top-down 방식 함수 실행
fibTab(50); // Bottom-up 방식 함수 실행
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
// Top-down 방식보다 Bottom-up 방식이 더 효율적?
Top-down 방식 함수 실행 시간
✅ 코플릿 문제는 Github에 따로 정리해놓기!