chapter2
2-2.최초의 알고리즘
: 유클리드의 최대공약수 알고리즘
2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수가 같다는 성질을 이용하여 최대공약수를 찾음.
Euclid(a,b)
입력 : 정수 a,b : 단, a >= b >= 0
출력 : 최대공약수(a,b)
if(b = 0 ) return a
return Euclid(b, a mod b) // "a mod b" 는 큰 수에서 작은 수를 뺀 수와 같음
2-3. 알고리즘 표현
"의사코드(pseudo code)"
2.4 알고리즘 분류
1) 문제해결 방식
분할정복(Divide and Conquer)
그리디(Greedy)
동적 계획(Dynamic Programming)
근사(Approximation)
백트래킹(Backtracking)
분기 한정(Branch and Bound)
2)문제에 기반
정렬 알고리즘
그래프 알고리즘
기하 알고리즘
3)특정 환경에 따른
병렬 알고리즘
분산 알고리즘
양자 알고리즘
4) 기타
2-4. 알고리즘의 효율성 표현
- 무결성 확인
- 자원(시간, 통신대역)
- 시간 - 점근적 분석 (입력의 크기가 충분히 큰 경우에 대한 분석) =>점근적 표기 사용
- 시간 복잡도
- 공간 복잡도
=> 최악경우 분석!
2.6 복잡도의 점근적 표기
-복잡도의 점근적 상한
-복잡도의 점근적 하한
-복잡도의 상한과 하한이 동시에 적용되는 경우
1) Big-Oh
n이 증가함에따라 O(g(n))이 점근적 상한이라는 것 (즉, c(g(n))이 n0 보다 큰 모든 n에 대해서 f(n)보다 크다는 것)을 보여 준다.
f(n) = O(g(n))
2) Big-Omega
n이 증가함에 따라 오메가(g(n))이 점근적 하한이라는 것(즉, cg(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 작다는 것)을 보여준다.
3)Theta
Theta 표기는 복잡도 O-표기와 Omega-표기가 같은 경우에 사용한다.
자주 사용하는 O-표기
O(1) 상수시간
O(log n) 로그(대수) 시간
O(n) 선형 시간
O(n log n) 로그 선형 시간
O(n^2) 이차 시간
O(n^3) 3차 시간
O(2^n) 지수 시간
다음 chapter 3 : 분할 정복 알고리즘
3.1 합병 정렬
3.2 퀵 정렬
3.3 선택 문제
3.4 최근접 점의 쌍 찾기
3.5 분할 정복을 적용하는 데 있어서 주의할 점
'2023 2학기 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 선택 문제 (selection_merge) (1) | 2023.10.09 |
|---|---|
| [알고리즘] 퀵 정렬 (quick sort) (1) | 2023.10.09 |
| [알고리즘] 삽입 정렬 (insertion sort) (0) | 2023.10.08 |
| [알고리즘] selection sort (선택 정렬) (0) | 2023.10.08 |
| [알고리즘-백준 10828번] 스택 (C언어) (0) | 2023.09.10 |
