brunch

연재 중 알고리즘과 수학 04화

라이킷 16 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by ZeRO Dec 01. 2024

4. 다양한 함수

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

알고리즘을 공부할 때 함수를 아는 것은 매우 중요합니다. 예를 들어, 알고리즘의 계산횟수로 "다항식 함수", "지수함수", "로그함수"와 같은 것이 나오는 경우가 있습니다. 이번에는 함수가 무엇인지 설명하고, 알고리즘에서 중요한 함수를 정리해보겠습니다.

⑴ 함수란?

함수란, 입력이 정해지면 출력값이 하나로 결정되는 관계를 말합니다. 어떤 숫자를 입력하면 그에 상응하는 숫자가 나오는 기계와 같은 느낌입니다. 예를 들어, 아래 그림처럼 예시1은 입력한 수의 제곱을 반환하는 함수로 3을 입력하면 9, 10을 입력하면 100을 반환합니다.

수학에서는 예제1과 같은 함수를,

라고 씁니다. 기계에 입력되는 숫자를 x로 결과를 y로 표현합니다. 즉, 'x를 입력하면 y가 돌아온다'라는 관계를 나타냅니다. 또한, y 대신 f(x)를 사용하여,

와 같이 쓸수도 있습니다. 이때 x에 구체적인 수치를 넣어서 작성하는 경우도 있으며 예로 f(10) = 100, f(17) = 289가 됩니다. 이 강좌에서는 상황에 따라 구분하여 사용합니다.

⑵ 함수예시: 수조에 들어있는 물의 양

함수는 우리 주변에서 흔히 볼 수 있는 상황에서도 활용됩니다. 예를 들어 부피가 5리터인 비커가 있고 분당 1리터의 비율로 물을 넣는다고 가정해 봅시다. 물을 넣기 시작한 후, 5분이 지나기 전까지는 물이 넘치지 않고 경과시간을 X분이라고 할 때 X리터의 물이 들어 있습니다. 반면에 5분이 지나면 물이 넘쳐서 5리터에서 멈추게 됩니다.

따라서, 물을 넣기 시작한 후 경과시간을 x분, 물의 양을 y리터라고 할 때, 그 관계를 나타내는 함수는 y = min(x, 5)가 됩니다. 아래 표는 경과시간에 따라 물의 양 변화를 보여줍니다. 참고로 min(a, b)는 a와 b중 작은 쪽을 반환하는 함수입니다. 비슷한 함수로 a와 b중 큰것을 반환하는 함수 max(a, b)가 있습니다.

⑶ 함수 그래프를 알기 전에 좌표평면이란?

함수 그래프를 설명하기 전에 우선 전제지식이 되는 좌표평면에 대해 설명하겠습니다. 좌표평면은 점의 위치를 좌표로 표현하는 평면을 말하며 아래와 같은 순서로 만들어집니다.

우선 가로방향으로 몇 개의 직선을 하나 그려서 x축을 삼습니다.

다음으로 세로방향으로 몇 개의 직선을 하나 그려서 y축으로 삼습니다. 이때 x축과 y축은 직각으로 교차합니다.

x축과 y축의 교차점을 원점이라고 합니다.

여기서 원점에서 오른쪽 방향으로 a만큼 이동한 후, 위쪽으로 b만큼 이동한 지점을 좌표(a, b)로 합니다. 예를 들어,

- 좌표(4, 5)는 원점에서 오른쪽 방향으로 4이동 후, 위로 5이동한 지점입니다.

- 좌표(3, -3)은 원점에서 오른쪽 방향으로 3이동 후, 아래로 3이동한 지점입니다.

- 좌표(-5,-1)은 원점에서 왼쪽으로 5이동 후, 아래로 1이동된 지점입니다.

a, b가 음수인 경우, 방향이 반전된다는 점에 주의해야 합니다.

⑷ 함수 그래프

x, y의 관계를 좌표평면 위에 나타내는 것을 함수 그래프라고 합니다. 예를 들어, 앞에서 소개한 비커의 예에서 함수 y = min(x, 5)의 관계를 그래프로 표현하면 아래 그림과 같습니다. 예를 들어, x=3일 때 y=3이므로 이 그래프는 좌표(3, 3)을 통과합니다. 함수를 그래프로 표현하면 x와 y의 관계를 한눈에 알 수 있고, x가 어느 정도의 값일 때 y가 증가하는지등의 특징을 알 수 있습니다.

x, y의 관계를 좌표 평면 위에 나타낸 것을 함수 그래프라고 합니다. 예를 들어 2.3.2절에서 소개한 수조의 예에서 함수 y = min(x, 5)의 관계를 그래프로 표현하면 다음 페이지의 그림과 같습니다. 예를 들어 x = 3일 때 y = 3이므로 이 그래프는 좌표(3, 3)을 통과합니다.　함수를 그래프로 표현하면 x와 y의 관계를 한눈에 알 수 있고, x가 어느 정도 값일 때 y가 증가하는지 등의 특징을 알 수 있습니다.

⑸ 다양한 함수 - ⓐ일차함수

여기부터는 알고리즘과 프로그래밍에서 활용되는 몇가지 함수를 소개합니다. 우선 y = ax+ b형태로 표현되는 아래와 같은 함수를 일차함수라고 합니다.

y = x + 1

y = 3x

y = 314x - 159

