C로 배우는 알고리즘 - 복습 겸 요약 1

1. 개요

1. 알고리즘의 정의

책이서는 알고리즘의 정의를 이렇게 하고 있다.

 “알고리즘이란 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합이다.”

2. 알고리즘과 자료구조와의 관계

그냥 밀접한 관계라고만 알고 있었는데 말이지..

알고리즘과 자료구조는 뗄레야 뗄 수 없는 관계임은 명백하다.

책에서는 그 관계를 계란의 노른자와 흰자로 비유했는데, 그 전체 크기가 정해져 있어 한쪽이 복잡해지면 다른 쪽이 단순해진다고 했다.

예를들어 스택이 큐같은 자료구조는 그 자체로 자료를 취급하는 행위까지 규정하고 있어 추상적인 자료형Abstracted data type이라 한다. 이렇게 자료구조가 행위적 측면을 포함하면 알고리즘은 그 행위적 측면때문에 단순해진다고 했다.

책만 봐서 그런지 잘은 모르겠지만, 행위적 측면을 분리시켜서 자료구조로 본다면 나머지 알고리즘만 보기 때문에 단순해진다는 말일까?

3. 알고리즘의 선택

먼저 알아두어야 할 것이 "절대적으로 최상의 알고리즘은 없다"라고 한다..

알고리즘에서 가장 많이 거론되는 정렬을 보면 알 수 있다는 것 같다. 하지만 나는 아직 안 배웠으니까 이 부분은 나중에 쓰자.

일반적으로 알고리즘의 속도와 메모리 소요는 반비례하므로, 상황에 따라 맞는 방법을 골라 쓰는 것을 최선으로 뒀다.

또한 프로그램을 처음 짤 때는 가장 단순한 알고리즘을 쓰는 것이 좋다고 한다. 납득이 간다. (그럼 내가 예전에 욕심을 부려서 코딩이 느렸던 걸까..)

4. 알고리즘의 실행시간 분석

분석 방법론

경험적 분석: 걍 프로그램을 직접 실행시켜서 나온 실행시간 자료로 분석하는 것이다.

수학적 분석: 알고리즘 자체만 가지고 분석하는 것이다. 프로그램 편차를 없앤 순수 알고리즘의 성능을 비교한다는 장점이 있다.

알고리즘 분석단계

1. 대상 자료구조를 정한다. 같은 알고리즘이라도 넣는 자료구조에 따라 처리시간이 달라질 수도 있다. 일단 정하고 비교하게 되면 최소시간, 평균시간, 최대시간 등등이 나올 것이다.

2. 알고리즘의 동작들을 분해하여 계산한다. 한 번 루프를 돌았을 때 몇 번 연산한 걸로 칠지 결정해야 할 것 아닌가. 이건 아마 수학적 분석의 과정인 듯 하다. 

3. 수학적인 알고리즘 분석: 다음에 나오는 함수관계로 표현해야 실행시간이 어떤 형태를 가지는 지 알 수 있을 것이다.

알고리즘의 유형

1, logN, N, NlogN, N², 2^N등이 있다. 각각의 함수그래프를 보면 쉽게 어떤 건지 알 수 있다.

특히 N의 3승 같은 경우는 3중 루프의 경우 발생한다.

하지만 실제로는 상수가 더하거나 곱해져 표현된다. 

알고리즘의 표기법

O표기법Big-Oh Notation

정확한 정의가 나와있었는데, 사용은 어렵지 않지만 말뜻을 이해하는 데는 시간이 좀 걸려 나도 주석을 달아야 겠다.

만약 실행 시간 함수 T(N)이 N₁보다 큰 N에 대하여 항상 C₁f(N)보다 작거나 같은 C₁와 N₁가 존재한다면 T(N)은 O(f(N))이라고 한다.

즉 N≥N₁인 모든 N에 대하여 T(N)≤C₁f(N)이 만족하면 T(N)=O(f(N))이다

사실 별거 아니었다. f(N)은 그냥 알고리즘, T(N)이 그 알고리즘의 실행시간, C₁f(N)이 T(N)보다 좀 더 가속도있는 그래프로 보면 된다. 여기서 N₁은 아무거나 되어도 상관이 없고, 고로 상수는 별로 영향을 끼치지 않기 때문에 무시될 수 있다. (마지막 결론에서)

그러므로 예제로 T(N)=3n*n + 1일 때 O(n*n)이라고 말할 수도 있지만 O(n*n*n)이라고 말할 수도 있는 것이다.

하지만 가장 작은 경우가 효용이 크므로 일반적으로 최고차항으로 표기를 한다. O(N)표기법은 적어도 그래프의 가속도가 N보다 작음을 나타내준다.

O표기법: 최악의 경우

Ω표기법: 최선의 경우

θ표기법: 일반적 경우 (상수만 조절해서 다 커버될 때 - 고로 정확하다)

실행시간을 분석하는 것과 마찬가지로 (=시간소요량) 메모리 공간차지도 분석할 수 있다. (=공간소요량)

나머지는 C를 병행한 실습이다.

유클리드 GCD알고리즘과 사람의 GCD구하는 방법을 비교해보고, 실행시간을 분석.

소수를 구할 때 정의를 이용하는 방법과 범위에서 구해야 할 때 에라토스테네스의 체를 쓰는 것이 더 적합한 경우.

최적화에 대한 설명도 나오지만 내가 보기엔 다 사족. 그나마 최적화는 맨 마지막에 해야 한다는 게 내가 명심해야 한다는 느낌이 든달까.