알고리즘

최종 수정 2026.03.24

![Flowchart of using successive subtractions to find the [greatest common divisor of number r and s|alt=In a loop, subtract the larger number against the smaller number. Halt the loop when the subtraction will make a number negative. Assess two numbers, whether one of them is equal to zero or not. If yes, take the other number as the greatest common divisor. If no, put the two numbers in the subtraction loop again.]] 수학과 컴퓨터 과학에서 알고리즘()은 특정 부류의 문제를 해결하거나 연산을 수행하는 데 일반적으로 사용되는 수학적으로 엄밀한 명령어의 유한한 순서열이다.[^1] 알고리즘은 계산 및 데이터 처리를 수행하기 위한 명세로 사용된다. 보다 진보된 알고리즘은 조건문을 사용하여 코드 실행을 다양한 경로로 분기시키고(자동화된 의사 결정이라 함), 유효한 추론을 도출할 수 있다(자동화된 추론이라 함).

이와 대조적으로, 휴리스틱은 명확하게 정의된 정확하거나 최적의 결과 없이 문제를 해결하는 접근 방식이다.[^2] 예를 들어, 소셜 미디어 추천 시스템은 흔히 "알고리즘"이라 불리지만, 진정으로 "올바른" 추천이란 존재하지 않으므로 실제로는 휴리스틱에 의존한다.

유효한 방법으로서, 알고리즘은 유한한 공간과 시간 내에서[^3] 함수를 계산하기 위한 잘 정의된 형식 언어로[^4] 표현될 수 있다.[^12] 초기 상태와 초기 입력(비어 있을 수도 있음)에서 시작하여,[^13] 명령어는 실행 시 유한한[^14] 수의 잘 정의된 연속적인 상태를 거쳐 진행되고, 최종적으로 "출력"을 생성하며[^15] 최종 종료 상태에서 멈추는 연산을 기술한다. 한 상태에서 다음 상태로의 전이는 반드시 결정론적일 필요는 없다. 무작위 알고리즘으로 알려진 일부 알고리즘은 무작위 입력을 포함한다.[^16]

어원

서기 825년경, 페르시아의 과학자이자 박학자인 무함마드 이븐 무사 알콰리즈미는 kitāb al-ḥisāb al-hindī(「인도 계산의 책」)와 kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī(「인도 산술의 덧셈과 뺄셈」)를 저술하였다. 12세기 초, 힌두-아라비아 숫자 체계와 산술을 다루는 이 문헌들의 라틴어 번역본이 등장하였는데, 예를 들어 세비야의 요한에게 귀속된 Liber Alghoarismi de practica arismetrice와 바스의 아델라드에게 귀속된 Liber Algorismi de numero Indorum이 있다.[^5] 여기서 alghoarismi 또는 algorismi는 알콰리즈미 이름의 라틴어화이며,[^1] 본문은 Dixit Algorismi, 즉 "알콰리즈미가 이르기를"이라는 문구로 시작한다.[^2]

영어에서 algorism이라는 단어는 계산에서 위치값 표기법의 사용을 의미하게 되었으며, 약 1225년경의 Ancrene Wisse에 등장한다.^17 14세기 후반 제프리 초서가 캔터베리 이야기를 저술할 무렵, 그는 위치값 계산에 사용되는 돌인 augrym stones를 묘사하면서 같은 단어의 변형을 사용하였다.[^18][^19] 15세기에 그리스어 ἀριθμός(arithmos, "수"; 참조 "arithmetic")의 영향으로 라틴어 단어는 algorithmus로 변형되었다.[^20] 1596년에 이르러 이 형태의 단어는 토마스 후드에 의해 영어에서 algorithm으로 사용되었다.^21

정의

하나의 비공식적 정의는 "일련의 연산을 정확하게 정의하는 규칙의 집합"으로, 이는 모든 컴퓨터 프로그램(수치 계산을 수행하지 않는 프로그램 포함)과 규정된 모든 관료적 절차[^22] 또는 요리책의 조리법을 포함한다.[^23] 일반적으로, 프로그램은 무한 루프가 때로 바람직할 수 있음에도 불구하고, 궁극적으로 정지하는 경우에만 알고리즘이다.[^24] 알고리즘을 출력을 결정하기 위한 명시적인 명령어의 집합으로 정의하며, 이는 기호에 대한 특정한 기본 연산만을 수행할 수 있는 컴퓨팅 기계 또는 인간이 따를 수 있는 것이다*.*[^25]

역사

고대 알고리즘

수학 문제를 풀기 위한 단계별 절차는 고대부터 기록되어 왔다. 여기에는 바빌로니아 수학(기원전 약 2500년), 이집트 수학(기원전 약 1550년), 인도 수학(기원전 약 800년 이후),[^6][^26] 이파 신탁(기원전 약 500년),[^27] 그리스 수학(기원전 약 240년),[^7] 중국 수학(기원전 약 200년 이후),[^28] 그리고 아랍 수학(서기 약 800년)이 포함된다.[^8]

알고리즘의 가장 초기 증거는 고대 메소포타미아 수학에서 발견된다. 바그다드 인근 슈루팍에서 발견된 수메르 점토판은 가장 초기의 나눗셈 알고리즘을 기술하고 있다. 함무라비 왕조 시대에 바빌로니아 점토판은 공식을 계산하기 위한 알고리즘을 기술하였다.[^29] 알고리즘은 바빌로니아 천문학에서도 사용되었다. 바빌로니아 점토판은 중요한 천문학적 사건의 시간과 장소를 계산하기 위한 알고리즘적 절차를 기술하고 활용하였다.[^30]

