1. 알고리즘

작성일 2019-08-15

 

앞으로 있을 알고리즘 설명에 앞서 알고리즘이란 무엇인지 알아보고 가도록 하겠습니다.

 

 1. 알고리즘의 어원

 

 아부 압둘라 무함마드 이븐 무사 알콰리즈미

 페르시아의 수학자로 페르시아 최초의 수학책을 만들었는데, 인도에서 도입된 아라비아 숫자를 이용하여 최초로 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈)을 만들고 0과 위치값을 사용한 수학자이다.

 

이 사람의 이름을 라틴어화한 algorismus에서 따온 말이 Algorithm이다

 

 

 

2. 알고리즘이란?

 

사전적 정의를 한 번 살펴보자

 

표준국어대사전

(컴퓨터) 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. 

 

고려대한국어대사전

(전산) 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법.

 

간략하게 말하자면 문제 해결을 위한 절차나 방법 모두를 알고리즘이라고 말 할 수 있다.

 

간단하게 알고리즘의 예를 들자면

요리를 만들기 위한 레시피, 자동차의 생산공정, 자판기에서 음료수를 뽑아 먹기 위한 일련의 과정 모두 알고리즘라고 할 수 있다.

 

※최초의 알고리즘은 기원전 300년경 유클리드의 최대공약수 알고리즘이다

 

 

 

3. 알고리즘의 특징/조건

 

대부분의 알고리즘은 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수를 생성하기 위한 일반화된 작업을 정의

 

◎ 입력과 출력

    입력은 없을 수도 있으나, 출력은 반드시 하나 이상 있어야한다

 

◎ 유한성

    한정된 수의 작업 후에는 반드시 알고리즘이 종료 되어야 함

 

◎ 명확성

    각 단게는 단순 명확해야하며, 모호하지 말아야 함

 

◎ 효과성

    알고리즘은 효율적일수록 가치가 높다(시간, 공간적 효율성)

 

◎ 일반성

    특정 입력값만이 아니라 요구되는 형태의 모든 문제에 적용 가능 해야 된다

 

 

 

4. 알고리즘의 표현

 

◎ 알고리즘의 표현

    알고리즘은 일상 언어, 의사코드, 흐름도(순서도), 프로그래밍 언어 등 다양하게 표현할 수 있다

 

◎의사코드(pseudo code)

   -pseudo는 '허위의, 가짜의, 모조의' 라는 뜻을 가진 단어로 pseudo code는 일반적인 프로그래밍 언어가 아닌

   일반적인 언어로 코드를 흉내 내어 놓은 코드이다.

 

   -알고리즘의 표현은 pseudo code로 많이 하는 편이다

 

예시)

 

Num이라는 배열에서 가장 작은 수를 찾아내는 알고리즘

 

 

-일상언어(한글)

 

(1) Num배열의 첫번째 인덱스에 들어 있는 값을 Min 변수에 추가 시켜 준다.

(2) Num배열의 인덱스를 순차적으로 탐색한다

(3) Num의 값이 Min보다 작을 경우 Min의 값을 Num[탐색한 순서]로 치환시켜 준다.

(4) Min에 들어있는 값을 반환시켜 준다

 

 

-Programming language(Java)

 

 public int MinNumber(int[] Num){

   int Min = Num[0];

   

   for(int i = 0; i < Num.length; i++){

       if(Num[i] < Min) Min = Num[i];

     }

   return Min;

 }

 

 

-pseudo code

 

(1) Min = Num[0]

(2) for i = 0 to length of Num

(3) if(Num[i] < Min) Min = Num[i]

(4) return Min

 

 

위에서와 같이 의사코드를 사용하게 되면 조금 더 직관적이고 간단하게 표현 할 수 있다.

 

 

 

5. 알고리즘의 효율성 표현

 

◎ 시간 복잡도

    알고리즘의 연산 횟수 or 수행 시간을 나타냄

 

◎ 공간 복잡도

    알고리즘이 수행 될 동안 사용 되는 메모리의 크기

 

일반적으로 알고리즘의 효율성을 비교할 때는 시간 복잡도가 주로 사용된다

 

※효율적인 알고리즘이 필요한 이유는 시간 복잡도, 공간 복잡도 파트에서 자세하게 설명할게요

 

 

 

Summary

알고리즘은 어떠한 문제를 해결하는 단계적 절차(과정) 또는 방법이며 어떠한 언어로도 작성될 수 있고 알고리즘의 효율성은 거의 알고리즘의 수행 시간과 직결된다.