알고리즘 정의 (Algorithm)

1. 정의

  알고리즘은 잘 정의된 계산적 절차를 의미합니다. 어떤 input을 받아서 어떤 값 등을 산출합니다. 즉, 알고리즘은 input을 output으로 바꾸는 계산 단계들을 의미합니다. 우리는 잘 정의된 계산 문제들을 해결하는데 사용하는 tool로서 알고리즘을 봐 왔습니다. 이런 문제들은 input과 output간의 관계를 잘 정의합니다. 

 

  간단히 말해 수학과 computer science등의 분야에서 문제를 해결하기 위한 일련의 잘차나 방법을 계산적 형태로 공식화 한 것이 바로 알고리즘 입니다. 

 

2. 알고리즘의 예

예를들어 우리가 어떤 숫자들을 증가수열로서 정렬하고 싶다고 가정합시다. 이 문제는 실제적으로 많이 맞닥드리게 되는 문제이며, 다음과 같이 문제를 정의할 수 있습니다. 

 

• input
  • 숫자들의 배열 (a1, a2, ..., an)
• output
  • 정렬된 순열 (a'1, a'2, ... a'n)
  • a'1 <= a'2 <= ... <= a'n을 만족함

[4, 2, 7, 9]와 같은 input sequence가 있다고 할 때 우리는 이 input sequence를 "instance of a problem"라고 부릅니다. 

 

3. 알고리즘의 구현

의사코드, 순서도, Finite State Machine, 프로그래밍 언어 등을 통해서 알고리즘을 표현할 수 있으며, 구체적인 알고리즘 개발의 순서는 다음과 같습니다. 

 

1) 문제 정의, 모델 및 명세 작성

실제로 풀고자 하는 문제가 무엇인지를 구체적으로 정의 합니다. 이 과정에서 해결하고자 하는 알고리즘의 동작 및 input 그리고 output에 대한 상세 명세를 정의합니다. 

 

2) 설계 및 구현

구체적인 문제 해결 방법을 설계합니다. 동적 계획법을 사용할 지 혹은 Brute force 방법을 사용할지, backtracking 방법을 사용할지 등을 문제에 따라 결정하여 해결 방법을 설계 합니다. 

 

3) 테스트

구현한 알고리즘을 검증합니다. 여러가지 코너 case등을 적용하여 구현한 알고리즘이 문제 없음을 보장합니다. 

 

4. 알고리즘 성능

  문제 해결을 위한 알고리즘은 어떻게든 작성할 수 있습니다. 그러나 효과적인 알고리즘인지는 성능을 통해 정량적으로 파악해야 합니다. 구현한 알고리즘의 성능을 측정하는데는 두 가지 측면이 고려 됩니다.  첫 번째는 속도 이며 그 다음은 공간 입니다. 알고리즘의 성능은 속도와 공간의 효율을 보고 정량적으로 측정하게 됩니다. 

 

  보통 점근 표기법인 big-O notation을 사용하여 성능을 평가합니다. (점근 표기법은 최악의 상황을 고려합니다) 다음과 같은 성능 평가가 가능합니다. 

 

입력의 크기는 n으로 가정합니다. 

성능 평가 지표	설명
O(1)	n의 크기에 관계 없이 고정된 시간에 수행되는 알고리즘
O(log n)	log2n에 비례하는 시간이 소모되는 알고리즘
O(n)	n의 시간이 소모되는 알고리즘
O(n log n)	n에 비례되는 log n의 시간이 소모되는 알고리즘
O(n^2)	n^2의 시간이 소모되는 알고리즘 e.g., 최장 공통 부분 수열 문제
O(n^3)	n^3의 시간이 소모되는 알고리즘 e.g., 행렬 곱셈
O(M^n)	2^n와 같은 수행 시간이 소모되는 알고리즘
O(n!)	n!의 시간이 소모되는 알고리즘 e.g., 모든 순열 검사

 

5. Strassen's algorithm

  앞서 살펴봤듯이 Matrix multiplication(행렬 곱)에는 많은 연산 시간이 소모 됩니다. (O(N^3)) 많은 알고리즘 연구자들은 이런 행렬 곱에 대한 최적화된 계산 방법에 대해 연구해 왔으며, 그 중 대표적으로 유명한 알고리즘이 바로 스트라센의 알고리즘 입니다. 

 

이 알고리즘의 문제는 '행렬 곱' 이므로 매우 간단하게 문제정의를 할 수 있습니다. 

 

이 문의 알고리즘은 "pseudo code"로서 다음과 같이 표현 될 수 있습니다. 

출처: Introductio to Algorithm 2nd e/d