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') // 함수 실행시간 확인

더 공부할 것

• BFS / DFS 문제 더 풀어보기
• BackTracking!!!!!!!!!!!!!!!!!

내일 할 일

• lesson / Algorithm with Math
  • GCD/LCM(최대공약수/최소공배수), 순열/조합, 멱집합
• lesson / 정규 표현식
• Coplit / Algorithm #16~#20
• 학교 사이버강의 듣기