앨거리듬

필독 사항	유닠스 계열	저작물, 성인물, 도박	웹 써버 보안	프로그래밍	그래핔	파싱
필독 사항	고스트BSD	표면 웹 싸이트 제작	리눅스 마스터	파이썬	트킨터	뷰티펄 숲
수학	아이투피	마약, 아청물, 해킹	웹 싸이트 보안	웹 프로그래밍	데이터 분석	게임 제작
통계학	뮤와이어	다크넽 싸이트 제작	정보 보안 기사	쟁고우	팬더즈	파이게임

* 컴퓨터 관련 정보
* 관련 문서: 컴퓨터 과학, 프로그래밍

개요

문제를 해결하기 위한 절차나 방법.

algorithm의 발음 기호는 [|ӕlgərɪðəm]이며 ð는 this [ðɪs]의 ð 발음이다. 즉, algorithm을 알고리즘으로 읽는 건 this를 "지스"로 읽는 것과 마찬가지이다. 이 단어는 영어식으로 앨거리듬으로 표기하거나 좀 더 한국식 발음으로 표기하더라도 알고리듬으로 표기해야 한다. rhythm [|rɪðəm]을 "리즘"이 아닌 "리듬"으로 표기하는 것과 마찬가지이다.

algorism이라는 "아라비아 숫자식 기수법"이라는 뜻을 가진 유사한 단어가 있으며 이 단어의 발음기호는 [ǽlɡərìzm]이므로 오히려 이 단어를 앨거리즘이나 알고리즘이라고 읽어야 한다.

이 단어는 아랍의 수학자인 알-콰리즈미(الخوارزمي)의 이름에서 유래했다고 알려졌다. 아라비아 기수법을 나타내는 algorism도 같은 어원을 가진다. 이 때문에 구분을 위해 algorithm 쪽을 '알고리듬'으로 읽는 경우도 있으나 일반적으론 그냥 알고리즘으로 쓰며[* 2012년 구글 검색결과 수 "알고리듬" 290,000건, "알고리즘" 4,510,000건], 그냥 algorism 쪽을 뜻으로 풀어 쓰기 때문에 혼동은 없는 편이다. 참고로 algorithm을 알고리즘이라 읽어버리는 이유는 중역의 흔적인데, 유성음 th(they의 th)가 일본어에서는 ざ(za)행에 대응되므로[* [유행했던 사나와 강남의 발음 언쟁]에서 이를 확인할 수 있다.] algorithm은 일본어로 '아루고리즈무'가 되는데 이를 한국어에 그대로 가져온 것.

알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다. 컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저(진행절차)를 의미한다. 컴퓨터 시대 이후로는 알고리즘이라고 하면 컴퓨터를 통해 실행되는 것이라고 여겨지는 경향이 있으나, 사실 알고리즘 자체는 컴퓨터가 등장하기 이전부터도 존재했다. 즉, 사람이 수동으로 종이를 사용해 일정한 절차로 문제를 풀더라도 알고리즘에 해당한다. 다만, 컴퓨터의 등장과 함께 알고리즘 역시 급속도로 발전하게 된 것은 사실이다.

알고리즘의 조건

알고리즘은 이하의 요건을 만족해야만 한다.

* 입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
* 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다.
* 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.[* 이 조건에 의해 난수를 사용하는 절차는 알고리즘에 포함되지 않을 것 같으나, 난수의 확률 분포가 가져야 할 특성이 명백하다면 알고리즘에 포함된다.]
* 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0[* m은 0이 아니다. a!=b ↔ b가 고정된 상태에서 a≠b를 의미한다.]이면 n의 값은 다음 번 단계에서 줄어든다.
* 효과성 - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

한편 대니얼 데닛은 자신의 저서 "직관 펌프" 에서 (pp.184-185) 세 가지 핵심 특징을 거론했다.

