TIL : Algorithm (1)

1. 알고리즘

어떤 문제를 해결할 때의 논리적인 절차과정 ( = 문제를 어떻게 푸는 것이 최선인가?!)

ex) 자판기 : 화폐 투입 -> 음료수 선택 -> 음료수 받기

---

2. 시간 복잡도 (Time Complexity)

: 실행시간이라는 관점에서 알고리즘의 효율을 측정하는 표기법

· 최선 : Big-Ω 표기법

· 평균 : Big-θ 표기법

· 최악 : Big-O 표기법

=> 최선의 상황이나 평균적인 상황만 고려하다가 최악의 상황이 벌어지는 것보다 처음부터 최악의 상황까지 고려하여 대비하는 것이 바람직하다. 따라서 보통 Big-O 표기법을 사용한다!!

 

---

3. Big-O 표기법

1. O(1) : 입력에 관계없이 시간 동일 (상수)

2. O(n) : 입력이 증가하면 시간dl 같은 비율로  증가 (선형) - 반복문 1번 있는 경우!

3. O(logn) : 입력이 증가해도 시간 증가 비율이 작다. - 이진 탐색

4. O(n^2) : 입력값이 증가함에 따라 시간이 제곱수의 비율로 증가 - 반복문 2번 있는 경우!

5. O(2^n) : 입력값이 증가할 때 시간 증가 비율이 크다. - ex) 피보나치

 

---

4. 탐욕 알고리즘 (Greedy Algorithm )

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

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

3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사한 후, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복

---

5. 동적 계획법 (Dynamic Programming)

: 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결

· 가정 1 : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)

· 가정 2 : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)