수열은 정수 인덱스를 입력으로 받는 함수이고, 행렬은 수를 행과 열에 맞춰 배열한 구조다. 바닥·천장 함수로 정수 단위의 자원을 계산하고, 점화식으로 반복되는 변화를 표현하고, 행렬로 여러 관계와 방정식을 한꺼번에 다룰 수 있다. 정의를 실제 계산에 적용하면서 각 구조의 성질을 살펴보자.
연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.
1. 함수의 성질을 판단하는 연습
단사는 같은 출력에서 같은 입력이 따라오는지, 전사는 공역의 모든 값에 원상이 있는지 확인한다. 정의역과 공역을 함께 보아야 한다.
| 함수 | 단사 | 전사 | 이유 |
|---|---|---|---|
| , | O | O | 이면 이고 의 원상은 |
| , | X | X | , 0의 원상이 없음 |
| , | X | O | , 각 정수 에 를 선택 |
| , | O | O | 의 원상 이 유일 |
| , | X | X | , 7보다 큰 값은 출력되지 않음 |
실수에서 , 이면 다. 정수에서 의 역함수는 다. 역함수는 출력을 다시 입력으로 되돌리는 함수이며 와는 다르다.
2. 바닥함수와 천장함수
바닥함수 는 이하의 최대 정수, 천장함수 은 이상의 최소 정수다.
| 3 | 4 | |
| -2 | -1 | |
| -1 | 0 | |
| -3 | -2 | |
| 7 | 7 |
음수에서는 소수 부분을 지우는 것과 바닥함수가 다르다. 정의를 부등식으로 쓰면 정수 에 대해
따라서
마지막 식은 이동량이 정수일 때의 성질이다. 임의의 실수끼리 더할 때는 성립하지 않는다. 이면 이지만 다.
필요한 자원은 올림, 담을 수 있는 개수는 내림
비트를 8비트 단위로 저장하려면 바이트가 필요하다.
| 비트 수 | 필요한 바이트 |
|---|---|
| 4 | 1 |
| 10 | 2 |
| 100 | 13 |
| 500 | 63 |
| 3000 | 375 |
500바이트를 셀당 48바이트의 데이터 영역에 넣는다면 셀이 필요하다. 반대로 셀 전체 길이가 53바이트이고 초당 500,000비트를 전송한다면, 1분에 완전히 전송 가능한 셀 수는
개다. 앞의 문제는 필요한 공간을 확보하고, 뒤의 문제는 제한된 공간 안의 완전한 단위를 세므로 반올림 방향이 다르다.
바닥함수 항등식의 증명
모든 실수 에 대해
로 쓰되 , 로 둔다. 이면 왼쪽은 이고 오른쪽은 이다. 이면 왼쪽은 이고 오른쪽은 이다. 모든 실수가 두 경우 중 하나에 속하므로 증명이 끝난다.
3. 계승, 부분함수, 무한집합
계승은 , 로 정의한다. , 이다. 점화식으로는 이다. 큰 에서 스털링 근사
를 사용할 수 있다. 은 두 값의 차가 0이 된다는 뜻이 아니라 비율 이 1에 수렴한다는 뜻이다.
부분함수는 지정한 입력 집합의 일부에서만 값이 정의된다. 정수에서 실수로 값을 생각할 때 은 에서만 정의되고, 은 에서만 정의된다. 입력 집합 전체에서 정의되면 전함수다. 정의역을 처음부터 로 잡은 은 그 정의역에서는 전함수다.
무한집합의 크기도 대응으로 비교한다. 에서 로 전단사가 있으면 , 단사가 있으면 로 정의한다. 유한집합이거나 양의 정수와 전단사인 집합을 가산집합이라고 한다.
양의 홀수는 로 양의 정수와 전단사이고, 정수는 로 나열된다. 양의 유리수도 분자와 분모의 합이 작은 순서로 훑으면서 이미 나온 값을 건너뛰면 나열할 수 있다. 반면 실수는 비가산이다. 소수 전개를 목록으로 만들었다고 가정하고 번째 수의 번째 자릿수와 다른 숫자를 골라 새 실수를 만들면, 그 수는 목록의 모든 수와 적어도 한 자리에서 다르다. 자릿수를 1과 2 중에서 고르면 유한소수와 9가 반복되는 표현의 중복도 피할 수 있다.
4. 수열과 점화식
수열 은 정수의 부분집합에서 어떤 집합으로 가는 함수다. 순서와 중복을 유지하므로 일반 집합과 다르다. 은 부터 시작하고, 은 부터 시작할 수도 있다. 시작 인덱스를 먼저 확인해야 한다.
일 때 등차수열은 , 등비수열은 이다.
| 일반항 | 처음 다섯 항 |
|---|---|
문자열은 유한한 알파벳에서 고른 문자들의 유한 수열이다. abcde는 길이 5이고, 빈 문자열 는 길이 0이다.
점화식은 앞선 항들로 다음 항을 정한다. , 이면 이고, , 이면 이다. 이전 두 항을 사용하는 점화식에는 보통 그에 맞는 두 초기조건이 필요하다.
피보나치 수열은
로 정한다. 처음 항들은 이다.
제안된 식이 해인지 확인하기
에서 을 대입하면 이므로 해다. 상수수열 도 여서 해다. 하지만 은 에서 이므로 해가 아니다. 점화식만 만족하는 것과 특정 초기조건까지 만족하는 것은 따로 확인한다.
반복 대입으로 일반항 구하기
, 이면 뒤로 대입할 때마다 3이 하나씩 더해져
초기항이 인 문제라면 이다. 인덱스 하나 차이로 상수항이 달라진다. 같은 방식으로 , 의 해는 이고, , 의 해는 이다.
, 이면
, 이면
각 식을 다시 점화식과 초기조건에 대입하면 결과를 확인할 수 있다.
고정 비율의 증가도 등비수열이다. 초기값이 10,000이고 매 단계 11%씩 늘어난다는 수학적 모형이면 , 이므로 이다. 초기값 5,000, 증가율 8%라면 이다.
처음 몇 항으로 규칙 추측하기
에서는 , 에서는 을 추측할 수 있다(부터). 는 (부터), 는 (부터)에 맞는다. 는 앞의 두 항의 합이라는 규칙에 맞는다. 는 양의 정수 를 번씩 반복한 수열이다.
알려진 정수 수열을 찾는 데 OEIS 같은 수열 데이터베이스를 사용할 수도 있다. 다만 유한하게 주어진 항들은 여러 규칙과 동시에 맞을 수 있다. 패턴을 발견하는 것은 추측이고, 일반항을 확정하려면 정의나 추가 조건, 증명이 필요하다.
5. 합과 곱의 표기
아래와 위의 숫자는 합의 범위를 정하고, 는 합 안에서만 쓰는 인덱스다. 이며, 인덱스를 로 옮기면 가 된다. 이고 다.
등비급수와 망원합
이라고 하자. 에서 를 빼면 중간 항들이 사라져
따라서
인 경우에는 0으로 나누지 말고 항의 개수로 계산한다. 망원합도 같은 소거 원리다.
을 합하면 이다. 따라서 이고
또 을 합하면
즉 이다.
| 합 | 공식 |
|---|---|
| , | |
| , |
무한등비급수는 유한합 공식에서 인 조건 을 사용한다. 마지막 공식은 수렴 구간 안에서 등비급수를 항별 미분해 얻는다.
구간 합과 이중합의 계산
시작점이 1이 아니면 앞부분을 빼면 된다.
같은 방식으로 이고,
지수의 합은
이중합은 안쪽부터 계산한다.
범위가 , 인 경우에도 이지만, 합치는 항들은 다르다. 집합 위의 합 는 그 원소를 한 번씩 더해 6이다.
6. 행렬의 크기와 연산
개의 행과 개의 열을 가진 배열을 행렬이라고 한다. 에서 첫 인덱스는 행, 둘째는 열이다. 같은 행렬이려면 크기와 모든 성분이 같아야 한다. 3×2 행렬과 2×3 행렬은 성분의 수가 같아도 다른 크기다.
덧셈
같은 크기끼리 대응 성분을 더한다.
곱셈
가 , 가 이면 는 이고
왼쪽 행렬의 한 행과 오른쪽 행렬의 한 열을 곱해 더한다. 안쪽 크기가 맞지 않으면 곱을 정의할 수 없다. 2×3 행렬 와 4×2 행렬 에서는 는 정의되지 않지만 는 4×3이다.
이면
첫 성분은 이고, 둘째 행·둘째 열 성분은 다.
연습으로
를 곱하면
예를 들어 이다.
순서를 바꾸면 달라진다
이면
따라서 행렬곱은 교환되지 않는다. , 에서도 , 로 다르다.
7. 항등행렬, 전치, 역행렬
항등행렬 은 주대각선 성분이 1이고 나머지가 0이다. 가 이면
정사각행렬의 거듭제곱은 , 로 정의한다. 전치행렬 는 행과 열을 바꾼 것으로 다.
인 정사각행렬을 대칭행렬이라고 한다. 와 모든 항등행렬은 대칭이다.
2×2 역행렬
이면 를 의 역행렬 이라고 한다. 행렬 에서 이면
실제로
이고, 반대 순서의 곱도 같은 행렬이다. 로 나누면 양쪽 모두 가 된다.
연립방정식 풀기
각 방정식이 이면 계수행렬 , 미지수 열벡터 , 상수 열벡터 를 사용해 로 쓴다. 가 가역이면 왼쪽에 을 곱해 를 얻는다.
일 때
의 해는
이를 대입하면 좌변은 차례로 , , 으로 확인된다.
8. 0–1 행렬과 불 연산
성분이 0 또는 1인 행렬은 관계나 연결 여부를 나타내는 데 쓰인다. 같은 크기의 두 행렬에 대해 조인(join)은 성분별 OR, 미트(meet)는 성분별 AND다.
이면
불 곱 는 일반 행렬곱의 곱셈을 AND로, 덧셈을 OR로 바꾼다.
즉 중간 인덱스 중 하나라도 두 성분이 모두 1이면 출력이 1이다.
예를 들어 성분은 이다. 일반 행렬곱은 해당 연결 방법의 수를 셀 수 있지만, 불 곱은 그런 방법이 존재하는지만 남긴다.
불 거듭제곱
, 로 정의한다. 일반 곱의 거듭제곱과 구별하기 위해 지수에 대괄호를 붙인다.
이면 반복 계산하여
이 의 각 열에는 적어도 하나의 1이 있으므로, 모든 성분이 1인 행렬 에 대해 다. 따라서 에서 가 유지된다. 단순히 어떤 단계에서 전부 1이 되었다는 사실뿐 아니라, 다음 곱에서도 유지되는 이유까지 확인해야 한다.
9. 연습문제
문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.
01. 단사와 전사 판정
다음 세 함수는 다. 단사·전사를 각각 판정하고 증명하거나 반례를 들자.
- .
- .
- .
다음 두 함수가 전단사인지도 판정하자.
- .
- .
해설 보기
- 단사·전사다. 이면 . 임의의 정수 의 원상은 이다.
- 둘 다 아니다. 이고 0은 출력되지 않는다.
- 단사는 아니다. 이다. 전사는 맞다. 각 정수 에 를 넣으면 다.
- 전단사다. 이면 . 모든 실수 의 원상 이 존재한다.
- 전단사가 아니다. 라 단사가 아니고, 치역이 이어서 8 등의 원상이 없다.
02. 바닥·천장함수와 필요한 바이트
- 바닥·천장함수를 정의하고 를 계산하자.
- 모든 실수에서 인가?
- 비트를 저장할 최소 바이트 수를 쓰고 에서 계산하자. 1바이트는 8비트다.
해설 보기
- 는 이하의 최대 정수, 은 이상의 최소 정수다. 따라서 -3, -2다.
- 거짓이다. 이면 왼쪽은 , 오른쪽은 다.
- 바이트 수 는 정수이고 이어야 한다. 따라서 최소값은 이다.
| 최소 바이트 | ||
|---|---|---|
| 4 | 0.5 | 1 |
| 10 | 1.25 | 2 |
| 500 | 62.5 | 63 |
| 3000 | 375 | 375 |
나머지 비트가 하나라도 있으면 바이트를 하나 더 확보해야 한다.
03. 계승과 부분함수
- 를 계산하자.
- 정수 입력에 을 대응시키면 전함수인가? 실제 정의되는 입력 집합을 쓰자.
해설 보기
- 이다.
- 에서 정의되지 않으므로 정수 전체에 대한 전함수가 아니다. 정수에서 실수로의 부분함수로 볼 수 있고 실제 정의되는 입력은 다. 처음부터 이 집합을 정의역으로 정하면 그 정의역에 대해서는 전함수다.
04. 반복 대입으로 점화식 풀기
에서 다음 점화식의 닫힌 공식을 반복 대입으로 구하자.
- .
- .
- .
- .
- 초기금액 5,000달러가 매년 8%씩 복리로 증가한다고 할 때 잔액 의 점화식과 초기조건을 세우자.
해설 보기
- 이므로 반복 대입하면 이다.
- 이다.
- 다.
- 상수항이 추가될 때마다 앞 단계에 3이 곱해진다.
이면 1이고, 이를 점화식에 대입해도 같은 일반항이 나온다. 5. , 이다. 따라서 이다. 고정 증가율을 가정한 수열 모형이다.
05. 구간 합·등비합·이중합
다음을 계산하자.
- .
- .
- .
- .
- .
- .
해설 보기
- 안쪽 합이 이므로 .
- 1부터 20까지에서 1부터 10까지를 빼면 .
- 첫 항 2, 공비 2, 8항인 등비합이므로 .
- 첫 항 2, 공비 -3, 9항이므로
- 안쪽 합은 이므로 . 1번과 값은 같아도 합치는 순서와 범위가 다르다.
- 100도 포함되므로 1부터 99까지를 뺀다.
항이 101개이고 양 끝의 평균이 150이어서 으로도 확인된다.
06. 망원합으로 합 공식 유도하기
- 를 보이자.
- 을 이용해 를 구하자.
- 을 이용해 를 구하자.
해설 보기
- 에서 중간 항이 모두 상쇄되어 만 남는다.
- 양변을 부터 까지 더하면 . 따라서 다.
- 같은 방식으로 이다. 2번을 대입하면
각 합에 상수항 1이 번 들어가는 점을 빠뜨리지 않는다.
07. 행렬의 크기와 곱의 순서
- 행렬 와 행렬 의 곱 크기는?
- 가 , 가 이면 는 각각 정의되는가?
- 가 일 때 가 모두 정의될 의 크기는? 두 곱은 항상 같은가?
해설 보기
- 이다. 왼쪽의 행과 오른쪽의 열마다 하나의 성분을 만든다.
- 는 안쪽 크기 3과 4가 달라 정의되지 않는다. 는 2가 맞아 이다.
- 가 이어야 한다. 는 , 는 으로 크기부터 다를 수 있다. 크기가 같더라도 계산에 쓰는 행과 열이 달라 일반적으로 같지 않다.
08. 행렬 덧셈과 2×2 곱셈
다음 에 대해 와 를 계산하자.
해설 보기
덧셈은 같은 위치끼리 더한다.
곱셈은 행과 열을 곱해 더한다.
이 를 오른쪽에서 곱하면 의 두 열을 서로 바꾸는 효과가 있다.
09. 교환법칙의 반례
, 일 때 를 계산하자.
해설 보기
각 행과 열의 내적을 계산하면
성분부터 다르므로 다. 정사각행렬끼리라도 교환법칙이 항상 성립하지 않는다.
10. 3×3 행렬과 3×4 행렬의 곱
다음 를 구하자.
해설 보기
결과는 다. 각 행을 의 네 열과 차례로 곱한다.
따라서
11. 항등행렬과 대칭행렬
- 정사각행렬 의 는?
- 는 대칭행렬인가?
- 대칭행렬의 정의를 쓰고 모든 이 대칭임을 보이자.
해설 보기
- 정의상 다.
- 행과 열을 바꾸어도 같으므로 대칭이다. 특히 두 비대각 성분이 모두 2다.
- 인 정사각행렬, 즉 모든 에서 인 행렬이다. 은 대각 성분이 모두 1이고 비대각 성분이 모두 0이므로 언제나 이 조건을 만족한다.
12. 조인·미트와 불 곱
- 일 때 를 구하자.
- 에 대해서도 계산하자.
- 조인과 미트의 성분 정의를 쓰자.
- 일반 행렬곱과 불 곱의 성분을 비교하자.
해설 보기
- 성분마다 OR하면 , AND하면 이다.
- , 이다. 마지막 위치만 두 입력이 모두 1이다.
- , 이며 같은 크기끼리 정의한다.
- 안쪽 차원이 일 때
일반 곱은 곱해서 더하지만, 불 곱은 AND한 결과들을 OR한다. 조건을 만족하는 중간 인덱스가 하나라도 있으면 불 곱의 성분은 1이다.
13. 2×2 역행렬 공식 검증
, 이다. 에 대해 임을 직접 계산하자.
해설 보기
양쪽 곱을 각각 계산한다.
행렬곱의 교환법칙을 가정하지 않고 두 방향을 각각 보였다. 이므로 나눗셈도 정의된다. 따라서 이다.
14. 연립방정식의 행렬 표현
- ()를 로 쓸 수 있음을 보이자.
- 가 가역이면 해가 임을 보이자.
해설 보기
- , , 로 둔다. 곱의 번째 성분은 여서 번째 방정식의 좌변과 같다. 그러므로 성분별 방정식 전체가 와 동치다.
- 양변 왼쪽에 을 곱하면
반대로 이 를 대입하면 이므로 실제 해다. 모든 해가 이 식을 만족하므로 유일하다. 행렬곱의 순서를 바꿔 오른쪽에 곱하면 안 된다.
15. 주어진 역행렬로 방정식 풀기
다음 은 서로 역행렬이다.
, , 을 풀자.
해설 보기
상수 열벡터는 다. 따라서
검산하면 세 좌변이 , , 이다. 그러므로 다.
Comments