* 재료 중립성(substrate neutrality) - 알고리즘은 그 절차적 논리에 의해 결과를 도출하며, 재료가 갖는 인과적 힘은 알고리즘의 작동에 어떤 영향도 갖지 않는다.
* 마음 없는 토대(underlying mindlessness) - 알고리즘의 절차는 세분화된 일련의 단계들로 구성되며, 이 각각의 단계들은 별다른 의미해석이 요구되지 않을 만큼 지극히 단순하다.
* 결과 보장(guaranteed result) - 일단 알고리즘의 각 단계들이 실수나 오류 없이 수행된다면, 알고리즘은 최종 단계에서 반드시 성공적인 결과물을 산출한다.

즉, 쉽게 말하면 알고리즘은 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고, 효과적으로 입력에 따른 결과물을 도출 할 수 있다면 알고리즘으로 볼 수 있다는 의미이다. 반대로 명령에 애매함이 있다거나 유한한 시간 안에 끝나는 것이 보장되지 않은 경우를 메서드(Method)라고 한다. 예를 들어 '산에서 길을 잃었을때 계곡을 찾아서 아래로 내려간 뒤 물길을 따라 하류로 가면 된다.' 라는 문장은 메서드이다.

알고리즘의 표현 방법

알고리즘은 크게 3개의 표현 방법을 가진다. 첫번째는 고차원적인 언어로 인간이 이해하기 쉬운 말로 설명되어 있는 형태이며[* 의사코드(pseudocode)가 이 범주에 들어간다], 두번째는 구현 상세 내역이며, 마지막으로는 인간이 꽤 알아먹기 힘든 튜링 머신의 Stable Table이라고 불리는 그림이나 출력물의 형태로 나타내는 방법이 있다.

알고리즘의 평가

알고리즘이 위의 조건들을 모두 만족한다면 문제를 풀 수 있다고 할 수 있지만, '효과적으로' 풀어낸다고 할 수는 없다. 위에서 말한 유한한 시간이 몇 달 혹은 몇 년이 될 수도 있기 때문이다. 따라서 우리는 알고리즘을 효율성으로 평가하게 되고, 컴퓨터에서는 시간과 메모리라는 두 자원을 얼마나 소모하는지가 효율성의 중점이 된다.

* 시간 복잡도(time complexity) 

알고리즘의 소요 시간을 정확히 평가할 수는 없으므로, 자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 시간 복잡도라는 이름으로 나타내게 된다.[* 자세한 asymptotic이나 O-표기법의 이론은 생략한다.] 이를 O 표기법(Big O notation)으로 주로 나타낸다. 예를 들어 입력 자료의 크기 n에 대하여 O(n)의 시간복잡도를 가진 알고리즘은 대략 크기 n에 비례하는 수의 연산을 수행한다고 보면 된다.

알고리즘의 종류에 따라 시간복잡도의 평가기준도 다양하다. 일반적으로는 O(n)의 시간복잡도를 가지면 좋은 알고리즘으로 취급하며[* 대부분의 경우 자료를 읽는 데에 어쨌든 n의 시간이 필요하므로. 물론 검색 알고리즘에서 O(n)은 최악.][* 물론 O(1)같은 상수항도 있다. 크기에 상관없이 (1을 넣든 10000을 넣든) 특정한 시간 내에 끝낸다.], log(n)의 지수승이 붙는 정도로 막으면(O(n log n) 등) 매우 바람직한 결과이다. O(n^^3^^) 정도만 돼도 큰 자료수에선 급격히 느려진다. 검색 알고리즘의 경우 O(1)이나 O(log(n))의 시간복잡도를 가지는 알고리즘을 선호한다.

이런 식으로 시간 복잡도가 n의 다항식 이하가 되는 알고리즘들을 다항 시간 알고리즘(polynomial time algorithm)이라고 한다. 여기까지만 보면 다항식과는 넘사벽[* 굳이 표현하자면 n < n log n << n^^2^^ <<< n^^3^^ <<<< n^^4^^ <<<<< (넘사벽) <<<<< 2^^n^^ <<<<< (넘사벽) <<<<< n! 정도가 되지 않을까.]의 증가속도를 자랑하는 O(2^^n^^) 또는 O(n!) 같은 알고리즘은 매우 막장인 것처럼 보이지만, 세상에는 이런 알고리즘밖에 방법이 없는 어려운 문제들이 수두룩하다. 이런 경우에는 정답을 포기하고 근사해를 구해주는 알고리즘을 찾게 된다. 더 자세한 이야기는 P-NP 문제 참고.

