알고리즘

알고리즘(algorithm)은 주어진 문제를 해결하거나 특정한 계산을 수행하기 위해 정의된 유한한 규칙과 절차의 집합이다. 알고리즘은 입력을 받아 정해진 연산을 수행하고, 문제에서 요구하는 출력을 생성한다. 같은 문제를 해결하는 알고리즘이 여러 개 존재할 수 있으며, 각 알고리즘은 정확...

알고리즘(algorithm)은 주어진 문제를 해결하거나 특정한 계산을 수행하기 위해 정의된 유한한 규칙과 절차의 집합이다. 알고리즘은 입력을 받아 정해진 연산을 수행하고, 문제에서 요구하는 출력을 생성한다. 같은 문제를 해결하는 알고리즘이 여러 개 존재할 수 있으며, 각 알고리즘은 정확성, 실행 시간, 메모리 사용량, 구현 난이도와 적용 가능한 입력의 범위에서 서로 다른 특성을 가진다.^[1]

알고리즘은 특정 프로그래밍 언어로 작성된 소스 코드 그 자체가 아니라, 계산 과정을 추상적으로 기술한 것이다. 하나의 알고리즘은 자연어, 의사 코드, 순서도, 수학적 표기 또는 여러 프로그래밍 언어로 표현될 수 있다. 프로그램은 이러한 알고리즘을 실제 컴퓨터에서 실행할 수 있도록 자료형, 자료구조, 입출력 처리와 실행 환경을 포함해 구현한 결과이다.

컴퓨터 과학에서 알고리즘을 연구할 때는 원하는 결과를 생성하는지만 확인하지 않는다. 모든 허용된 입력에서 알고리즘이 종료하고 올바른 결과를 생성하는지 증명하는 정확성 분석, 입력 크기가 증가할 때 필요한 실행 시간과 저장 공간이 어떻게 변하는지를 다루는 복잡도 분석, 그리고 문제의 구조에 적합한 해결 절차를 만드는 알고리즘 설계가 함께 다뤄진다.^[2]

알고리즘의 효율성은 일반적으로 특정 컴퓨터의 실제 실행 시간보다 입력 크기에 따른 연산량의 증가율로 분석한다. 이를 위해 점근 표기법을 사용하며, 최악의 경우, 평균적인 경우와 최선의 경우를 구분할 수 있다. 그러나 실제 성능은 자료구조, 메모리 접근 패턴, 캐시, 병렬성, 컴파일러 최적화, 입력 데이터의 분포와 하드웨어 특성에도 영향을 받는다.

알고리즘은 정렬, 검색, 그래프 탐색, 문자열 처리, 수치 계산, 최적화, 암호화, 압축과 스케줄링을 비롯한 거의 모든 계산 분야의 기반을 이룬다. 또한 분할 정복, 동적 계획법, 탐욕 알고리즘, 백트래킹과 같은 설계 기법은 서로 다른 문제에서 반복적으로 활용되는 일반적인 문제 해결 구조를 제공한다.^[3]

알고리즘 종류

알고리즘은 해결하는 문제, 사용하는 설계 기법, 입력이 주어지는 방식, 계산 환경과 결과의 보장 수준에 따라 분류할 수 있다. 이 기준은 서로 배타적이지 않으므로 하나의 알고리즘이 여러 분야와 기법에 동시에 속할 수 있다. 아래 둘러보기 상자는 대표적인 알고리즘과 설계 방법을 분야별로 연결한다.^[4]^[5]

알고리즘 종류와 대표 알고리즘

설계 기법	완전 탐색 · 분할 정복 · 동적 계획법 · 탐욕 알고리즘
	기본 설계	완전 탐색 · 분할 정복 · 감소 정복 · 변환 정복 · 재귀 알고리즘 · 반복 알고리즘
	상태 공간 탐색	백트래킹 · 분기 한정법 · 반복 깊이 증가 탐색 · 빔 탐색
	효율화	메모이제이션 · 테이블화 · 탐욕 알고리즘 · 근사 알고리즘 · 휴리스틱 알고리즘