산술을 위한 알고리즘은 린드 수학 파피루스로 거슬러 올라가는 고대 이집트 수학에서도 발견된다. 알고리즘은 이후 고대 헬레니즘 수학에서도 사용되었다. 두 가지 예로는 니코마코스의 산술 입문에 기술된 에라토스테네스의 체[^31][^7]와 유클리드 원론()에서 처음 기술된 유클리드 호제법이 있다.[^7] 고대 인도 수학의 예로는 슐바 수트라, 케랄라 학파, 브라마스푸타싯단타가 있다.[^6]

암호화된 코드를 해독하기 위한 최초의 암호 알고리즘은 9세기 아랍 수학자 알킨디가 암호 메시지 해독에 관한 필사본에서 개발하였다. 그는 빈도 분석에 의한 암호 분석, 즉 최초의 암호 해독 알고리즘에 대한 최초의 기술을 제시하였다.[^8]

컴퓨터

추 구동식 시계

데이비드 볼터는 추 구동식 시계의 발명을 "중세 유럽의 핵심 발명"으로 평가하였으며, 특히 기계식 시계의 틱톡 소리를 만들어내는 버지 이스케이프먼트 메커니즘을 강조하였다.[^32] "정확한 자동 기계"[^33]는 곧바로 13세기의 "기계식 오토마타"와 19세기 중반 찰스 배비지와 에이다 러브레이스의 차분 기관 및 해석 기관이라는 "계산 기계"로 이어졌다.[^34] 러브레이스는 컴퓨터에서 처리하기 위한 최초의 알고리즘을 설계하였는데, 이는 단순한 계산기가 아닌 최초의 진정한 튜링 완전 컴퓨터로 간주되는 배비지의 해석 기관을 위한 것이었다. 배비지의 두 번째 장치의 완전한 구현은 그녀의 생전에 수십 년이 지나서야 실현되었지만, 러브레이스는 "역사상 최초의 프로그래머"로 불려 왔다.

전기기계식 계전기

벨과 뉴웰(1971)은 자카드 직기가 홀러리스 카드(천공 카드)의 전신이며, "전화 교환 기술"이 최초의 컴퓨터 개발로 이어졌다고 기술하였다.[^35] 19세기 중반까지 전화의 전신인 전신기가 전 세계적으로 사용되고 있었다. 19세기 후반에는 시세 표시기()가 사용되었고, 홀러리스 카드(약 1890년)도 사용되었다. 이어서 보도 코드를 테이프에 천공하여 사용하는 텔레프린터()가 등장하였다.

전기기계식 계전기를 이용한 전화 교환 네트워크는 1835년에 발명되었다. 이는 1937년 조지 스티비츠의 디지털 가산 장치 발명으로 이어졌다. 벨 연구소에서 근무하던 그는 톱니바퀴가 달린 기계식 계산기의 "번거로운" 사용을 관찰하였다. "그는 1937년 어느 날 저녁 자신의 아이디어를 시험하려고 귀가하였고... 작업이 끝났을 때, 스티비츠는 이진 가산 장치를 만들어 냈다."[^36][^37]

형식화

![[에이다 러브레이스 의 "주석 G" 도표, 최초로 출판된 컴퓨터 알고리즘]]

1928년, 다비트 힐베르트가 제기한 결정 문제(Entscheidungsproblem)를 풀려는 시도와 함께 현대적 알고리즘 개념의 부분적 형식화가 시작되었다. 이후의 형식화는 "유효 계산 가능성"[^38] 또는 "유효 방법"[^39]을 정의하려는 시도로 구성되었다. 이러한 형식화에는 1930년, 1934년, 1935년의 괴델-에르브랑-클레이니 재귀 함수, 1936년 알론조 처치의 람다 대수, 1936년 에밀 포스트의 공식화 1, 그리고 1936-37년 및 1939년 앨런 튜링의 튜링 기계가 포함된다.

현대 알고리즘

알고리즘은 시간이 지남에 따라 여러 방면에서 발전하고 개선되어 왔다. 오늘날 알고리즘의 일반적인 용도에는 인스타그램이나 유튜브와 같은 소셜 미디어 앱이 포함된다. 알고리즘은 사람들이 좋아하는 것을 분석하고 그와 상호작용하는 사람들에게 그러한 콘텐츠를 더 많이 추천하는 방식으로 사용된다. 양자 컴퓨팅은 문제를 더 빠르게 해결하기 위해 양자 알고리즘 절차를 사용한다. 보다 최근인 2024년에 NIST는 양자 컴퓨팅을 이용한 공격에 대한 방어를 강화하기 위한 새로운 암호화 알고리즘을 포함하는 포스트 양자 암호화 표준을 업데이트하였다.

표현 방식

알고리즘은 자연어, 의사코드, 순서도, 드라콘 차트, 프로그래밍 언어 또는 제어 테이블(인터프리터에 의해 처리됨) 등 다양한 종류의 표기법으로 표현할 수 있다. 알고리즘의 자연어 표현은 장황하고 모호한 경향이 있어 복잡하거나 기술적인 알고리즘에는 거의 사용되지 않는다. 의사코드, 순서도, 드라콘 차트, 제어 테이블은 자연어의 일반적인 모호성을 피하는 구조화된 알고리즘 표현 방식이다. 프로그래밍 언어는 주로 알고리즘을 컴퓨터가 실행할 수 있는 형태로 표현하기 위한 것이지만, 알고리즘을 정의하거나 문서화하는 데에도 사용된다.

튜링 기계

