6. 기타 기초적인 수학지식

문제해결을 위한 알고리즘 입문

Dec 21. 2024

지금까지 2진법, 각종 연산, 지수함수, 로그함수등의 함수에 대해 설명했지만, 이번에는 아직 다루지 않은 기본적인 수학지식을 정리하였습니다. 이것들은 나중에 설명을 하는 알고리즘에서 여러번 사용되므로 이해가 되도록 익숙해지시기 바랍니다.

⑴ 소수

1과 자기 자신외에는 나눌 수 없는 2이상의 정수를 소스, 그렇지 않은 2이상의 정수를 합성수라고 합니다. 아래와 그림과 같이 소수는 2, 3, 5, 7, 11, 13, 17, 19, ...로 이어집니다. 어떤 수가 소소인지 아닌지를 빠르게 판단하는 방법은 따로 다룹니다.

⑵ 최대공약수, 최소공배수

2개 이상의 양의 정수에 공통으로 적용되는 약수(공약수) 중 가장 큰 것을 최대공약수라고 합니다. 예를 들어, 6과 9의 최대공약수는 3입니다. 이는 6의 약수가 '1 , 2, 3, 6', 9의 약수가 '1, 3, 9'이고 공통 최대공약수가 3이기 떄문입니다.

한편, 2개 이상의 양의 정수에 공통으로 나타나는 배수(공배수) 중 가장 작은 것을 최소공배수라고 합니다. 예를 들어, 6과 8의 최소공배수는 18입니다. 이는 6의 배수가 '6, 12, 24, 30, ...", 9의 배수가 '9, 12, 18, ..." 9의 배수가 '9, 18, 27, 36, 45, ..."로 이어지며, 공통적으로 가장 작은 수는 18이기 때문입니다.

두 양의 정수 a, b에는 다음과 같은 성질이 성립하므로 최대공약수와 최소공배수 중 하나만 알면 다른 하나는 쉽게 계산할 수 있습니다.

a X b = (a와 b의 최대공약수) X (a와 b의 최소공배수)

참고로 최대공약수는 유클리드의 상호제거법을 통해 효율적으로 계산할 수 있습니다.

⑶ 팩토리얼(Factorial, 계승)

양의 정수 N에 대해 1부터 N까지의 곱 1 X 2 X 3 X ... X N을 N의 제곱이라고 하며, N! 예를 들어,

2! = 1 X 2 = 2

3! = 1 X 2 X 3 = 6

4! = 1 X 2 X 3 X 4 = 24

5! = 1 X 2 X 3 X 4 X 5 = 120

입니다. 또한, 아래 표는 N = 30까지의 계수 값을 나타내며, 매우 빠른 속도로 증가하는 것을 알 수 있습니다. 또한, 팩토리얼은 계산횟수 평가뿐만 아니라, 경우의 수, 계산문제, 상태수 추정에서도 활용됩니다.

⑷ 수열의 기본

수열이란 숫자의 배열을 말합니다. 간단한 예로 아래는 모두 수열입니다.

1, 2, 3, 4, 5, 6, 7, ... (양의 정수를 작은 순서로 정렬)

1, 4, 9, 16, 25, 36, 49, ... (양의 정수의 제곱을 정렬)

3, 1, 4, 1, 5, 9, 2, ... (원주율의 자릿수를 정렬)

일반적으로 수열 A의 앞쪽에서 i번째 요소를 i항이라고 하며, Ai라고 씁니다. 예를 들어, 양의 정수의 제곱을 나열한 수열 A = (1, 4, 9, 16, 25, ...)의 경우 4번째 항 A4의 값은 16입니다.

등차수열과 등비수열

