mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-10-01 11:02:48

알고리즘


파일:나무위키+유도.png  
은(는) 여기로 연결됩니다.
ITZY의 일본 싱글 3집에 대한 내용은 Algorhythm 문서
번 문단을
부분을
, BEMANI 시리즈의 수록곡에 대한 내용은 ALGORITHM(BEMANI 시리즈) 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
참고하십시오.
파일:하위 문서 아이콘.svg   하위 문서: 알고리즘/컴퓨터 알고리즘
,
,
,
,
,
#!wiki style="display: inline; display: none;"
, }}}
알고리즘 관련 틀
[ 펼치기 · 접기 ]
''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
<colbgcolor=#a36> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 }}}}}}}}}


이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"
이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( 공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}



[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]
[ 펼치기 · 접기 ]
||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 || 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술 기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속
연구

기타
논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) · 버전 ( 버전 관리 시스템 · Git · GitHub)

1. 개요2. 알고리즘의 조건3. 알고리즘의 표현 방법4. 알고리즘의 평가
4.1. 시간 복잡도4.2. 공간 복잡도
5. 주요 알고리즘 종류6. 알고리즘 경시대회7. 관련 문서

1. 개요

Algorithm | 연산법

문제를 해결하기 위한 절차나 방법. 더 정확한 정의로는, 모든 입력값에 대해 튜링머신이 정지하게 하는 명령.

이 단어는 페르시아의 수학자인 알-콰리즈미(الخوارزمي)의 이름에서 유래했다고 알려졌다.[1] 아라비아 기수법을 나타내는 algorism도 같은 어원을 가진다. 이 때문에 구분을 위해 algorithm 쪽을 '알고리듬'으로 읽는 경우도 있으며 #, 실제 영어 발음은 미국식이나 영국식이나 [ǽlgərìðm]('앨거리듬'에 가까움)이나 한국에서는 일반적으론 그냥 알고리즘으로 쓴다.[2] 그런데 algorism 쪽을 뜻으로 풀어 쓰기 때문에 혼동은 없는 편이다.

참고로 algorithm을 알고리즘이라 읽어버리는 이유는 중역의 흔적으로 보인다. 유성음 th(they, the의 [ð])가 일본어에서는 ざ(za)행에 대응되므로[3] algorithm은 일본어로 '아루고리즈무'가 되는데 이를 한국어에 그대로 가져왔다는 것. # 리듬과 똑같은 발음인데 리즘이라 표기하는 것이니 좀 이상한 일이다.[4] 참고로 국립국어원은 알고리듬(Algorithm)과 알고리즘(Algorism) 둘다 표기의 근거가 되는 원어는 다르지만, 같은 어원과 동일한 의미를 지닌 표준어로 인정했다.

알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넓은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다.

컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 진행절차(procedure)를 의미한다. 컴퓨터 시대 이후로는 알고리즘이라고 하면 컴퓨터를 통해 실행되는 것이라고 여겨지는 경향이 있으나, 사실 알고리즘 자체는 컴퓨터가 등장하기 이전부터도 존재했다. 즉, 사람이 수동으로 종이를 사용해 일정한 절차로 문제를 풀더라도 알고리즘에 해당한다. 다만, 컴퓨터의 등장과 함께 알고리즘 역시 급속도로 발전하게 된 것은 사실이다. 스택, , 환형 큐, , 트리, 그래프 6가지가 숙지되면 자료구조의 거의 대부분 이해한 것이라 볼 수 있다.

아이러니한 점은, 알고리즘이 문제의 정답을 제시할 필요는 없다는 것이다. 예를 들어, "저게 대체 뭡니까?"란 질문을 들었을 때, "몰라요."라고 답하는 것도 알고리즘이다. 중요한 포인트는 어떤 질문을 받더라도 제한된 시간내에 답을 하는 것이다. 이는 튜링머신에서는 결과값을 반환하지 않더라도, 중간에라도 정지하기만 하면 되는 것과 같다.

2. 알고리즘의 조건

알고리즘은 이하의 요건을 만족해야만 한다.
한편 대니얼 데닛은 자신의 저서 "직관 펌프" 에서 (pp.184-185) 세 가지 핵심 특징을 거론했다.
즉, 쉽게 말하면 알고리즘은 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고, 효과적으로 입력에 따른 결과물을 도출 할 수 있다면 알고리즘으로 볼 수 있다는 의미이다. 반대로 명령에 애매함이 있다거나 유한한 시간 안에 끝나는 것이 보장되지 않은 경우를 메서드(Method)라고 한다. 예를 들어 '산에서 길을 잃었을때 계곡을 찾아서 아래로 내려간 뒤 물길을 따라 하류로 가면 된다.' 라는 문장은 메서드이다.

3. 알고리즘의 표현 방법

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

4. 알고리즘의 평가

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

4.1. 시간 복잡도

Time Complexity

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

알고리즘의 종류에 따라 시간 복잡도의 평가기준도 다양하다. 일반적으로는 [math(\mathcal{O}(n))]의 시간 복잡도를 가지면 좋은 알고리즘으로 취급하며[9][10], [math(\log n)]의 지수승이 붙는 정도로 막으면([math(\mathcal{O}(n \log n))]) 등) 매우 바람직한 결과이다. [math(\mathcal{O}(n^3))] 정도만 돼도 큰 자료수에선 급격히 느려진다.

