[Algorithm] 정리

알고리즘
문제를 해결하기위한 일련의 절차를 공식화한 형태로 표현한 것.

필요한 개념들

• 시간 복잡도

• 자료구조
  단순구조: 정수/실수/문자/문자열
  선형구조: 자주 출제
  순차리스트/스택/큐/덱
  연결리스트=> 단순연결리스트/이중연결리스트/원형연결리스트
  비선형구조: 자주 출제
  트리 => 일반트리/이진트리
  그래프 => 방향 그래프/무방향 그래프
  

• 정렬

알고리즘 종류

1. 검색알고리즘
   1-1) 선형검색(Linear-search): 복잡도 O(n)
   배열을 검색하여 원하는 key값을 찾는
   배열의 맨앞부터 순차적으로 검색
   1-2) 이진검색(Binary-search): 복잡도 O(log(n))
   정렬된 배열에서 원하는 key값을 찾는
   선형검색보다 빠름.
   
2. 재귀알고리즘
   2-1) 피보나치 수열: 복잡도 O(2^n)
   0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
   처음 시작하는 두개의 값은 0, 1
   두개의 키를 더해서 다음 값을 산출
   재귀호출 구조는 거듭되는 연산이 많아서 복잡
   2-2) 최대공약수(GCD) : 복잡도 O(log(n+m))
   유클리드 알고리즘을 재귀호출 방법으로 사용할 수 있다.
   a>=라면 GCD(a,b) = GCD(b,r)이다. 여기서 r=a%b(나머지)
   2-3) 하노이의 탑알고리즘
   이미 알아본 방법으로 원반 n-1개를 옮긴다.(재귀)
   이미 알아본 방법으로 마지막 원반을 옮긴다.(재귀)
   
3. 정열알고리즘
   3-1) 선택정렬(Selection Sort): 복잡도 O(n^2)
   리스트안에 이/ㅆ는 자료들(작은것부터 큰것 순으로) 순서로 나열
   가장 단순한 정렬, 많은 비교가 필요하므로 복잡도 높음
   전체 비교횟수는 n(n-1)/2
   3-2) 삽입정렬(Insertion sort): 복잡도 O(n) ~ O(n^2)의 사이
   입력 리스트가 이미 정렬에 가까운 ㅅㅇ태라면 복잡도 낮아짐
   일반적으로 선택정렬과 유사한 성능
   자료가 담긴 리스트에서 순차적으로 값을 가져옴
   첫번재 값은 arr[0]은 바로가져옴 , 두번재 값부터 결과 리스트와 비교 후위치를 정함.3-3) 병합정렬(Merge Sort): 복잡도 O(log(n))
   재귀호출을 사용하는 정렬
   분할정복 방법의 알고리즘이다.divide & conquer
   자료가 담긴 리스트를 가운데 기준으로 두개로 분할 => 두개의 리스트에 첫값을 비교 후
   작은 것을 골라 결과 리스트로 옮김 => 재귀 3-4) Quick Sort: 복잡도 O(log(n))
   재귀호출
   분할정복 방법의 알고리즘
   병합정렬과 다르게 특정값을 피봇으로 정해서 입력할 a,b리스트를 두개 준비
   피봇보다 작은값은 a리스트, 큰값은 b리스트
   두개의 a,b리스트에 재귀호출을 적용해서 정렬된 리스트로 만든다. 3-5) 버블 Bubble Sort: 복잡도 O(n^2)
   리스트를 처음부터 훑어가며 인접값 두개를 비교해서 정렬
   정렬까지 반복단순하지만 비효율적인 방법 : 삽입정렬 / 선택정렬 / 버블정렬
   복잡하지만 효율적인 방법 : 퀵 / 힙 / 합병 / 기수
   

3 Types of Algorithm You should know

Top7 Algorithm

Searching Algorithms

• used to find or retrieve an element from a data structure, or to determine its existence and location in the dataset. We discuss linear search and binary search.

like 숫자마추기 게임
[1,2,3,4 ~ 25 ~ 99,100]

• Linear Search
  -- 1부터 순차적으로 물어보는 경우 : Linear Search O(n) - Inefficient
• Binary Search (+Sorted List)
  -- 50 중간부터 물어보는 경우 UP/DOWN : Binary Search O(log2(n)) => O(log(n)) - Efficient

• Depth-First Search(DFS)
  

const visited = [] 
visited = [1,2,3,4,5]

O(V + E)
V = vertices or nodes
E = edges or branches

• Breadth-First Search(BFS)
  

const visited = [] 
const neighbours = []

phase 1 
visitied = [1]
neighbours = [2,5] 

phase 2 
visited = [1,2]
neighbours = [5,3,4]

phase 3
visited = [1,2,5]
neighbours = [3,4]
.
.
.

result 
visitied = [1,2,5,3,4] 

O(V + E)
V = vertices or nodes
E = edges or branches

Sorting Algorithms

• used to rearrange elements in a list or an array in a certain order. We discuss bubble sort, insertion sort, and merge sort.

• Insertion Sort : Best for when lists are already sorted, or small size
  Best case : O(n)_ 리스트가 이미 정렬된 상태
  Worst case : O(n^2)

• Merge Sort
  divide and conquer
  Best case : O(n log(n))
  Worst case : O(n log(n))

Insertion VS Merge 비교

Array List Smaller & Sorted
Insertion : O(n)
Merge : O(n log(n))

Array List Larger & Unsorted
Insertion : O(n^2)
Merge : O(n log(n))

• Quick Sort
  divide-and-conquer algorithm + recursion

const source = [3,5,2,4,8,7,1,6]


const smallerThanMedian = [1,2,3] 
const medianValue = [4] // pivot
const biggerThanMedian = [5,6,7,8]

## Prepare
try to select number close to the median. 
4 is median value here.
Once we've selected that number, we move it to the end of the list 

const source = [3,5,2,8,7,1,4]

Now we place a pointer at the left-most element, and the right-most element.

Pointer on index 0 = [value: 3] 
pointer on index 6 = [value: 1] here is 6 out of 0 ~ 7 
const source = [**3**,5,2,8,7,**1**,4]



phase 1 
compare index 0 value and index 6 value. 
if 
the left-most value (here 3) is bigger than pivot(here 4) 
and 
the right-most  value (here 6) is smaller than pivot(here 4) 
swap both 

Best case : O(n log(n))
Worst case : O((n^2))

• Bubble Sort 느리지만 알아두자.

Graph Algorithms

• used to solve problems related to graph theory, where data is represented as a collection of nodes (or vertices) connected by edges. You probably know these as trees. We discuss depth-first search (dfs), breadth-first search (bfs), Dijkstra's algorithm, and A* algorithm.

Greedy
Not used for efficiency!

Brute-Force

divide & conquer 분할정복

Greedy

Queue