동아리 스터디 메모

아마 저번주쯤이었음 

대충 아는 내용이었지만 그래도 더 알아볼만한 재미있는 부분들도 있었다

 

---

 

알고리즘
<공부가 어렵다. >
- 프로그래밍 트렌드가 많이 바뀌었기 때문에... (C>py)
- 기존 기술 원리를 이해하기 > 누군가 구현한 알고리즘을 가져다 쓰기
- 수학적인 것이라 이해하기가 몹시 힘들 수 있다. 
- 알고리즘을 몰라도 프로그램을 만들 수 있으므로 경시되기도 한다. 
- 컴공 수업에서만 배울 수 있다. 

- 알고리즘 지식이 있어야 좋은 소프트웨어를 개발할 수 있다. 

<알고리즘>
- 사칙연산도 알고리즘. (받아올림, 받아내림... 기계적인 규칙을 따라 계산) 

<정렬 sorting>
- 순서에 맞게 출력하기. (대표적인 것은 수십가지가 있음...)
- Bubble, insertion : 느림
: Bubble : 처음부터 하나씩 옆과 비교하여 바꾸기. 
- Quicksort, merge : 빠름
: Quicksort : 마지막을 pivot으로 두고 그것보다 큰것과 작은 것으로 나누기. 

<Time complexity>
- big O notation. 
- bubble : O(n^2)
- quicksort : O(nlogn)
( nlnn < n^2 )
( n^1000 < 1.001^n )

- average, best, worst... 

<sorting의 복잡도>
- sorting algorithm의 가장 빠른 속도는 nlogn
- Stirling's approximation : 
logn! ~= nlogn

- 길이 n 배열이 취할 수 있는 가지수는 n!가지이므로... 
- 정보이론에 따라 log_2^n!회의 비교연산이 필요. 
(10번의 질문으로는 2^10개를 구분가능하다)

<알고리즘의 특징>
- 기계적인 절차를 반복하다 보면 항상 정확한 답을 얻는다. 
- 속도는 제각각이다. 
- 재귀적인 구조를 가진다. 


<Search 알고리즘>
- 입력이 두 줄이다. (haystack & needle) : 위치를 찾아야한다. 

*미리 sorting이 되어있을 경우
- Brute force method : 앞에서부터 읽으면서 찾기. 
- 최악의 경우 O(n) 
- 그래도 답은 항상 잘 찾는다. 

- Binary search : O(logn)