문서 둘러보기
최장 공통 부분 수열
최장 공통 부분 수열은 여러 문자열에서 순서를 유지하며 뽑아낼 수 있는 공통 문자 나열 중 길이가 가장 긴 것이다. 문자들이 원문에서 연속해 있을 필요는 없다.
KMP 알고리즘
KMP 알고리즘은 패턴의 반복 구조를 미리 분석하여 텍스트에서 패턴을 찾는 문자열 검색 알고리즘이다. 비교에 실패해도 이미 일치한 부분의 정보를 활용해 불필요한 재검사를 줄인다.
문자열
문자열은 문자를 순서 있게 나열한 데이터다. 같은 문자들을 포함하더라도 순서가 다르면 다른 문자열이며 길이가 0인 빈 문자열도 다룬다.
문자열 검색
문자열 검색은 텍스트 안에서 주어진 패턴 문자열이 나타나는 위치를 찾는 문제다. 패턴이 연속해서 정확히 일치하는 검색과 오차를 허용하는 검색을 구별한다.
최악의 경우 분석
최악의 경우 분석은 같은 크기의 입력들 중 알고리즘의 자원 사용량이 가장 큰 경우를 기준으로 비용을 평가하는 방법이다. 실행 시간뿐 아니라 메모리나 비교 횟수에도 적용할 수 있다.
평균의 경우 분석
평균의 경우 분석은 입력의 확률 분포를 정하고 그 분포에 대한 알고리즘 비용의 기댓값을 구하는 방법이다. 무엇을 얼마나 자주 입력한다고 가정하는지가 결과의 일부다.
제자리 정렬
제자리 정렬은 원래 원소가 저장된 공간을 재사용하여 정렬하는 방식이다. 전체 원소를 담는 별도의 결과 배열을 두는 방식과 구별하며, 추가 공간의 허용 범위는 사용하는 정의와 구현에 따라 확인해야 한다.
빅오 표기법
빅오 표기법 O(g(n))은 함수의 증가율에 대한 점근적 상한을 나타낸다. 알고리즘 분석에서는 입력이 충분히 커졌을 때 비용이 g(n)의 일정한 상수배를 넘지 않는다는 뜻으로 사용한다.
세타 표기법
세타 표기법 Θ(g(n))은 함수가 충분히 큰 입력에서 g(n)의 양의 상수배 사이에 놓인다는 뜻이다. 점근적 상한과 하한을 함께 주므로 증가율을 같은 차수로 묶는다.
공간 복잡도
공간 복잡도는 입력 크기에 따라 알고리즘이 필요로 하는 메모리 공간이 어떻게 증가하는지 나타내는 척도다. 입력 자체를 포함하는 전체 공간과 계산 중 추가로 쓰는 보조 공간을 구별해야 한다.
시간 복잡도
시간 복잡도는 입력 크기에 따라 알고리즘의 계산 비용이 어떻게 증가하는지 나타내는 척도다. 실제 경과 시간을 초로 한 번 측정한 값과 구별하며 비교 횟수 등 정한 계산 모형의 연산 수로 분석한다.
계수 정렬
계수 정렬은 각 키가 나타나는 횟수를 세고 그 정보를 이용해 원소를 배치하는 정렬 알고리즘이다. 정수 키의 범위가 원소 수에 비해 작을 때 유용하다.
기수 정렬
기수 정렬은 키를 자리나 부분 단위로 나누어 여러 번 배치하는 정렬 알고리즘이다. 낮은 자리부터 처리하는 방식에서는 매 단계 같은 자리값을 가진 원소의 상대 순서를 유지해야 한다.
안정 정렬
안정 정렬은 정렬 키가 같은 원소들의 입력 순서를 결과에서도 유지하는 정렬이다. 정렬 결과의 대소 관계가 맞는지와 같은 키의 상대 순서를 보존하는지는 별개의 성질이다.
버블 정렬
버블 정렬은 이웃한 두 원소를 비교해 순서가 잘못되었으면 교환하는 과정을 반복하는 정렬 알고리즘이다. 오름차순에서는 한 번의 순회로 큰 값이 뒤쪽으로 이동한다.
힙 정렬
힙 정렬은 힙 자료 구조로 최댓값이나 최솟값을 반복해서 선택하여 원소를 정렬하는 비교 기반 알고리즘이다. 배열 안에 최대 힙을 만들고 가장 큰 원소를 뒤쪽부터 확정하는 방식이 대표적이다.
백트래킹
백트래킹은 후보 해를 단계적으로 만들며 선택지를 탐색하고, 조건을 만족할 수 없는 경로에서는 이전 선택으로 돌아가는 탐색 기법이다. 해 하나를 찾거나 가능한 모든 해를 구하는 데 사용할 수 있다.
탐욕 알고리즘
탐욕 알고리즘은 단계마다 그 시점의 기준에서 가장 유리한 선택을 하며 해를 구성하는 방법이다. 그리디 알고리즘이라고도 하며 각 단계의 좋은 선택이 전체 최적해로 이어지는지는 문제별로 증명해야 한다.
메모이제이션
메모이제이션은 함수의 입력과 계산 결과를 저장해 두었다가 같은 입력이 다시 들어오면 저장한 결과를 사용하는 기법이다. 반복되는 부분 문제의 중복 계산을 줄이는 데 쓰인다.
분할 정복
분할 정복은 문제를 더 작은 부분 문제로 나누어 각각 해결한 뒤 그 결과를 결합하는 알고리즘 설계 방식이다. 부분 문제에도 같은 구조를 적용하는 재귀적 형태가 흔하다.
이진 거듭제곱
이진 거듭제곱은 지수의 이진 표현을 이용해 제곱을 반복하고 필요한 값만 곱하여 거듭제곱을 계산하는 방법이다. 지수가 커져도 곱셈 횟수를 지수의 자릿수에 비례하도록 줄일 수 있다.
메르센 소수
메르센 소수는 2ⁿ−1의 꼴로 나타나는 소수다. 지수 n이 소수여야 하지만 지수가 소수라는 사실만으로 2ⁿ−1도 소수라고 결론낼 수는 없다.
친화수
친화수는 서로 다른 두 양의 정수에서 각 수의 양의 진약수 합이 상대 수가 되는 쌍이다. 우애수라고도 하며 220과 284가 대표적인 예다.
부족수
부족수는 자기 자신을 제외한 양의 약수들의 합이 원래 수보다 작은 양의 정수다. 전체 양의 약수의 합을 쓰면 σ(n)<2n이다.
풍부수
풍부수는 자기 자신을 제외한 양의 약수들의 합이 원래 수보다 큰 양의 정수다. 전체 양의 약수의 합으로는 σ(n)>2n이라는 조건으로 나타낸다.
완전수
완전수는 자기 자신을 제외한 양의 약수들의 합이 원래 수와 같은 양의 정수다. 모든 양의 약수의 합을 σ(n)이라 쓰면 σ(n)=2n으로 나타낸다.
에라토스테네스의 체
에라토스테네스의 체는 정해진 범위의 소수들을 한꺼번에 찾는 알고리즘이다. 작은 소수의 배수들을 차례로 제외하여 남은 수를 소수로 판별한다.
윌슨의 정리
윌슨의 정리는 1보다 큰 정수 n이 소수일 필요충분조건이 (n−1)!≡−1 (mod n)이라는 정리다. 계승에 1을 더한 값이 n의 배수인지로 표현할 수도 있다.
오일러 정리 (정수론)
정수론의 오일러 정리는 m>1인 정수 m과 서로소인 정수 a에 대해 a^φ(m)≡1 (mod m)이 성립한다는 정리다. φ는 오일러 피 함수다.
오일러 피 함수
오일러 피 함수 φ(n)은 양의 정수 n에 대해 1부터 n까지의 정수 중 n과 서로소인 수의 개수를 나타낸다. 토션트 함수라고도 부른다.
페르마의 소정리
페르마의 소정리는 소수 p와 정수 a에 대해 aᵖ≡a (mod p)가 성립한다는 정리다. a가 p의 배수가 아니면 aᵖ⁻¹≡1 (mod p)로도 나타낼 수 있다.
중국인의 나머지 정리
중국인의 나머지 정리는 법들이 쌍마다 서로소일 때 여러 나머지 조건을 동시에 만족하는 정수가 존재하며, 그 법들의 곱을 법으로 하여 유일하다는 정리다.
확장 유클리드 알고리즘
확장 유클리드 알고리즘은 두 정수의 최대공약수와 함께 그 최대공약수를 원래 두 수의 정수 계수 합으로 나타내는 계수를 구하는 방법이다.
베주 항등식
베주 항등식은 동시에 0이 아닌 두 정수 a와 b의 최대공약수를 ax+by의 꼴로 나타낼 수 있다는 정리다. 이때 계수 x와 y도 정수로 택할 수 있다.
모듈러 역원
법 m에서 정수 a의 모듈러 역원은 ax≡1 (mod m)을 만족하는 정수 x다. m>1일 때 역원이 존재하는 필요충분조건은 a와 m이 서로소인 것이다.
합동식
정수의 합동식은 두 정수를 같은 양의 정수로 나누었을 때 나머지가 같다는 관계를 나타낸다. a≡b (mod m)은 a−b가 m의 배수라는 뜻이다.
계차수열
계차수열은 원래 수열에서 이웃한 두 항의 차를 순서대로 모아 만든 수열이다. aₙ에 대해 보통 bₙ=aₙ₊₁−aₙ으로 정의하며 항의 변화량을 살피는 데 쓴다.
상수수열
상수수열은 모든 항이 같은 값을 갖는 수열이다. aₙ=c로 나타내며 실수 상수수열의 극한은 그 일정한 값 c다.
망원급수
망원급수는 부분합을 전개했을 때 중간 항들이 상쇄되어 처음과 끝의 일부 항만 남는 형태의 급수다. 무한히 많은 항을 바로 지우기보다 유한한 부분합을 먼저 정리하고 극한을 구한다.
절대수렴
급수의 각 항에 절댓값을 씌운 급수가 수렴할 때 원래 급수가 절대수렴한다고 한다. 실수나 복소수 급수의 절대수렴은 원래 급수의 수렴을 보장한다.
교대급수
교대급수는 양의 항과 음의 항이 번갈아 나타나는 급수다. 부호가 번갈아 바뀐다는 조건만으로 수렴이 보장되는 것은 아니며 항의 크기가 어떻게 변하는지도 살펴야 한다.
단조수열
단조수열은 항의 번호가 커질 때 값이 한 방향으로만 변하는 수열이다. 감소하지 않는 수열과 증가하지 않는 수열을 포함하며 엄격한 단조성과는 등호 허용 여부를 구별한다.
부분수열
부분수열은 원래 수열에서 일부 항을 순서를 유지하며 골라 만든 수열이다. 선택한 항의 번호가 엄격하게 증가해야 하므로 같은 항을 반복 선택하거나 순서를 뒤바꾸는 것은 허용하지 않는다.
일반항
수열의 일반항은 항의 번호 n을 이용해 n번째 항 aₙ을 나타내는 식이다. 특정한 몇 항을 나열하는 대신 각 번호의 값을 결정하는 규칙을 표현한다.
점화식
점화식은 수열의 항을 앞선 항들과 연결하여 나타내는 식이다. 필요한 초기값과 함께 주어지면 뒤의 항들을 차례로 계산할 수 있다.
발산 (수학)
실수 수열이 발산한다는 것은 유한한 실수 극한값으로 수렴하지 않는다는 뜻이다. 항이 한없이 커지는 경우뿐 아니라 서로 다른 값 사이에서 반복되어 극한이 없는 경우도 포함한다.
수렴 (수학)
실수 수열이 수렴한다는 것은 항의 번호가 커질수록 어떤 실수에 원하는 만큼 가까워지고 그 가까운 상태를 계속 유지한다는 뜻이다. 그 실수를 수열의 극한값이라 한다.
원판
원판은 평면에서 중심으로부터 일정한 반지름 이내에 있는 점들로 이루어진 영역이다. 중심에서 거리가 반지름과 같은 점들만 모은 원의 둘레와 구별한다.
접점
접점은 곡선과 접선 또는 곡면과 접평면이 접하는 위치를 나타내는 점이다. 원에서는 접선이 원과 만나는 한 점을 뜻하며 중심에서 접점으로 그은 반지름은 접선에 수직이다.
겉넓이
겉넓이는 입체를 둘러싼 표면의 넓이다. 표면적이라고도 하며 내부 공간의 크기를 나타내는 부피와 구별한다.
단면 (기하학)
단면은 입체를 평면으로 잘랐을 때 나타나는 도형이다. 절단하는 평면의 위치와 방향에 따라 같은 입체에서도 서로 다른 단면이 생길 수 있다.
전개도
전개도는 입체의 표면을 잘라 평면 위에 펼쳐 나타낸 도형이다. 면의 모양뿐 아니라 서로 붙는 위치를 보여 주며 접었을 때 원래 입체가 되는지를 함께 살펴야 한다.
볼록집합
볼록집합은 집합 안의 임의의 두 점을 잇는 선분 전체가 다시 그 집합 안에 들어가는 집합이다. 평면의 채워진 원판이나 직사각형 영역이 대표적인 예다.
정다면체
정다면체는 합동인 정다각형 면으로 이루어지고 각 꼭짓점에 같은 수의 면이 모이는 규칙적인 다면체다. 볼록한 경우에는 정사면체, 정육면체, 정팔면체, 정십이면체, 정이십면체의 다섯 종류가 있다.
정이십면체
정이십면체는 합동인 정삼각형 스무 개로 둘러싸인 볼록한 입체다. 꼭짓점은 열두 개이며 각 꼭짓점에는 다섯 면이 모인다.
정십이면체
정십이면체는 합동인 정오각형 열두 개로 둘러싸인 볼록한 입체다. 꼭짓점은 스무 개이며 각 꼭짓점에는 세 면이 모인다.
정팔면체
정팔면체는 합동인 정삼각형 여덟 개로 둘러싸인 볼록한 입체다. 꼭짓점은 여섯 개이고 각 꼭짓점에는 네 면이 모인다.
다면체
다면체는 다각형인 평면 조각들로 둘러싸인 입체 또는 그 경계 구조를 가리킨다. 면과 모서리, 꼭짓점의 연결을 통해 형태를 살펴보며 곡면으로 둘러싸인 구와 구별한다.
정사면체
정사면체는 합동인 정삼각형 네 개로 둘러싸인 입체다. 모서리는 모두 같은 길이이고 각 꼭짓점에는 세 면이 모인다.
구면
구면은 공간에서 한 점으로부터 거리가 일정한 점들을 모두 모은 곡면이다. 기준점은 중심, 일정한 거리는 반지름이며 내부를 채운 입체와 표면을 구별해 다룬다.
원점
원점은 좌표를 측정하는 기준점이다. 평면의 직교 좌표계에서는 좌표가 (0,0)인 점이며 공간의 직교 좌표계에서는 (0,0,0)으로 나타낸다.
좌표축
좌표축은 좌표계에서 위치를 나타내는 기준으로 사용하는 축이다. 평면의 직교 좌표계에서는 서로 수직인 x축과 y축을 사용하며 두 축의 교점을 원점으로 정한다.
사분면
사분면은 평면의 직교 좌표축이 나누는 네 영역이다. 좌표축 자체는 어느 사분면에도 포함하지 않으며 각 영역에서 두 좌표의 부호가 정해진다.
복소평면
복소평면은 복소수 a+bi를 평면의 점 (a,b)에 대응시켜 나타내는 방법이다. 가로 방향은 실수부, 세로 방향은 허수부에 해당하며 복소수의 연산을 도형의 변화로 해석할 수 있다.
켤레복소수
복소수 a+bi의 켤레복소수는 a−bi다. 실수부는 그대로 두고 허수부의 부호를 바꾸며 복소평면에서는 실수축에 대한 반사로 해석한다.
허수 단위
허수 단위 i는 i²=−1을 만족하도록 정한 복소수다. 복소수는 실수 a와 b를 이용해 a+bi의 형태로 나타내며 이때 i가 실수 범위 밖의 방향을 표현한다.
무리방정식
무리방정식은 미지수가 근호 안에 들어 있는 식을 포함하는 방정식이다. 실수 범위의 제곱근을 다룰 때에는 근호 안의 조건과 제곱으로 생기는 추가 후보를 함께 검토한다.
유리방정식
유리방정식은 유리식으로 이루어진 방정식이다. 다항식만으로 이루어진 경우와 구별하여, 미지수가 분모에 들어가는 방정식을 가리키는 뜻으로도 사용한다.
이차부등식
이차부등식은 미지수에 관한 이차식의 값이 0보다 크거나 작은 범위를 구하는 부등식이다. 실수 범위에서는 이차함수의 그래프와 영점, 최고차항 계수의 부호를 이용해 해석할 수 있다.
연립부등식
연립부등식은 여러 부등식을 동시에 만족하는 값을 구하는 문제다. 각 부등식의 해집합을 먼저 구한 뒤 공통으로 들어가는 부분을 찾는다.
일차부등식
일차부등식은 미지수에 관한 일차식으로 정리되는 부등식이다. 실수 한 개를 미지수로 하는 경우에는 계수의 부호에 따라 부등호를 처리하여 해의 범위를 구한다.
동치변형
동치변형은 방정식이나 부등식의 해집합을 유지하면서 식을 다른 형태로 바꾸는 과정이다. 단순히 모양을 바꾸는 것과 모든 해가 정확히 보존되는 것은 구별해야 한다.
해집합
해집합은 방정식이나 부등식 등 주어진 조건을 만족하는 모든 값을 모은 집합이다. 해를 논할 때에는 값을 찾는 범위와 식이 정의되는 조건을 함께 정해야 한다.
영점 (수학)
함수의 영점은 함수값이 0이 되는 정의역의 원소다. 함수 f의 영점을 구한다는 것은 주어진 정의역에서 방정식 f(x)=0의 해를 찾는 일이다.
고정점 (수학)
함수의 고정점은 함수를 적용해도 값이 바뀌지 않는 정의역의 원소다. 함수 f에서 x가 고정점이라는 조건은 f(x)=x로 나타낸다.
오선
오선은 악보에서 음의 위치를 표시하는 다섯 개의 평행한 가로줄이다. 줄 위와 줄 사이의 칸에 음표를 놓으며 음자리표를 기준으로 각 위치의 음을 읽는다.
음자리표
음자리표는 악보에서 오선의 특정 위치가 어떤 음을 가리키는지 정하는 기호다. 같은 줄에 놓인 음표라도 음자리표가 달라지면 읽는 음이 달라질 수 있다.
탐탐 (악기)
탐탐은 매달린 큰 금속 원반을 두드려 넓게 퍼지는 울림을 내는 타악기이다. 오케스트라에서는 보통 특정한 하나의 음높이보다 복합적인 금속성 음색을 활용한다.
탬버린
탬버린은 얕은 테두리에 작은 금속판들을 달아 두드리거나 흔들어 연주하는 타악기이다. 막을 갖춘 전형적인 형태에서는 북의 타격음과 금속판의 울림이 함께 난다.
튜블러 벨
튜블러 벨은 여러 길이의 금속관을 매달고 두드려 정해진 음높이를 내는 타악기이다. 오케스트라에서 종소리를 표현하며 차임 또는 관종이라고도 부른다.
스네어 드럼
스네어 드럼은 막을 두드릴 때 아래쪽 막에 닿은 줄 등이 함께 진동하여 특유의 날카로운 울림을 내는 북이다. 작은북이라고도 하며 오케스트라와 드럼 세트, 행진 악대 등에서 사용한다.
심벌즈
심벌즈는 원반 모양의 금속 몸체를 부딪치거나 두드려 소리를 내는 타악기이다. 한 쌍을 맞부딪치는 형태와 매달거나 스탠드에 놓고 치는 형태 등이 있다.
큰북
큰북은 큰 몸통과 막을 사용해 낮고 넓은 울림을 내는 북이다. 베이스 드럼이라고도 하며 오케스트라의 큰북과 드럼 세트의 발 페달 북 등은 연주 방식과 쓰임을 구별한다.
글로켄슈필
글로켄슈필은 음높이에 따라 배치한 금속 음판을 두드리는 유율 타악기이다. 오케스트라에서는 높고 선명한 소리로 쓰이며 일반적으로 말렛으로 직접 음판을 친다.
비브라폰
비브라폰은 금속 음판을 말렛으로 두드리는 유율 타악기이다. 공명관과 울림을 조절하는 댐퍼 페달을 갖추며 회전 장치로 특유의 맥동하는 효과를 만들 수 있다.
첼레스타
첼레스타는 건반을 누르면 내부 해머가 금속 음판을 쳐 소리를 내는 악기이다. 피아노와 비슷한 건반을 갖지만 줄이 아닌 금속 음판의 진동을 이용한다.
마림바
마림바는 음높이별로 배치한 나무 음판을 말렛으로 두드리는 유율 타악기이다. 음판 아래의 공명관이 소리의 울림에 관여하며 독주와 합주에서 사용한다.
실로폰
실로폰은 음높이에 따라 배열한 나무 음판을 말렛으로 두드리는 유율 타악기이다. 현대 오케스트라에서는 선명한 발음의 높은 음역을 담당하는 경우가 많다.
팀파니
팀파니는 그릇 모양의 몸통 위에 팽팽하게 건 막을 두드리는 유율 타악기이다. 막의 장력을 바꾸어 음높이를 조절하며 오케스트라에서 여러 대를 함께 사용하는 경우가 많다.
잉글리시 호른
잉글리시 호른은 오보에 계열의 겹리드 목관악기이다. 코르 앙글레라고도 하며 일반적으로 F조 악기로서 기보된 음보다 완전5도 낮게 울린다.
하프
하프는 프레임에 걸린 여러 줄을 손가락으로 뜯어 소리를 내는 현악기이다. 현대 콘서트 페달 하프는 페달로 같은 음 이름을 가진 줄들의 높이를 바꾸어 조성을 조절한다.
피콜로
피콜로는 플루트 계열의 작은 고음 목관악기이다. 리드 없이 취구 가장자리에 공기를 불어 소리를 내며 일반적인 C 피콜로는 악보보다 한 옥타브 높게 울린다.
튜바
튜바는 입술의 진동과 긴 관의 공명을 이용하는 저음 금관악기이다. 밸브로 관의 길이를 바꾸며 오케스트라와 관악 합주에서 낮은 성부를 맡는 대표 악기다.
호른
호른은 길게 감긴 관과 넓게 벌어진 벨을 갖춘 금관악기이다. 입술을 진동시켜 소리를 내며 현대 오케스트라에서는 밸브를 갖춘 악기가 널리 사용된다.
트롬본
트롬본은 입술의 진동으로 소리를 내는 금관악기이며 대표적인 형태는 슬라이드를 움직여 관의 길이를 바꾼다. 테너 트롬본과 베이스 트롬본 등 여러 음역의 악기가 있다.
트럼펫
트럼펫은 마우스피스에 댄 입술을 진동시켜 소리를 내는 금관악기이다. 현대 악기에서는 밸브로 공기가 지나는 관의 길이를 바꾸며 오케스트라와 관악 합주, 재즈 등에서 사용한다.
바순
바순은 접힌 긴 관과 겹리드를 사용하는 저음 목관악기이다. 파곳이라고도 하며 오케스트라와 실내악에서 낮은 성부와 선율을 모두 맡는다.
클라리넷
클라리넷은 마우스피스에 고정한 한 장의 리드를 진동시켜 소리를 내는 목관악기이다. 여러 크기와 조율의 악기가 있으며 B♭ 클라리넷과 A 클라리넷 등이 널리 사용된다.
오보에
오보에는 두 장의 리드가 맞닿아 진동하는 겹리드 목관악기이다. 현대 오케스트라의 주요 목관악기 중 하나로 관과 음공, 키 장치를 통해 음높이를 조절한다.
플루트
플루트는 공기의 흐름을 취구 가장자리에 부딪혀 관 안의 공기를 진동시키는 관악기이다. 오케스트라의 현대 콘서트 플루트는 보통 가로로 들고 연주하며 리드를 사용하지 않는다.