[[분류:알고리즘]] ==개요== 알고리즘(algorithm)이란 문제를 해결하기 위해 입력을 받아 유한한 단계의 계산을 거쳐 출력을 생성하는 절차적 규칙을 말한다. 알고리즘은 모든 가능한 입력에 대해 명확하게 정의되며 반드시 종료됨이 보장되는 계산 방법이어야 한다.[* 즉 모든 입력값에 대해 튜링머신이 정지하게 하는 명령을 말한다.] ==상세== 알고리즘은 계산을 실행하기 위한 규칙들의 집합이라고 보면 편하다. 정의를 보면 알 수 있겠지만, 본래 알고리즘은 수학에서 출발했다.[* 뉴턴 방법, 유클리드 알고리즘과 같은 것들.] 단어 자체도 페르시아의 수학자인 알콰리즈미([[아랍어|الخوارزمي]])의 이름에서 유래했다고 알려졌다. 형식적으로 알고리즘은 다음 조건을 만족해야 한다. * 입력이 명확히 정의되어 있다 * 각 단계가 모호하지 않다 * 유한한 횟수의 단계 후 반드시 종료한다 * 모든 허용된 입력에 대해 동작이 정의된다 이를 표현하기 위해 크게 의사코드, 순서도, 프로그래밍 언어를 사용한다. '쉽게 배우는 알고리즘'과 같은 책은 코딩 언어를 배우기보다는 알고리즘의 사고 구조 틀에 기반하기 때문 의사코드를 애용한다. ===설계 및 구현=== 대표적인 것 일부 소개한다. * 재귀 - 자기 자신을 호출하는 방법이다. 함수 f가 f를 재호출하는 것, 수열의 귀납적 정의(피보나치 수열) 등을 생각하면 된다. * 근사 - 답을 내기 어려운 문제일 때 어떤 입력값을 받고 최대한 가장 가까운 방법을 찾는 것이다. 예를 들자면 뉴턴 방법[* 복잡한 방정식을 풀 때 수치해석적으로 해를 구하는 대표적인 알고리즘이다.]으로 [math(\sqrt2)]를 찾을 때 소숫점 이하로 무한히 출력할 수 없으므로 어떤 양수 [math(\delta)]에 대하여 유한한 시간 안에 [math(|\sqrt2-a|<\delta)]를 만족하는 [math(a)]를 찾겠다는 거다. 더 수학적으로 쓰면 [math(\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의 자연수를 모두 검사해보는 것이다. 알고리즘을 설계하는 데에 의외로 도움이 많이 될 수 있다. * 분할 정복 - 어려운 문제를 쉬운 문제 여러개로 쪼개는 것이다. 예를 들어 여러 항목들에서 중앙값을 한번에 찾기 어려운 상태일 때, 여러 그룹으로 쪼개서 중앙값의 중앙값을 찾는 방법 같은 것들이 있다. 이 방법은 최악의 경우에도 선형 시간이 보장되는 훌륭한 탐색 알고리즘이다. * 휴리스틱 - 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘 내부에서 쓰이는 평가 기준. 대표적으로 최단 경로 문제에서 여러 길들이 후보가 있을 때 어떤 길을 선택할지 정해진 조건에 따라 고르는 것이 있다. ==분야== * [[정렬 알고리즘]] * [[선택 알고리즘]] * [[탐색 알고리즘]] * 그래프 알고리즘 * [[수치해석학|수치해석 알고리즘]] * 기계학습 * 데이터 압축 ==[[시간 복잡도]]== 굉장히 중요한 개념이다. 알고리즘이 입력의 크기에 따라 얼마나 많은 연산을 수행하는지를 나타내는 척도이다. 이는 실제 실행 시간 자체를 의미하기보다는, 입력 크기가 증가할 때 필요한 계산량이 어떤 형태로 증가하는지를 분석하는 개념이다.