계산과 실행 방식	결정적 알고리즘 · 무작위 알고리즘 · 온라인 알고리즘 · 병렬 알고리즘
	결과 보장	정확 알고리즘 · 근사 알고리즘 · 몬테카를로 알고리즘 · 라스베이거스 알고리즘
	입력·갱신	온라인 알고리즘 · 오프라인 알고리즘 · 스트리밍 알고리즘 · 동적 알고리즘 · 외부 메모리 알고리즘
	실행 모델	순차 알고리즘 · 병렬 알고리즘 · 분산 알고리즘 · GPU 알고리즘 · 양자 알고리즘
정렬	정렬 알고리즘 · 퀵 정렬 · 병합 정렬 · 힙 정렬
	비교 정렬	버블 정렬 · 선택 정렬 · 삽입 정렬 · 셸 정렬 · 병합 정렬 · 퀵 정렬 · 힙 정렬
	실용·특수 정렬	팀 정렬 · 인트로 정렬 · 이중 피벗 퀵 정렬 · 트리 정렬 · 비토닉 정렬
	비비교 정렬	계수 정렬 · 기수 정렬 · 버킷 정렬
	대용량 정렬	외부 병합 정렬 · 다중 경로 병합 · 치환 선택 정렬
탐색과 선택	검색 알고리즘 · 이진 탐색 · 빠른 선택 알고리즘
	순차·정렬 데이터	선형 탐색 · 이진 탐색 · 점프 탐색 · 보간 탐색 · 지수 탐색 · 피보나치 탐색
	최적값·순위	삼분 탐색 · 빠른 선택 알고리즘 · 중앙값의 중앙값 알고리즘
	색인·구조	해시 탐색 · 이진 탐색 트리 · B 트리 탐색 · 트라이
자료구조·구간 질의	자료구조 · 구간 질의 · 합집합 찾기 자료구조
	구간 계산	누적 합 · 차분 배열 · 슬라이딩 윈도우 · 투 포인터 · 희소 테이블
	트리 질의·갱신	세그먼트 트리 · 펜윅 트리 · 지연 전파 · 무거운 경로 분할 · 최소 공통 조상
	집합과 해싱	경로 압축 · 합집합 찾기 자료구조 · 로빈 후드 해싱 · 쿠쿠 해싱
그래프 탐색·연결성	그래프 알고리즘 · 너비 우선 탐색 · 깊이 우선 탐색 · 위상 정렬
	기본 그래프 탐색	너비 우선 탐색 · 깊이 우선 탐색 · 양방향 탐색 · 위상 정렬
	연결 요소	타잔 알고리즘 · 코사라주 알고리즘 · 강한 연결 요소 · 단절점과 단절선 탐색
	그래프 순회	히에르홀처 알고리즘 · 오일러 경로 · 해밀턴 경로 문제
최단 경로·최소 신장 트리	최단 경로 문제 · 다익스트라 알고리즘 · 크루스칼 알고리즘
	최단 경로	다익스트라 알고리즘 · 벨만-포드 알고리즘 · 플로이드-워셜 알고리즘 · 존슨 알고리즘 · 0-1 BFS
	휴리스틱 경로 탐색	A* 알고리즘 · IDA* · 양방향 다익스트라 알고리즘
	최소 신장 트리	크루스칼 알고리즘 · 프림 알고리즘 · 보루프카 알고리즘
네트워크 흐름·매칭	최대 유량 문제 · 이분 매칭 · 최소 비용 최대 유량
	최대 유량	포드-풀커슨 알고리즘 · 에드먼즈-카프 알고리즘 · 디닉 알고리즘 · 밀어내기-재명명 알고리즘
	비용과 할당	최소 비용 최대 유량 · 연속 최단 경로 알고리즘 · 헝가리안 알고리즘
	그래프 매칭	홉크로프트-카프 알고리즘 · 에드먼즈 꽃 알고리즘