아래 그림과 같이 일차함수 그래프는 직선입니다. 또한 x의 값이 1증가하면 반드시 y의 값이 a만큼 증가하는데 이를 '일차함수의 기술기가 a이다'라고 합니다. 예를 들어, 함수 y = 3x의 기술이는 3입니다.

⑹ 다양한 함수 - ⓑ 이차함수

위와 같은 형태로 표현되는 함수를 이차함수라고 합니다.

아래 그림은 이차함수 그래프 예시입니다. 일반저긍로 a의 값이 양수일 때 이차함수는 물건을 던졌을 때의 괘적(포물선)을 거꾸로 뒤집어 놓은 것과 같은 형태입니다. 즉, 어느 정도까지는 y값이 감소하거나 이후 증가세로 전환됩니다. 참고로 a = 0일 때는 1차함수가 된다는 점에 주의해야 합니다.

⑺ 다양한 함수 - ⓒ 다항식과 다항식함수

1차함수에서는 x까지, 2차함수에서는 x제곱까지 나왔지만,

이상으로 범위를 넓힌 다음과 같은 함수를 다항식 함수라고 합니다. 또한 'y ='부분을 뗴버리고 문자식 형태로 표현한 것이 다행식입니다. 특히

등 덧셈기호를 사용하지 않고 사용할 수 있는 다항식을 단항식이라고 합니다.

수식으로 표현하면 음이 아닌 정수 n에 대해 다항식은 다음과 같이 표현합니다.

다음으로 다항식 관련 용어를 정리해보면, 우선 다항식을 구성하는 단항식 하나하나를 "항"이라고 하고,

를 포함한 것을 k차 항이라고 합니다. 특히 O차항을 상수항, 차수가 최대가 되는 항(n차항)을 최고차항이라고 합니다. 또한, 각 항에서 수만 취하는 것을 계수라고 하는데,

과 같이 수가 붙지 않은 항인 경우, 계수는 1입니다.

⑻ 지수함수 - 거듭제곱의 확장

이전에

로 b가 자연수인 경우의 거듭제곱을 설명했는데 아래 공식을 사용하면 b가 음수나 소수인 경우에도 거듭제곱을 계산할 수 있습니다.

① 공식: 비부정수n에 대해,

이해를 돕기 위해 직관적으로 설명합니다.

① 공식에 대한 직관적인 설명

을 계산시, 10을 곱하면 n의 값이 1증가하는 반면, 10으로 나누면 n값이 1감소합니다.

을 10을 나누면 100 = 1이 되고, 이를 다시 10으로 나누면 10-1=0.1이 됩니다. 또한, 100을 10으로 n번 나누면 10-n이 되고, 이 값과 일치합니다.

① 공식의 직관적인 설명

제곱은 곱셈에 관한 연산으로 같은 수를 곱하면 같은 수만큼 지수(제곱의 오른쪽 어꺠의 작은 부분)가 증가합니다. 예를 들어,

가 됩니다.

따라서,

등을 계산할 수 있습니다.

⑼ 다양한 함수 - ⓓ 지수함수

다음으로 지수함수에서는 아래와 같은 4가지 중요한 공식(지수법칙)이 성립합니다. 계산횟수 추정등 알고리즘의 다양한 케이스에서 사용할 수 있어 기억해 둡시다. 특히 1번 공식은 이전에 설명한 "같은 수를 곱하면 같은 수만큼 증가하는 성질"에 해당합니다.

⑽ 다양한 함수 - ⓔ 대수함수

우선 로그

는 지수를 뒤집어 높은 것으로 a를 몇 제곱하면 b가 되는지를 나타냅니다. 예를 들어, 10을 3제곱하면 10X10X10X10 = 1000이 되므로

a를 바닥, b를 진수라고 합니다. 바닥이 1이 아닌 양수이고, 진수가 양수인 경우에만 대수를 계산할 수 있습니다. 바닥으로는 10과 2가 자주 이용됩니다. 바닥이 10인 대수,

의 그래프이며, x값이 증가해도 y의 값이 별로 증가히자 않는 특징이 있습니다.

대수함수는 아래 4가지 중요한 공식이 있는데 이는 다음 강좌에서 소개하는 계산량 주문 분석에도 사용할 수 있어 꼭 기억해 둡시다. 어떤 것인지 잘 모르겠다는 독자는 컴퓨터의 계산기 기능에 다양한 값을 대입해서 계산해봅시다.

⑾ 다양한 함수- ⓕ바닥함수, 천장함수, 가우스기호

바닥함수

는 x 이하에서 가장 큰 정수 y를 반환하는 함수로 예를 들어, ⎣6.5⎦= 6, ⎣10⎦= 10, ⎣-2.1⎦= -3입니다. 바닥함수는 가우스기호 [x]를 사용하여 작성할 수 있습니다. 반면에 천장함수 ⎡x⎤는 x이상에서 가장 작은 정수 y를 반환하는 함수로, ⎡6.5 ⎤= 7, ⎡10 ⎤= 10, ⎡-2.1 ⎤= -2입니다. 바탕함수와 천장함수는 x가 음수일 때 단순 소수점 이하 절삭 및 반울림이 되지 않는 것에 주의합시다.

다음으로 각 함수의 프래프는 아래 그림과 같은 구조로 되어 있습니다. 보라색원은 경계가 포함되고 빈원은 경계가 포함되지 않음을 나타냅니다.