가능한 표현 방식은 많으며, 튜링 기계 프로그램은 기계 테이블의 나열(자세한 내용은 유한 상태 기계, 상태 전이표, 제어 테이블 참조), 순서도 및 드라콘 차트(자세한 내용은 상태 다이어그램 참조), "사중조 집합"이라 불리는 초보적인 기계어 또는 어셈블리 코드의 형태 등으로 표현할 수 있다. 알고리즘 표현은 또한 튜링 기계 기술의 세 가지 공인된 수준으로 분류할 수 있다: 고수준 기술, 구현 기술, 형식적 기술이 그것이다.[^9] 고수준 기술은 튜링 기계에서 어떻게 구현되는지를 무시하고 알고리즘 자체의 특성을 기술한다.[^9] 구현 기술은 알고리즘을 수행하기 위해 기계가 헤드를 이동하고 데이터를 저장하는 일반적인 방식을 기술하지만, 정확한 상태는 제시하지 않는다.[^9] 가장 상세한 수준인 형식적 기술은 튜링 기계의 정확한 상태표와 전이 목록을 제시한다.[^9]

순서도 표현

순서도라 불리는 그래픽 도구는 알고리즘(및 그에 대응하는 컴퓨터 프로그램)을 기술하고 문서화하는 방법을 제공한다. 순서도에는 네 가지 주요 기호가 있다: 프로그램 흐름을 나타내는 화살표, 직사각형(순차, GOTO), 마름모(IF-THEN-ELSE), 그리고 점(OR 연결)이다. 하위 구조는 직사각형 안에 "중첩"될 수 있지만, 상위 구조에서 단일 출구가 발생하는 경우에만 가능하다.

알고리즘 분석

알고리즘이 얼마나 많은 시간, 저장 공간, 또는 기타 비용을 필요로 하는지 아는 것은 종종 중요하다. 이러한 정량적 답변(추정치)을 얻기 위해 알고리즘 분석 방법이 개발되었다. 예를 들어, n개의 숫자로 이루어진 목록의 원소를 합산하는 알고리즘은 빅오 표기법을 사용하여 의 시간 요구량을 갖는다. 이 알고리즘은 두 가지 값만 기억하면 된다: 지금까지의 모든 원소의 합과 입력 목록에서의 현재 위치이다. 입력 숫자를 저장하는 데 필요한 공간을 계산하지 않으면 의 공간 요구량을 가지며, 그렇지 않으면 이 필요하다.

서로 다른 알고리즘은 동일한 작업을 다른 명령어 집합으로 수행하면서 시간, 공간, 또는 '노력'을 더 적게 혹은 더 많이 소모할 수 있다. 예를 들어, 이진 탐색 알고리즘(비용 )은 정렬된 목록이나 배열에서 테이블 검색에 사용될 때 순차 탐색(비용 )보다 우수한 성능을 보인다.

형식적 분석 대 경험적 분석

알고리즘의 분석과 연구는 컴퓨터 과학의 한 분야이다. 알고리즘은 특정 프로그래밍 언어나 구현을 참조하지 않고 추상적으로 연구되는 경우가 많다. 알고리즘 분석은 구현이 아닌 알고리즘의 속성에 초점을 맞춘다는 점에서 다른 수학 분야와 유사하다. 의사코드는 단순하고 일반적인 표현이므로 분석에 일반적으로 사용된다. 대부분의 알고리즘은 특정 하드웨어/소프트웨어 플랫폼에서 구현되며, 실제 코드를 사용하여 알고리즘 효율성이 테스트된다. 특정 알고리즘의 효율성은 많은 "일회성" 문제에서는 중요하지 않을 수 있지만, 빠른 대화형, 상업적, 또는 장기 과학적 용도로 설계된 알고리즘에서는 매우 중요할 수 있다. 작은 n에서 큰 n으로 규모를 확대하면 그렇지 않으면 무해한 비효율적 알고리즘이 드러나는 경우가 많다.

경험적 테스트는 성능에 영향을 미치는 예상치 못한 상호작용을 발견하는 데 유용하다. 벤치마크는 프로그램 최적화 후 알고리즘의 잠재적 개선 사항에 대한 전후 비교에 사용될 수 있다. 그러나 경험적 테스트는 형식적 분석을 대체할 수 없으며, 공정하게 수행하기가 쉽지 않다.[^10]

실행 효율성

잘 확립된 알고리즘에서도 가능한 잠재적 개선을 설명하자면, FFT 알고리즘(이미지 처리 분야에서 많이 사용됨)과 관련된 최근의 중요한 혁신은 의료 영상과 같은 응용 분야에서 처리 시간을 최대 1,000배까지 줄일 수 있다.[^40] 일반적으로 속도 향상은 문제의 특수한 속성에 의존하며, 이는 실제 응용에서 매우 흔하다.^11 이러한 규모의 속도 향상은 이미지 처리를 광범위하게 사용하는 컴퓨팅 장치(디지털 카메라 및 의료 장비 등)의 전력 소비를 줄일 수 있게 한다.

최선의 경우와 최악의 경우

알고리즘의 최선의 경우는 알고리즘이나 자료 구조가 작업을 완료하는 데 가장 적은 시간과 자원을 소모하는 시나리오 또는 입력을 말한다.[^41] 알고리즘의 최악의 경우는 알고리즘이나 자료 구조가 최대한의 시간과 계산 자원을 소모하게 만드는 경우를 말한다.[^42]

설계

