알고리즘이란?

이번 포스팅에서는 알고리즘(algorithm)에 대해 알아보겠습니다.

일상생활에서도 간혹 알고리즘이란 용어를 사용할 때가 있습니다.

보통 문제 해결을 위한 방법론 또는 문제를 풀 수 있는 레시피 정도로 사용되곤 합니다.

레시피가 식재료를 사용해서 음식을 조리하는 일련의 절차, 과정을 나타내는 것처럼,

알고리즘은 주어진 문제를 해결하기 위한 일련의 처리 과정을 나타내는 것입니다.

 

예를 들어서 스마트폰에 '한붓그리기' 게임을 해보신 적이 있을 것입니다.

뭐 그냥 게임이니까 각 점을 순차적으로 이어나가다가 막히면 다시 도전하곤 했지요.

하지만 이 게임에는 수학자 오일러(Euler) 경로를 찾는 문제로

각 정점의 차수(각 점에 연결된 선의 개수)가 홀수인 점이 없거나 두 개인 모형에서 홀수 점에서 시작해야 한붓 그리기를 성공할 수 있다는 알고리즘이 숨겨있습니다.

한붓 그리기 예

 

또 한 가지 예로 내비게이션 앱을 이용해서 최단거리로 이동하려면 T맵의 경우 "아리야! 최단거리 안내해줘!" 하고 음성명령을 주면 바로 최단거리 경로로 수정해서 안내를 하는데, 바로 여기에도 다익스트라(Dijkstra) 알고리즘을 통해서 도로 간 연결된 간선의 길이와 이동 시간 등을 이용해 최단거리 또는 최소 시간으로 안내를 해주는 알고리즘이 적용됩니다.(물론 다른 알고리즘이 적용될 수도 있지요. 알고리즘은 무궁무진할 수 있으니까요^^)

 

그럼 컴퓨터에서는 알고리즘을 연산이나 명령어를 통한 제어 또는 문제 해결이라고 보았을 때 아래와 같은 조건을 만조해야 합니다.

• 입출력(Input/Output) : 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 합니다.
• 명확성(definiteness) : 각 명령은 모호하지 않고 단순 명확해야 합니다.
• 유한성(finiteness) : 한정된 수의 단계를 거친 후에는 반드시 종료되어야 합니다.
• 유효성(effectiveness) : 모든 명령 또는 연산은 컴퓨터에서 수행이 가능해야 합니다.

그럼 알고리즘은 어떻게 표현할까요?

알고리즘은 입출력 조건과 처리 조건 등을 고려해서 설계할 수 있는데 일상적인 언어로 표현하거나 순서도(flow chart), 의사 코도(pseudo code) 등을 통해서 표현되고 기술할 수도 있습니다.

일상적인 언어로 표현한다면 단순하게 아래와 같이 기술할 수 있습니다.

Step 1 : 숫자를 입력한다.

Step 2 : 숫자가 0이 아니면 값을 저장한다.

Step 3 : 종료한다.

 

의사 코드로 표현한다면

Insert(Num)

if(Num != 0)

    Save(Num)

End

 

순서도로 다이어그램을 만들어 보면 아래와 같습니다.

 

프로그램 개발 시 어떤 기능을 구현하기 위해서 절차적인 사고가 필요합니다.

문제 해결 과정을 단계적으로 기술하여 코드화 해 나가는 것이 코딩이고 알고리즘 구현이라 할 수 있습니다.

 

알고리즘에서 반드시 고려해야 할 사항이 또 한 가지가 있습니다.

바로 자료구조(data structure)인데,

자료 구조라 함은 컴퓨터 기억 공간 내에 자료를 표현하고 조직화하는 방법을 말합니다.

효율적인 알고리즘을 설계하기 위해서는 반드시 적절한 자료구조를 선택해야 합니다.

자료구조의 성격에 따라 프로그램 성능이 좌우될 수도 있기 때문에 최적화를 추구하기 위해서는 데이터 입출력 빈도나 데이터 양, 탐색 방법 등을 고려하여 목적에 부합한 자료구조를 만들어야 합니다.

 

이번 포스팅에서는 알고리즘이 무엇인지에 대해 살펴보았습니다.

문제 해결을 위한 알고리즘 개발은 매우 중요하기 때문에 거의 모든 분야에서 연구되고 있고

지금 이 시간에도 새로운 알고리즘이 탄생하고 있습니다.

여러분들도 문제 해결 시 알고리즘을 만들어서 적용해 본다면 도움이 될 수 있을 거라 생각합니다.

 

다음 포스팅에서는 알고리즘과 단짝이 되는 자료구조에 대해 정리해 보겠습니다.

감사합니다.