생각날때마다 올리는 블로그

Machine learning algorithm categoriesSupervised learning:답(Label)이 있는 채로 학습하는 것을 의미답이 실수형이면 Regression, 그렇지 않고 Discrete하면 Classfication을 활용하여 학습남아 있는 데이터를 이용하여 Label을 예측하며 정확도를 측정Unsupervised Learning답(Label)이 없는 채로 학습하는 것을 의미비슷한 성질을 가진 것들끼리 모으는(패턴을 파악하는) Clustering의 목적Reinforcement Leanring학습데이터는 필요가 없으며, 환경이라는 것과 상호작용을 하며 학습을 진행현재 상태(State)에서 취할 수 있는 행동(Action)을 취했을 때의 보상(Reward)가 최대가 되는 것을 목적..

Problem If $G$ is a group in which $\forall a,~b\in G\,:\,\left(a\cdot b \right )^i=a^i\cdot b^i$ for three consecutive integers $i$, show that $G$ is abelian Solution Lemma $a\cdot b^i=b^i \cdot a$ ($a$와 $b^i$가 commutative propery를 가진다. 더보기 일단 3개의 연속된 숫자라는 사실에 주목을 하자. 이를 활용하기 위해 $\left(a\cdot b \right )^{-1}\cdot\left(a\cdot b \right )^i\cdot\left(a\cdot b \right )$라는 식을 생각하자. 군의 특성에 의해 결합법칙이 성..

Problem 1.2.11 $0$이 아닌 대각 항들을 갖는 $d\times d$ 삼각 행렬 $L$에 대해 가역 행렬 $\Delta$ 와 순 삼각행렬 $A$가 존재하여 $L=\left(\Delta + A\right)$로 표현이 가능하다. 이떄 행렬에 대한 역변환과 행렬 곱셉 및 덧셈만 이용하여 $L$의 역행렬을 계산하라. Hint. $d\times d$ 크기의 순 삼각행렬은 항상 멱영이며, $A^d=0$임을 주목하라. 더보기 앞의 정리 $\left(I+A \right )^{-1}=\displaystyle\sum_{d=0}^\infty A^d$가 유도되는 과정을 활용하자. 우변에 $\left(I+A \right )$를 곱했을 때, $I$만 남고 나머지는 뒤의 $A$항에 의해 삭제가 되는 원리를 활용한 방법인..

Problem 1.2.1 원점, $\bar{x}$, $\bar{y}$이 있을 때, $\lVert \bar{x}-\bar{y}\rVert\leq \lVert\bar{x}\rVert+\lVert\bar{y}\rVert$임을 증명하라. Hint. Cauchy–Schwarz inequality를 사용하라 더보기 $a>0$, $b>0$이고 $a^2>b^2$이면 $a>b$이 성립함을 이용하자. $\lVert \bar{x}-\bar{y}\rVert>0$이고 $\lVert\bar{x}\rVert>0$, $\lVert\bar{y}\rVert>0$이므로 norm의 정의를 활용하기 위해 양변을 제곱하여 비교하자. $\begin{aligned} \lVert \bar{x}-\bar{y}\rVert^2&=\left( \bar{x..

이전에 진행했었던 Gram-Schmidt Process에 이어 이번 시간엔 푸리에 계수, 직교 여집합에 대해 소개해보려 한다.푸리에 계수 같은 경우 추후에 자세히 진행할 예정이므로 간단하게 맛만 보고, 직교 여집합과 그의 정리에 포커스를 맞추어 진행할 예정이다.Definition of Fourier coefficient$\mathsf{V}$를 내적공간이라 하고, $\beta\subseteq\mathsf{v}$을 정규직교집합이라 하고, $x\in \mathsf{V}$라 하자. 이 때, $\beta$에 대한 $x$의 푸리에 계수를 다음과 같이 정의한다.$\forall y\in\beta~:~\left$ 푸리에 계수는 정의에 대한 언급 밖에 없어서 추후 챕터에 나오면 그 때 다시 서술하겠다.이제 직교 여집합에 ..

Definition of orthonormal basis$\mathsf{V}$를 내적 공간이라 하자. 이 때, $\beta\subseteq\mathsf{V}$가 다음 두 조건을 만족 할 때, 정규직교 기저라고 한다. ① $\beta$가 정규직교여야 한다.② $\beta$가 ordered basis여야 한다.여기서, 정규직교는 다음 두 조건을 모두 만족하는 집합을 의미한다.$\forall v_i,~v_j\in\mathsf{V}:\left=\begin{cases}1 & \left( i=j \right )\\0 & \left(i\neq j \right )\end{cases}$Theorem 6.3$\mathsf{V}$를 내적공간이라 하고, $S=\left\{v_1,~v_2,\cdots,~v_k\right\}\s..

링크http://icpc.me/1185문제1. 모든 마을을 최소 한 번씩은 방문해봐야 한다.2. 반드시 출발한 곳으로 돌아와야 한다.3. 출발점은 "임의로" 설정할 수 있다. 이 때 최소 코스트를 출력하라 풀이핵심은 "다시 돌아와야 한다"라는 것이다.일단, 출발점은 임의로 설정할 수 있고, MST 특성 상 어떤 곳에서 시작해도 상관이 없음을 생각하면그냥 그리디스럽게 방문할 때 가장 작은 코스트가 드는 곳에서 시작하면 된다.예제를 생각해보면, 4번 마을을 방문할 때 코스트가 6으로 제일 적으므로 4번에서 시작하는 것이다.이제 어떻게 방문할지를 생각해봐야 한다. 관찰을 해보면, 다시 자기자신으로 돌아와야 한다는 특징 때문에, 간선을 무조건 "짝수"번 들러야 함을 알 수 있다.MST 특성 상 사이클은 없으므로..

링크http://icpc.me/7453 문제네 개의 배열 A, B, C, D가 주어질 때, A[a]+B[b]+C[c]+D[d]=0이 되는 (a, b, c, d)의 순서쌍의 갯수즉, 걍 아무거나 네 개 뽑아서 더했을 때 0되게 하는 갯수 풀이먼저, $N\leq4000$임을 생각해야한다.이를 왜 생각해야하느냐?만약 완전탐색 기법으로 A, B, C, D 모든 배열 훑으면서 쓰으으윽 하면 $O(N^4)$이된다.$4000=4\times10^3$이고, $4000^4=2^8\times10^{12}$인데 이를 1초내에 돌리는건 그냥 불가능하다...따라서 좀 더 효율적은 방법을 생각해보아야 한다! Key-Idea : Meet in the Middle영어로 까리하게 Meet in the middle인데 한국어로 직역하면 ..

https://www.acmicpc.net/problem/1071문제$N$개의 숫자가 주어진다. 이 때, $A[i]+1\neq A[i+1]$이 되지 않게 숫자의 순서를 바꾸고자 한다.만약 답이 여러개면 사전순으로 제일 빠른 것을 출력하라. 풀이풀이의 시작은 제일 빠른에 있다.제일 빠른 것을 출력할려면 일단 숫자를 최대한 작게 하되 "필요할 때만" 바꿔줘야 한다.예를 들어서 1 3 4 4 이렇게 있으면 굳이 안바꿔도 위 조건을 만족시키기 때문에 상관이 없다는 것이다.하지만 3 4 4 1 이렇게 인풋이 들어오면 1이 제일 앞에 오게 바꿔줘야 한다. 따라서 먼저 들어온 input들을 정렬해서 그 이후 순서를 적절히 바꿔줘야 함을 알 수 있다.이제 정렬되었다고 가정하자. $A_i,\ A_{i+1},\ \cdot..

http://icpc.me/2858문제가장자리에 까는 빨간색 타일 R, 가장자리가 아닌 곳에 까는 갈색 타일 B를 준다.이 때, 방의 크기를 맞추어라 풀이간단한 수학문제이다.$N\times M$의 타일을 생각해보자.그러면, 가로와 세로가 만나는 총 4개의 지점은 겹치게 된다.즉, $2\times(N+M)-4$가 되는 것이다.이가 빨간색 타일의 개수이다.또한 타일을 안 쓰는 부분이 없으므로 R+B하면 총 면적이 된다. 이는 $N\times M$ 이로써 우리는 $N+M=\frac{R+4}{2}$, $L\times M=R+B$를 얻을 수 있다.$R\leq5000$이므로 반복문을 돌리면서 $L$과 $M$을 찾아주면 된다. 코드 1234567891011121314#include using namespace std..