이머시브 코스 TIL 3주차 모음

0307.월

Time Complexity(시간 복잡도)

• 효율적인 방법을 고민 = 시간 복잡도를 고민
• 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성

Big-O 표기법

• 입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가를 표기하는 방법
• O(1) : constant complexity라고 부르며, 입력값이 증가해도 시간은 늘어나지 않음
  입력값이 얼마나 커지는가와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미
• O(n) : linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
• O(log n) : logarithmic complexity라고 부르며 Big-O 표기법 중 O(1) 다음으로 빠른 시간복잡도를 가짐
• O(n^2) : quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 그의 제곱수의 비율로 증가하는 것을 의미
• O(2^n) : exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간복잡도를 가짐

Greedy Algorithm

• 그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식(항상 최적의 결과를 보장하진 XX)

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 우의 과정을 반복

Dynamic Programming(동적 계획법)

• 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식
• Overlapping Sub-problems 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다
• Optimal Substructure 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

• 위의 피보나치 구하는 코드는 작은 문제들을 배열에 저장해놓은 뒤 꺼내서 사용

0309.화

Algorithm with Math

최대 공약수(GCD)와 최소 공배수(LCM)

• 약수 : 어떤 수를 나누어 떨어지게 하는 수 / 배수 : 어떤 수의 1,2,3... 배하여 얻는 수
• 공약수 : 둘 이상의 수들의 공통인 약수 / 공배수 : 둘 이상의 수들의 공통인 배수

순열/조합

• 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5x4x3x2x1) / (2x1) = 60
  일반식 : nPr = n! / (n-r)!
• 5장에서 3장을 선택하는 모든 조합의 수 = 5C3 = 5! / (3!*2!) = 10
  일반식 : nCr = n! / r!(n-r!)

멱집합

• 어떤 집합의 모든 부분 집합

0310.수

Basic CS Hiring Assessment

0311.목 0312.금

<리액트를 다루는 기술> 로 리액트 공부.. 커밋해놈

https://github.com/zzangsemin/study-react