Algorithms Chapter 1 (part1)

단순한 연산들의 sequence에 따라서 실행을 하면 그 결과로서 주어진 문제의 solution이 얻어지는 해법이 알고리즘이다.

여기서 중요한 것은 각 스텝이 기계적으로 연산 가능한 단순한 연산이다.

단순하지 않는 연산 : 두 수의 최대 공약수를 구하라

 

이 과정이 언젠가는 끝나야 한다.

끝나지 않고 영원히 돌아가면 알고리즘이 아니다. 솔루션을 내놓아야 한다.

 

항상 정확한 솔루션이여야 알고리즘이라고 말할 수 있다.

sorting 알고리즘이라고 부를 수 있으려면 그 알고리즘은 어떤 input이 들어오더라고 sorting할줄 알아야 한다.

 

인스턴스라는 것은 어떤 문제에 무수히 많은 경우가 있다.

최단경로 문제를 보면 최단경로 문제를 푸는 무수히 많은 그래프가 있고, 각각에서 최단경로 문제가 있는것이다.

인스턴스라는 것은 그 문제 개개의 것을 말한다.

최단 경로 문제에서는 무수히 많은 인스턴스가 존재한다.

최단 경로의 해답은 솔루션이다.

 

 

알고리즘이 주어진 문제를 푼다라고 말할 수 있으려면 모든 인스턴스에 대해서 정확한 답을 구해낼 수 있어야 한다.

 

 

알고리즘을 discribe할 때에는 C언어처럼 정확하게 기술하진 않는다.

꼭 프로그래밍 언어로만 써져야 알고리즘은 아니다. 그냥 영어로만 쓰여도 알고리즘이다.

 

 

이런 것을 pseudo-code 라고 한다. 유사 코드

 

 

이런 것도 알고리즘이라고 한다.

 

 

이것은 버블솔트다. 나쁜 거다. 실제로 솔팅할때 이거 쓰지마라

 

 

이것은 행렬의 곱셈 알고리즘이다.

이산수학에서 배웠을 것이다.

행렬 두 개 곱하는거다. 이런게 있었다라는 것을 기억해두고 나중에 다시 언급할 것이다.

 

 

 

왜 우리가 효율적인 알고리즘 짜야 하는가?

그냥 좋은 컴퓨터 사면 되는거 아니냐?

비효율적인 알고리즘은 빠른 하드웨어로 커버 할 수가 없다

 

 

사이즈가 커지면 점점 벌어진다.

빠른 하드웨어를 쓴다고 해서 해결될 문제가 아니다.

---

 

피보나치 수열의 n번째를 구하는 것을 생각해보자.

 

 

그런데 이 알고리즘의 시간은 얼마나 걸릴 것인가?

function call 2번 ,비교 1번

function call 이 일어나는 횟수를 세어보자.

 

 

이 트리의 노드의 개수가 fib(5)를 구할 때의 횟수이다.

이 것을 n에 관한 대수 식으로 구할 수 있다. 

하지만 그걸 구할 필요는 없고 이 알고리즘이 굉장히 비효율 적이라는 것을 보여주려고 한 것이다.

 

 

밑은 수학적 귀납법으로 증명한 것이다.

induction -> 수학적 귀납법. 풀네임은 아니다.

T(3) 는 노드가 5개이다.

 

T(n) = T(n-1) + T(n-2) + 1

전체 노드 개수 = 자손 노드 개수 + 다른 자손 노드 개수 + 꼭대기

 

그러니까 걸리는 시간이 2^(n/2)보다 더 걸린다는 것이다.

 

 

ㅈㄴ 오래걸린다.

 

다른 피보나치 방법이다.

for루프로 돌리기

걸리는 시간 = for 루프의 반복 횟수에 비례할 것이다.

 

n값이 작을 적에는 별 차이 안나지만 n값이 크면 차이가 매우 크다.

 

이것이 바로 빠른 알고리즘을 개발해야할 필요성이다.

 

---

 피보나치 수열 알고리즘