알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
알고리즘은 9세기 페르시아 수학자 알콰리즈미의 이름을 라틴어화한 단어로, 유한한 규칙에 따라 명확한 기호 조작을 통해 입력에서 출력을 생성하는 작업으로 정의된다. 컴퓨터 프로그램, 관료적 절차, 요리법 등 다양한 분야에서 활용되며, 정밀성, 유일성, 타당성, 입력, 출력, 유한성, 일반성과 같은 특징을 갖는다. 알고리즘은 고대부터 수학 문제 해결에 사용되었으며, 튜링 기계, 람다 대수 등의 계산 모델을 통해 형식화되었다. 구현 방식, 설계 패러다임, 연구 분야, 계산량, 계산 능력에 따라 다양한 방식으로 분류되며, 법적인 문제도 존재한다. 정렬되지 않은 숫자 목록에서 최댓값을 찾는 것과 같은 간단한 예시를 통해 알고리즘을 이해할 수 있다.
더 읽어볼만한 페이지
- 이론 컴퓨터 과학 - 자동화된 추론
자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다. - 이론 컴퓨터 과학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다. - 알고리즘 - 텍스트-비디오 모델
텍스트-비디오 모델은 텍스트 입력을 기반으로 비디오를 생성하는 인공지능 모델로서, 다양한 모델들이 개발되고 교육, 홍보, 창작 산업 등 여러 분야에 활용되지만 컴퓨팅 자원 소모, 데이터 부족, 텍스트 해석 오류, 윤리적 문제 등의 한계점을 가진다. - 알고리즘 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다. - 전산언어학 - 단어 의미 중의성 해소
단어 의미 중의성 해소(WSD)는 문맥 내 단어의 의미를 파악하는 계산 언어학 과제로, 다양한 접근 방식과 외부 지식 소스를 활용하여 연구되고 있으며, 다국어 및 교차 언어 WSD 등으로 발전하며 국제 경연 대회를 통해 평가된다. - 전산언어학 - 질의 응답
질의응답 시스템은 자연어 질문을 이해하고 답변을 생성하며, 질문 유형과 사용 기술에 따라 분류되고, 읽기 이해 기반 또는 사전 지식 기반으로 작동하며, 대규모 언어 모델과 다양한 아키텍처 발전에 힘입어 복잡한 질문에 대한 답변과 다양한 분야에 활용이 가능해졌다.
알고리즘 |
---|
2. 어원
알고리즘이라는 용어는 9세기 페르시아(오늘날 이란)의 수학자인 무함마드 알콰리즈미의 이름에서 유래했다.[70] 알콰리즈미의 저서가 12세기에 라틴어로 번역되면서 그의 이름을 라틴어화한 '알고리스무스(Algorismus)'라는 단어가 사용되기 시작했다.[2] 이 책은 "알고리즈미가 말했다(Dixit Algorismi)"라는 구절로 시작하는데,[2] 여기서 알콰리즈미의 이름을 라틴어화한 'algorismi'가 사용되었다. 이 번역본은 『algoritmi de numero Indorum|알고리트미 데 누메로 인돌룸la』[56] (직역하면 “인도의 수에 대한 알고리트미”)이라는 제목으로, 이후 500년 동안 유럽 대학에서 수학의 주요 교재로 사용되었다.
알고리즘은 유한한 계산을 통해 정의된다. 알고리즘은 유한한 수의 규칙에 따라, 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업으로 정의된다.
15세기에 그리스어 ἀριθμός (arithmos, "숫자")의 영향을 받아 라틴어 단어가 *algorithmus*로 변경되었다.
3. 정의
좋은 알고리즘은 다음과 같은 특징을 갖는다.
비형식적인 정의 중 하나는 "연산 순서를 정확하게 정의하는 일련의 규칙"이다.[11] 여기에는 모든 컴퓨터 프로그램(수치 계산을 수행하지 않는 프로그램 포함)과 모든 규정된 관료주의적 절차[12] 또는 요리책 레시피[13]가 포함된다. 일반적으로 프로그램은 결국 중지되는 경우에만 알고리즘이다.[14]
대부분의 알고리즘은 구현될 컴퓨터 프로그램으로 의도된다. 그러나 알고리즘은 생물학적 신경망(예: 산술을 수행하는 인간의 뇌 또는 먹이를 찾는 곤충), 전기 회로 또는 기계 장치와 같이 다른 방법으로도 구현된다.
이와나미 국어사전의 “알고리즘(算法)”에서는 “계산 방법”이라고 정의한 후, algorithm의 번역어로서 다음과 같이 설명한다.
: 특히, 동종의 문제 일반에 대해, 유한 번의 기본적인 조작을, 지시의 순서대로 실행하면, 해가 있는 경우에는 그 해가 얻어지고, 해가 없는 경우에는 그 사실이 확인될 수 있도록, 명확하게 체계화된 절차.
4. 역사
수학 문제 풀이 절차는 고대부터 기록되어 왔다. 여기에는 기원전 2500년경의 바빌로니아 수학, 기원전 1550년경의 이집트 수학, 기원전 800년경 이후의 인도 수학, 기원전 240년경의 그리스 수학, 기원전 200년경 이후의 중국 수학, 서기 800년경의 아랍 수학 등이 포함된다.[16][17][18][20][21][22]
알고리즘의 초기 증거는 고대 메소포타미아 수학에서 발견된다. 바그다드 근처 슈루팍에서 발견된 기원전 2500년경의 수메르 점토판은 초기 나눗셈 알고리즘을 설명한다.[16] 기원전 1800년에서 1600년경의 함무라비 왕조 시대 바빌로니아 점토판에는 공식을 계산하는 알고리즘이 있었다.[23] 바빌로니아 천문학에서도 알고리즘이 사용되었는데, 중요한 천문 현상의 시간과 장소를 계산하는 절차를 설명한다.[24]
기원전 1550년경 고대 이집트 수학의 린드 수학 파피루스에도 산술 알고리즘이 기록되어 있다.[16] 이후 고대 헬레니즘 수학에서는 에라토스테네스의 체(산술입문에 설명[25][20])와 유클리드 알고리즘(유클리드 원론에 처음 설명[20]) 등이 사용되었다. 고대 인도 수학의 예로는 술바 수트라, 케랄라 학파, 브라마스푸타시다탄타가 있다.[17]
9세기 아랍 수학자 알킨디는 '암호 메시지 해독에 관한 원고'에서 암호 해독 알고리즘인 빈도 분석을 최초로 설명했다.[22]
기록에 남아있는 가장 오래된 알고리즘은 유클리드의 원론에 있는 최대공약수를 구하는 유클리드 호제법이다.[55]
"알고리즘"이라는 명칭은 9세기 바그다드에서 활동한 수학자 알콰리즈미(الخوارزمي|al-Khwarizmiar)의 이름에서 유래했다. 그가 인도 수학을 소개한 『인도의 수의 계산법』(825년)은 체스터의 로버트(혹은 바스의 아델라드)에 의해 라틴어로 번역되어 『algoritmi de numero Indorumla』[56] (직역하면 "인도의 수에 대한 알고리트미")이라는 제목으로 500년 동안 유럽 대학에서 수학 교재로 사용되었다. 이 책은 "algoritmi dictila (알-콰리즈미에 의하면)"이라는 구절로 시작한다.
1920~30년대, 튜링 기계, 귀납적 함수, 람다 대수 등 계산 가능성을 위한 수학적 모델(계산 모델)이 제안되었다. 이 정의들은 모두 동등하며, 이를 통해 "계산 가능하다"는 개념이 제안되었다(처치-튜링 명제).[58][59] 현재는 이들에 의해 '계산 가능한 것'을 계산하는 절차를 알고리즘이라고 부른다.
5. 형식화
알고리즘은 자연어, 의사코드, 순서도, 프로그래밍 언어 등 다양한 방식으로 표현될 수 있다.[34] 튜링 기계와 같은 계산 모델은 알고리즘의 형식적 논의에 사용된다.[58][59]
자연어로 표현된 알고리즘은 내용이 길고 모호해지는 경향이 있어, 복잡하거나 전문적인 알고리즘에는 거의 사용되지 않는다. 의사 코드, 순서도 등은 자연어의 모호성을 피하는 구조화된 알고리즘 표현 방식이다. 프로그래밍 언어는 주로 컴퓨터에서 실행 가능한 형태로 알고리즘을 표현하지만, 알고리즘을 정의하거나 문서화하는 데에도 사용된다.[34]
튜링 기계 프로그램은 기계 테이블, 플로차트(흐름도), 원시적인 기계어 또는 어셈블리어 형태 등으로 표현될 수 있다. 알고리즘 표현은 튜링 기계 설명의 세 가지 수준으로 분류할 수도 있다. 고수준 설명은 튜링 기계에서 어떻게 구현되는지 무시하고 알고리즘 자체를 설명한다. 구현 설명은 기계가 헤드를 움직이고 데이터를 저장하는 일반적인 방식을 설명하지만, 정확한 상태는 제공하지 않는다. 가장 상세한 형식적 설명은 튜링 기계의 정확한 상태표와 전이 목록을 제공한다.[34]
6. 구현
알고리즘은 컴퓨터 프로그램으로 구현되는 경우가 많지만, 전기 회로나 생물학적 신경회로를 통해 구현되기도 한다. 알고리즘 설계에는 운용과학의 방법이나 설계짜임새를 활용하는 방법 등이 있다. 알고리즘 설계 및 구현 기법은 알고리즘 설계 패턴[38]이라고도 하며, 템플릿 메서드 패턴과 데코레이터 패턴 등이 여기에 해당한다. 알고리즘 설계에서 가장 중요한 측면 중 하나는 자원(실행 시간, 메모리 사용량) 효율성이다.[39]
7. 분석
알고리즘의 효율성을 파악하기 위해 시간 복잡도, 공간 복잡도 등을 분석한다. 빅 O 표기법은 알고리즘의 성능을 나타내는 데 사용된다. 알고리즘 분석에는 공식적인 방법과 경험적인 방법이 모두 사용된다.[35]
알고리즘이 얼마나 많은 시간, 저장 공간, 또는 다른 비용을 필요로 하는지 파악하는 것은 중요하다. 이러한 정량적인 답(추정치)을 얻기 위해 알고리즘 분석 방법이 개발되었다. 예를 들어, 크기가 ''n''인 숫자 목록의 요소를 더하는 알고리즘은 빅 O 표기법을 사용하여 의 시간이 필요하다. 이 알고리즘은 지금까지의 모든 요소의 합과 입력 목록에서 현재 위치의 두 값만 기억하면 된다. 입력 숫자를 저장하는 데 필요한 공간을 고려하지 않으면 의 공간이 필요하지만, 그렇지 않으면 이 필요하다.
서로 다른 알고리즘은 다른 알고리즘보다 적거나 많은 시간, 공간 또는 '노력'으로 동일한 작업을 완료할 수 있다. 예를 들어, 이진 탐색 알고리즘(의 비용)은 정렬된 목록이나 배열에 대한 표 검색에 사용될 때 순차 검색(의 비용)보다 성능이 우수하다.
알고리즘의 분석 및 연구는 컴퓨터 과학의 한 분야이다. 알고리즘은 특정 프로그래밍 언어나 구현을 참조하지 않고 추상적으로 연구되는 경우가 많다. 알고리즘 분석은 구현이 아닌 알고리즘의 속성에 초점을 맞춘다는 점에서 다른 수학 분야와 유사하다. 간단하고 일반적인 표현이기 때문에 의사 코드가 분석에 일반적으로 사용된다. 대부분의 알고리즘은 특정 하드웨어/소프트웨어 플랫폼에 구현되며 실제 코드를 사용하여 알고리즘 효율을 테스트한다. 특정 알고리즘의 효율성은 많은 "일회성" 문제에는 중요하지 않을 수 있지만, 빠른 대화형, 상업용 또는 장기간의 과학적 사용을 위해 설계된 알고리즘에는 중요할 수 있다. 작은 n에서 큰 n으로 확장하면 그렇지 않으면 무해한 비효율적인 알고리즘이 자주 드러난다.
실험적 테스트는 성능에 영향을 미치는 예상치 못한 상호 작용을 발견하는 데 유용하다. 벤치마크는 프로그램 최적화 후 알고리즘에 대한 잠재적 개선 사항을 비교하기 위해 사용될 수 있다.
잘 확립된 알고리즘에서도 가능한 개선의 잠재력을 보여주는 예로, 최근 FFT 알고리즘(영상 처리 분야에서 많이 사용됨)과 관련된 중요한 혁신은 의료 영상과 같은 응용 프로그램의 처리 시간을 최대 1,000배까지 단축할 수 있다.[36] 일반적으로 속도 향상은 문제의 특수한 속성에 따라 달라지는데, 이러한 속성은 실제 응용 프로그램에서 매우 일반적이다.[37] 이러한 규모의 속도 향상을 통해 영상 처리를 광범위하게 사용하는 컴퓨팅 장치(디지털 카메라 및 의료 장비 등)의 전력 소비량을 줄일 수 있다.
어떤 알고리즘의 실행에 필요한 계산 자원(시간이나 기억 공간)의 양을 추정하는 것은 중요하다. 그러한 양을 정량적으로 구하는 분석 방법은 알고리즘 분석이라고 불리며, 연구되어 왔다.
입력값의 크기가 일 경우, 점근 표기법 를 사용하여 다음과 같이 나타낸다.
표기법 | 설명 | 예시 |
---|---|---|
에 관계없이 일정 시간 이하에 수행되는 알고리즘이다. | 파일의 첫 번째 바이트가 널(null)인지 검사하는 것. | |
에 비례하는 시간 이하에 수행되는 알고리즘이다. | 이진 탐색. | |
에 비례하는 시간 이하에 수행되는 알고리즘이다. | 기수 정렬. | |
에 비례하는 시간 이하에 수행되는 알고리즘이다. | 정렬 알고리즘. | |
에 비례하는 시간 이하에 수행되는 알고리즘이다. | 최장 공통 부분 수열 문제. | |
에 비례하는 시간 이하에 수행되는 알고리즘이다. | 행렬 곱셈. | |
과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. | 충족 가능성 문제. | |
즉 과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. | 배열의 모든 순열을 검사하는 것. |
대문자 O 표기법의 정의상 아래의 복잡도는 그 위의 복잡도를 포함하므로, 대부분의 알고리즘은 의 수행 시간을 가진다.
8. 분류
알고리즘은 다양한 기준에 따라 분류할 수 있으며, 각 분류는 알고리즘의 특징과 장단점을 이해하는 데 도움을 준다.
- 구현 방식:
- 재귀 알고리즘: 자신을 다시 호출하는 방식 (예: 하노이의 탑)
- 반복 알고리즘: 루프나 스택 사용
- 직렬 알고리즘: 한 번에 하나의 명령어만 실행
- 병렬 알고리즘: 여러 프로세서가 동시에 문제 처리
- 분산 알고리즘: 네트워크로 연결된 여러 컴퓨터 사용
- 결정론적 알고리즘: 모든 단계에서 정확한 결정
- 비결정론적 알고리즘: 추측을 통해 문제 해결, 휴리스틱으로 정확도 향상
- 근사 알고리즘: 근사치 탐색 (예: 배낭 문제)
- 양자 알고리즘: 양자 컴퓨팅 모델에서 실행
- 설계 패러다임:
- 무작위 탐색: 모든 해 시도
- 분할 정복 알고리즘: 문제 분할 및 해결, 결과 결합 (예: 합병 정렬)
- 탐색 및 열거: 그래프 문제에 사용 (탐색 알고리즘, 분기 한정법, 백트래킹 등)
- 확률적 알고리즘: 무작위성 이용 (몬테카를로 알고리즘, 라스베이거스 알고리즘 등)
- 복잡도 감소: 어려운 문제를 쉬운 문제로 변환
- 백트래킹: 유효하지 않으면 이전 단계로 복귀
- 최적화 문제:
- 선형 계획법: 선형 함수 최적화 (단체법(심플렉스 알고리즘) 사용)
- 동적 계획법: 최적 부분 구조, 겹치는 부분 문제 (예: 플로이드-워셜 알고리즘)
- 탐욕 알고리즘: 각 단계에서 최선 선택 (크루스칼 알고리즘, 프림 알고리즘 등)
- 휴리스틱 방법: 근사해 탐색 (국소 탐색, 타부 탐색, 시뮬레이티드 어닐링, 유전 알고리즘 등)
- 연구 분야:
- 검색 알고리즘, 정렬 알고리즘, 병합 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 계산 기하 알고리즘, 조합 알고리즘, 기계 학습, 암호학적 알고리즘, 데이터 압축 알고리즘, 구문 분석 등
- 계산량:
- 입력 크기()에 따른 계산 시간: 점근 표기법 로 표현 (예: , , , , , , , 등)
- 최선의 알고리즘 계산량 기반 문제 분류
- 계산 능력:
- 튜링 계산 가능 함수, 계산 자원등을 이용하여 계층적으로 분류
8. 1. 구현 방식에 따른 분류
재귀 알고리즘은 종료 조건을 만날 때까지 자신을 반복적으로 호출하며, 일반적인 함수형 프로그래밍 방법이다. 반복 알고리즘은 루프 또는 스택과 같은 자료 구조를 사용하여 문제를 해결한다. 하노이의 탑은 재귀적 구현을 사용하는 대표적인 예시이다. 모든 재귀 알고리즘은 동등한 반복 알고리즘으로 구현할 수 있으며, 그 반대도 마찬가지다(단, 복잡도는 달라질 수 있다).알고리즘은 일반적으로 한 번에 하나의 명령어만 실행하는 직렬 컴퓨터를 가정하고 논의된다. 이러한 환경을 위해 설계된 알고리즘을 직렬 알고리즘이라고 하며, 병렬 알고리즘과 분산 알고리즘은 이와 대조적이다. 병렬 알고리즘은 여러 프로세서가 동시에 문제를 처리할 수 있는 컴퓨터 아키텍처를 활용하고, 분산 알고리즘은 컴퓨터 네트워크로 연결된 여러 기계를 사용한다. 병렬 및 분산 알고리즘은 문제를 하위 문제로 나누고 결과를 다시 수집하는데, 이때 각 프로세서의 처리 시간뿐만 아니라 프로세서 간 통신 오버헤드도 자원 소비에 포함된다. 일부 정렬 알고리즘은 효율적으로 병렬화할 수 있지만 통신 오버헤드가 크다. 반복 알고리즘은 일반적으로 병렬화할 수 있지만, 일부 문제는 병렬 알고리즘이 없어 본질적으로 직렬 문제라고 불린다.
결정적 알고리즘은 모든 단계에서 정확한 결정으로 문제를 해결하는 반면, 비결정론적 알고리즘은 추측을 통해 문제를 해결하며, 휴리스틱을 사용하여 추측의 정확도를 높인다.
많은 알고리즘이 정확한 해를 구하지만, 근사 알고리즘은 실제 해에 가까운 근사치를 찾는다. 이는 많은 어려운 문제에 대한 실용적인 해결책이 될 수 있다. 예를 들어 배낭 문제에서는 여러 항목의 무게와 가치를 고려하여 총 무게 제한을 넘지 않으면서 최대 가치를 얻도록 배낭을 채워야 한다.
양자 알고리즘은 양자 컴퓨팅의 현실적인 모델에서 실행된다. 이 용어는 본질적으로 양자적인 알고리즘, 또는 양자 중첩이나 양자 얽힘과 같은 양자 컴퓨팅의 특징을 사용하는 알고리즘을 의미한다.[45]
8. 2. 설계 패러다임에 따른 분류
무작위 탐색 또는 완전 탐색은 가능한 모든 해를 시도하여 문제를 해결하는 방법이다. 이 방법은 모든 가능한 조합을 검사하므로 시간이 오래 걸릴 수 있지만, 다른 방법이 없거나 너무 복잡할 때 유용하다.- '''분할 정복''': 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 해결한 다음, 그 해를 결합하여 원래 문제를 해결한다. 합병 정렬이 대표적인 예시이다.
- '''탐색 및 열거''': 그래프 문제로 모델링될 수 있는 문제에 사용되는 방법이다. 탐색 알고리즘, 분기 한정, 백트래킹 등이 여기에 속한다.
- '''확률적 알고리즘''': 무작위성을 이용하여 문제를 해결하는 알고리즘이다. 몬테카를로 알고리즘과 라스베이거스 알고리즘이 있다.
- '''복잡도 감소''': 어려운 문제를 이미 잘 알려진 알고리즘으로 해결할 수 있는 문제로 변환하는 방법이다.
- '''백트래킹''': 가능한 해를 점진적으로 구축하다가, 더 이상 유효한 해가 없을 경우 이전 단계로 돌아가 다른 해를 시도하는 방법이다.
최적화 문제를 해결하기 위한 알고리즘은 다음과 같이 분류할 수 있다.
- '''선형 계획법''': 선형 함수를 최적화하는 문제에 사용되며, 단체법(심플렉스 알고리즘)과 같은 알고리즘으로 해결할 수 있다.
- '''동적 계획법''': 최적 부분 구조와 겹치는 부분 문제를 가지는 문제에 사용되며, 플로이드-워셜 알고리즘이 그 예시이다. 메모이제이션을 사용하여 중복 계산을 피한다.
- '''탐욕 알고리즘''': 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘이다. 크루스칼 알고리즘, 프림 알고리즘 등이 여기에 속한다.
- '''휴리스틱 방법''': 최적 해를 찾는 것이 비실용적인 경우, 근사해를 찾는 데 사용된다. 국소 탐색, 타부 탐색, 시뮬레이티드 어닐링, 유전 알고리즘 등이 있다.
8. 3. 연구 분야에 따른 분류
알고리즘은 다양한 연구 분야에서 활용되며, 각 분야는 고유한 문제와 효율적인 알고리즘을 필요로 한다. 여러 분야에서 함께 연구되는 문제들도 있는데, 다음과 같이 분류할 수 있다.[1]각 분야는 서로 중복되기도 하며, 한 분야에서의 알고리즘 발전이 다른 분야의 개선으로 이어지기도 한다. 예를 들어 동적 계획법은 원래 산업 자원 소비 최적화를 위해 발명되었지만, 현재는 다양한 분야에서 활용되고 있다.[1]
8. 4. 계산량에 따른 분류
입력값의 크기가 일 경우, 점근 표기법 를 사용하여 다음과 같이 나타낸다.- : 에 관계없이 일정 시간 이하에 수행되는 알고리즘이다. (예: 파일의 첫 번째 바이트가 널(null)인지 검사)
- : 에 비례하는 시간 이하에 수행되는 알고리즘이다. (예: 이진 탐색)
- : 에 비례하는 시간 이하에 수행되는 알고리즘이다. (예: 기수 정렬)
- : 에 대략 비례할 수 있는 시간 이하에 수행되는 알고리즘이다. (예: 정렬 알고리즘)
- : 에 비례하는 시간 이하에 수행되는 알고리즘이다. (예: 최장 공통 부분 수열 문제)
- : 에 비례하는 시간 이하에 수행되는 알고리즘이다. (예: 행렬 곱셈)
- : 과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. (예: 충족 가능성 문제)
- : 즉 과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. (예: 배열의 모든 순열을 검사)
대문자 O 표기법의 정의상 아래의 복잡도는 그 위의 복잡도를 포함하므로, 대부분의 알고리즘은 의 수행 시간을 가진다.
알고리즘은 입력 길이에 대한 계산 시간으로 분류된다. 어떤 알고리즘은 입력 길이에 대해 선형 시간에 완료되고, 다른 알고리즘은 지수 시간 이상 걸리거나, 경우에 따라 완료되지 않을 수도 있다. 문제에 따라 계산량이 다른 여러 알고리즘이 존재하며, 효율적인 알고리즘이 전혀 알려져 있지 않은 문제도 있다. 문제에 따라 다른 문제로의 사상(mapping)이 존재하기도 한다. 이러한 이유로, 계산량에 의한 분류는 알고리즘 자체가 아니라 문제를 대상으로 수행하는 것이 적절하며, 문제를 푸는 최선의 알고리즘의 계산량을 기반으로 문제를 분류한다.
8. 5. 계산 능력에 따른 분류
일반적으로 알고리즘은 계산 능력에 따라 계층적으로 분류된다. “재귀적 클래스”는 모든 튜링 계산 가능 함수에 대한 알고리즘을 포함하는 클래스이다. 이러한 계층화를 통해 계산에 필요한 계산 자원(시간과 메모리)을 제한할 수 있는 가능성이 생긴다. “부분 재귀 클래스”는 모든 튜링 계산 가능 함수를 얻을 수 없다. 예를 들어, 다항식 시간에 실행되는 알고리즘에는 많은 중요한 계산이 포함되지만, 튜링 계산 가능 함수 전체를 포함하지는 않는다. 원시 재귀 함수로 구현되는 알고리즘의 클래스는 또 다른 부분 재귀적 클래스의 예이다.[66]함수를 계산하는 알고리즘은 유한 단계 후에 반드시 출력이 결정되어야 한다는 일반적인 조건을 완화한 알고리즘의 범용적인 정의가 제시되기도 한다. “초재귀적 클래스”는 “튜링 머신으로 계산할 수 없는 함수를 계산 가능한 알고리즘의 클래스”로 정의된다.[66] 이것은 하이퍼컴퓨터 기법의 연구와 밀접하게 관련되어 있다.
9. 법적 문제
알고리즘 자체는 일반적으로 특허 대상이 아니다. 미국에서는 추상적인 개념, 숫자 또는 신호의 단순한 조작으로만 구성된 청구항은 "공정"을 구성하지 않으므로 알고리즘은 특허 대상이 아니다(''갓츠샬크 대 벤슨'' 사건 참조). 그러나 알고리즘의 실용적인 응용은 특허 대상이 될 수 있다. 예를 들어, ''다이아몬드 대 다이어'' 사건에서 합성고무 경화를 돕기 위한 단순한 피드백 알고리즘의 응용은 특허 대상으로 간주되었다.[44] 소프트웨어 특허는 논란의 여지가 있으며,[67] 특히 데이터 압축 알고리즘과 같은 알고리즘을 포함하는 특허, 예를 들어 유니시스의 LZW 특허가 비판을 받고 있다.
데이터 압축 알고리즘 분야에서는 유니시스의 LZW 알고리즘의 특허 문제가 유명하다. 산술 부호화에서 취득된 특허의 범위는 3가지로 여겨진다. 산술 부호화로 인해 포기된 소프트웨어와 파일 형식은 많으며, 대체품이 잇따라 개발되었다.
선형 계획 문제의 해법인 카마카의 알고리즘은 일본에서 특허 무효 심판이 이루어졌지만, 2000년 12월 11일자로 특허청에 해당 특허의 포기로 인한 특허권 소멸이 등록되었기 때문에, 최종적으로 심판이 기각되었다.
일본 저작권법 제10조 3항은 알고리즘이 명시적으로 저작권법의 보호 대상이 아님을 규정하고 있다.[68] 다만, 알고리즘을 기록한 문서나 알고리즘을 구현한 프로그램은 저작물로서 보호 대상이 된다.[69]
암호 알고리즘 중에는 수출이 규제되는 것도 있다(미국 사례).
10. 예시
정렬되지 않은 숫자 목록에서 최댓값을 찾는 알고리즘은 다음과 같이 간단하게 설명할 수 있다. 목록 안에 있는 모든 수를 차례대로 살펴보면서, 현재까지 찾은 최댓값보다 큰 수가 나타나면 그 수를 새로운 최댓값으로 기억하는 방식이다.
'''상위 수준 설명:'''
# 숫자 목록이 비어 있으면 최댓값은 없다.
# 목록의 첫 번째 숫자를 최댓값이라고 가정한다.
# 목록의 나머지 각 숫자에 대해: 현재 최댓값보다 큰 숫자가 나타나면, 그 숫자를 새로운 최댓값으로 설정한다.
# 더 이상 확인할 숫자가 없으면, 현재 최댓값이 목록 전체의 최댓값이다.
이를 좀 더 형식적으로 표현하면 다음과 같은 의사 코드로 나타낼 수 있다.
'''입력:''' 숫자 목록 ''L''.
'''출력:''' 목록 ''L''의 가장 큰 숫자.
'''만약''' ''L.크기'' = 0 '''이면''' null을 '''반환'''
''최대값'' ← ''L''[0]
'''각''' ''항목'' '''에 대해''' ''L'' '''에서''', '''다음을 수행'''
'''만약''' ''항목'' > ''최대값'' '''이면''', '''다음을 수행'''
''최대값'' ← ''항목''
'''반환''' ''최대값''
위 의사 코드에서 "←" 기호는 값을 할당하는 것을 의미하며, '''return'''은 값을 반환하고 알고리즘을 종료한다는 의미이다.
참조
[1]
웹사이트
Definition of ALGORITHM
https://www.merriam-[...]
2019-11-14
[2]
서적
Information Retrieval: Algorithms and Heuristics
2004
[3]
서적
1987
[4]
서적
1987
[5]
서적
1987
[6]
서적
1973
[7]
서적
1973
[8]
서적
1973
[9]
서적
1987
[10]
서적
Information: A Historical Companion
Princeton University Press
2021
[11]
서적
1973
[12]
서적
The Death Algorithm and Other Digital Dilemmas
https://books.google[...]
MIT Press
2018
[13]
서적
The MIT Encyclopedia of the Cognitive Sciences
https://books.google[...]
MIT Press
2001
[14]
서적
1973
[15]
서적
1999
[16]
서적
A History of Algorithms: From the Pebble to the Microchip
Springer Science & Business Media
2012
[17]
서적
Contributions to the History of Indian Mathematics
https://books.google[...]
Springer
2005
[18]
웹사이트
Brahmagupta
https://www.britanni[...]
2023-01-01
[19]
학술지
Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria
https://www.jstor.or[...]
1970
[20]
서적
The History of Mathematics: A Brief Course
John Wiley & Sons
2005
[21]
학술지
A History of Algorithms
https://link.springe[...]
1999
[22]
서적
A Brief History of Cryptology and Cryptographic Algorithms
Springer Science & Business Media
2013
[23]
학술지
Ancient Babylonian Algorithms
http://steiner.math.[...]
1972
[24]
서적
Episodes from the Early History of Astronomy
Springer
2001
[25]
웹사이트
Eratosthenes
http://www.math.wich[...]
Wichita State University: Department of Mathematics and Statistics
[26]
서적
1984
[27]
서적
1984
[28]
서적
1984
[29]
서적
1971
[30]
뉴스
A Tinkerer Gets a Place in History
Valley News West Lebanon NH
1983-03-31
[31]
서적
2000
[32]
서적
1943
[33]
서적
1939
[34]
서적
2006
[35]
학술지
The (black) art of run-time evaluation: Are we comparing algorithms or implementations?
2016
[36]
웹사이트
Better Math Makes Faster Data Networks
http://discovermagaz[...]
discovermagazine.com
2014-05-13
[37]
논문
ACM-SIAM Symposium On Discrete Algorithms (SODA)
http://siam.omnibook[...]
2012-01-01
[38]
서적
Algorithm Design: Foundations, Analysis, and Internet Examples
http://ww3.algorithm[...]
John Wiley & Sons, Inc.
2018-06-14
[39]
웹사이트
Big-O notation (article) Algorithms
https://www.khanacad[...]
2024-06-03
[40]
서적
Back to Basic: The History, Corruption, and Future of the Language
Addison-Wesley Publishing Company, Inc.
[41]
서적
[42]
서적
[43]
서적
[44]
뉴스
The Experts: Does the Patent System Encourage Innovation?
https://www.wsj.com/[...]
2017-03-29
[45]
서적
Knapsack Problems
https://www.springer[...]
Springer
2017-09-19
[46]
논문
A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies
1991-01-01
[47]
서적
Linear Programming 2: Theory and Extensions
Springer-Verlag
[48]
기타
[49]
웹사이트
https://kotobank.jp/[...]
[50]
웹사이트
https://kotobank.jp/[...]
[51]
웹사이트
https://kotobank.jp/[...]
[52]
웹사이트
https://kotobank.jp/[...]
[53]
웹사이트
https://kotobank.jp/[...]
[54]
웹사이트
アルゴリズム IoT用語辞典 キーエンス
https://www.keyence.[...]
キーエンス
2024-12-27
[55]
서적
ユークリッド『原論』第 7 巻「数論」、命題 1〜3
[56]
웹사이트
Britannica Encyclopedia - Algorithm: Definition, Types, & Facts
https://www.britanni[...]
2023-01-14
[57]
논문
Sequential Abstract State Machines Capture Sequential Algorithms
http://research.micr[...]
2000-07-01
[58]
기타
[59]
기타
[60]
서적
Introduction to Metamathematics
노스 홀랜드 출판
[61]
서적
Fundamental Algorithms, Third Edition
아디슨-웨슬리
[62]
서적
Computation: Finite and Infinite Machines
프렌티스 홀, 미국 뉴저지주
[63]
기타
[64]
서적
Introduction to the Theory of Computation
PWS 출판
[65]
논문
Algorithm=Logic+Control
ACM Press
[66]
서적
Super-recursive algorithms
Springer
[67]
웹사이트
2106.02 **>Mathematical Algorithms< - 2100 Patentability
http://www.uspto.gov[...]
미국 특허 상표청
[68]
웹사이트
저작권 잘 알고 계십니까? 질문 상자
http://chosakuken.bu[...]
문화청
[69]
웹사이트
기본 정보 기술자 평성 24년 춘기 오전 문제 78
http://www.fe-siken.[...]
기본 정보 기술자 시험 .com
[70]
웹사이트
구글에서 "알고리즘" 검색 결과 및 "알고리듬" 검색 결과
https://www.google.c[...]
관련 사건 타임라인
( 최근 20개의 뉴스만 표기 됩니다. )
소년엔 '폭력', 소녀엔 '강박'…SNS, 유해 요소 난무 [소셜픽]
노르마, 엔비디아 GPU로 신약 개발용 양자 AI 성능 검증 – 바이라인네트워크
[책과 삶] 범죄자였던 데이터 기반 감시사회의 설계자
폴더소비·N놀러·듣폴트…Z세대 소비 트렌드 들여다보니
새정부 성장전략, ‘장밋빛 AI’로 가득…양극화·민생경제 회복은 ‘뒷전’
[인기검색TOP5] 제놀루션, 스튜디오드래곤, 지투지바이오, 에이프로젠, 한화솔루션
중년의 나는 왜 유튜브에 빠지게 됐나
한 달 걸린 ‘이형 패널 엣지’ 설계, AI에 맡겨보니 8시간 만에 ‘뚝딱’
[인기검색TOP5] 삼아알미늄, 풀무원, NHN, 한국카본, 일진전기
중국, ‘제살깎기’ 저가경쟁 제동…27년 만에 가격법 손질
“좋은 리뷰만 보이네?”…온라인몰 36% 자체 알고리즘 정렬 ‘아전인수’
"안 좋단 글은 못 찾겠네"…온라인몰 36%, 자의적 리뷰 정렬
[인기검색TOP5] 형지글로벌, 휴메딕스, 현대힘스, 비에이치, 엘엔씨바이오
엑스, '알고리즘 조작 의혹' 수사에 반발…"협조 안 한다"
한투운용, 퇴직연금 로보어드바이저 서비스 ‘킴로보’ 출시
한투운용, 퇴직연금 로보어드바이저 서비스 ‘KimRobo’ 출시
[인기검색TOP5] 샌즈랩, 제넥신, 펩트론, NHN KCP , 대양전기공업
‘정숙해야 고급차’는 옛말…“예민한 귀로 ‘좋은 소리’ 만들어요”
스피커스 #43 알고리즘, 누가 견제할 것인가
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com