TIL -211109 [자료구조/알고리즘] 코딩 테스트 준비

Achievement Goals

• 알고리즘이 무엇인지 설명할 수 있다.
• 알고리즘 문제를 이해하고 전략을 세울 수 있다.
• 알고리즘 풀이에 필요한 수도 코드를 작성할 수 있다.
• 수도 코드에서 세운 전략을 코드로 구현할 수 있다.
• 내가 구현한 알고리즘을 자바스크립트 언어로 설명할 수 있다.

Chapter 1 - Time Complexity

(1) 시간 복잡도

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

그러므로 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 만들어야 한다.

Big-O(상한 접근)

Big-Ω(omega)(하한 접근)

Big-Θ(theta)(평균 접근)

 

(2) Big-O 표기법

Big-O 표기법은 최악의 경우를 고려하므로 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.

 

 

O(1)

constant complexity라고 하며 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기에 상관없이 출력밧을 즉시 얻어낼 수 있다.

 

O(n)

linear complexity 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미

입력값이 1일 때 1초의 시간이 걸리고 입력값을 100배로 증가시키면 100초가 걸리는 알고리즘

 

O(log n)

logarithmic complexity O(1) 다음으로 빠른 복잡도

BTS(Binary Search Tree)에서 원하는 값을 탐색할 때마다 노드를 이동할 경우 경우의 수가 절반으로 줄어든다.

매번 숫자를 제시할 때마다 경우의 수가 절반으로 줄어들기 때문에 효율적이다.

 

O(n²)

quadratic complexity 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리되는 경우

 

O(2ⁿ)

exponential complexity. 가장 느린 복잡도

 

 

입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어내고

주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 데 집중

O(1) < O(log n) < O(n) < O(n2) < O(2n)

 

Chapter 2 - Greedy Algorithm

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법.

알고리즘 문제를 푼다는 의미 : 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것

 

완전탐색: brute Force(무차별 대입, 조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS
시뮬레이션

 

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

Recursion + Memoization

Iteration + Tabulation

 

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

var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')