행렬
수를 직사각형 모양으로 배열한 것을 말한다. 일반적으로 괄호 안에 수를 적는다. 가로 줄의 수를 '행' 세로 줄의 수를 '열'이라고 한다. 행의 수과 열의 수를 묶어서 행X열 행이라고도 부른다. 행렬에 들어가는 수는 성분이라고 부른다. 성분을 말할 때 n행 m열 성분이라고 표현하면 되는데 파란색으로 표시된 경우 1행 2열 성분이라고 부를 수 있다.
행렬의 덧셈
두 행렬을 더하려면 두 행렬의 행의 수, 열의 수가 같아야 한다. 예를 들어 2 X 3 행렬 두 개는 더할 수 있지만, 2 X 3 행렬과 3X2행렬은 더할 수 없다. 덧셈은 같은 위치에 있는 성분끼리 더하는 것으로 정의된다. 행렬의 덧셈은 교환법칙과 결합법칙이 성립한다.
A + B = B + A
(A + B) + C = A + (B + C)
행렬의 곱셈
1. 행렬의 실수(정수)배
행렬에 정수를 곱하는 것은 모든 성분에 그 정수를 곱한 것과 같다. 예를 들어 3*A는 A의 모든 성분에 3을 곱한 것과 같다.
2. 행렬간의 곱
A, B 두 행렬을 곱하려면 A의 열 수와 B의 행의 수가 같아야 한다. A가 n X m, B가 m X k 행렬이라면 결과는 n X k 행렬이 된다.
곱셈의 경우 교환법칙이 성립하지 않는다. 순서가 바뀌면 곱셈 자체가 되지 않을 수 있다. 하지만 결합법칙, 분배법칙은 성립한다.
AB ≠ BA
(AB)C = A(BC)
A(B + C) = AB + AC
행렬의 이용
대표적인 이용 세가지를 소개한다
1. 연립방정식 풀이
x + 2y + 4z = 17
2x + 5y + 10z = 42
x + 4y +9z = 36
위 식을 모두 만족하는 x, y, z가 있다고 하자 위 세 등식은 오른쪽과 같은 행렬 곱으로 표현 가능하다.
양 변의 세번째 행의 값을 두 배로 늘려도 등식은 성립한다. 이는 x + 4y + 9z = 36을 2x + 8y + 18z = 72 로 변경하는 것과 같다.
세번째 행에서 첫번째 행을 빼도 등식은 성립한다. 부등식에서 소거법과 같다.
※ 가우스 소거법
① 첫 행을 제외하고는 첫 열의 값이 모두 0이 되도록 다른 행에서 첫 행의 값을 뺀다
② 첫번째와 두번째 행을 제외하고는 두번째 열의 값이 모두 0이 되도록 다른 행에서 두번째 행을 계속 뺀다
③ 위 과정을 모든 행에 진행하면 마지막 행은 마지막 변수에 대한 식으로 남게 된다. 이를 이용해 역순으로 답을 구한다.
2. 그래프의 인접 행렬 표현
그래프의 노드가 1~4번까지 존재한다고 하자. 1번에서 3번, 1번에서 4번 2번에서 3번, 3번에서 1번, 4번에서 2번으로 가는 단방향 간선이 있다면 오른쪽과 같은 행렬로 표현 가능하다. 이를 인접행렬이라고 한다.
이제 이 그래프에서 1번 노드에서 출발해 정확히 두개의 간선을 지나 1번으로 돌아오는 경로가 있는지 찾으려고 한다.
인접행렬을 제곱한 행렬릐 (1, 1) 성분을 구한다. 그래프를 인접행렬로 표현할 경우 n행 m열의 값은 n번 노드에서 하나의 노드를 지나 m번 노드로 갈 수 있는지를 표현하는데 이 행렬을 제곱할 경우 n행 m열 의 값은 n번 노드에서 정확히 두 개의 간선을 지나 m번 노드로 갈 수 있는지를 표현하게 된다.
3. 빠른 점화식 계산
피보나치 수열은 아래와 같이 f(0) = f(1) =1로 시작하고 f(2)부터는 바로 이전 두 항의 합으로 표현되는 수열을 말한다.
1 1 2 3 5 8 13 21 34 55...
점화식은 f(n) = f(n-1) + f(n-2) 형태가 된다. 이를 행렬로 표현해보자.
이전항을 다시 전전항으로 표현해보자. 그리고 초항으로 표현해본다.
이 수식을 이용해 1025항을 구해보자. 단 수가 너무 커질 수 있으므로 십의 자리 이상은 지우고 마지막 한자리만 구해보자. 피보나치 점화식으로 직접 1024번의 계산을 하지 않고 이 수식으로 약 10번의 행렬 제곱을 통해 f(1025)를 구할 수 있다.
점화식이 f(n) = af(n-1) + bf(n-2) + cf(n-3)이라면 f(n)을 구하기 위해 3개의 항이 필요하므로 3 X 3 크기의 행렬을 만든다.
연습문제
해답
투포인터
투 포인터는 아래 두가지 유형으로 나온다.
① 특정 조건을 만족하는 범위를 찾는 문제
② 특정 조건을 만족하는 두 수를 찾는 문제
투 포인터가 어떤 방식인지 각 유형별로 어떤 특징이 있는지는 예시를 보며 설명한다. 투 포인터를 이해하기 위해 다음 문제를 살핀다.
다음과 같이 오름차순으로 정렬된 9개의 서로 다른 수가 주어진다.
2 5 6 7 8 9 10 11 14
위 수열에서 합이 60인 7개의 수를 고르는 경우의 수를 구하여라.
어떻게 찾을까?
- 9개의 수 중 합이 60인 7개의 수를 찾는 문제다
- 위 예시에서 주어진 수열 2 5 6 7 8 9 10 11 14의 전체 합을 구하면 72가 된다
- 따라서 합이 12인 두 개의 수를 제거하면 나머지 합이 60이 된다.
s와 e의 현재합은 2+14므로 12를 만들기 위해 s와 e가 모두 왼쪽으로 이동할 수 있다. 하지만 s는 처음 위치므로 e만 왼쪽으로 이동할 수 있다. 또한 14와 11은 절대 답이 될 수 없으므로 표에서 제거해도 된다. s가 2일 때 e가 10의 위치에 도달하면 12를 만들 수 있다.
| 2 | 5 | 6 | 7 | 8 | 9 | 10 |
| s | s | e | e |
12합을 만든 순간 s는 왼쪽으로 한칸 이동하고 e도 다시 탐색한다. 7을 만나면 다시 둘의 합이 12가 되며 s가 한 칸 앞으로 이동하고 e가 왼쪽으로 이동해 서로 만나면서 계산은 종결된다.
예시문제
해답
슬라이딩 윈도우
슬라이딩 윈도우는 투 포인터의 특정 조건을 만족하는 구간을 찾는 것과 아주 유사하다. 투 포인터는 s, e 두 포인터를 상황에 따라 하나씩 움직이며 정답을 구했다. 슬라이딩 윈도우는 s와 거리 e를 유지한 채 같이 이동하며 구간을 살핀다. 투 포인터는 구간 구하는 문제와 비슷한 형태로 나오지만 구간의 길이가 문제에서 주어지는 경우 슬라이딩 윈도우 문제라고 보면 된다.
해답
그리디 알고리즘
그리디 알고리즘, 다른 말로 욕심쟁이 알고리즘이라고 하는 알고리즘이 있다. 개념은 간단하지만 문제에 맞는 증명을 요구하기 때문에 상당히 까다로운 문제고 그만큼 출제하기 좋은 유형이다. 그리디 알고리즘은 당장 보이는 최선의 선택을 따라가서 정답을 구하는 알고리즘이다.
예를 들어, 13,200원에 대해 거스름돈을 주는 상황을 생각해보자.
- 10,000원 지폐 한 장, 1000원 지폐 세 장, 100원 동전 두 개를 주면 된다.
- 혹은 1,000원 지폐 열 두 장, 100원 동전 두 개를 줘도 된다.
만약 거스름돈을 줄 때 지폐와 동전의 수를 최소화하는 문제라면 첫번째 방법이 정답이 된다. 저 정답을 어떻게 구할 수 있을까?
줄 수 있는 가장 큰 단위로 거스름돈을 주면 된다.
연습문제
문제 해답