* 공간 복잡도(space complexity)

현실에서는 시간 복잡도보다 중요도는 떨어지는데, 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 없기 때문이고, 다항 시간 내에서 나타나는 메모리 문제들은 보통 알고리즘 자체보다는 알고리즘의 구현에서 발생하는 문제이기 때문이다. 다만 동적 계획법의 경우에는 메모리를 상당히 많이 필요하기 때문에 (즉, 공간복잡도가 크기 때문에) 입력 값의 범위가 넓으면 사용하지 못하는 경우가 많다. 이론적으로는 n에 대한 다항식만큼의 공간으로도 해결이 안 되는 정말 어려운 문제들[* 앞에 넘사벽처럼 어렵다고 한 문제들 이상의 우주급 넘사벽이 있다!] 을 생각하기도 한다.

프로그래밍에서 사용하는 알고리즘들

* 자료구조: 관심있는 위키러는 정렬, 탐색 문서를 반드시 읽어보길 바란다.
 * 정렬, 정렬/예제, 탐색
  * 탐색 알고리즘: DFS (Depth-First Search), BFS (Breadth-First Search), 이진 탐색 등.
   * 트리 탐색 알고리즘: 우선법, 힙 트리(heap), 트라이(Trie)
    * 그래프 알고리즘 기반의 최단 경로 탐색: 다익스트라 알고리즘, 벨먼-포드 알고리즘, A* 알고리즘
* 알고리즘 패러다임: 백트래킹, 동적 계획법, 분할 정복법, 분기 한정법, 그리디 알고리즘
 * 동적 계획법: 메모이제이션 문서도 참조.
 * 최소 신장 트리: 크러스컬 알고리즘
* 그래프 알고리즘: 경로 탐색, Union Find, 네트워크 흐름(network flow) 알고리즘
* 기계학습: 서포트 벡터 머신(SVM) 등.
* 문자열 알고리즘: KMP 등,
* 기타 Pollard's rho 등의 정수론 알고리즘, 선형합동법등의 난수발생 알고리즘, 해석기하/그래픽 알고리즘, 유전 알고리즘 기법 등.

* 응용 분야에 따른 구분
 * 미로탐색 알고리즘: 트리 탐색 알고리즘 예제로 많이 나오는 문제.
 * 알고리즘 트레이딩
 * 암호 알고리즘: AES, DES, SEED, 아리아, LEA, MD5, ROT13, 공개키 암호화 방식, 대칭 열쇠 암호, RSA 암호화, 복호화, SHA

일상 생활에 쉽게 사용하는 알고리즘들

현실적으로 쓸모있는 알고리즘은 생각외로 많다. --예를들면 파인만 알고리즘이라든지--

* 미로 찾기 : 우선법이나 좌선법이 미로를 찾는 알고리즘 중 하나다.
* 루빅스 큐브 풀기 : 큐브의 해법 참고.
* 마방진 : 홀수 마방진의 경우 대각선으로 숫자를 써가면서 다 채운 다음에 상하좌우에 튀어나온 숫자들을 반대편으로 넘기면 끝난다. 뿌리깊은 나무에서 어린 세종이 이걸 스스로 찾아내는 장면이 나온다.
* 뉴턴-랩슨 방법 : 방정식의 해를 구하는 방법.

알고리즘 트레이닝 사이트

온라인 DB를 이용하여 평가하는 자발 트레이닝 시스템으로 보통 온라인 저지라고 한다.

* 더블릿
* Baekjoon OJ
* CodeUp
* JUNGOL
* KOISTUDY
* [OJ]
* [[1]]