다음으로 특수한 규칙을 가진 수열로는 인접한 두 항의 차이가 일정한 등차수열, 인접한 두 항의 비율이 일정한 등비수열이 유명합니다. 그외에도 예를 들어, 1, 2, 3, 5, 8, 13, ...과 같이 '앞의 두 항을 합한 값은 같고, 뒤의 두 항을 합한 값은 같지 않은 것'과 '앞의 두 항을 더하면 된다'와 같은 규칙을 가지는 경우가 있습니다. 이처럼 앞의 항에 따라 수열의 값이 결정되는 관계식을 점화식이라고 하는데 이에 대해서는 나중에 따로 설명합니다. 점증식의 개념은 동적계획법이라는 유명한 알고리즘과 깊은 관련이 있습니다.

유한수열과 무한수열

수열에 대해 '규칙성이 있고 무한히 계속되는 것'이라는 이미지를 가진 사람도 있지만, A = (9, 9, 8, 2, 4, 4, 3, 5, 3)과 같이 규칙성이 없는 유한한 수열도 수열 중 하나라는 점에 유의해야 합니다. 특히 마지막 항을 가진 수열을 유한 수열이라고 하며, 무한히 항이 계속되는 무한 수열과 구별됩니다. 또한, 항이 N개인 수열을 길이 N의 수열이라고도 합니다.

유한수열은 프로그래밍의 '배열(Array)'과 비슷한 이미지로 단순히 N개의 숫자가 N개씩 늘어선 열이라고 생각하면 됩니다. 참고로 많은 프로그래밍 문제에서 유한수열의 항 형태를 사용하여 문제문장을 작성하는 경우가 있습니다.

⑸ 집합의 기본

집합은 몇 가지 사물의 집합을 말합니다. 예를 들어, 아래 그림의 야구부원들처럼 하나의 그룹을 고학학교 수학에서는 집합이라고 합니다. 또한, 집합에 속한 하나하나의 사물을 요소라고 하는데, 예를 들어, '야구부원'이라는 요소는 A, B, C 3명입니다.

기본적으로 집합은 다음 예시와 같이 요소를 열거하는 형태로 표기합니다. 여기서 집합은 순서가 중요하지 않다는 점에 유의해야 합니다.

야구부 집합을 A라고 할 때, A = { A, B, C }

바둑부 집합을 B라고 할 때, B = { H, I, J }

또한, 다루는 문제에서 생각하는 모든 요소를 전체집합이라고 하며, U로 표기하는 경우가 많습니다. 예를 들어 위 그림에서 1학년 1반 학생 10명이 전체집합 U가 됩니다.

집합의 또다른 예시

좀더 수학적으로 예를 들어봅니다. 예를 들어, 20이하의 소수 집합을 C라고 할 때, C의 요소는 2, 3, 5, 7, 11, 13, 17, 19이므로 C = {2, 3, 5, 7, 11, 13, 17, 19}라고 표기합니다. 참고로 '모든 정수'나 '모든 자연수'등 요소 수가 유한하지 않은 집합(무한집합)도 있지만, 알고리즘의 맥락에서는 요소수가 유한한 집합을 다루는 경우가 많습니다.

집합에 관한 용어

다음 집합과 관련 용어와 기호 중 중요한 것들은 아래와 같습니다.

예를 들어, A = {1, 2, 3, 4}, B = {2, 3, 5, 7, 11}인 경우, 각 집합의 요소수는 |A| = 4, |B| = 5입니다. 또한, 합집합이나 적분집합등에 대해서는 다음과 같습니다.

4 ∈ A (4는 집합A에 포함)

A ∩ B = {2, 3}

A ∪ B = {1, 2, 3, 4, 5, 7, 11}

집합에 대한 지식은 나중에 집합을 잘 다루는 기법에서 다룹니다.

⑹ 필요조건과 충분조건

어떤 조건 X를 만족시키기 위해서는 조건A를 반드시 만족시켜야 할 때, 조건A는 조건X의 필요조건이라고 합니다. 예를 들어, '시험점수가 60점 이상'은 '시험점수가 80점 이상'의 필요조건입니다. 반면, 조건A가 충족하면 조건X를 충족할 때, 조건A는 조건X의 충분조건이라고 합니다.

