Ch2. 알고리즘

2.1 알고리즘이란

: 문제를 해결하기 위한 단계적인 절차 또는 방법

• 입력이 주어지고 → 알고리즘 수행 → 결과 도출

알고리즘의 일반적 특성

1. 입력이 존재
2. 결과값이 존재(출력)
3. 정확성문제 해결의 과정이 논리적이고 정확해야 한다.
4. 주어진 입력에 대해 올바른 해를 주어야 함
5. 수행성알고리즘에 모호한 표현(ambiguity)이 있다면 알고리즘을 프로그래밍을 할 수 없게 된다.
6. 알고리즘의 각 단계는 컴퓨터에서 수행 가능
7. 유한성제한된 개수의 명령 단계를 거쳐서 반드시 언젠가는 종료되어야 한다.
8. 유한 시간 내에 종료되어야 한다.
9. 효율성
10. 문제 해결 과정이 비교했을 때 좀 더 효율적일수록 가치가 높다.
11. 일반성
12. 같은 타입의 문제가 들어온다면 해당 알고리즘을 항상 적용할 수 있어야 함
13. 확장성함수의 특성과 비슷
14. 동일한 입력이 들어왔을 때 출력이 항상 같아야 한다.

2.2 최초의 알고리즘

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

-가장 오래된 알고리즘

-최대 공약수 = 2개의 자연수의 공약수들 중에서 가장 큰 수

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

→ 뺄셈 대신 나눗셈을 사용하면 빠르게 해를 찾을 수 있다.

-방법 = 작은 수가 0이 될 때까지 과정을 반복하다가 0이 되면 나머지 숫자가 최대 공약수임

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

1. if b == 0 return a // b가 0일 때 최대 공약수는 a이다
2. return Euclid(b, a mod b) //작은 수 b , a를 b로 나눈 나머지

-함수는 메모리의 시스템 스택에 저장된다.

E(24, 14) → E(14, 10) → E(10, 4) → E(4, 2) → E(2, 0)

결과값 2를 자신을 호출한 곳으로 이동

다른 최소 공배수 구하는 알고리즘

alg greatestCommondivisor (a, b)
	input integer a, b (a >= b)
	output integer gcd
-- (1) --
1. gcb <- 1
2. for i <- 1 to b // i는 1 ~ b까지 (최대 공약수는 b보다 작을 것임)
			if (a % i == 0 && b % i == 0 ) // i가 둘 사이의 약수라면 
					gcd <- i
3. return gcd

--다른 방법 (2) -- 
1. for i <- b downto 1
			if(a % i == 0  && b % i == 0)
					return i

(1) 과 (2) 의 차이는 (1) 은 gcd가 계속 업데이트되면서 찾는데 (2) 는 역으로 찾기 때문에 바로 조건에 맞으면 그것이 최대 공약수이므로 더 효율적인 알고리즘이라고 할 수 있다.

2.3 알고리즘의 표현방법

-알고리즘의 형태는 단계별 절차

-일반적으로 의사코드로 표현 (프로그래밍 언어와 유사한 형태)

-각 특징

자연어와 플로우 차트는 표현의 제약이 있다.

플로우 차트는 복잡한 알고리즘은 표현하기 어렵다. 간단한 알고리즘에 한하여 제한적으로 사용된다.

예시 - 최대 정수 찾기 문제

(1) 자연어로 표현

   1. 첫 카드의 숫자를 읽고 머릿속에 **기억**

1. 다음 카드 숫자를 읽고 그 숫자를 머릿속의 숫자와 비교
2. 비교 후 큰 숫자를 머릿속에 기억
3. 다음에 읽을 카드가 남아있으면 2번으로 간다.
4. (더 이상 읽을 카드가 없을 때까지 1~4번 반복)
5. 머릿속에 기억된 숫가자 최대 숫자이다.

-모호한 표현을 사용하면 안된다. 명확하게 각각의 절차들을 명확하게 표현

(2) 의사코드로 표현

배열 A에 10개의 숫자가 있다면 (랜덤숫자)
1. max = A[0]
2. for i = 1 to 9
3. if (A[i] > max)
			max = A[i] // 새로운 최대 숫자로 업데이트 
4. return max

 

(3) 플로우 차트

세모 = 조건문 (A[i] > max)

2.4 알고리즘의 분류

