티스토리 뷰

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다.


예를 들어, 학생 100명의 시험점수를 입력으로 받아 최고점을 출력하는 작업을 한다면 입출력을 다음과 같이 표현할 수 있다.


  • 입력 : 100개의 점수
  • 출력 : 입력된 100개의 점수 중 최대값


이 입출력을 다음과 같이 좀더 구체적으로 표현할 수도 있다.


  • 입력 : 100개의 변수 x[1],...,x[100]의 값
  • 출력 : x[1],...,x[100] 중 최대값


이런 입출력을 요구하는 알고리즘은 대략 다음과 같은 모양을 가질 것이다.


maxScore(x[], n)

{

num <- x[1...n]중 최대값.

return num;

}


위의 알고리즘은 maxScore 내의 서술적 표현을 필요한 수준까지 더 구체화할 수 있따. 실제 알고리즘을 만들 때는 구체화 과정을 거쳐 모호함이 없는 수준에서 마무리를 하게 된다. 함수나 서브루틴도 구체화 과저에서 도입되는 것이다. 잘 설계된 알고리즘은 명확하고 효율적이어야 한다.



알고리즘을 표현하는 방법은 여러가지가 존재하는데 자연어(natural language), 순서도(flow language), 가상 코드(pseudo code), 프로그래밍 언어(programming lungauge)로 나뉘어 진다. 위의 maxScore 알고리즘은 슈도코드로 작성된 알고리즘이다.



위의 그림은 알고리즘 순서도로 알고리즘의 내용을 기호로 사용한 그림으로 알기 쉽게 나타낸 것이다.


알고리즘이 어떠한 조건을 만족해야하는 지 살펴보면 다음과 같다. 알고리즘을 작성할 때 아래의 조건을 만족하는지 생각을하며 명확하고 효율적으로 작성해야한다.

  1. 입력 : 외부에서 제공되는 자료가 있을 수 있다.
  2. 출력 : 적어도 한가지 결과가 생긴다.
  3. 명백성 : 각 명령들은 명백해야 한다.
  4. 유한성 : 알고리즘의 명령대로 수행하면 한정된 단계를 처리한 후에 종료된다.
  5. 효과성 : 모든 명령어들은 명백하고 실행 가능한 것이어야 한다.


위에서 여러번 언급하였듯이 알고리즘은 가능하면 효율적이어야되는데, 알고리즘은 궁극적으로는 컴퓨터를 통해서 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 작은 입력에 대해서는 아무리 복잡한 알고리즘도 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때의 이야기인데, 충분히 큰 입력에 대해서는 알고리즘의 효율성에 따라 수행시간이 크게 차이가 날 수 있다. 같은 문제를 해결하기 위해 어떤 알고리즘은 100년이 걸리는데 다른 알고리즘은 1분이 걸릴 수도 있다. 입력이 충분히 큰 경우에 대한 분석을 점근적 분석(Asymptotic Analysis)이라고 하는데, 고등학교의 수학에서 배우는 와 비슷한 경우라고 생각하면 된다. 이렇게 점근적 분석을 통해 알고리즘들의 효율성을 나타내고 비교한다.


Reference : 

  • IT COOKBOOK - 쉽게 배우는 알고리즘 (문병로 저)
  • 컴퓨터인터넷IT용어대사전


아래의 손가락 버튼 눌러주는 센스^^


'프로그래밍 > 자료구조&알고리즘' 카테고리의 다른 글

삽입정렬(Insertion Sort)  (0) 2014.04.22
버블정렬(Bubble Sort)  (0) 2014.04.22
선택정렬(Selection Sort)  (0) 2014.04.22
알고리즘이란?  (0) 2014.04.22
레드블랙 트리(Red-black tree)  (0) 2014.04.15
이진트리의 순회 (Binary Tree Traversal)  (0) 2014.04.14
댓글