중간 범위 1~4장
1장
알고리즘(Algorithm)이란 단어는 알 콰리즈미라는 페르시아의 수학자에게서 유래되었다고 알려진다.
최대 숫자 찾기(순차 탐색) : 앞부터 순서대로 탐색하여 가장 큰 수 찾기
임의 숫자 찾기(이진 탐색) : 절반씩 나눠가면서 찾기 ( 단 정렬된 데이터 )
동전 거스름돈 문제(그리디 알고리즘) : 큰 수부터 가능한 한 최대로 가지기
한 붓 그리기 문제 : 현재 점으로 돌아오는 사이클 찾기
가짜 동전 찾기 문제 : 3그룹으로 분할하여 찾기
독이 든 술단지 문제 : 이진수처럼 해서 찾기
2장
① 유클리드의 최대 공약수 찾기 알고리즘
| A | B | A mod B |
| 24 | 14 | 10 |
| 14 | 10 | 4 |
| 10 | 4 | 2 |
| 4 | 2 | 0 |
위와 같이 A, B, A mod B로 3열 행을 만든 뒤,
B값과 A mod B를 다음 행의 A,B로 내리면서 반복한다.
나머지가 0인 행의 B값이 최대 공약수가 된다.
② 시간 복잡도 분석
O(n) : 최악의 경우 실행될 속도
Ω(n) : 최선의 경우 실행될 속도
θ(n) : 최악의 경우와 최선의 경우가 똑같을 경우의 속도
③ 마스터 정리
각 주기마다 문제가 a개로 분할, 부분문제가 1/b 감소하고,
다시 병합하는데 들어가는 비용을 f(n) = n^d로 할 때,
T(n) = aT(n/b)+n^d 형태의 식으로 표현이 가능하다.
3장
정렬 알고리즘의 종류
① 병합 정렬 ( Merge Sort )
입력된 배열을 반으로 나누고 왼쪽, 오른쪽을 순서대로 재귀적으로 반복한다.
이후 왼쪽 오른쪽 정렬이 끝나면 병합하여 정렬을 완성한다.
시간 복잡도 : O(n * log n)
② 퀵 정렬 ( Quick Sort )
피봇을 선택하고 0번으로 이동한 후,
1번부터 오른쪽으로 피봇보다 큰 수를 찾고, 끝부터 왼쪽으로 피봇보다 작은 수를 찾아서 위치를 교체한다.
피봇의 위치를 마지막 키의 위치로 바꾸고 피봇을 기준으로 왼쪽과 오른쪽 배열을 재귀적으로 반복한다.
시간 복잡도 : O(n * log n)
③ 선택 문제 ( Selection )
퀵 정렬과 유사한 방식이지만 찾으려는 수가 포함된 배열만 반복하고 나머지 배열은 버린다.
이 때, 배열 크기가 1/4이하나 3/4 이상으로 분할될 경우 Bad분할, 그 외에는 Good 분할이다.
시간 복잡도 : O(n)
④ 분할 정복이 안 좋은 케이스
피보나치 배열 계산과 같은 경우, 계속 아래쪽에 같은 계산이 반복되므로 비효율적이다.
4장
그리디 알고리즘의 종류
① 동전 거스름돈 문제
동전들이 배수관계일 때 큰 수의 동전부터 그리디 알고리즘을 이용해 최적해를 구할 수 있다.
단, 동전들 간 배수관계가 성립되지 않을 경우 최적해가 아닌 결과가 도출될 수 있다.
※ 10, 50, 100, 500 원 동전일 때에는 그리디 알고리즘을 통해 최적해를 도출할 수 있다.
※ 10, 50, 80 원 동전일 때 100원이면 {80,10,10} 이지만 최적해는 {50,50} 이다
② MST ( Minimum Spanning Tree, 최소 신장 트리 )
Kruskal의 MST 알고리즘
트리에 존재하는 최소 가중치 순서대로 신장트리를 구성하고
만약 생성할 트리가 사이클을 형성한다면, 다음 간선으로 미룬다.
Prim의 MST 알고리즘
최소 가중치 간선을 먼저 하나 둔 뒤, 주변의 간선들의 가중치 중 가장 적은 것부터 트리를 구성한다.
만약 생성할 트리가 사이클을 형성한다면, 다음 간선을 선택한다.
③ SP ( Shortest Path, 최소 거리 )
Dijkstra 알고리즘
최초 지점부터 연결된 정점까지의 거리를 모두 계산한다. 연결되지 않는 정점과의 거리는 무한이다.
거리가 가장 가까운 정점과 연결 한 후, 다시 연결된 모든 정점과의 거리를 계산하고, 이를 반복한다.
시간 복잡도 : 1차배열 O(n^2), 힙 트리 O(m * log n) [ m은 간선의 개수 ]
④ 가방 채우기 문제
무게당 가격을 계산하면서 빈 가방에 넣을 수 있는 가장 비싼것부터 넣는다.
⑤ Set Cover ( 최적 집합 문제 )
부분 집합 중 가장 전체 집합과의 교집합이 많은 집합을 선택한다.
최적해를 만들기 위해서는 너무 큰 시간 복잡도가 필요하므로, 근사해를 구하는 알고리즘이다.
시간 복잡도 : O(n^3)
⑥ 작업 스케줄링 문제
FCFS ( First Come First Serve ) : 먼저 온 순서대로 스케줄링한다.
SJF ( Shortest Job First ) : 가장 실행시간이 짧은 것부터 스케줄링한다.
⑦ 허프만 압축 문제
빈도수가 적은 순서대로 단말 노드에 놓으면서 이진 트리를 만들고
최종 트리에서 왼쪽으로 갈때마다 0, 오른쪽으로 갈때마다 1로 설정하여
각 단말노드에 코드를 정해서 텍스트를 압축한다.