문자열·구문 분석	문자열 탐색 알고리즘 · KMP 알고리즘 · 접미사 배열
	패턴 매칭	브루트 포스 문자열 탐색 · 크누스-모리스-프랫 알고리즘 · 라빈-카프 알고리즘 · 보이어-무어 알고리즘
	다중 패턴·색인	아호-코라식 알고리즘 · Z 알고리즘 · 접두사 함수 · 접미사 배열 · 접미사 자동자
	문자열 비교	레벤슈타인 거리 · 최장 공통 부분 수열 · 허시버그 알고리즘 · 마나커 알고리즘
	파싱	재귀 하강 파서 · CYK 알고리즘 · 이어리 파서 · 시프팅 야드 알고리즘
동적 계획법	동적 계획법 · 배낭 문제 · 최장 공통 부분 수열
	대표 문제	0-1 배낭 문제 · 동전 교환 문제 · 행렬 연쇄 곱셈 · 편집 거리 · 최장 증가 부분 수열
	상태 구성	비트마스크 동적 계획법 · 트리 동적 계획법 · 구간 동적 계획법 · 자릿수 동적 계획법
	DP 최적화	분할 정복 DP 최적화 · 크누스 최적화 · 컨벡스 헐 트릭 · 단조 큐 최적화
정수·수론·대수	유클리드 호제법 · 에라토스테네스의 체 · 밀러-라빈 소수 판별법
	정수 계산	유클리드 호제법 · 확장 유클리드 알고리즘 · 이진 거듭제곱 · 카라추바 알고리즘
	소수·인수분해	에라토스테네스의 체 · 선형 체 · 밀러-라빈 소수 판별법 · AKS 소수 판별법 · 폴라드 로 알고리즘
	모듈러 연산	모듈러 역원 · 몽고메리 곱셈 · 가너 알고리즘 · 아기 걸음 거인 걸음 알고리즘
	다항식·변환	고속 푸리에 변환 · 수론적 변환 · 다항식 곱셈
수치 해석·선형대수	수치 알고리즘 · 가우스 소거법 · 뉴턴 방법
	근 계산	이분법 · 뉴턴-랩슨 방법 · 할선법 · 브렌트 방법
	적분·미분방정식	사다리꼴 공식 · 심프슨 공식 · 오일러 방법 · 룽게-쿠타 방법
	행렬 계산	가우스 소거법 · LU 분해 · QR 분해 · 켤레 기울기법 · 스트라센 알고리즘
	고유값 계산	거듭제곱 방법 · 야코비 방법 · 특잇값 분해
계산 기하학·공간	계산 기하학 · 볼록 껍질 · 델로네 삼각분할
	볼록 껍질	그레이엄 스캔 · 앤드루의 단조 사슬 알고리즘 · 자비스 행진 · 회전하는 캘리퍼스
	교차·분할	스위프 라인 알고리즘 · 벤틀리-오트만 알고리즘 · 델로네 삼각분할 · 포천 알고리즘
	최근접·충돌	최근접 점 쌍 문제 · 최근접 이웃 탐색 · 길버트-존슨-커어티 알고리즘
	기초 그래픽스	브레즌햄 직선 알고리즘 · 코헨-서덜랜드 알고리즘 · 서덜랜드-호지먼 알고리즘
조합·제약 해결	조합 알고리즘 · 제약 충족 문제 · SAT 솔버
	생성과 열거	순열 생성 알고리즘 · 조합 생성 알고리즘 · 그레이 코드 · 포함 배제 원리
	백트래킹	N-퀸 문제 · 알고리즘 X · 댄싱 링크스 · 분기 한정법
	논리·제약	DPLL 알고리즘 · CDCL · AC-3 알고리즘
수학적 최적화·휴리스틱	최적화 알고리즘 · 선형 계획법 · 경사 하강법
	정확 최적화	심플렉스 알고리즘 · 내부점 방법 · 분기 한정법 · 정수 선형 계획법
	연속 최적화	경사 하강법 · 확률적 경사 하강법 · 뉴턴 방법 · 준뉴턴 방법 · BFGS
	메타휴리스틱	담금질 기법 · 유전 알고리즘 · 개미 군집 최적화 · 입자 군집 최적화 · 타부 탐색
