문제 이 문제를 풀기 위해서는 가장 먼저 다음과 같은 관찰을 해야된다 :가로등을 위치 순서대로 나타내면 가로등의 상태는 항상 켜짐, 켜짐, ... , 켜짐, 꺼짐, ... , 꺼짐, 켜짐, ... , 켜짐 형태이다. 그 다음으로 해볼수 있는 시도는 $\text{dp}[i][j]$를 i ~ j 번 가로등들에 대한 문제의 답으로 정의하고 점화식을 만드는 것이다. 하지만 이렇게 하면 점화식이 잘 만들어지지 않는다. 그 다음으로 시도해볼수 있는 것은 $\text{dp}[i][j]$를 1 ~ i, j ~ N 번 가로등을에 대한 문제의 답으로 정의하는 것이다. 실제로 이렇게 정의하면 점화식을 어렵지 않게 만들 수 있다. (다만 디테일한 부분이 구현을 어렵게 한다.) 끝

문제 먼저 이 문제를 다음과 같은 관점으로 보자 :문제에서 주어진 수열에서 몇개의 원소들을 선택해서 만들어진 부분수열 $a_k$와 선택하지 않은 원소들을 통해 만들어지는 부분수열 $b_k$에 대해 $(|a_1-a_2|+|a_2-a_3|+\cdots)+(|b_1-b_2|+|b_2-b_3|+\cdots)$ 의 최솟값을 구한다. 그리고 다음과 같이 점화식을 정의해보자.dp[i][j] : $A_{1:i}$에 대해 i번째 원소와 임의의 원소를 선택해 수열 $a_k$를 만들고 나머지로 수열 $b_k$를 만들때 $(|a_1-a_2|+|a_2-a_3|+\cdots)+(|b_1-b_2|+|b_2-b_3|+\cdots) + |A_j-b_\text{last}|$ 의 최솟값 이 dp를 이용하면 다음과 같이 전체 문제에 대한 ..

Background$W \in \mathbb{R}^{D_2 \times D_1}$, $X \in \mathbb{R}^{D_1 \times N}$ 에 대해 bias가 생략된 linear layer의 출력값 $Z=WX, Z \in \mathbb{R}^{D_2 \times N}$가 있다고 하자.또한 $L : \mathbb{R}^{D_2 \times N} \rightarrow \mathbb{R}$은 최적화 하려는 object function이라고 하자. Chain Rule 에 따라 gradient를 다음과 같이 구할수 있다.$$ \frac{\partial{L}}{\partial{W}} = \frac{\partial{L}}{\partial{Z}} \frac{\partial{Z}}{\partial{W}} $$하만 ..