[TIL] Day74 #알고리즘 #시간복잡도 #공간복잡도 #Greedy #Brute-Force #DP

Beanxx·2022년 8월 10일
TILalgorithm
0

TIL

목록 보기
74/120
post-thumbnail

2022.08.10(Wed)

[TIL] Day74
[SEB FE] Day75

☑️ Algorithm

: 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법
👉 input 값을 통해 output 값을 얻기 위한 계산 과정

  • 입력(Input): 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 함.
  • 출력(Output): 알고리즘은 실행이 되면 적어도 1가지 이상의 결과를 반드시 출력해야 함.
  • 유한성(Finiteness): 알고리즘은 유한한 명령어 수행 후, 유한한 시간 내에 종료해야 함. ⇒ 실행된 후엔 반드시 종료되어야 함
  • 명확성(Definiteness): 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해선 안됨.
  • 효율성(Efficiency): 알고리즘은 가능한 한 효율적이어야 함. (시간&공간 복잡도 ⬇️ ⇒ 효율적 알고리즘)

☑️ 시간 복잡도(Time Complexity)

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

효율적인 알고리즘을 구현한다
👉 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성

📎 Big-O 표기법

  • 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,000O(n) / O(logn)
n ≤ 10,000O(n^2)
n ≤ 500O(n^3)

☑️ 공간 복잡도(Space Complexity)

알고리즘이 수행되는 데에 필요한 메모리 총량
👉 프로그램이 필요로 하는 메모리 공간을 산출하는 것

➰ 프로그램이 요구하는 공간 =
     고정적인 공간(데이터 양과 무관하게 항상 요구되는 공간)
➕ 가변적 공간(처리할 데이터 양에 따라 다르게 요구되는 공간 → 프로그램 성능에 큰 영향을 줌)

// 재귀함수로 구현된 factorial 함수
function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}

// 1까지 호출할 경우 n~1까지 스택에 쌓임 -> 공간 복잡도: O(n)

☑️ Algorithm 유형

📎 Greedy Algorithm

선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
👉 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식

  1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답 선택
  2. 적절성 검사(Feasibility Check): 선택된 해가 문제 조건을 만족하는지 검사
  3. 해답 검사(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

📎 Algorithm 구현

🔹 완전 탐색

: 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식

  • Brute Force Algorithm(무차별 대입): 모든 가능성을 시도하여 문제를 해결하는 방법
    • 시간복잡도 & 공간복잡도 요소 고려 X → 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법
    • 👎 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘

    1. 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때 사용

    2. 문제를 해결하는 여러 솔루션이 있고, 각 솔루션을 확인해야 할 때 사용

      🔸 순차 검색 알고리즘(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 ]
  • 재귀, 순열, DFS/BFS …

🔹 Simulation
: 모든 과정과 조건 제시 → 그 과정을 거친 결과가 무엇인지 확인하는 유형
👉 문제에서 요구하는 복잡한 구현 요구사항을 코드로 옮겨, 마치 시뮬레이션하는 것과 같은 구현 방식

📎 Dynamic Programming(DP, 동적 계획법)

: 모든 경우의 수를 조합하여 최적의 해법을 찾음
👉 주어진 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제 해결
👉 하위 문제 계산 후 그 해결책을 저장하고, 나중에 동일 하위 문제를 만날 경우 저장된 해결책 적용 → 계산 횟수 줄임
🧙 하나의 문제는 단 한 번만 풀도록 하는 알고리즘!!

✋ 이 때 결과를 저장하는 방법 ⇒ memoization

✋ DP는 아래의 2가지 가정이 만족하는 조건에서 사용 가능!

  1. Overlapping Sub-problems
    : 큰 문제로부터 나누어진 작은 문제는 큰 문제 해결시 여러번 반복해서 사용될 수 있어야 함
    - ex - 피보나치 수열 문제
  2. Optimal Substructure
    : 문제의 최적 해법(Optimal solution)을 구할 때, 주어진 문제의 작은 문제들의 최적 해법(Optimal solution of Sub-problems)을 찾아야 함
    👉 작은 문제들의 최적 해법을 결합하면, 결국 전체 문제의 최적 해법을 구할 수 있음!
    - ex - 최단 경로 찾는 문제

🔸 Fibonacci

  1. 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)

  1. 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 방식 함수 실행 시간

  • Bottom-up 방식 함수 실행 시간

✅ 코플릿 문제는 Github에 따로 정리해놓기!

profile
Beanxx
FE developer
이전 포스트

[TIL] Day73 #AWS #CodePipeline

다음 포스트

[TIL] Day75 #알고리즘 #순열 #조합 #GCD #LCM #멱집합 #정규표현식

0개의 댓글