알고리즘 설계는 문제 해결과 알고리즘 공학을 위한 방법 또는 수학적 과정이다. 알고리즘의 설계는 운용 과학 내의 분할 정복법이나 동적 프로그래밍과 같은 많은 해법 이론의 일부이다. 알고리즘 설계를 설계하고 구현하는 기법을 알고리즘 설계 패턴이라고도 하며,[^43] 그 예로는 템플릿 메서드 패턴과 데코레이터 패턴이 있다. 알고리즘 설계에서 가장 중요한 측면 중 하나는 자원(실행 시간, 메모리 사용량) 효율성이다. 대문자 O 표기법은 예를 들어 입력 크기가 증가함에 따른 알고리즘의 실행 시간 증가를 설명하는 데 사용된다.[^44]

구조적 프로그래밍

처치-튜링 논제에 따르면, 모든 알고리즘은 튜링 완전한 모델로 계산할 수 있다. 튜링 완전성은 조건부 GOTO, 무조건 GOTO, 대입, HALT의 네 가지 명령어 유형만을 필요로 한다. 그러나 Kemeny와 Kurtz는 무조건 GOTO와 조건부 IF-THEN GOTO의 "무질서한" 사용이 "스파게티 코드"를 초래할 수 있지만, 프로그래머는 이러한 명령어만을 사용하여 구조적 프로그램을 작성할 수 있다고 관찰하였다. 반면에 "구조적 언어로 구조가 나쁜 프로그램을 작성하는 것도 가능하며, 그리 어렵지도 않다"고 하였다.[^45] Tausworthe는 세 가지 Böhm-Jacopini 표준 구조인[^46] SEQUENCE, IF-THEN-ELSE, WHILE-DO에 DO-WHILE과 CASE 두 가지를 추가하였다.[^47] 구조적 프로그램의 추가적인 장점은 수학적 귀납법을 사용한 정확성 증명에 적합하다는 것이다.[^48]

법적 지위

알고리즘 자체는 일반적으로 특허를 받을 수 없다. 미국에서는 추상적 개념, 숫자 또는 신호의 단순한 조작만으로 구성된 청구항은 "프로세스"를 구성하지 않으므로(USPTO 2006), 알고리즘은 특허를 받을 수 없다(Gottschalk 대 Benson 사건에서와 같이). 그러나 알고리즘의 실용적 응용은 때때로 특허를 받을 수 있다. 예를 들어, Diamond 대 Diehr 사건에서 합성 고무의 가황을 돕기 위한 단순한 피드백 알고리즘의 적용은 특허 가능한 것으로 판결되었다. 소프트웨어의 특허는 논란이 있으며,[^49] 특히 Unisys의 LZW 특허와 같은 데이터 압축 알고리즘을 포함하여 알고리즘과 관련된 비판받는 특허들이 있다. 또한 일부 암호화 알고리즘에는 수출 제한이 있다(암호화 수출 참조).

분류

구현 방식에 따른 분류

재귀 재귀 알고리즘은 종료 조건을 만족할 때까지 자기 자신을 반복적으로 호출하며, 함수형 프로그래밍에서 흔히 사용되는 기법이다. 반복 알고리즘은 루프나 스택과 같은 데이터 구조를 사용하여 문제를 해결한다. 문제에 따라 어느 한쪽 구현 방식이 더 적합할 수 있다. 하노이의 탑은 재귀적 구현으로 흔히 풀리는 퍼즐이다. 모든 재귀 버전에는 동등한(그러나 더 복잡하거나 덜 복잡할 수 있는) 반복 버전이 존재하며, 그 반대도 마찬가지이다. 직렬, 병렬 또는 분산 알고리즘은 일반적으로 직렬 컴퓨터에서 한 번에 하나의 명령을 실행한다는 가정 하에 논의된다. 직렬 알고리즘은 이러한 환경을 위해 설계되며, 병렬 또는 분산 알고리즘과는 다르다. 병렬 알고리즘은 여러 프로세서가 동시에 하나의 문제를 처리할 수 있는 컴퓨터 아키텍처를 활용한다. 분산 알고리즘은 컴퓨터 네트워크로 연결된 여러 기계를 사용한다. 병렬 및 분산 알고리즘은 문제를 하위 문제로 나누고 결과를 다시 합친다. 이러한 알고리즘에서의 자원 소비는 각 프로세서의 프로세서 사이클뿐만 아니라 프로세서 간의 통신 오버헤드도 포함된다. 일부 정렬 알고리즘은 효율적으로 병렬화할 수 있지만, 통신 오버헤드가 많이 든다. 반복 알고리즘은 일반적으로 병렬화가 가능하지만, 병렬 알고리즘이 존재하지 않는 문제도 있으며, 이를 본질적으로 직렬인 문제라고 한다. 결정적 또는 비결정적 결정적 알고리즘은 매 단계에서 정확한 결정을 내려 문제를 해결하는 반면, 비결정적 알고리즘은 추측을 통해 문제를 해결한다. 추측은 일반적으로 휴리스틱을 사용하여 더 정확하게 만든다. 정확 또는 근사 많은 알고리즘이 정확한 해를 구하지만, 근사 알고리즘은 참 해에 가까운 근사값을 구한다. 이러한 알고리즘은 많은 어려운 문제에 대해 실용적 가치를 지닌다. 예를 들어, 배낭 문제에서는 항목의 집합이 있고 배낭에 담아 총 가치를 최대화하는 것이 목표이다. 각 항목에는 무게와 가치가 있다. 운반할 수 있는 총 무게는 고정된 수 X를 초과할 수 없다. 따라서 해는 항목의 무게와 가치를 함께 고려해야 한다.[^50] 양자 알고리즘 양자 알고리즘은 현실적인 양자 계산 모델에서 실행된다. 이 용어는 일반적으로 본질적으로 양자적이거나 양자 중첩 또는 양자 얽힘과 같은 양자 컴퓨팅의 핵심 특성을 활용하는 알고리즘에 사용된다.

