알고리즘
알고리즘이란?
알고리즘이란, 어떠한 문제를 해결하기 위한 명확한 일련의 단계적인 처리 과정을 지칭하는 단어이다. 쉽게 말해 어떤 문제를 풀어나가는 명시적인 방법이라고 할 수 있다.
예를 들어, 요리를 할 때 원하는 음식을 만들기 위해서는 그 음식을 만드는 방법 즉 레시피가 필요하다. 문제해결이라는 주제에 있어서는 알고리즘이 이러한 레시피와 같은 역할을 한다.
컴퓨터 과학에서 알고리즘은 “주어진 문제에 대해 하나 이상의 결과를 만들 수 있고, 여러 의미로 해석되지 않게 모호하지 않고 명확하며, 컴퓨터가 수행할 수 있는, 유한한 단계로 이루어진 일련의 명령어들의 집합” 이라고도 정의된다.
알고리즘의 어원
알고리즘은 아랍어 al-khwarizmi를 잘못 음역한 중세 라틴어 algorismus 에서 유래했다.. 이는 Khwarazm 출신이라는 의미로, 이 지역은 현대 우즈베키스탄의 히바 지역에 해당한다.
혹은 페르시아의 수학자 Al-Kwarizmi 의 이름에서 유래했다고도 한다. 그의 저서가 서구에 정교한 수학 개념을 전파하면서, 그의 이름이 변형되어 알고리즘이라는 단어로 정착되었다는 설이다.
컴퓨터과학에서의 알고리즘
컴퓨터의 핵심 역할은 입력 데이터와 프로그램을 이용해 빠르고 정확하게 문제를 해결하는 것이다. 여기서 프로그램은 문제를 해결하기 위한 일련의 명령어들의 집합으로 정의되는데, 알고리즘이 이에 해당한다.
즉, 알고리즘이 없다면 프로그램도 존재할 수 없으며, 컴퓨터를 활용해 문제를 해결하는 것도 불가능해진다. 따라서 알고리즘은 컴퓨터 과학에서 필수적이며, 핵심적인 개념이라고 할 수 있다.
알고리즘의 조건
알고리즘의 조건들
알고리즘은 다음과 같은 조건들을 만족해야 한다.
| No | 구분 | 조건 |
|---|---|---|
| 1 | 입력과 출력input&output |
0개 이상의 입력을 받아서 1개 이상의 출력을 생성할 수 있어야 한다. |
| 2 | 명확성definiteness |
각 단계(명령)은 모호하지 않고 단순하며 명확해야 한다. |
| 3 | 유한성finiteness |
무한하지 않은, 유한한 개수의 단계를 거친 후 반드시 종료가 될 수 있어야 한다. |
| 4 | 유효성effectiveness |
모든 명령은 컴퓨터에서 수행할 수 있어야 한다. |
| + | 효율성efficiency |
알고리즘은 효율적인 구조여야 하며, 이를 통해 계산량과 계산시간을 최소화할 수 있어야 한다. |
(1) 입력과 출력
알고리즘은 0개 혹은 그 이상의 입력을 받아 반드시 출력을 만들 수 있어야 한다. 만약 출력을 만들 수 없다면, 문제 해결에 기여할 수 없다는 의미(상황에 변화를 줄 수 없다는 의미)이므로 그 존재 의미가 없다.
0개 이상의 입력이라는 것은 문제 해결을 위해 주어지는 입력 데이터가 없거나, 혹은 1개 이상의 입력 데이터가 주어지는 환경을 의미한다.
(2) 명확성
알고리즘의 각 단계는 여러 의미로 해석되지 않고 단 하나의 의미로 명확하게 해석되어야 하며 단순해야 한다.
(3) 유한성
알고리즘은 반드시 끝이 있어야 한다. 즉, 유한한 개수의 단계를 거쳐 반드시 종료가 될 수 있어야 하며 무한 루프에 빠지는 알고리즘은 문제 해결을 위한 올바른 알고리즘이 아니다.
(4) 유효성
알고리즘은 반드시 컴퓨터에서 실행 가능해야 한다. 즉, 실행 불가능한 연산이나 비현실적인 복잡도의 계산을 포함하면 안된다.
(5) 효율성
위와 같은 조건들을 만족한다면 기본적으로 해당 알고리즘의 대상 문제는 “해결 가능한 문제”라는 것이다.
여기에 더해 실용적인 관점에서 알고리즘은 효율적이어야 한다는 단서가 하나 더 붙는다. 아무리 해결 가능한 알고리즘이더라도 계산량이 지나치게 많거나, 실행 시간이 비현실적으로 길다면 실질적으로 사용할 수 없기 때문이다.
알고리즘 예시
(1) 최솟값 찾기
주어진 숫자들 중 가장 작은 값을 찾는 알고리즘.
선형 탐색, 이진 탐색 등의 알고리즘이 있다.
(2) 퀘닉스버그 다리 문제
7개의 다리가 있는 도시에서 한 번씩 모든 다리를 건너 원래 위치로 돌아올 수 있는지 판단하는 문제.
오일러 경로와 같은 알고리즘이 있다.
(3) 최단 경로를 찾는 문제
그래프에서 특정 시작점에서 목적 지점까지의 최단 거리를 찾는 문제.
데이크스트라 알고리즘, 벨만-포드 알고리즘 등이 있다.