Coursera - Algorithmic Toolbox : week.2

1주차를 언제 했는데 이제야 2주차를..? 하지만..직장+야간대학원 병행하면서 코셰라까지 듣는건...무리였기도 하고.....종강하고 나니까 보고싶은 마음이 싹 사라지는 바람에....ㅎ

아무튼...

 

2주차부터는 훨씬 본격적인 과제들이 나온다. 

가장 먼저 왜 알고리즘을 배우는가에 대한 영상이 나오는데, 알고리즘은 맞닥뜨릴일이 있는 많은 문제들을 해결하기 위함인데

 보통 이런 문제들은 명확하게 뭘 해야할지 알기가 드물며(not clear how to do), 단순한 해결책은 너무 느려서(Simple ideas too slow),  최적화할 부분(Room for optimization)이 필요하다. 이런 이유로 알고리즘을 공부해야한다는 것이 영상의 주제다.

 

이번 주차에선 아래의 두가지 문제를 다룬다

• 피보나치 수열
• 최대공약수

 

피보나치 수열

F(n)

0 (n=0), 1 (n=1), ...

F(n-1) + F(n-2)   (n>1)

0,1,1,2,3,5....

 

피보나치수열 푸는법

1. 가장 단순한 알고리즘

• 재귀함수를 사용

if n<=1:
	return n
else:
	return F(n-1) + F(n-2)
T(n) = 3 + T(n-1) + T(n-2)

이 알고리즘은 당연하게도 아주 느리다. 재귀되는 매 순간마다 해당 케이스를 계산해야하기 때문이다.

 

2. 효율적인 알고리즘

일단 피보나치 수열의 양상을 보도록 하자

0,1,1,2,3,5,8...  -> 가장 마지막의 두 숫자를 더하게 된다.

0+1 = 1
1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8

피보나치 수열에 관한 리스트를 만든 후, 현재 i번째 원소는 i-1번째 원소 + i-2번째 원소의 합으로 구한다!

이렇게 하면 T(n) = 2n+2 가 되고, 쉽게 계산이 가능하다.

 

최대공약수(GCD)

기본 포맷은 분수 a/b를 놓고, 분모와 분자를 (a/d) / (b/d) 처럼 나눌수있는 d를 구한다. 여기서 d는 당연 a, b를 나눌수 있고 최대한  큰 값을 구하도록 한다.

 

 1. 단순한 알고리즘

best <- 0
for d from 1 to (a+b):
	if d/a and d/b:
    	return best
	best <- d

 

2. 유클리드 호제법

최대공약수: 정수 a, b를 나눌 수 있는 값중 가장 큰 값 d를 최대공약수라고 한다.

  a'를 b로 나눈 a의 나머지라고 할때, 다음의 식이 성립한다

gcd(a, b) = gcd(a', b) = gcd(a, b')

증명은 다음과 같다

a = a' + bq

d는 a와 b를 나눌수있으므로 a'와 b 역시 나눌 수 있다.

function EuclidGCD(a, b)
b=0?
    return a
a' <- b로 나눈 나머지
return EuclidGCD(a', b)

Big O

• 정확한 런타임을 알아내는 것은 매우 거대한 작업이다.
• 다양한 세부사항에 대해서도 알 길이 없다. (예를 들어 프로그램이 어느 컴퓨터에서 돌고 있는냐와 같은..)

목표

• 자잘한 세부사항에 대한 정보 없이도 런타임을 측정하는것
• 많은 입력사항에도 동작하는 결과물 얻기

점근식 방법(Asymptotic)

• 점진적으로 런타임의 규모가 어떻게 변하는지 살펴보자!
• 1, n, nlogn, n^2에 각각 값을 집어넣어보고 비교해보는 방법
• 상수에 대해선 신경쓸 필요 없고, 변수에 따라 바뀌는 부분만 주목하면 된다

Big O

f(n) = O(g(n))이거니 f<g일때 상수 N, c에 대해서 모든 n은 N보다 크고 f(n) < c * g(n)이다

 

이게 공식정의인데 그냥... 원래 내가 아는대로 n중 가장 차수가 큰걸로 결정된다고 보면 된다.

아무튼 이 수업에선 Big O 를 사용하여 알고리즘을 측정할 것인데 그 이유는 다음과 같다

• 알고리즘이 동작하는데에 걸리는 런타임의 성장률을 명확하게 해준다
• 인용(notation)을 간결하게 해준다. ex)O(n^2) vs 3n^2 + 5n + 2
• 빅 오를 사용하면 자잘한 사항에 대해 생각할 필요가 없다! 예를 들어 알고리즘을 수행하는 컴퓨터의 속도가 빠른지 느린지와 같은 문제들..

- 빅오에도 물론 단점은 존재하는데 실제로 걸리는 시간을 알려주는것이 아니고, 또 상황에 따라선 빅오로 측정한 성능은 알고리즘a가 b보

다 낫지만, 아주 큰 값을 넣기 전엔 b가 낫기에 대부분의 상황에선 b를 사용하는게 낫다던가 하는 경우도 있다.

 

이번주의 과제 코드: 링크

GitHub - prograsshopper/coursera: Learning things from coursera

이번주라고는 하지만 과제는 이전에 했었는데 사실 뭐 완전히 내가 푼것도 아니고 시간에 쫓겨서 다른 사람껄 참고해서 푼 것도 있고 통과 안된것도 있다 (...) 하지만 그냥 2주차에 계속 매여있는게 싫으니 일단 그냥 넘어가기로...