알고리즘이란

(1) 알고리즘이란

(2) 알고리즘 표현 방법

(3) 알고리즘의 분류

(4) 알고리즘의 효율성 표현

---

(1) 알고리즘이란

 

알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다.
컴퓨터 분야에서는 컴퓨터를 이용하여 해결할 수 있는 문제여야 한다.

다음은 알고리즘의 일반적인 특성이다.

정확성 : 모든 입력에 대하여 원칙적으로 올바른 답을 출력해야 한다.
수행성 : 각 단계는 컴퓨터에서 수행이 가능하여야 한다. 애매한 표현은 컴퓨터에서 수행할 수 없다.
유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.
효율성 : 알고리즘은 항상 시간적, 공간적인 효율을 갖도록 고안되어야 한다.

---

(2) 알고리즘의 표현 방법

 

알고리즘의 형태는 단계별 절차이므로, 컴퓨터 프로그래밍 언어로만 표현할 필요는 없다.
그러나 일반적으로 프로그래밍 언어와 유사한 의사 코드로 표현한다.
이전 포스트(2020/12/28 - [Algorithm/개념] - 일상 생활에서의 알고리즘)에서 다룬 ‘최대 숫자 찾기’ 알고리즘

은 다음과 같다.

 

보통 말로 표현한 알고리즘

첫 카드의 숫자를 읽고 머릿속에 기억해 둔다.
다음 카드의 숫자를 읽고, 그 숫자를 머릿속의 숫자와 비교한다.
비교 후 큰 숫자를 머릿속에 기억해 둔다.
다음에 읽을 카드가 남아 있으면 line 2로 간다.
머릿속에 기억된 수자가 최대 숫자이다.

의사 코드로 표현한 알고리즘

max=A[0]
for i = 1 to 9
  if(A[i] > max) max = A[i]
return max

위 경우는 카드가 10장 있다고 가정한 경우이다.

 

알고리즘이 매우 간단하면, 보통 말로도 표현할 수 있으나, 복잡하면 표현하기 어렵다.
그리하여 많은 경우 알고리즘을 의사코드로 표현한다.
‘플로우 차트’형식으로도 알고리즘을 표현하기도 하지만, 매우 제한적인 경우이다.

---

(3) 알고리즘의 분류

 

알고리즘은 문제의 해결 방식에 따라 다음과 같이 분류된다.

• 분할 정복 알고리즘(Divide-and-Conquer)

• 그리디 알고리즘(Greedy)

• 동적 계획 알고리즘(Dynamic Programming)

• 근사 알고리즘(Approximation)

• 백트래킹 기법(Backtracking)

• 분기 한정 기법(Branch-and-Bound)

 

이 외에도 랜덤 알고리즘, 병렬 알고리즘, 분산 알고리즘, 양자 알고리즘, 유전자 알고리즘 등이 있다.
문제에 따라 어떤 알고리즘이 더 효율적일지는 다를 것이다.
또한, 이름 지어지지 못한 알고리즘들도 다수 존재한다.
위와 같이 해결 방식에 따른 알고리즘 분류 외에도 문제에 기반을 두어 알고리즘을 분류하기도 한다.
정렬 알고리즘, 그래프 알고리즘, 기하 알고리즘 등이 그 예이다.

---

(4) 알고리즘의 효율성 표현

 

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

 

알고리즘을 프로그램으로 구현 및 실행 시켜 시간을 측정할 수 있으나, 이러한 방법은 객관적으로 평가하기가 어렵다. 왜냐하면 컴퓨터 환경, 프로그래밍 언어, 프로그래머 실력 등에 의하여 달라질 수 있기 때문이다. 그리하여 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.
예를 들어, n장의 숫자 카드 중에서 최대 숫자를 찾는데, 순차탐색으로 찾을 경우, (n-1)번의 비교를 수행한다. 이 경우, 시간복잡도는 (n-1)이다.

알고리즘의 복잡도를 표현하는 데는 다음과 같은 분석 방법들이 있다.

 

• 최악 경우 분석(worst case analysis)

• 평균 경우 분석(average case analysis)

• 최선 경우 분석(best case analysis)

 

일반적으로 ‘최악 경우 분석’으로 알고리즘의 복잡도를 나타낸다.

---

Reference

• 양성봉, 『알기 쉬운 알고리즘』. 파주: (주)생능출판사, 2013