예를 들어, '시험점수가 80점 이상'은 '시험 점수가 60점 이상'의 충분조건입니다.

좀더 수학적인 예를 들어봅시다. 조건 X를 'N이 3이상의 소수일 것'이라고 할 때,

'N이 홀수일 것'은 조건X의 필요조건입니다.

'N이 5 또는 11일 것'은 조건X의 충분조건입니다.

으로 아래 그림과 같이 범위가 넓은 쪽이 필요조건입니다.

조건X가 조건Y의 필요조건이자 충분조건인 경우 '조건X는 조건Y의 필요충분조건' 또는 '조건X와 조건Y는 같은 값이다'라고 말할 수 있습니다.

필요조건과 충분조건의 개념은 알고리즘의 정당성을 정명하고 싶을때, 문제조건을 바꿔서 고찰을 진행하고 싶을 때등의 상황에서 사용합니다.

⑺ 절대오차와 상대오차

근사치 a와 이론치 b의 오차를 평가하는 방법으로는 다음 2가지가 있습니다.

예를 들어, 근사값이 103, 이론값이 100인 경우, 절대오차는 3, 상대오차는 0.03입니다. 참고로 절대오차가 같더라도 상대오차가 다를 수 있다는 점에 유의해야 합니다. 알고리즘 설계에서 오차개념은 매우 중요합니다. 예를 들어, 몬테카를로법, 부동소수점수등에서 사용합니다.

⑻ 폐쇄구간, 반개방구간, 개방구간

수학이나 알고리즘의 맥락에서 구간을 표현시 아래와 같은 표기법을 사용하기도 합니다.

특히 배열의 인덱스와 같이 값이 정수로 알고 있는 경우, 예를 들어, 반개방구간 [l, r)은 l, l + 1, ..., r - 1을 포함합니다. 아래 그림은 l = 2, r = 6인 경우의 형태를 보여줍니다. 참고로 반개방구간등의 개념은 분할정복법(Divide and Conquer, 병합정렬)에서 사용합니다.

⑼ 시그마 기호

시그마 기호는 합계를 나타내는 기호입니다. 수식으로 쓰면 아래와 같습니다.

구체적인 예를 들어봅시다. 예를 들어,

이며, 이를 시그마기호를 사용하면 표현하면 아래와 같습니다. 오른쪽 식은 좀 복잡하지만, for문에서 i = 1, 2, 3, 4, 5에 대해

의 값을 계산하여 이 합계를 구하는 것으로 생각할 수도 있습니다.

또한, 이중 시그마를 사용하여 쓰기도 합니다. 예를 들어, 아래 식은]

를 만족하는 모든 정수 쌍 (i, j)에 대해 i+j의 값을 계산했을 때의 합을 나타냅니다. (2 + 4 = 6, 2 + 5 = 7, 3 + 4 = 7, 3 + 5 = 8)이며, 이를 모두 더하면 6 + 7 + 7 + 8 = 28이 됩니다.)

이중 시그마의 개념은 어렵지만, 아래 그림처럼 직사각형 영역의 합을 구하는 이미지를 떠올리면 이해하기 쉬울 것입니다. 참고로 시그마 기호는 3배 이상이 될 수도 있습니다. 시그마 기호는 나중에 '더해진 횟수를 생각하는 기법', '대칭성에 주목하는 기법'등에서 사용합니다.

⑽ 이차방정식의 근의 공식(화의 공식)

일부 시그마 계산은 아래와 같이 쉽게 구할 수 있습니다. 예를 들어, 이전에 소개한 '1부터 100까지의 정수를 모두 더하는 문제'는 공식에 대입하면 100 X 101 ÷ 2 = 5050로 계산됩니다. 특히 2번째 공식을 직접 도출하는 것은 어렵기 때문에 여기서는 기억만 해둡시다.