문제의 해결방식에 따라서 (접근 방법에 따라)

-분할 정복 알고리즘

-그리디 알고리즘

-동적 계획 알고리즘

-근사 알고리즘

-백트래킹 알고리즘

-분기 한정 알고리즘

문제의 속성에 따라서 각각에 적합한 해결방식들이 있다.

문제 자체에 기반하여 분류

-정렬 알고리즘

-그래프 알고리즘

-기하 알고리즘

특정 환경에 따른 분류

어떤 환경에서 제기되는 문제들을 위한 알고리즘이냐에 따라

-병렬 알고리즘

-분산 알고리즘

-양자 알고리즘

-유전자 알고리즘

2.5 알고리즘의 효율성 표현

알고리즘이 효율적인지 아닌지에 따라

자료구조는 데이터를 어떻게 조직하고 어떻게 접근하는 것인지가 가장 좋은 방식인지에 대한 이야기

가장 중요한 관심사는 얼마나 좋은 알고리즘과 좋은 데이터구조를 사용하는가 이다.

여기서 “좋은”에 대한 척도는 알고리즘의 효율성을 의미

알고리즘의 효율성

(1) 알고리즘의 수행시간 = 시간 복잡도

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

현재 메모리의 용량이 좋아서 크게 영향을 끼치지 않음

⇒ 일반적으로 알고리즘을 비교할 때 “시간 복잡도”가 주로 사용

시간 복잡도

: 알고리즘이 실행되는 동안 사용된 기본적인 연산 횟수를 입력 크기(n = 입력 데이터의 개수)의 함수

n에 대한 다항식

알고리즘의 효율성 비교를 위해 시간 복잡도를 확인해야 하는데 시간 복잡도는 n에 대한 함수

실행시간 측정법

(1) 실험적인 방법

1. 알고리즘을 실제로 프로그램으로 구현
2. input으로 다양한 크기와 요소를 준다. 그리고 실제 실행 시간을 측정한다

start time - end time 의 값들을 비교한다.

• 특징 = 알고리즘의 효율성을 객관화 시키기 어렵다. → 이론적인 방법으로 측정
• 컴퓨터의 사양 고려, 언어, 프로그램 작성 사람

(2) 이론적인 방법

findMax(A)

1. max ← A[0](1) 배열의 index에 접근 = 1번
2. (2) 해당 값을 max에 assignment = 1번
3. 이때 수행되어지는 연산
4. for i ← 1 to n-1(2) i값이 n-1 보다 작은가 비교 = n-1번총 = n+1번이다.
5. (3) (2) 에서의 비교연산은 i = n일 때까지 시도하고 n-1을 넘어가니 빠져나감 = 1번
6. (1) 대입 = 1번
7. if ( A[i] > max )(2) 비교 연산 = n-1번
8. 총 = 2(n-1)
9. (1) index 를 n-1번까지 넣어서 값 확인 = n-1번
10. max ← A[i]*여기서 if 문의 조건에 만족해야 실행되는 문장인데 왜 n-1번 대입한다고 했느냐 → 알고리즘의 효율성을 따질 때는 최악의 경우를 고려하여 따진다. <매번 할당된다>총 = 2(n-1)
11. (2) max에 대입 = n-1번
12. (1) index 를 n-1번까지 넣어서 값 확인 = n-1번
13. i = i +1(2) i 대입
14. 총 = 2(n-1)
15. (1) i 증가
16. return max
17. 총 = 1번

총 시간 복잡도 = 7n-2

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

1. 최악 경우 분석최악의 경우
2. 상한의 의미 = 아무리 ~해도 ~이상은 안걸림
3. 가장 일반적인 표현
4. 평균 경우 분석현실적으로 평균적인 입력을 가늠하지 쉽지 않음
5. 입력이 일반적으로 균등 분포로 들어온다고 가정
6. 최선 경우 분석제일 운이 좋은 경우 발생하는 경우
7. 분석에서 사용하지 않음
8. 가장 빠른 수행시간 분석

2.6 복잡도의 점근적 표기

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

n에 대한 함수 , 다항식의 함수

입력의 크기에 대한 함수로 표현하기 위해(단순하게 표현하기 위해)

⇒ “점근적 표기” 를 사용

점근적 표기

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

-최악의 경우를 n에 대한 함수로 구한 다음 밑의 표기법으로 표현

