알고리즘

알고리즘은 우리의 일상생활에서 그리 낯익은 단어는 아니다. 2016년 알파고와 이세돌 9단의 대국이 화제가 되면서 A.I와 함께 IT분야의 핫 키워드가 되었다. 알고리즘이라는 용어는 9세기경 페르시아의 수학자인 알콰리즈미(al-Khwarizmi)의 이름으로부터 유래되었다.

 

무함마드 이븐 무사 알콰리즈미

알고리즘은 기본적으로 문제를 해결하기 위한 단계적인 절차를 의미한다. 우리는 알게 모르게 알고리즘을 세우거나 실천한다.

대표적인 예로 요리가 있다. 요리를 하기 위해서 식재료를 준비하는 단계부터 요리를 순차적으로 하는 과정이 알고리즘과 유사하다.

요리라는 알고리즘을 단계적으로 실행하면 음식이라는 결과물이 나온다. 이 음식은 문제를 해결하면 나오는 답과 같다.

이렇듯이 알고리즘을 단계적인 정차를 따라하면 주어진 문제의 답을 준다. 

 

문제를 푸는 방법에 여러가지 방법이 있듯이 알고리즘의 종류도 여러가지이다. 주어진 문제에 대해 알맞는 알고리즘을 적용하는 능력과 보다 효율적인 알고리즘을 고안하는 것, 이러한 것이 알고리즘을 사용하는 것에 있어서 가장 중요하다고 필자는 생각한다.

 

알고리즘의 일반적인 특성

 

•정확성

알고리즘은 주어진 input에 대해서 올바른 output을 도출해야만한다.

예를 들어서 어느 정렬 알고리즘이 있다고 치자, 이 알고리즘이 A라는 입력에 대해서는 올바른 결과를 출력하지만 B라는 입력에 대해서는 정렬되지 않은 결과를 출력하면, 이는 알고리즘이라고 볼 수 없다.

 

•수행성

컴퓨터적 알고리즘을 실현화 할 때는 알고리즘에 애매모호한 표현이 있으면 안된다.

알고리즘을 이용하여 결과 값을 도출할 경우에 보통은 컴퓨터를 사용하고 high-level language를 통해 명령한다. 따라서 적어도 컴퓨터가 수행을 할 수 있어야한다.

 

•유한성

알고리즘은 일정한 시간 내에 종료되어야 한다.

알고리즘의 수행이 끝나지 않거나(무한 루프), 매우 오래걸리면 현실적으로는 결과 값을 도출받을 수 없는 경우, 이는 알고리즘으로서의 가치를 잃는다. 

 

•효율성

알고리즘은 효율적일 수록 그 가치가 높아진다. 

항상 시간적 효율성과 공간적인 효율성(메모리 공간 제한)을 생각해서 고안되어야한다.

이러한 효율성은 입력의 크기가 커질수록 그 가치가 높아진다.

자세한 내용은 시간복잡도 파트에서 다루겠다.

/// 시간복잡도 url ///

 

알고리즘의 표현

알고리즘의 표현 방법은 다음 글을 참고하자. 

various-data-analysis.tistory.com/6

자료구조와 알고리즘

알고리즘의 분류

알고리즘은 문제 해결 방식에 따라 분류된다.

대표적인 알고리즘을 몇가지 나열해 보겠다.

 

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

•그리디(Greedy) 알고리즘

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

•근사(Approximation) 알고리즘

•백트래킹(Backtracking) 알고리즘

•분기 한정(Branch-and-Bound) 알고리즘

•랜덤(Random) 알고리즘

•병렬(Parallel) 알고리즘

•분산(Distributed) 알고리즘

•양자(Quantum) 알고리즘

•유전자(Genetic) 알고리즘

 

모든 문제들이 위에 기재된 알고리즘들로만 해결되는 것이 아니다. 우리가 아는 알고리즘보다 모르는 알고리즘이 더 많다. 

이렇게 알려지지 않은 알고리즘은 서로 유사한 성격을 지니지 못하므로 따로 분류하여 명명하기도 힘들고 세분화하기에는 너무 다양하다.

 

문제를 해결하는 방식은 문제의 본질과 속성에 밀접한 관계가 있기 때문에 문제에 따라 효율적으로 작동하는 알고리즘이 달라진다. 

위 서론에서 말 했듯이 주어진 문제에 대해 알맞는 알고리즘을 적용하는 능력과 보다 효율적인 알고리즘을 고안하는 것이 가장 중요하다고 필자는 생각한다.

 

잘못된 정보나 오류, 오타, 독자 입장에서의 수정사항 및 피드백 환영합니다. 

E-mail : jhmh0226@gmail.com