이것 저것 공부하는 사람

그동안 행렬관련해서 기초적인 지식이나 연산들에 대해 배웠다. 선형대수를 제대로 시작하는 부분은 벡터공간을 이해하는 것 부터라고 하신다. 일단 Permutation Matrix P는 행렬에 곱했을때, 행을 바꿔주는 행렬이다. 행을 바꾸는 경우는 A=LU분해를 할때, 행을 바꿔야 Pivot을 찾을 수 있는 경우였다. 행 교환이 없다면 바로 A=LU를 구할 수 있는데, 필요하다면 P를 곱한 PA를 기준으로 분해를 하면 된다. 배운 내용이지만 P의 역행렬은 P의 전치행렬이다. 따라서 P^T P = I가 된다. I를 통해 만들 수 있는 P의 개수는 n!개 이다. 전치행렬(Transpose Matrix)는 행과 열이 바뀐 행렬을 말한다. 대칭행렬(Symmetric Matrix)는 대각선을 기준으로 대칭인 행렬을 말..

2차 접종을 맞을 타이밍이 되어서 22일 토요일 2차접종을 맞았다. 아스트라제네카로 1차를 맞고 화이자로 2차를 맞으면 좋다는 얘기가 있어 우리나라에서 임상실험 중이라는데 섞어맞을 타이밍은 아니라 1차와 마찬가지로 아스트라로 2차를 맞았다. 마찬가지로 주사 전후로 접종자들에게 타이레놀을 주시며 열있거나 미리 먹어두면 좋다고 하셨다. 주사는 넣을땐 그렇게 아프진 않고 주사를 뺀 후 알코올 솜으로 문지르는데 위치가 안보여서 감으로 찾는데 애좀 먹었다... 1차때는 9시~10시에 주사를 맞고난 후에 밤 9시? 전부터 열이 나고 몸살이 시작되었는데 2차맞고 난 후에는 저녁에 조금 주사부위만 근육통있고 괜찮았다. 그런데 다음날(일요일)에 주사부위에 근육통이 심해졌고 어지러움이랑 두통이 조금 있었다. 남들 다 괜찮..

이번강의 목표는 행렬 A를 L과 U의 곱으로 나타내는 방법을 배운다. 행렬 A와 B를 곱한 결과인 AB의 역행렬은 무엇일까? 역행렬은 행렬의 곱 순서가 바뀌고 각 행렬을 역행렬 해주면 된다. 즉 \[(AB)^{-1} = B^{-1}A^{-1}\] 로 나타낼 수 있다. 역행렬은 왼쪽에 곱하나 오른쪽에 곱하나 I행렬이 나와야 하는데, 직접 오른쪽 왼쪽 각각 곱한 후, 안쪽부터 계산한후 나머지 부분을 계산해 주면 I행렬이 나온다. 그렇다면 역행렬의 전치행렬은 무엇일까? 전치행렬(Transpose Matrix)은 행과 열을 바꿔준 행을 말한다. 위에서 보는대로 첫번째 식에서 전치를 해주면(T) 행렬 곱셈 순서가 바뀌고 각 행렬이 전치가 된다. 따라서 질문인 전치행렬의 역행렬은 빨간색으로 표시한 부분이 답이다. ..

문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N) 출력 (NK)를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 5 2 예제 출력 1 10 코딩을 처음 입문하면 재귀함수를 호출하여 시간이 오래걸리는 방법을 썻지만, dp를 이용하여 빠르게 구한다. 이항계수를 배우면 파스칼 삼각형을 당연히 떠올리게 된다. 보면 가로로 연속하는 두개의 숫자의 합이 첫째와 둘째숫자의 중간 숫자 임을 알 수 있다. 따라서 다음이 성립한다. n C k = n-1 C k-1 + n-1 C k #include using namespace std; int main(){ in..

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..

이전에는 행렬을 곱할때, 그냥 했지만 이번강에서는 이를 체계적으로 다룬다. 다양한 행렬곱셈을 배운 후에, 역행렬(Inverse Matrices)에 대해 다룬다. 행렬 곱하기 를 바라보는 시각은 크게 4가지 방법이 있다. 1. 일반적 방법 2. 행렬 X Column 3. Row X 행렬 4. Column X Row I . 일반적 방법 C행렬의 C(3,4) 원소가 있다면 이 원소는 어떻게 만들어 졌는가? ==> A의 3번째 row와 B의 4번째 col이 곱해져서 만들어 진다. 이를 수식화 하면 C34 = (row 3 of A) X ( col 4 of B) 가 된다. 일반화 하여 시그마로 있어보이게 쓰면 II . 행렬 X column C행렬의 col1은 B의 col1이 관여하여 만들어 진 것이다. 이를 명확하..

문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는..

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래..

Elimination(소거법)은 선형방정식을 풀기 위해 가장 흔하게 사용되는 기법이다. Elimination은 경우에 따라 원하는 결과가 나올 수도 있고 그렇지 않을 수도 있다. 다음과 같은 선형 방정식이 있다고 가정하자, 이 식은 Ax=b로 표현이 될 수 있음을 1강에서 확인했다. Ax=b로 표현 한 후에 A의 1행 1열의 원소를 Pivot이라 한다. (이때 1은 첫번째 Pivot) 소거를 시작하기 위해서 적당한 multiplier를 찾아야 한다. 일단 첫번째 식에 적당한 수를 곱해 두번째 식에서 빼야 하는데 3을 곱해서 뺀다. 그결과 2행 1열의 원소가 0이된다는 것을 확인 할 수 있고, 두번째 pivot은 2이다. 다음은 3행 1열을 0으로 만들어야 하는데, 이미 0이 되어 있으므로 3행 2열을 0..

문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 예제 입력 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2..