210308_TIL

seungyeon·2021년 3월 8일

목록 보기

32/64

IM: DAY 15

Awesome한 날이었다. 주말 동안 꿈에서도 백트래킹 타령을 할 정도로 연구했는데 오늘 페어님과 4시간동안 알고리즘을 한 문제 밖에 못풀었다. 정규 세션이 끝나고 개인 학습 시간과 스터디시간을 통해 두문제를 더 해결했지만 아직 DP 한 문제가 남아있다.. 오늘 풀고 잘 수 있을까 ㅇㅅㅇ
IM 코스에 들어오고 나서 매일이 쉽지 않았지만, 오늘은 다같이 멘탈의 위협을 받은 날이었던 것 같다. 그래도 다같이 흔들렸던만큼 동기들과 더 많이 대화를 하면서 불안감도 없애고 전우애(?)를 다질 수 있어서 엄청 힘들지만은 않은 날이 되었다. THANK U 🙏 LOVE U 💕

오늘 한 일

Algorithm 학습
- Time Complexity
- Greedy Algorithm
  - 최소비용 신장 트리
  - Kruskal 알고리즘
- Dynamic Programming
  - Recursion
  - Recursion + Memoization (Top-down 방식)
  - Iteration + Tabulation (Bottom-up 방식)
- 크롬 개발자 도구에서 함수 실행 시간 측정 방법
Coplit - Algorithm 풀기 #13~#15

기억할 것

Algorithm

알고리즘은 '문제를 어떤 식으로 푸는 것이 최선인가'로 정의할 수 있다.

Time Complexity

시간복잡도의 빠른 순서

O(1) →O(logn) → O(n) → O(nlogn) → O(n^2) → O(n^3) → O(2^n) → O(n!)
- O(1)은 배열의 길이에 상관없이 맨 앞(혹은 맨 뒤 혹은 특정 인덱스)만 뽑아라 같은 경우에 해당하는 시간복잡도이다.
- for문은 일반적으로 O(n) 시간복잡도를 갖는다.
- nlogn은 병합정렬에 해당하는 사간복잡도이다. (둘씩 나눌 때 logn이 걸리고 합칠 때 n이 걸린다.)

Dynamic Programming

Bottom-up 방식을 사용한 DP의 실행시간이 가장 빠르다.

실행시간 비교
Iteration + Tabulation < Recursion + Memoization << Only Recursion

크롬 개발자 도구에서 함수 실행 시간 측정 방법

이 방식은 크롬 개발자 도구에서만 사용 가능하다.

const func = function(num) {...}

var t0 = performance.now(); // 함수 실행 시작 시각 체크
func(50); // 함수 실행
var t1 = performance.now(); // 함수 실행 종료 시각 체크
console.log("runtime: " + (t1 - t0) + 'ms') // 함수 실행시간 확인