알고리즘

알고리즘(algorithm)이란 문제를 해결하기 위해 입력을 받아 유한한 단계의 계산을 거쳐 출력을 생성하는 절차적 규칙을 말한다. 알고리즘은 모든 가능한 입력에 대해 명확하게 정의되며 반드시 종료됨이 보장되는 계산 방법이어야 한다.⁽¹⁾

알고리즘은 계산을 실행하기 위한 규칙들의 집합이라고 보면 편하다. 정의를 보면 알 수 있겠지만, 본래 알고리즘은 수학에서 출발했다.⁽²⁾ 단어 자체도 페르시아의 수학자인 알콰리즈미(الخوارزمي)의 이름에서 유래했다고 알려졌다.

형식적으로 알고리즘은 다음 조건을 만족해야 한다.

• 입력이 명확히 정의되어 있다
• 각 단계가 모호하지 않다
• 유한한 횟수의 단계 후 반드시 종료한다
• 모든 허용된 입력에 대해 동작이 정의된다

이를 표현하기 위해 크게 의사코드, 순서도, 프로그래밍 언어를 사용한다. '쉽게 배우는 알고리즘'과 같은 책은 코딩 언어를 배우기보다는 알고리즘의 사고 구조 틀에 기반하기 때문 의사코드를 애용한다.

대표적인 것 일부 소개한다.

• 재귀 - 자기 자신을 호출하는 방법이다. 함수 f가 f를 재호출하는 것, 수열의 귀납적 정의(피보나치 수열) 등을 생각하면 된다.
• 근사 - 답을 내기 어려운 문제일 때 어떤 입력값을 받고 최대한 가장 가까운 방법을 찾는 것이다. 예를 들자면 뉴턴 방법⁽³⁾으로 \sqrt2를 찾을 때 소숫점 이하로 무한히 출력할 수 없으므로 어떤 양수 \delta에 대하여 유한한 시간 안에 |\sqrt2-a|<\delta를 만족하는 a를 찾겠다는 거다. 더 수학적으로 쓰면 \forall\delta>0\;\exists\;Algorithm\;A\;s.t.\;A(\delta)=a\in\mathbb Q\;and\;|\sqrt2-a|<\delta),\;where\;A(\delta)\;halts\;in\;finite\;time.에서 알고리즘 A가 그 뉴턴 방법 중의 하나라는 것.
• 무차별 대입 공격 - 브루트 포스라고도 한다. 말그대로 무차별적으로 제한조건만 가지고 막 대입해보는 것. 예를 들어 10보다 작은 제곱수는 뭐가 있는지 알아보기 위해 1~9의 자연수를 모두 검사해보는 것이다. 알고리즘을 설계하는 데에 의외로 도움이 많이 될 수 있다.
• 분할 정복 - 어려운 문제를 쉬운 문제 여러개로 쪼개는 것이다. 예를 들어 여러 항목들에서 중앙값을 한번에 찾기 어려운 상태일 때, 여러 그룹으로 쪼개서 중앙값의 중앙값을 찾는 방법 같은 것들이 있다. 이 방법은 최악의 경우에도 선형 시간이 보장되는 훌륭한 탐색 알고리즘이다.
• 휴리스틱 - 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘 내부에서 쓰이는 평가 기준. 대표적으로 최단 경로 문제에서 여러 길들이 후보가 있을 때 어떤 길을 선택할지 정해진 조건에 따라 고르는 것이 있다.

굉장히 중요한 개념이다. 알고리즘이 입력의 크기에 따라 얼마나 많은 연산을 수행하는지를 나타내는 척도이다. 이는 실제 실행 시간 자체를 의미하기보다는, 입력 크기가 증가할 때 필요한 계산량이 어떤 형태로 증가하는지를 분석하는 개념이다.