1주차 빅오표기법(상한) 빅세타표기법(하한) -> 계산 방법과 유도과정
2주차
선택정렬
버블정렬
i는 검사할 배열 A의 배열의 주소를 지정하기 위해서 사용되고 Sorted는 앞에 단계에서 자리바꿈이 일어났는지 검사
- 일단 Sorted를 False로 둠
- Sorted가 False인 경우에만 반복문 실행
- Sorted를 True로 두고
- A[0]부터 A[n]까지 검사함
- 만약 A[i-1] 과 A[i]를 비교했을 때 A[i-1]이 더 큰 경우에는 둘이 서로 바꿔주고 Sorted를 False로 변경해줌 만약 그렇지 않다면 Sorted를 True로 유지가 되어 바로 전단계에서 자리바꿈이 일어나지 않은 것을 알 수 있고 그 덕에 알고리즘의 실행을 끝낼 수 있음
삽입정렬
- 삽입하고자하는 원소 i=2부터 왜냐면 i=1일 때는 비교할게 없으므로 2부터 시작
- Value에 A[i]를 넣어줌 Value는 앞에 배열을 비교할 값임(임시로 저장한다고 생각하면 댐)
- j=i
- Value값과 그 앞에 있는 원소들을 비교했을 때 Value값보다 크면 그 앞에 있는 값이랑 비교하고 큰 값의 index를 하나씩 증가시켜서 앞으로 당긴다?
- 만약 Value값과 같거나 작다면 반복문을 멈추고 A[j]에 Value갑을 넣고 종료시킴
만약 Value값이 최솟값이고 A[0]=최솟값으로 채우지 않는다면
Value가 마지막 A[0]와 비교해서 A[0]가 더 크므로 A[1]의 주소로 A[0]의 값이 복사가 될 것이다.
하지만 A[0]의 값은 그대로 유지되어 Value값은 계속 A[0]와 비교->A[1]에 A[0]값 복사 <-이것이 무한 반복되므로
A[0]에는 배열의 최솟값을 넣어주고 A[1:n]에 실제 자료를 둔다.
쉘 정렬
- h=1로 설정
- h_(i+1)=3*h_i+1로 설정하고 n값에 따라 h값 증가시킴 n이 12이면 h는 13이 된다
- h를 3으로 나누면서 h가 1보다 클때까지 반복문을 진행시킴
- Value에 A[i]=A[h]값을 넣음
- j=i로 둠
- A[j-h]>Value 만약 h만큼 떨어진 원소의 값A[j-h]가 Value보다 크다면 값을 index를 h씩 증가시켜서 값을 당겨준다? 그리고 앞에꺼를 더 비교하기 위해서 j-h를 진행하는데 여기서 j<h-1이면 멈춤
- 그러고서 빈자리를 Value로 채워줌
퀵 정렬
최선,최악,평균 구하는 방법 연습하고 암기
합병정렬
최악의 경우 시간복잡도 유도해보기
힙 정렬
힙생성에는 두가지 방법이 존재
힙정렬
힙생성 방식은 첫번쨰를 사용하는 대신
힙정렬 방식은 하나이므로 계속 힙을 정렬시킴
계수 정렬
기수정렬
선택정렬은 코드 포기함,
외부정렬은 정의와 특징을 암기
합병 정렬
대치 선택
다단계 합병 정렬
다이나믹, 그리디 Lecture5
순차탐색
이진탐색
이진 탐색 나무
균형나무-2-3-4나무,RedBlackTree
레드블랙트리
라빈카프 알고리즘
kmp 알고리즘
Trivial Mapping Algorithm
Indexing Algorithm
Burrow-wheeler transform
walk-left optimization
그래프
BFS
DFS
NP
Euler Cycle Problem
1. 무방향 그래프
오일러 회로
그래프가 연결되어 있고
모든 정점의 차수(degree)가 짝수이면
오일러 회로가 존재
오일러 경로
그래프가 연결되어 있고
정확히 두 개의 정점만 홀수 차수, 나머지는 짝수 일 때
이 두 정점 중 하나는 시작점, 다른 하나는 끝점
오일러 경로가 존재함(시작점은 끝점과 같지 않음)
2. 방향 그래프
오일러 회로
그래프가 연결되어 있고
모든 정점의 in-degree와 out-degree가 같을 때
오일러 회로가 존재
오일러 경로
그래프가 연결되어 있고
모든 정점 중 정확히 두 개의 정점만 in-degree ≠ out-degree이고,
그 중 하나는 out-degree=in-degree+1 (시작점)
다른 하나는 in-degree=out-degree+1(끝점)
오일러 경로가 존재
| 종류 | 오일러 회로 조건 | 오일러 경로 조건 |
| 무방향 | 모든 정점 짝수 차수 | 정확히 2개의 정점만 홀수 차수 |
| 방향 | 모든 정점 in-degree = out-degree | 한 정점 out-degree가 1 더 많고, 다른 정점은 in-degree가 1 더 많음 |
Eulerian Cycle 만드는 법
임의의 정점에서 시작하여 사용하지 않은 간선을 따라가며 사이클을 만들면, 그래프가 균형잡혀 있다면 이 경로는 다시 출발 정점으로 되돌아온다. 이것이 Eulerian Cycle이다.
절차:
1. 아무 정점 v에서 시작
2. 아직 사용하지 않은 간선들만 따라 사이클을 형성
3. 더 이상 진행할 수 없는 시점(dead end)에 도달하면 이 지점은 항상 시적 정점 v임
단계 설명
| (a) | 임의의 정점에서 시작하여 사용하지 않은 간선을 따라 사이클 생성 |
| (b) | 그 사이클에서 사용하지 않은 간선을 가진 정점을 찾아 새로운 사이클 생성 |
| (c) | 사이클들을 하나로 연결하고, 더 이상 간선이 없을 때까지 반복 |
SBH
| 항목 | 해밀턴 path | 오일러 path |
| 정점 | l-mer | (l-1)-mer |
| 간선 | l-mer 간 오버랩 | l-mer 자체가 간선 |
| 목표 | 모든 정점 한 번씩 방문 | 모든 간선 한 번씩 방문 |
| 난이도 | NP-complete | 선형 시간 알고리즘 존재 |
| 실전 활용성 | 적음 | 매우 높음 (De Bruijn 그래프 기반) |