알고리즘 intro..

알고리즘이란?

 

- 문제를 해결하는 단계적 절차 또는 방법

- 컴퓨터를 이용하여 해결할 수 있어야 한다.

- 해를 출력

 

<알고리즘의 일반적 특성>

 

1. 정확성: 주어진 입력에 대해 올바른 해를 주어야 함

2. 수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 함

3. 유한성: 알고리즘은 유한 시간 내에 종료되어야 함

4. 효율성: 알고리즘은 효율적일수록 그 가치가 높아진다.

 

최초의 알고리즘

 

: 유클리드의 최대공약수 알고리즘

 

2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.

 

ex. 최대공약수(24, 14) = 최대공약수(10, 14)

= 최대공약수(14-10, 10) = 최대공약수(4, 10)

= 최대공약수(10-4, 4) = 최대공약수(6, 4)

= 최대공약수(6-4, 4) = 최대공약수(2, 4)

= 최대공약수(4-2, 2) = 최대공약수(2, 2)

= 최대공약수(2-2, 2) = 최대공약수(0, 2)

= 2

 

Euclid(a, b)
입력: 정수 a, b; 단, a>=b>=0
출력: 최대공약수(a, b)

1: if b==0 return a
2: return Euclid(b, a mod b)

 

 

알고리즘의 표현 방법

 

- 알고리즘의 형태는 단계별 절차이므로, 마치 요리책의 요리를 만드는 절차와 유사

- 알고리즘의 각 단계는 보통 말로 서술할 수 있으며, 컴퓨터 프로그래밍 언어로만 표현할 필요x

- 일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드로 표현 

 

 

최대 숫자 찾기

 

 

- 카드의 숫자를 하나씩 비교하면서 본 숫자들 중 가장 큰 숫자를 기억해가며 찾는다.

- 마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다.

배열 A에 10개의 숫자가 있다면
1. max = A[0]
2. for i = 1 to 9 // 10번 이루어짐
3.    if (A[i] > max) max = A[i] // (n-1)번 이루어짐
4. return max // 1번 이루어짐

 

알고리즘 분류

 

1. 문제 해결 방식에 따른 분류

- 분할 정복 알고리즘

- 그리디 알고리즘

- 동적 계획 알고리즘

- 근사 알고리즘

- 백트래킹 알고리즘

- 분기 한정 알고리즘

 

2. 문제에 기반한 분류

- 정렬 알고리즘

- 그래프 알고리즘

- 기하 알고리즘

 

3. 특정 환경에 따른 분류

- 병렬 알고리즘

- 분산 알고리즘

- 양자 알고리즘

 

알고리즘의 효율성 표현

 

- 알고리즘의 수행 시간(시간 복잡도) => 알고리즘 비교에 많이 사용

- 알고리즘이 수행되는 동안 사용되는 메모리 크기(공간 복잡도)

 

<시간 복잡도>

: 알고리즘이 실행되는 동안 사용된 기본적인 연산(비교/읽기/갱신/숫자 계산) 횟수를 입력 크기의 함수로 나타냄

: 예제

* 순차 탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 총 비교 횟수는 9번

* n장의 카드가 있다면, (n-1)번의 비교 수행으로 시간 복잡도는 (n-1)

 

- 알고리즘 복잡도 표현 방법

* 최악 경우 분석: '어떤 입력이 주어지더라도, 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한의 의미

* 평균 경우 분석: 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등 분포를 가정

* 최선 경우 분석: 가장 빠른 수행 시간 분석(잘 하지 않음)

 

* 상각 분석

: 수행 시간 = (총 수행 시간)/(연산 횟수)

조건

1. 알고리즘에서 적어도 두 종류의 연산이 수행됨

2. 하나는 수행 시간 길고 다른 하나는 짧음

3. 짧은 연산은 많이 수행되고, 긴 연산은 적게 수행되어야 함

4. 분할 상환

 

<예제-등교 시간 분석>

집에서 지하철역까지 6분, 지하철을 타면 학교까지 20분, 강의실까지 걸어서 10분 걸린다.

 

1. 최선 경우

: 집을 나와서 6분 후 지하철역에 도착하고, 운이 좋게 바로 열차를 탄 경우

=> 6+20+10=36분

2. 최악 경우

: 열차에 승차하려는 순간, 열차의 문이 닫혀서 다음 열차를 기다려야 하고 다음 열차가 4분 후에 도착하는 경우

=> 6+4+20+10=40분

3. 평균 경우

: 대략 최악과 최선의 중간이라고 가정

=> 38분

 

4. 상각 분석

: 1회의 등교 시간을 분석하는 것이 아니라, 예를 들어, 한 학기 동안의 등교 시간을 분석

ex. 100번 학교에 갔는데 대부분은 지하철을 이용하지만 실제로 지하철보다 시간이 오래 걸리지만 버스를 타고 가끔 학교에 갈 때도 있다면 

: (한 학기 동안 학교 가는 데 소요된 시간)/100=1회 등교 시간

ex. 크러스컬의 최소 신장 트리 알고리즘

 

복잡도의 점근적 표기

 

- 시간 복잡도는 입력 크기에 대한 함수로 표기

: 함수는 여러 개의 항을 가지는 다항식

: 점근적 표기(for 입력 크기에 대한 함수로 표현)

* 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용

 

<𝑓(𝑛) = 𝑂(𝑔(𝑛))>

모든 𝑛 ≥ 𝑛0 에 대해서 𝑓(𝑛) ≤ 𝑐𝑔(𝑛)이 성립하는 양의 상수 𝑐와 𝑛0 가 존재하면, 𝑓(𝑛) = 𝑂(𝑔(𝑛))이다.

 

=> g(n)은 f(n)의 상한

(𝑔(𝑛)이 𝑛0 보다 큰 모든 𝑛에 대해서 항상 𝑓(𝑛)보다 크다)

밑에 두 개는 권장x

<𝑓(𝑛) = Ω(𝑔(𝑛))>

모든 𝑛 ≥ 𝑛0 에 대해서 𝑓(𝑛) ≥ 𝑐𝑔(𝑛)이 성립하는 양의 상수 𝑐와 𝑛0 가 존재하면, 𝑓(𝑛) = Ω(𝑔(𝑛))이다.

 

=> g(n)은 f(n)의 하한

(𝑔(𝑛)이 𝑛0 보다 큰 모든 𝑛에 대해서 항상 𝑓(𝑛)보다 작다)

 

<𝑓(𝑛) = Θ(𝑔(𝑛))>

모든 𝑛 ≥ 𝑛0 에 대해서 𝑐1𝑔(𝑛) ≥ 𝑓(𝑛) ≥ 𝑐2𝑔(𝑛)이 성립하는 양의 상수 𝑐1, 𝑐2, 𝑛0가 존재하면, 𝑓(𝑛) = Θ(𝑔(𝑛))이다.

 

=>  𝑛0보다 큰 모든 𝑛에 대해서 Θ-표기가 상한과 하한을 동시에 만족

=> 수행시간의 O-표기와 Ω-표기가 동일한 경우에 사용한다. 즉 동일한 증가율을 의미

 

n의 값이 줄어들면 c값들도 줄어듦

 

예제

풀이

 

자주 사용하는 O-표기

 

O-표기의 포함 관계

 

함수의 증가율 비교

 

효율적 알고리즘의 필요성

 

10억 개를 정렬하는 데 PC에서 O(n^2) 알고리즘은 300년, O(nlogn) 알고리즘은 5분

 

 

O(n^2)

O(n^2)

O(n^3)

O(n^4)

O(2^n) => 계속 재귀호출하기 때문에