알고리즘
위키백과 ― 우리 모두의 백과사전.
 |
이 문서는 편집 지침에 맞춰 다듬어야 합니다. 이 문서를 정리해 주세요. |
알고리즘(algorithm)이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.
목차 |
[편집] 알고리즘의 조건
알고리즘은 일반적으로 다음의 조건을 만족해야 한다.
- 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
- 출력 : 적어도 1개 이상의 결과를 내어야 한다.
- 명확성 : 각 명령어들은 명확하고 모호하지 않아야 한다.
- 유한성 : 알고리즘의 명령어들은 유한번의 수행후에 종료되어야 한다. 이것은 수행 시간의 현실적인 유한성을 의미한다.
- 효과성 : 모든 명령어들은 원칙적으로 종이와 연필만으로 수행될 수 있는 기본적인 것이어야 한다.
[편집] 알고리즘의 연구 분야
- 고안 : 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리즘을 개발하는데 그 의미가 있다.
- 검증 : 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요하다. 알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는데 그 목적이 있다.
- 분석 : 고안된 알고리즘을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.
- 테스트 : 디버깅, 성능분석
[편집] 알고리즘의 분석 기준
- 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
- 기억 장소 사용량
- 단순성
- 최적성 : 그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 잘 알려진 이 아니라 가장 좋은의 의미이다.
[편집] 평균과 최악의 경우 분석
- O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
- O(log N) : 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형
- O(N) : 입력 자료에 따라 선형적으로 실행 시간이 걸리는 경우
- O(N log N) : 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타남.
- O(N2) : 이중 루프 내에서 입력 자료를 처리하는 경우에 나타남.그러나 N의 크기가 작을 때에는 N2이 NlogN보다 작을 수 있음.
- O(N3) : 삼중 루프.
- O(2n) : 가끔씩 알고리즘을 처음 개발할 때 나타날 수 있는 수행시간..
[편집] 알고리즘의 예
[편집] 정렬 알고리즘
정렬 알고리즘은 내부정렬과 외부정렬로 나눌 수 있다.
내부정렬(internal sorting)은 정렬하고자 하는 모든 요소들(elements)이 동시에 주 메모리(main memory)에서 정열되어 지는 것을 말하며, 외부정렬(external sorting)은 반대로 정렬하고자 하는 특정 요소들(elements)이 주 메모리(main memory)에서 정열되고,나머지 대부분 요소들은 외부저장 장치(secondary memory)에 존재하는 것이다.
내부정렬에는 다음과 같은 것이 있다.
외부정렬에는 다음과 같은 것이 있다.
- 퀵 정렬 (quick sort)
[편집] 검색 알고리즘
- 이진 검색 (binary search)
|
|
|
|---|---|
| 수학적 기초 | 수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치해석 |
| 계산 이론 | 오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론 |
| 알고리즘 & 자료 구조 | 알고리즘 해석 · 알고리즘 · 알고리즘 설계 · 자료구조 · 계산 기하학 |
| 프로그래밍 언어 & 컴파일러 | 구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 순차적 프로그래밍 · 객체지향 프로그래밍 |
| 병행,병렬 & 분산 시스템 | 병행 컴퓨팅 · 분산 컴퓨팅 · 병렬 컴퓨팅 · 그리드 컴퓨팅 |
| 소프트웨어 공학 | 요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스팅 · 소프트웨어 개발 |
| 시스템 아키텍처 | 컴퓨터 아키텍처 · 마이크로아키텍처 · 운영체계 |
| 통신 & 네트워크 | 컴퓨터 오디오 · 라우팅 · 네트워크 토플로지 · 암호학 |
| 데이터베이스 | 데이터 마이닝 · RDBMS · SQL |
| 인공 지능 | 자동추론 · 전산언어학 · 컴퓨터 비전 · 진화연산 · 기계학습 · 자연언어 처리 · 로봇학 |
| 컴퓨터 그래픽 | Visualization · 영상 처리 |
| 인간과 컴퓨터 상호 작용 | Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실 |
| 계산과학 | 인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치해석 · Symbolic mathematics |