설계 패러다임에 따른 분류

알고리즘을 분류하는 또 다른 방법은 설계 방법론 또는 패러다임에 의한 것이다. 몇 가지 일반적인 패러다임은 다음과 같다:

무차별 대입 또는 완전 탐색 무차별 대입은 최적의 해를 찾을 때까지 가능한 모든 선택지를 체계적으로 시도하는 문제 해결 방법이다. 이 접근법은 변수의 모든 가능한 조합을 테스트하므로 매우 시간이 많이 소요될 수 있다. 다른 방법을 사용할 수 없거나 너무 복잡할 때 주로 사용된다. 무차별 대입은 두 지점 간의 최단 경로 찾기, 비밀번호 해독 등 다양한 문제를 해결할 수 있다. 분할 정복 분할 정복 알고리즘은 인스턴스가 쉽게 풀 수 있을 만큼 작아질 때까지 문제를 하나 이상의 더 작은 인스턴스로 반복적으로(보통 재귀적으로) 축소한다. 병합 정렬은 분할 정복의 예로, 정렬되지 않은 리스트를 더 작은 리스트로 반복적으로 분할하고, 같은 방식으로 정렬한 다음 병합한다.[^51] 분할 정복의 더 단순한 변형으로 가지치기 탐색 또는 감소 정복 알고리즘이 있는데, 이는 자기 자신의 더 작은 인스턴스 하나를 풀며 병합 단계가 필요 없다. 가지치기 탐색 알고리즘의 예로는 이진 탐색 알고리즘이 있다. 탐색과 열거 많은 문제(예: 체스 게임)는 그래프 위의 문제로 모델링할 수 있다. 그래프 탐색 알고리즘은 그래프를 이동하는 규칙을 명시하며 이러한 문제에 유용하다. 이 범주에는 탐색 알고리즘, 분기 한정 열거, 역추적도 포함된다. 무작위 알고리즘 이러한 알고리즘은 일부 선택을 무작위로(또는 의사 무작위로) 수행한다. 정확한 해를 찾는 것이 비현실적일 때 근사해를 찾는다(아래 휴리스틱 방법 참조). 일부 문제에서는 가장 빠른 근사가 반드시 어느 정도의 무작위성을 포함해야 한다.[^52] 다항 시간 복잡도를 가진 무작위 알고리즘이 일부 문제에 대해 가장 빠른 알고리즘이 될 수 있는지는 P 대 NP 문제로 알려진 미해결 문제이다. 이러한 알고리즘에는 두 가지 큰 부류가 있다:

  1. 몬테카를로 알고리즘은 높은 확률로 정확한 답을 반환한다. 예를 들어 RP는 다항 시간에 실행되는 이 부류의 하위 클래스이다.
  2. 라스베이거스 알고리즘은 항상 정확한 답을 반환하지만, 실행 시간이 확률적으로만 한정된다. 예를 들어 ZPP가 있다. 복잡도 축소 이 기법은 어려운 문제를 (이상적으로는) 점근적으로 최적인 알고리즘으로 풀 수 있는 잘 알려진 문제로 변환한다. 목표는 축소 알고리즘의 복잡도가 결과적으로 축소된 알고리즘에 의해 지배되지 않는 축소 알고리즘을 찾는 것이다. 예를 들어, 한 선택 알고리즘은 먼저 리스트를 정렬하고(비용이 큰 부분), 정렬된 리스트에서 중간 요소를 추출하여(비용이 작은 부분) 정렬되지 않은 리스트의 중앙값을 찾는다. 이 기법은 변환 정복이라고도 알려져 있다. 역추적 이 접근법에서는 여러 해를 점진적으로 구축하며, 유효한 완전한 해로 이어질 수 없다고 판단되면 폐기한다.

최적화 문제

최적화 문제에 대해서는 알고리즘의 보다 구체적인 분류가 있다. 이러한 문제의 알고리즘은 위에서 설명한 일반 범주 중 하나 이상에 해당할 수 있으며, 동시에 다음 중 하나에도 해당할 수 있다:

