Algorithm : What is the best way to solve the problem?
Time complexity
- 입력값의 증가/감소에 따라 시간이 얼마만큼 비례하여 증가/감소하는가??
- 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘:efficient algorithm
Big-O Notation
- 입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가
- O(1) : constant complexity - 입력값 상관없이 즉시 출력값 얻음
- O(n) : linear complexity - 입력값 증가 시간도 같은 비율로 증가
ex) 입력값이 1일때 1초의 시간이 걸림 - O(log n) : logarithmic complexity - O(1)다음으로 빠른 시간 복잡도
ex)BST의 값 탐색, up&down game
-log의 뜻: 입력값의 몇번곱 - O(n^2) : quadratic complexity - 입력값이 증가 시간이 그의 제곱수비율로 증가
ex) 이중 for문 - O(2^N) : exponential complexity - 가장 느린 시간 복잡도
ex) fibonacci
가장 빠른/느린 시간 복잡도는 무엇일까요? // O(1) / O(2의 n제곱)
효율적인 알고리즘을 구성했다 함은 무엇을 의미할까요? // 입력값의 증가에 따라 증가하는 시간비율을 최소화 되는 것
시간복잡도는 A와 B의 비례함이 어느 정도인지를 나타냅니다. A와 B는 무엇일까요? //입력 값과 실행되는 시간
Greedy Algorithm : 당장 좋은 것만 선택하는 알고리즘
눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법
1. 선택적 절차(Selection Procedure) : 현재 상태에서의 최적의 선택
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사, 해결 안되었으면 다시 1번으로!!!
ex) 동전 거스름돈, 도둑이 훔치는 물건
2가지의 조건을 성립해야 잘 작동한다.
1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substucture) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
Dynamic Programming : 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는다.
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식
Dynamic Programming을 사용하는 조건
- Overlapping Sub-problem : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 큰 문제를 해결하는 데에 중복 가능해야함
ex) 재귀 - Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답은 큰 문제에서도 사용할 수 있다.
- Recusion + Memoization (Top-down 방식)
Memoization(메모화) : 컴퓨터 프로그램이 동일한 계산을 반복해야 할때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 하는 기술 - Iteration + Tabulation(표) (Bottom-up 방식) => 이 방식이 크롬 개발자 도구에서 함수 실행시간 측정을 했을때 가장 시간이 적게 들었다. 그리고 코드로 작성을 했을 때 훨씬 직관적으로 해석을 할수 있다.
크롬 개발자 도구에서 함수 실행 시간 측정 방법
var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
Mathematics basic!!
fibonacci는 여전히 어렵다.
수열이 뭔지에 대해서 검색하다가 알게된 지식들!!
수학이 풀고 싶어진다. 하하하하
등비 = 몇배
등차 = 차이 변화
수열 = 규칙적인 수들의 나열
시그마 = 더한다는 의미
상수 = 언제나 같은 수, 절대 변하지 않는수
예측 => 변화를 파악 => 패턴을 인지(패턴화 위치무시)
수학은 그림으로 그릴수 있어야 한다.
있는 조건을 사용한다.
의미를 파악할 수 있어야 한다.
f(x) = x의 function = x 때문에 변하는 것(커지거나 작아진다) = x는 변화 유발자
sine = 높이는 걸어간 거리의 몇배
sin 30 = 1/2
sin 90 = 1
sin 0 = 0
sin 150(180-30) = 1/2
co각 = 90도
30도의 co각 = 60도
sin(90-x) = x의 co의 sine = x의 cosine = cosin x = cos x
cos(90-x) = x의 co의 co의 sine = x의 sine = sin x
sin(90-x) = cosx
cos(90-x) = sinx
It was from Quebong!!
I like the QUEBONG Mathematics!!
