[알고리즘] 2. 알고리즘을 배우기 위한 준비

2.1 알고리즘이란?

알고리즘 이란 문제를 해결하는 단계적 절차 또는 방법이다.

알고리즘의 일반적인 특성으로는

-정확성 : 주어진 입력에 대해 올바른 해가 주어져야 함

-수행성 : 각 단계는 컴퓨터에서 수행 가능하여야 함(반드시 컴퓨터로 수행되어야만 하는것은 아니지만 이 책은 컴퓨터로

             수행시킬수 있는 것만 다룸)

-유한성 : 일정한 시간 내에 종료되어야 함

-효율성 : 효율적일수록 그 가치가 높음(빠른 수행 시간, 크지 않은 메모리 공간)

 

2.2 최초의 알고리즘 : 유클리드(Euclid)의 최대공약수 찾는 알고리즘

핵심아이디어 : 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은수와의 최대 공약수와 같다는 성질을 이용하여 최대공약수를 찾았다. 단, 최대공약수(a, 0) = a 

ex) 최대공약수(24, 14)

= 최대공약수(24-14, 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)      = 최대공약수(2, 0) = 2

-> 뺄셈 대신에 나눗셈을 사용하면 매우 빠르게 해를 찾는다.

 

코드로 생각해보자.

def gcd(a, b): if a < b: (a, b) = (b, a) #a보다 b가 크면 서로의 자리를 바꾼다. #큰수가 왼쪽,작은수가 오른쪽 while b != 0: #b가 0일 될때까지 작업을 반복 (a, b) = (b, a%b) #(a, b)는 b와 a를 b로 나눈 나머지와의 최대 공약수랑 같다. return a #b(=나머지)가 0일때의 a값이 a,b의 최대 공약수가 된다. print(gcd(24,14))

결과 값 : 2

 

2.3 알고리즘의 표현 방법

- 말로표현

- 의사코드(pseudo code)로 표현(프로그래밍 언어와 유사한 코드)

- 플로우차트

 

2.5 알고리즘의 효율성 표현

알고리즘의 효율성은 알고리즘의 수행시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있다. 이들을 각각 시간복잡도, 공간복잡도라고 한다. 일반적으로 시간복잡도가 주로 사용됨

-최악 경우 분석

-평균 경우 분석

-최선 경우 분석

 

2.6 복잡도의 점근적 표기(책 p.42~ 그래프 확인!)

입력 크리 n이 무한대로 커질 떄의  복잡도를 간단히 표현하기 위해 사용하는 표기법이다.

- O(Big-Oh)표기 : 점근적 상한

- Ω(Big-Omega)표기 : 점근적 하한

- θ(Theta)표기 : 동일한 증가율

 

자주사용하는 O표기들

- O(1) : 상수시간

- O(log n) : 로그 시간

- O(n) : 선형시간

- O(nlog n) : 로그 선형시간

- O() : 제곱시간

- O() : 세제곱시간

- O() : 지수시간

 

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

효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다고 할 수 있다. 즉 값비싼 하드웨어의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 경제적이라고 할 수 있다.

 

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다.