(1) 빅오 표기법 (가장 일반적)

(2) 빅 오메가

(3) 세타

빅오 표기

• O-표기의 정의 – 모든 n ≥ n0에 대해서 f(n) ≤ cg(n)이 성립하는 양의 상수 c와 n0가 존재하면, f(n) = O(g(n))이다.
• O-표기의 의미 – n0와 같거나 큰 모든 n (즉, n0 이후의 모든 n)에 대해서 f(n)이 cg(n)보다 크지 않다는 것
• f(n) = O(g(n))은 n0 보다 큰 모든 n 대해서 f(n)이 양의 상수를 곱한 g(n)에 미치지 못한다는 뜻
• g(n)을 f(n)의 상한(Upper Bound)이라고 한다

f(n) = O(g(n)) – n이 증가함에 따라 O(g(n))이 점근적 상한이라는 것

(즉, g(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 크다는 것)을 보여 준다.

함수 표기 f(n) : 2n^2 - 8n - 3

⇒ 빅오 표기 : O(n^2)

• 중요 !

= C가 어떤 값이든 상관이 없는데

f(n)과 g(n)의 교차점이 존재만 하고 그 교차점 이후로 “ f(n) ≤ cg(n) “ 를 만족하는 C가 있다면

⇒ 시간복잡도를 점근적 표현 방법으로 표현할 수 있다.

• 함수 f(n) : 2n^2 - 8n - 3 에 대하여 다양한 빅오 표현 방법이 있음 (ex) O(n^3), O(2**n)

하지만 다항식에서 최고 차수 항만을 취한 뒤, 그 항의 계수를 제거 하여 g(n)을 정한다.

[ 예시 ]

f(c) ⇒ O(1) , O(c) 가능

빅오메가

• Ω-표기의 정의 – 모든 n ≥ n0에 대해서 f(n) ≥ cg(n)이 성립하는 양의 상수 c와 n0가 존재하면, f(n) = Ω(g(n))이다.
• Ω-표기의 의미 – n0 보다 큰 모든 n 대해서 f(n)이 cg(n)보다 작지 않다는 것
• f(n) = Ω(g(n))은 양의 상수를 곱한 g(n)이 f(n)에 미치지 못한다는 뜻
• g(n)을 f(n)의 하한(Lower Bound)이라고 한다.

f(n) = Ω(g(n)) – n이 증가함에 따라 Ω(g(n))이 점근적 하한이라는 것

(즉, g(n)이 n0보다 큰 모든 n에 대해서 항상 f(n )보다 작다는 것)을 보여준다.

빅세타

• Θ-표기의 정의 – 모든 n ≥ n0에 대해서 c1g(n) ≥ f(n) ≥ c2g(n)이 성립하는 양의 상수 c1, c2 , n0가 존재하면, f(n) = Θ(g(n))이다.
• Θ-표기의 의미 – 수행시간의 O-표기와 Ω-표기가 동일한 경우에 사용한다.
• 즉, 동일한 증가율을 의미
• 2n^2+3n+5=O(n^2)과 동시에 2n^2+3n+5=Ω(n^2) 이므로, → 2n^2+3n+5=Θ(n^2)
• (각 표기법마다 최고차항만 표시하는 게 가능함)
• Θ(n2)은 n2과 (2n2+3n+5)이 유사한 증가율을 가지고 있다는 뜻 – 따라서 2n^2+3n+5≠Θ(n^3) 이고, 2n^2+3n+5≠Θ(n)이다.

f(n)=Θ(g(n)) – n0보다 큰 모든 n에 대해서 Θ-표기가 상한과 하한을 동시에 만족한다는 것을 보여준다.

자주 사용하는 빅오 표기

O(1) 상수 시간(Constant time)

입력에 상관없이 연산이 정해진 만큼만 한다.

O(logn) 로그 시간(Logarithmic time)

O(n) 선형 시간(Linear time)

O(nlogn) 로그 선형 시간(Log-linear time)

O(n^2) 이차 시간(Quadratic time)

O(n^3) 3차 시간(Cubic time)

O(n^k) 다항식 시간(Polynomial time), k는 상수

O(2**n) 지수 시간 (Exponential time)

2.7 효율적인 알고리즘의 필요성

같은 결과를 도출하는데 엄청난 차이나는 결과들을 보여준다.