선형 계획법 선형 등식 및 부등식 제약 조건에 의해 한정된 선형 함수의 최적해를 탐색할 때, 제약 조건을 직접 사용하여 최적해를 구할 수 있다. 널리 사용되는 심플렉스 알고리즘과 같이 이 범주의 모든 문제를 풀 수 있는 알고리즘이 있다.[^53] 선형 계획법으로 풀 수 있는 문제에는 방향 그래프의 최대 유량 문제가 포함된다. 문제에서 미지수 중 하나라도 정수여야 한다면 정수 계획법으로 분류된다. 정수 값에 대한 모든 제한이 표면적인 것, 즉 해가 어차피 이러한 제한을 만족한다고 증명할 수 있다면 선형 계획법 알고리즘으로 이러한 문제를 풀 수 있다. 일반적인 경우에는 문제의 난이도에 따라 특수 알고리즘이나 근사해를 찾는 알고리즘이 사용된다. 동적 계획법 문제가 최적 부분 구조—즉 최적해가 하위 문제의 최적해로부터 구축될 수 있는 것—와 중복 부분 문제—즉 동일한 하위 문제가 여러 다른 문제 인스턴스를 풀기 위해 사용되는 것—를 보일 때, 동적 계획법이라는 더 빠른 접근법이 해의 재계산을 방지한다. 예를 들어, 플로이드-워셜 알고리즘에서 가중 그래프의 시작 정점과 목표 정점 사이의 최단 경로는 모든 인접 정점으로부터 목표까지의 최단 경로를 사용하여 찾을 수 있다. 동적 계획법과 메모이제이션은 함께 간다. 분할 정복과 달리 동적 계획법의 하위 문제는 종종 중복된다. 동적 계획법과 단순 재귀의 차이점은 재귀 호출의 캐싱 또는 메모이제이션이다. 하위 문제가 독립적이고 반복되지 않으면 메모이제이션은 도움이 되지 않으므로, 동적 계획법이 모든 복잡한 문제에 적용 가능한 것은 아니다. 메모이제이션을 사용하는 동적 계획법은 많은 문제의 복잡도를 지수적에서 다항적으로 줄여준다. 탐욕법 탐욕 알고리즘은 동적 계획법과 유사하게 부분 구조를 검사하여 작동하지만, 이 경우 문제가 아닌 주어진 해의 부분 구조를 검사한다. 이러한 알고리즘은 어떤 해에서 시작하여 작은 수정을 가해 개선한다. 일부 문제에서는 항상 최적해를 찾지만 다른 문제에서는 지역 최적점에서 멈출 수 있다. 탐욕 알고리즘의 가장 대표적인 용도는 음의 순환이 없는 그래프의 최소 신장 트리를 찾는 것이다. 허프만 트리, 크루스칼, 프림, 솔린은 이 최적화 문제를 풀 수 있는 탐욕 알고리즘이다. 휴리스틱 방법 최적화 문제에서 휴리스틱 알고리즘은 최적해를 찾는 것이 비현실적일 때 최적해에 가까운 해를 찾는다. 이러한 알고리즘은 진행됨에 따라 최적해에 점점 가까워진다. 원칙적으로 무한한 시간 동안 실행하면 최적해를 찾게 된다. 이상적으로는 비교적 짧은 시간에 최적해에 매우 가까운 해를 찾을 수 있다. 이러한 알고리즘에는 지역 탐색, 타부 탐색, 담금질 기법, 유전 알고리즘이 포함된다. 담금질 기법과 같은 일부는 비결정적 알고리즘이고, 타부 탐색과 같은 다른 것들은 결정적 알고리즘이다. 비최적 해의 오차 한계가 알려져 있을 때, 해당 알고리즘은 근사 알고리즘으로 추가 분류된다.

예시

가장 간단한 알고리즘 중 하나는 무작위 순서로 나열된 숫자 목록에서 가장 큰 수를 찾는 것이다. 해답을 찾으려면 목록의 모든 숫자를 살펴보아야 한다. 이로부터 다음과 같은 간단한 알고리즘이 도출되며, 이를 일상적인 언어로 설명하면 다음과 같다:

상위 수준 설명:

  1. 숫자 집합이 비어 있으면 가장 큰 수는 존재하지 않는다.
  2. 집합의 첫 번째 숫자가 가장 큰 수라고 가정한다.
  3. 집합의 나머지 각 숫자에 대해: 이 숫자가 현재 가장 큰 수보다 크면, 이 숫자가 새로운 가장 큰 수가 된다.
  4. 집합에 확인하지 않은 숫자가 남아 있지 않으면, 현재 가장 큰 수를 집합에서 가장 큰 수로 간주한다.

(준)형식적 설명: 산문 형식으로 작성되었지만 컴퓨터 프로그램의 고급 언어에 훨씬 가까운 다음은 의사코드 또는 피진 코드로 보다 형식적으로 작성된 알고리즘이다:

입력: 숫자 목록 L. 출력: 목록 L에서 가장 큰 수.

if L.size = 0 return null largest ← L[0] for each item in L, do if item > largest, then largest ← item return largest

같이 보기

  • 추상 기계
  • ALGOL
  • 알고리즘 = 논리 + 제어
  • 알고리즘 기피
  • 알고리즘 공학
  • 알고리즘 특성화
  • 알고리즘 편향
  • 알고리즘 작곡
  • 알고리즘 개체
  • 알고리즘 합성
  • 알고리즘 기법
  • 알고리즘 위상수학
  • 계산 수학
  • 쓰레기가 들어가면 쓰레기가 나온다
  • 알고리즘 입문 (교과서)
  • 알고리즘에 의한 통치
  • 알고리즘 목록
  • 알고리즘 서적 목록
  • 알고리즘 일반 주제 목록
  • 매체가 곧 메시지다
  • 알고리즘 규제
  • 계산 이론 ** 계산 가능성 이론 ** 계산 복잡도 이론

주석