무작위·통계·스트리밍	무작위 알고리즘 · 몬테카를로 방법 · 저수지 샘플링
	무작위 선택·표본	피셔-예이츠 셔플 · 저수지 샘플링 · 무작위 퀵 정렬 · 무작위 퀵 선택
	확률 추정	몬테카를로 방법 · 마르코프 연쇄 몬테카를로 · 메트로폴리스-헤이스팅스 알고리즘
	스트리밍 통계	HyperLogLog · Count-Min Sketch · Misra-Gries 알고리즘
데이터 압축·부호화	압축 알고리즘 · 허프만 부호화 · LZ77
	기초·사전 압축	런 길이 부호화 · LZ77 · LZ78 · LZW · 버로우즈-휠러 변환
	엔트로피 부호화	허프만 부호화 · 산술 부호화 · 범위 부호화 · 비대칭 숫자 체계
	복합 압축	DEFLATE · LZMA · Brotli · Zstandard
암호학·해시·보안	암호 알고리즘 · 암호학적 해시 함수 · RSA
	대칭키 암호	AES · DES · ChaCha20 · Salsa20
	공개키·키 교환	RSA · 디피-헬만 키 교환 · 타원곡선 디피-헬만 · ECDSA · EdDSA
	해시·키 유도	SHA-2 · SHA-3 · BLAKE3 · HMAC · PBKDF2 · Argon2
병렬·분산 시스템	분산 알고리즘 · 병렬 알고리즘 · 합의 알고리즘
	병렬 계산	병렬 접두사 합 · 병렬 병합 정렬 · 비토닉 정렬 · 작업 훔치기
	합의·복제	Paxos · Raft · 실용적 비잔틴 장애 허용 · 가십 프로토콜
	분산 상태·선출	찬디-램포트 알고리즘 · 불리 알고리즘 · 링 선출 알고리즘 · 램포트 논리 시계
데이터베이스·정보 검색	데이터베이스 알고리즘 · 해시 조인 · PageRank
	질의 실행	중첩 루프 조인 · 해시 조인 · 정렬 병합 조인 · 외부 정렬
	검색·순위	역색인 · BM25 · PageRank · TF-IDF
	캐시·색인	LRU · LFU · 일관된 해싱 · 블룸 필터
인공지능·기계학습	기계학습 알고리즘 · 경사 하강법 · 미니맥스 알고리즘
	게임·상태 탐색	미니맥스 알고리즘 · 알파-베타 가지치기 · 몬테카를로 트리 탐색 · A* 알고리즘
	지도·비지도 학습	k-최근접 이웃 알고리즘 · 결정 트리 학습 · k-평균 알고리즘 · DBSCAN
	학습·확률 추론	역전파 알고리즘 · 기댓값 최대화 알고리즘 · 비터비 알고리즘 · 전방-후방 알고리즘
	강화학습	Q-러닝 · SARSA · 가치 반복 · 정책 반복
네트워크·운영체제	라우팅 알고리즘 · 스케줄링 알고리즘 · 페이지 교체 알고리즘
	라우팅·혼잡 제어	거리 벡터 라우팅 · 링크 상태 라우팅 · TCP Reno · TCP CUBIC · BBR 혼잡 제어
	CPU 스케줄링	라운드 로빈 스케줄링 · 최단 작업 우선 스케줄링 · 최단 잔여 시간 우선 스케줄링 · 우선순위 스케줄링
	캐시·페이지 교체	LRU · LFU · Clock 페이지 교체 알고리즘 · 최적 페이지 교체 알고리즘
영상·신호·생물정보	영상 처리 알고리즘 · 서열 정렬 · 신호 처리
	생물정보	니들만-분쉬 알고리즘 · 스미스-워터먼 알고리즘 · BLAST · UPGMA
	영상·특징 검출	소벨 연산자 · 캐니 에지 검출 · 허프 변환 · 해리스 코너 검출 · RANSAC
	신호와 변환	고속 푸리에 변환 · 이산 코사인 변환 · 웨이블릿 변환 · 루카스-카나데 방법
