TIL47: [자료구조/알고리즘] 코딩 테스트 준비

오늘은 자료구조와 알고리즘을 학습했습니다. 섹션2에서의 자료구조와 알고리즘을 공부할 때, BFS와 DFS가 어려웠어서 시작하기 전부터 좀 겁을 먹은 상태였습니다. 하지만 이전에 Toy Problem과 코플릿으로 여러번 힘들어봤어서 그런지 생각외로 괜찮았습니다ㅎㅎ

 

시간 복잡도(Time Complexity)

다음의 세가지 경우와 같이 시간 복잡도를 표현할 수 있습니다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

Big-O 시간복잡도

 

function O_n(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function O_2n(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

첫번째 함수는 입력값이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 두번째 함수는 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가합니다. 실행시간의 차이가 이렇게 있지만 두번째 함수 또한 첫번째 함수처럼 Big-O 표기법으로 O(n)으로 표기합니다. 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배, 5배, 10배로 증가하더라도 O(n)으로 표기합니다.

 

• 가장 빠른/느린 시간 복잡도는 무엇일까요?
  가장 빠른 시간 복잡도는 O(1)이고, 가장 느린 시간 복잡도는 O(2의 n제곱) 입니다.
• 효율적인 알고리즘을 구성했다 함은 무엇을 의미할까요?
  입력값의 증가에 따라 증가하는 시간비율을 최소화한 것을 말합니다.
• 시간 복잡도는 A와 B의 비례함이 어느 정도인지를 나타냅니다. A와 B는 무엇일까요?
  입력값과 실행되는 시간의 비례함이 어느 정도인지를 나타냅니다.

 

let i = n;
while (parseInt(i) > 0) {
  i = i / 2;
}

위 코드의 시간 복잡도는 O(log n) 입니다.

 

for (let i = 0; i < n; i++) {
	i *= k;
}

위 코드의 시간 복잡도는 O(log k n)또는 O(log n) 입니다.

 

 

 

Greedy Algorithm (탐욕 알고리즘)

탐욕 알고리즘은 아래 2가지의 조건을 성립해야 잘 작동합니다. 

 

1. 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조 (Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 무제에 대한 최적 문제 해결 방법으로 구성된다.

 

 

탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있습니다.

 

1. 선택 절차 (Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.

2. 적절성 검사 (Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.

3. 해답검사 (Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

 

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식입니다. 그러나 항상 최적의 결과를 보장하지는 못합니다.

 

 

 

 

Dynamic Programming (DP; 동적 계획법)

주어지 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식입니다.

즉, 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견되어야 합니다.

또한, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일해야 합니다.

 

DP에는 크게 두가지 방식으로 할 수 있습니다.

 

Recursion + Memoization (Top-down 방식)

Memoization (메모화): 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전의 계산 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 할 수 있습니다.

 

Iteration + Tabulation (Botom-up 방식)

Top-down 방식보다 함수 실행시간이 더 적게 듭니다.

 

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

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