알고리즘_강의노트
1.[알고리즘] 수행시간 분석
바람직한 알고리즘 명확해야 한다. 이해하기 쉽고 가능하면 간명하도록 지나칙 기호적 표현은 오히려 명확성을 떨어뜨림 명확성을 해치지 않으면 일반언어의 사용도 무방 효율적이어야 한다. 같은 문제를 해결하는 알고리즘들의 수행 시간이 수백만 배 이상 차이날
2.[알고리즘] 알고리즘의 분석
시간 복잡도 분석의 종류 - Every-case time complexity analysis (모든 경우) - Worst-case (최악의 경우)
3.[알고리즘] 차수 (Order)
입력의 크기가 충분히 큰 경우도 효율적인 알고리즘을 찾기위해서는 점근적 분석 방식을 이용한다. O
4.[알고리즘] 점화식과 알고리즘 복잡도 분석
점화식의 이해 > 점화식 : 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 예) 병합 정렬의 수행 시간 >* - 수행시간의 점화식 : T(n) = 2T(n/2) + 오버헤드** ✔️ 크기가 n인 병합 정렬 시간은 크기가 n/2인 병합정렬을 두
5.[알고리즘] 집합
이 포스트에서는 상호배타적 집합만을 대상으로 한다. 그러므로 교집합은 없다.지원할 연산Make-Set(x): 원소 x로만 이루어진 집합을 만든다.Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다.Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진
6.[알고리즘] 정렬
평균적으로 $$⊝(n^2)$$의 시간이 소요되는 정렬 알고리즘들 \- 선택정렬 (selection Sort) \- 버블정렬 (Bubble Sort) \- 삽입정렬 (Insertion Sort) 각 루프마다최대 원소를 찾는다.최대 원소와 맨 오른쪽
7.[알고리즘] 그리디 알고리즘
그리디 알고리즘 개요 눈앞의 이익만 취하고 보는 알고리즘 현재 시점에 가장 이득이 되어 보이는 해를 선택하는 행위를 반복 대부분 최적해와의 거리가 멀다 드물게 최적해가 보장되는 경우가 있다. optimization 문제를 해결할 때 이용 : DP 또는 G
8.[알고리즘] 그래프
현상이나 사물을 정점vertex과 간선edge으로 표현한 것Graph G = (V, E)V : 정점 집합E : 간선 집합두 정점이 간선으로 연결되어 있으면 인접adjacent하다고 한다.간선은 두 정점의 관계를 나타낸다.N \* N 행렬로 표현 (N : 정점의 총 수)