참고 문헌

    • Bell, C. Gordon and Newell, Allen (1971), 컴퓨터 구조: 읽기 자료와 예제, McGraw–Hill Book Company, New York. .

  • 56개의 참고 문헌 목록을 포함한다.

  • ,

  • : 참조. 제3장 튜링 기계에서 "효과적으로(기계적으로) 열거할 수 없는 특정 열거 가능 집합"을 논의한다.

    • Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) 부분 재귀 함수의 아날로그 특성화. 제4회 실수와 컴퓨터 학술대회 논문집, Odense University, pp. 91–109

  • 결정 불가능한 것에 재수록, p. 89ff. "처치의 명제"의 최초 표현. 특히 100쪽(결정 불가능한 것)에서 그가 "알고리즘"의 관점에서 "효과적 계산 가능성"의 개념을 정의하고, "종료한다" 등의 용어를 사용하는 부분을 참조하라.

  • 결정 불가능한 것에 재수록, p. 110ff. Church는 약 3쪽의 본문과 3쪽의 각주로 결정 문제(Entscheidungsproblem)가 풀 수 없음을 보인다.

    • Davis는 각 논문 앞에 해설을 제공한다. Gödel, Alonzo Church, Turing, Rosser, Kleene, Emil Post의 논문이 포함되어 있으며, 본 문서에서 인용된 것은 저자명으로 여기에 나열되어 있다.

  • Davis는 Leibniz, Boole, Frege, Cantor, Hilbert, Gödel, Turing의 간결한 전기를 제공하며, von Neumann을 주목할 만한 악역으로 다룬다. Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken 등의 매우 짧은 약전도 포함되어 있다.

        • ,

  • Yuri Gurevich, 순차적 추상 상태 기계는 순차적 알고리즘을 포착한다, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pp. 77–111. 33개의 참고 문헌 목록을 포함한다.

  • , 제3판 1976[?], (pbk.)

  • , . 참조. "진리의 정신" 장에서 그의 증명으로 이어지는 역사와 그에 대한 논의를 다룬다.

  • 1935년 9월 미국수학회에 발표. 결정 불가능한 것에 재수록, p. 237ff. Kleene의 "일반 재귀"(현재 뮤 재귀로 알려진) 정의는 Church가 1935년 논문 초등 수론의 풀 수 없는 문제에서 "결정 문제"가 "결정 불가능"함을 증명하는 데 사용되었다(즉, 부정적 결과).

  • 결정 불가능한 것에 재수록, p. 255ff. Kleene는 "일반 재귀"의 정의를 정제하고 "12. 알고리즘 이론" 장에서 "명제 I"(p. 274)을 제시하였다; 그는 후에 이 명제를 반복하고(Kleene 1952:300) "처치의 명제"(Kleene 1952:317)라 명명하였다(즉, 처치 명제).

        • Kosovsky, N.K. 수리논리학의 기초와 부분 재귀 알고리즘 이론에의 응용, LSU Publ., Leningrad, 1981
    • A.A. Markov (1954) 알고리즘의 이론. [Jacques J. Schorr-Kon 및 PST 직원 번역] 발행지 Moscow, 소련 과학 아카데미, 1954 [즉, Jerusalem, 이스라엘 과학 번역 프로그램, 1961; 미국 상무부 기술서비스국에서 입수 가능] 설명 444 p. 28 cm. 러시아어 추가 표제지 소련 과학 아카데미 수학연구소 저작 번역, v. 42. 원제: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS .]

  • Minsky는 제5.1장 *계산 가능성, 효과적 절차와 알고리즘. 무한 기계.*에서 그의 "...알고리즘의 개념 – 효과적 절차..."를 확장한다.

  • 결정 불가능한 것에 재수록, pp. 289ff. Post는 한 사람이 표시를 쓰거나 지우고 상자에서 상자로 이동하며 간단한 지시 목록을 따라 최종적으로 정지하는 단순한 알고리즘적 과정을 정의한다. 이것은 Kleene가 그의 "명제 I", 이른바 처치-튜링 명제의 원천 중 하나로 인용한다.

    • 결정 불가능한 것에 재수록, p. 223ff. 여기에 Rosser의 유명한 "효과적 방법"의 정의가 있다: "...각 단계가 정확히 미리 정해져 있고 유한한 단계 내에 반드시 답을 산출하는 방법... 질문을 입력하고 (나중에) 답을 읽는 것 외에 인간의 개입 없이 집합의 어떤 문제든 풀 수 있는 기계" (p. 225–226, 결정 불가능한 것)
          • 참조. 특히 알고리즘, 튜링 기계, 그리고 프로그램이라는 제목의 첫 번째 장. 그의 간결한 비형식적 정의: "...로봇이 따를 수 있는 모든 명령의 순서를 알고리즘이라 한다" (p. 4).
    • . 정정, ibid, vol. 43(1937) pp. 544–546. 결정 불가능한 것에 재수록, p. 116ff. Turing의 유명한 논문은 영국 케임브리지 킹스 칼리지 재학 중 석사 학위 논문으로 완성되었다.

  • 결정 불가능한 것에 재수록, pp. 155ff. "오라클"을 정의한 Turing의 논문은 프린스턴 재학 중 그의 박사 학위 논문이었다.

  • United States Patent and Trademark Office (2006), *2106.02 *>수학적 알고리즘: 2100 특허 적격성, 특허 심사 절차 매뉴얼 (MPEP). 최신 개정 2006년 8월

  • Zaslavsky, C. (1970). 요루바족과 나이지리아 남부 이웃 민족의 수학. The Two-Year College Mathematics Journal, 1(2), 76–99. https://doi.org/10.2307/3027363

  • NIST, 최초의 포스트 양자 암호화 표준 3종 최종 발표. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

더 읽을거리

참고 문헌

[^1]: ALGORITHM의 정의

[^2]: David A. Grossman, Ophir Frieder, ''정보 검색: 알고리즘과 휴리스틱'', 제2판, 2004, isbn 1402030045

[^3]: "예를 들어, 모든 고전적 수학 알고리즘은 유한한 수의 영어 단어로 설명할 수 있다" (Rogers 1987:2).

[^4]: 알고리즘을 실행하는 주체에 관하여 잘 정의된: "계산을 수행하는 주체가 있으며, 보통 인간으로서, 명령에 반응하고 계산을 수행할 수 있다" (Rogers 1987:2).