양자 컴퓨팅	양자 알고리즘 · 쇼어 알고리즘 · 그로버 알고리즘
	대표 양자 알고리즘	쇼어 알고리즘 · 그로버 알고리즘 · 양자 푸리에 변환 · 양자 위상 추정 · 양자 진폭 추정
	하이브리드 최적화	변분 양자 고유값 해법 · 양자 근사 최적화 알고리즘

역사

알고리즘 개념의 기원

고대와 중세의 계산 절차

알콰리즈미와 명칭의 유래

근대 수학의 알고리즘

계산 이론의 형성

전자식 컴퓨터와 현대 알고리즘

기본 개념과 성질

계산 문제

입력과 출력

절차와 상태

명확성과 실행 가능성

유한성과 종료

결정성과 비결정성

정확성과 완전성

알고리즘과 휴리스틱

알고리즘과 프로그램

표현 방법

자연어

의사 코드

순서도

수학적 표기

프로그래밍 언어

재귀적 표현과 반복적 표현

계산 모델

계산 모델의 역할

튜링 기계

랜덤 액세스 머신

포인터 기반 계산 모델

회로와 병렬 계산 모델

외부 메모리와 스트리밍 모델

분산 계산 모델

양자 계산 모델

정확성 검증

사전 조건과 사후 조건

부분 정확성과 전체 정확성

반복문 불변식

수학적 귀납법

재귀 알고리즘의 정확성

종료 증명

형식 검증

테스트와 정확성 증명의 관계

효율성과 복잡도 분석

입력 크기와 기본 연산

시간 복잡도

공간 복잡도

최선·평균·최악의 경우

점근 표기법

상환 분석

재귀식과 점화 관계

실험적 성능 측정

이론적 복잡도와 실제 성능

알고리즘 설계 기법

완전 탐색

분할 정복

감소 정복

변환 정복

탐욕 알고리즘

동적 계획법

백트래킹

분기 한정법

무작위 알고리즘

근사 알고리즘

온라인 알고리즘

병렬 알고리즘

분산 알고리즘

자료구조와의 관계

데이터 표현과 알고리즘

추상 자료형

배열과 연결 구조

스택과 큐

트리와 힙

해시 테이블

그래프

자료구조 선택과 성능

주요 알고리즘 분야

정렬

검색

선택과 순위

문자열 처리

그래프 탐색

최단 경로

최소 신장 트리

네트워크 흐름

계산 기하학

수치 알고리즘

행렬과 선형대수

수론 알고리즘

조합 알고리즘

최적화 알고리즘

압축 알고리즘

암호 알고리즘

스케줄링 알고리즘

계산 가능성과 계산 복잡도

결정 문제

계산 가능성

결정 가능 문제와 결정 불가능 문제

문제와 알고리즘의 환원

복잡도 종류

P와 NP

NP-완전성과 NP-난해성

공간 복잡도

매개변수 복잡도

하한과 최적 알고리즘

알고리즘의 분류

결정적 알고리즘과 무작위 알고리즘

정확 알고리즘과 근사 알고리즘

순차 알고리즘과 병렬 알고리즘

중앙 집중형 알고리즘과 분산 알고리즘

온라인 알고리즘과 오프라인 알고리즘

재귀 알고리즘과 반복 알고리즘

정적 알고리즘과 동적 알고리즘

구현과 평가

자료형과 수치 표현

경계 조건과 예외 처리

메모리 계층과 캐시

지역성과 데이터 배치

병렬성과 동기화

입력 데이터의 분포

벤치마크

프로파일링

정확도와 성능의 절충

라이브러리와 기존 구현체

활용 분야

시스템 소프트웨어

데이터베이스

컴퓨터 네트워크

컴퓨터 그래픽스

게임과 시뮬레이션

인공지능과 머신러닝

과학 계산

정보 검색

보안과 암호학

로봇공학과 제어

일상적인 자동화와 의사 결정

장점과 한계