알고리즘

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm 알고리듬[*], IPA[ǽlɡərìðm])은 수학컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것을 말한다.

알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다. 산법(算法)으로 번역되기도 한다.

명칭[편집]

알고리즘은 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말이다.

영어로 algorithm의 발음 기호는 [ӕlgərɪðəm]이며 ð는 this [ðɪs]의 ð 발음이기 때문에, algorithm을 알고리즘으로 읽는 것은 this를 "지스"로, rhythm [rɪðəm]을 '리즘'으로 읽는 것과 마찬가지의 잘못이라는 주장이 있다. 하지만 실제 생활에서는 알고리즘이라는 표기가 알고리듬이라는 표기에 비해 압도적으로 많이 사용되고 있다.[1]

알고리즘의 정의[편집]

정지 문제의 결과로 알고리즘이 정지하는 데 걸리는 시간을 일반적으로 측정할 수 없기 때문에, 알고리즘에 대한 naive한 직관을 만족하는 형식적인 정의는 불가능하다. 따라서 알고리즘의 공식적인 정의는 없다.

대부분의 알고리즘은 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의한다. 다음은 좋은 알고리즘의 특징이다.

  • 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
  • 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
  • 타당성 : 구현할 수 있고 실용적이어야 한다.
  • 입력 : 정의된 입력을 받아들일 수 있어야 한다.
  • 출력 : 답으로 출력을 내보낼 수 있어야 한다.
  • 유한성 : 특정 수의 작업 이후에 정지해야 한다.
  • 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

구현[편집]

알고리즘은 자연어, 의사코드, 순서도, 프로그래밍 언어, 인터프리터가 작업하는 제어 테이블, 유한 상태 기계상태도 등으로 표현할 수 있다. 다음은 알고리즘 개발의 정형적인 단계이다.

문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화

알고리즘을 설계하는 기술에는 운용 과학의 방법, 설계 패턴을 이용하는 방법 등이 있다. 대부분의 알고리즘은 컴퓨터 프로그램으로 구현되지만, 전기 회로나 생물학적 신경 회로를 사용하기도 한다.

분류[편집]

복잡성[편집]

입력의 크기가 일 경우, 점근 표기법 를 사용하여 다음과 같이 나타낸다.

  •  : 에 관계없이 일정 시간 이하에 수행되는 알고리즘이다. 예) 파일의 첫 번째 바이트가 (null)인지 검사하는 것.
  •  : 에 비례하는 시간 이하에 수행되는 알고리즘이다. 예) 이진 탐색.
  •  : 에 비례하는 시간 이하에 수행되는 알고리즘이다. 예) 기수 정렬.
  •  : 에 대략 비례할 수 있는 시간 이하에 수행되는 알고리즘이다. 예) 정렬 알고리즘.
  •  : 에 비례하는 시간 이하에 수행되는 알고리즘이다. 예) 최장 공통 부분 수열 문제.
  •  : 에 비례하는 시간 이하에 수행되는 알고리즘이다. 예) 행렬 곱셈.
  •  : 과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. 예) 충족 가능성 문제.
  •  : 과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다. 예) 배열의 모든 순열을 검사하는 것.

대부분의 알고리즘은 의 수행 시간을 가진다.

[편집]

알고리즘의 예[편집]

가장 단순한 알고리즘 가운데 하나는 임의로 나열된 숫자들 가운데 가장 큰 수를 찾는 것이다. 다음은 목록 안에 있는 모든 수를 살펴보는 알고리즘이다.

알고리즘 LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • "←"은 대입을 가리킨다. 이를테면 "α ← β"는 α에 β를 대입하는 것을 뜻한다.
  • "return"은 알고리즘을 종료하고 다음의 값을 출력한다.

같이 보기[편집]

각주[편집]

외부 링크[편집]