[^5]: Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. 정보: 역사적 안내서, Princeton: Princeton University Press, 2021. p. 247

[^6]: Sriram, M. S.. 인도 수학사에 대한 기여. Springer. (2005)

[^7]: Cooke, Roger L.. 수학의 역사: 간략한 과정. John Wiley & Sons. (2005)

[^8]: Dooley, John F.. 암호학과 암호 알고리즘의 간략한 역사. Springer Science & Business Media. (2013)

[^9]: Sipser 2006:157

[^10]: Kriegel, Hans-Peter. 실행 시간 평가의 (블랙) 아트: 우리는 알고리즘을 비교하는가 구현을 비교하는가?

[^12]: "알고리즘은 (정수에 대해 선택된 표기법에 관하여) ''함수''를 계산하는 절차이다 ... 이 제한(수치 함수에 대한)은 일반성의 손실을 초래하지 않는다", (Rogers 1977:1)

[^13]: "알고리즘은 [[영]] 또는 그 이상의 입력을 가진다, 즉 알고리즘이 시작되기 전에 초기에 주어지는 [[수량]]이다" (Knuth 1973:5).

[^14]: "유한성이 결여될 수 있다는 점을 제외하고 알고리즘의 모든 특성을 가진 절차를 '계산 방법'이라 부를 수 있다" (Knuth 1971:5).

[^15]: "알고리즘은 하나 이상의 출력을 가진다, 즉 입력과 특정한 관계를 가지는 수량이다" (Knuth 1973:5).

[^16]: 무작위 내부 과정(입력을 포함하지 않는)을 가진 프로세스가 알고리즘인지 여부는 논쟁의 여지가 있다. Rogers는 다음과 같이 의견을 밝힌다: "계산은 이산적이고 단계적인 방식으로 수행된다,

[^18]: Chaucer, Geoffrey. 방앗간지기의 이야기

[^19]: Skeat, Walter William. 튜더 및 스튜어트 시대 용어집: 특히 극작가들의 용어. Clarendon Press

[^20]: cite book last = Grabiner first = Judith V. author-link = Judith Grabiner editor-last = Matthews editor-first = Michael R. contribution = 교양 교육에서 수학의 역할

[^22]: Simanowski, Roberto. 죽음의 알고리즘과 그 밖의 디지털 딜레마. MIT Press. (2018)

[^23]: Dietrich, Eric. MIT 인지과학 백과사전. MIT Press

[^24]: Stone은 "유한한 수의 단계에서 종료되어야 한다"고 요구한다 (Stone 1973:7–8).

[^25]: Boolos and Jeffrey 1974, 1999:19

[^26]: Hayashi, T. (2023년 1월 1일). [https://www.britannica.com/biography/Brahmagupta 브라흐마굽타]. Encyclopedia Britannica.

[^27]: Zaslavsky, Claudia. 요루바족과 나이지리아 남부 이웃 민족의 수학. (1970)

[^28]: 알고리즘의 역사. (1999)

[^29]: Knuth, Donald E.. 고대 바빌로니아 알고리즘. (1972)

[^30]: Aaboe, Asger. 초기 천문학 역사의 에피소드. Springer. (2001)

[^31]: Ast, Courtney. 에라토스테네스. Wichita State University: 수학 및 통계학과

[^32]: Bolter 1984:24

[^33]: Bolter 1984:26

[^34]: Bolter 1984:33–34, 204–206.

[^35]: Bell and Newell 도표 1971:39, cf. Davis 2000

[^36]: Melina Hill, Valley News 특파원, ''한 발명가가 역사에 자리를 얻다'', Valley News West Lebanon NH, 1983년 3월 31일 목요일, p. 13.

[^37]: Davis 2000:14

[^38]: Kleene 1943 in Davis 1965:274

[^39]: Rosser 1939 in Davis 1965:225

[^40]: cite web title=더 나은 수학이 더 빠른 데이터 네트워크를 만든다 author=Gillian Conahan date=2013년 1월 url=http://discovermagazine.com/2013/jan-feb/34-better-math-makes-faster-data-networks publisher=dis

[^41]: 최선의 경우. 미국 국립표준기술연구소 (NIST)

[^42]: 최악의 경우. 미국 국립표준기술연구소 (NIST)

[^43]: Goodrich, Michael T.. 알고리즘 설계: 기초, 분석 및 인터넷 예제. John Wiley & Sons, Inc.

[^44]: 빅오 표기법 (문서) {{!

[^45]: [[John G. Kemeny]]와 [[Thomas E. Kurtz]] 1985 ''베이직으로 돌아가기: 언어의 역사, 변질, 그리고 미래'', Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0 .

[^46]: Tausworthe 1977:101

[^47]: Tausworthe 1977:142

[^48]: Knuth 1973 섹션 1.2.1, Tausworthe 1977의 100쪽 이후 및 9.1장에서 확장

[^49]: 전문가들: 특허 제도는 혁신을 장려하는가?. (2013-05-16)

[^50]: Kellerer, Hans. 배낭 문제 {{!. Springer

[^51]: Goodrich, Michael T.. 알고리즘 설계: 기초, 분석 및 인터넷 예제. John Wiley & Sons

[^52]: 예를 들어, [[볼록 다면체]]의 [[부피]](멤버십 오라클을 사용하여 기술된)는 무작위 다항 시간 알고리즘으로 높은 정확도로 근사할 수 있지만, 결정론적

[^53]: [[George B. Dantzig]]와 Mukund N. Thapa. 2003. ''선형 계획법 2: 이론과 확장''. Springer-Verlag.