검색 알고리즘의 경우 [math(\mathcal{O}(1))]이나 [math(\mathcal{O}(\log n))]의 시간 복잡도를 가지는 알고리즘을 선호하고, 정렬 알고리즘의 경우 [math(\mathcal{O}(n \log n))]의 시간 복잡도를 가지는 알고리즘을 선호한다. 여기에 각각 해당되는 자료구조/알고리즘에는 해시 테이블과 퀵 정렬 등이 있다.

이런 식으로 시간 복잡도가 n의 다항식 이하가 되는 알고리즘들을 다항 시간 알고리즘(polynomial time algorithm)이라고 한다. 여기까지만 보면 다항식과는 넘사벽[11]의 증가속도를 자랑하는 [math(\mathcal{O}(2^n))] 또는 [math(\mathcal{O}(n!))] 같은 알고리즘은 매우 막장인 것처럼 보이지만, 세상에는 이런 알고리즘밖에 방법이 없는 어려운 문제들이 수두룩하다. 이런 경우에는 정답을 포기하고 근사해를 구해주는 알고리즘을 찾게 된다.
파일:상세 내용 아이콘.svg   자세한 내용은 P-NP 문제 문서
번 문단을
부분을
참고하십시오.

파일:상세 내용 아이콘.svg   자세한 내용은 시간 복잡도 문서
번 문단을
부분을
참고하십시오.

4.2. 공간 복잡도

Space Complexity

공간 복잡도 역시 앞서 언급한 시간 복잡도처럼 Big-O 표기법(Big O notation)을 주로 사용한다. 현실에서는 시간 복잡도보다 중요도는 떨어지는데, 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 없기 때문이고, 다항 시간 내에서 나타나는 메모리 문제들은 보통 알고리즘 자체보다는 알고리즘의 구현에서 발생하는 문제이기 때문이다.[12] 다만 동적 계획법의 경우에는 메모리가 상당히 많이 필요하기 때문에 (즉, 공간복잡도가 크기 때문에) 입력 값의 범위가 넓으면 사용하지 못하는 경우가 많다. 또한 임베디드, 펌웨어 등 하드웨어 환경이 극도로 한정되어 있을 경우 공간 복잡도도 상당히 중요하게 보게된다. 이론적으로는 n에 대한 다항식만큼의 공간으로도 해결이 안 되는 정말 어려운 문제들[13]을 생각하기도 한다.

5. 주요 알고리즘 종류

사실 수학적인 스킴 혹은 물리학 스킴을 컴퓨터에서 실행해 입력과 출력값이 명확하면 알고리즘이라고 정의할 수 있다. 수치해석, 최적화 이론, 통계학, 확률 등을 포함한 수학영역을 포함하면 정의는 끝없이 폭넓어 진다.

6. 알고리즘 경시대회

주어진 문제를 풀며 경쟁하는 것을 CP(Competitive Programming)이라고 하며, 보통 대회 등의 형식으로 치른다. 온라인 대회는 위의 온라인 저지 사이트들에서 자주 열며, 아래는 오프라인 대회의 목록이다.

7. 관련 문서


[1] 대수학을 뜻하는 영어 단어인 algebra 또한 그의 이름에서 유래된 단어이다. [2] 2012년 구글 검색결과 수 "알고리듬" 290,000건, "알고리즘" 4,510,000건. [3] 한때 유행했던 사나와 강남의 발음 언쟁에서 이를 확인할 수 있다. [4] 일본의 아케이드 리듬 게임인 CHUNITHM도 츄니 (중2) + 리듬의 합성어인데 츄니즘으로 읽는다. 일본어 표기의 흔적이라고밖에 할 수 없는 셈. [5] 이 조건에 의해 난수를 사용하는 절차는 알고리즘에 포함되지 않을 것 같으나, 난수의 확률 분포가 가져야 할 특성이 명백하다면 알고리즘에 포함된다. [6] m은 0이 아니다. a != b ↔ b가 고정된 상태에서 a ≠ b를 의미한다. [7] 의사코드(pseudocode)가 이 범주에 들어간다. [8] 자세한 asymptotic이나 O-표기법의 이론은 생략한다. [9] 대부분의 경우 자료를 읽는 데에 어쨌든 [math(n)]의 시간이 필요하므로. 물론 검색 알고리즘에서 [math(\mathcal{O}(n))]은 최악. [10] 물론 [math(\mathcal{O}(1))] 같은 상수항도 있다. 크기에 상관없이 (1을 넣든 10000을 넣든) 특정한 시간 내에 끝낸다. [11] 굳이 표현하자면 n < n log n < n2 < n3 < n4 < (넘사벽) < 2n < (넘사벽) < n! 정도가 되지 않을까. [12] 대표적인 예시는 배열로 구현한 이진 트리로, 편향 이진 트리인 경우 메모리가 지수 단위로 증가하게 된다. [13] 앞에 넘사벽처럼 어렵다고 한 문제들 이상의 우주급 넘사벽이 있다! [14] 알고리즘론의 선수과목이다. [15] MAC주소 할당개념도 포함