컴퓨터하는 kimmessi

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해결 알고리즘 1. 우선 토마토의 배열을 배열(arr)에 전부 입력을 받는다. 2. 방문확인(visited) 배열에 익은 토마토 칸(1)과 토마토가 없는 칸(0)을 입력하고,익은 토마토의 좌표를 큐(q)에 차례대로 저장한다. 3. 큐(q)에 저장한 익은 토마토의 좌표들을 차례대로 동서남북 방향으로 일수마다 한 칸씩 전진하면서 전에 있던 칸의 숫자에 +1 한 값을 입력한다. 그 과정에서 방문..

www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 해결 알고리즘 문제의 다리 놓기의 경우의 수는 사실 조합과 같다. 그렇기 때문에 $_{1}C_{1}$부터 $_{30}C_{30}$의 값을 배열에 넣고 입력 값에 대한 조합 값을 출력해주면 된다. 1. 우선 배열에 모든 조합 값을 다 넣어준다. 이때 입력 값이 너무 크면 오버플로우가 생길 수 있으므로 배열은 long long 으로 선언해주어야한다. 또, 동쪽과 서쪽의 사이트가 바뀌어도 경우의 수가 같으므로 ..

대수구조(Algebraic structure) 일련의 연산들이 주어진 집합 여러 대수구조 반군 : 집합과 그 위의 결합법칙을 따르는 하나의 이항 연산을 갖춘 대수구조 (결합법칙만 성립) 모노이드 : 항등원을 갖는 반군 (결합법칙, 항등원 성립) $ \begin{eqnarray} \mathrm{ex)} & &( \mathbb{R},*) \;\;\; x*y = 0 \\ & & (1*2)*3 = 0*3 = 0 \\ & & 1* (2*3) = 1*0 = 0 \\ & & 1* \square \neq 1 \end{eqnarray}$ 위의 대수구조는 결합법칙이 성립하므로 반군이다. 하지만 항등원이 존재하지 않으므로 모노이드는 아니다. 군 : 역원을 갖는 모노이드 (결합법칙, 항등원, 역원 성립) $ \begin{eq..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해결 알고리즘 1. 큐(q)에 1부터 N까지의 숫자들을 순서대로 push해준다. 2. 큐(q)안에 숫자들이 모두 없어질 때까지 K번 옆으로 갈 때 과정에서 지나치는 숫자들은 큐의 맨 앞에서 맨 뒤로 보내고, K번 가서 도착한 그 숫자는 출력하고 큐(q)에서 pop한다. 여기서 큐의 사이즈가 1이 아니면 뒤에 쉼표(,)를 출력한 후 pop한다. 소스 코드 #include using namespace std; int main(){ int N, K; cin >> N >> K; queue q; cout

직선의 표현 $R^2$ 또는 $R^3$ 에서 위치벡터가 $a$인 점 $A$를 지나며 방향벡터가 $v$인 직선 상의 임의의 점 $X$ 의 위치벡터 $x$는 $$ x = a + kv $$ 을 만족한다. (단, $k$는 임의의 실수) 위치벡터 : 원점을 시점으로 하는 벡터 방향벡터 : 직선이 늘어나는 방향을 가리키는 벡터 평면의 표현 $R^3$에서 위치벡터가 $a$인 점 $A$를 지나며 법선벡터가 $v$인 평면상의 임의의 점 $X$의 위치벡터 $x$는 $$(x-a)\cdot v = 0$$ 을 만족한다. 법선벡터 : 평면에 수직인 벡터 그림 1과 그림 2에서의 $O$는 원점이다.

벡터 곱(Vector product) 방향은 두 벡터에 동시에 수직이고, 크기는 두 벡터가 이루는 평행사변형의 면적인 $R^3$상의 벡터 3차원 공간에서 벡터간의 이항연산의 일종이다. 외적(outer product) 또는 가위곱(cross product)라고도 불린다. $$ v \times w = \left( \begin{vmatrix} v_2 & v_3 \\ w_2 & w_3 \end{vmatrix}, - \begin{vmatrix} v_1 & v_3 \\ w_1 & w_3 \end{vmatrix} , \begin{vmatrix} v_1 & v_2 \\ w_1 & w_2 \end{vmatrix} \right) $$ 벡터 곱의 성질 $R^3$상의 벡터 $u,\;v\;w$와 스칼라 $k$에 대하여 다음이 ..

스칼라 곱(Scalar product) 유클리드 공간에서 두 벡터로부터 스칼라 값을 얻는 연산이다. 내적(inner product) 또는 점곱(dot product)로도 부른다. $$ \begin{eqnarray} v \cdot w & = & \Vert v \Vert \Vert w \Vert \cos \theta \; \cdots \; (a) \\ & = & v_1 w_1 + v_2 w_2 + \cdots + v_n w_n \;\cdots\; (b)\end{eqnarray} $$ ($\theta$ 는 두 벡터 $ v,\, w$가 이루는 각) 식 $a$와 식 $b$가 같다는 것은 제 2코사인 법칙으로 증명 가능하다. 제 2 코사인 법칙으로 스칼라 곱 증명 $ w = v + x $ $ \therefore x..

평면 벡터 $R^{2}$(2차원)에서 크기와 방향의 의미를 수학적으로 표현한 개념 공간 벡터 $R^{3}$(3차원)에서 크기와 방향의 의미를 수학적으로 표현한 개념 n차원 벡터 $R^{n}$ 상의 벡터 $ v = (v_{1}, v_{2}, \cdots, v_{n}) = \vec{AB} = (b_1 - a_1 , b_2 - a_2 ,\cdots, b_n - a_n)$ 영벡터(Spirit vector) : 모든 성분이 0인 벡터 $ \vec{0} = 0 = (0,0, \cdots ,0) $ 두 벡터의 모든 성분이 같으면 두 벡터가 같다고 할 수 있다. $ v = (v_1, \cdots , v_n),\, w=(w_1, \cdots, w_n) $ 일 때, $ v_1 = w_1 , \cdots , v_n = w_..

행렬식(Determinant) 정방 행렬을 스칼라 값에 대응시키는 특별한 함수 $\mathrm{det}\,A = \begin{vmatrix} A \end{vmatrix} $ $0 \times 0 $ 행렬의 행렬식 $ \Rightarrow \mathrm{det} (\;) = 0 $ $1 \times 1 $ 행렬의 행렬식 $ \Rightarrow \mathrm{det} \begin{pmatrix} a \end{pmatrix} = a $ $2 \times 2 $ 행렬의 행렬식 $ \Rightarrow \mathrm{det} \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} = a_{11} a_{22} - a_{12} a_{21} $ $3 \ti..

연립 일차방정식의 행렬 표현 $\begin{cases} x + y =3 \\ 2x + 3y = 8 \end{cases}$ 첨가행렬(Augmented matrix) $ \begin{pmatrix} 1 & 1 & 3 \\ 2 & 3 & 8 \end{pmatrix} $ $\Rightarrow$ 가우스 조던 소거법 사용 계수행렬(Coefficient matrix), 상수행렬(Constant matrix) $\begin{pmatrix} 1 & 1 \\ 2 & 3 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 3 \\ 8 \end{pmatrix} $ $\Rightarrow$ 역행렬 이용 가우스 조던 소거법(Gauss Jordan Elimi..