지속 가능한 꾸준함

본 포스트는 알고리즘 문제를 해결해가며 공부한 알고리즘 중, 개인적인 판단하에 실용적이라 생각되는 알고리즘을 간략하게 정리한 글입니다. 게시글의 성격상 지속적으로 내용이 업데이트 됩니다. KMP(Knuth–Morris–Pratt) Algorithm: 문자열 검색 알고리즘

www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 본 문제는 차례로 입력받은 원소를 저장하는 배열 A를 오름차순(=비내림차순)으로 정렬하기 위하여, 배열 A의 각 원소를 몇 번째 인덱스에 배치해야하는지를 찾는 문제입니다. 예제로 A = {2, 3, 1}이라는 배열이 주어졌을때, A의 원소 "2", "3", "1"을 오름차순이 되도록 배치시켜 재배치(A) = {1, 2, 3}이 되도록 배열의 원소를 재배치해야..

임의의 두 벡터 \(a\), \(b\) 가 직교(Orthogonal)하다는 것은 벡터 \(a\)와 \(b\)간의 내적(Inner product)값이 0임을 의미합니다. 추가적으로, 두 벡터 \(a\), \(b\) 의 Norm이 각각 1이면 두 벡터는 Orthonormal 하다라고 정의됩니다. 임의의 한 행렬 \(A\)가 직교 행렬(Orthognal Matrix)일때, 직교 행렬 \(A\)는 아래와 같은 성질을 만족합니다. $$A^{-1} = A^T$$ $$AA^{T} = I$$ 여기서, \(I\) 는 단위 행렬입니다. 이렇게만 봐서는 벡터에서 쓰이는 Orthogonal의 의미와 행렬에서 쓰이는 Orthgonal의 의미가 사뭇 달라보입니다. 위의 성질을 만족하는 행렬을 왜 Orthogonal Matrix라..

import torch import torch.nn as nn import torchvision.models as models class CNN(nn.Module): def __init__(self, ): super(CNN, self).__init__() self.backbone = models.resnet18(pretrained=True) for p in self.backbone.parameters(): p.requires_grad = True self.fc = nn.Linear(512, 2) def forward(self, x): x = self.backbone.conv1(x) x = self.backbone.bn1(x) x = self.backbone.relu(x) x = self.backbone...

행렬 \(A\)가 존재합니다. \(det(A)\)가 0이 아니면, \(A\)는 invertible 합니다. \(det(A)\)가 0이면, \(A\)는 not invertible 합니다. 반대로, \(A\)가 invertible 하면, \(det(A)\)는 0이 아닙니다. \(A\)가 not invertible 하면, \(det(A)\)는 0입니다. Linear equation \(Ax=b\)가 존재합니다. \(det(A)\)가 0이 아니면, \(A\)는 invertible 하기때문에 다음의 공식을 통해 Unique solution인 \(x\)를 계산할 수 있습니다. Linear equation \(Ax=0\)가 존재합니다. \(det(A)\)가 0이 아니면, Unique solution인 \(x\)는 영..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 시뮬레이션 문제입니다. 알고리즘은 문제의 규칙에 맞게 아래의 순으로 진행됩니다. 1. 미세먼지 확산 *미세먼지는 확산시, 미세먼지가 존재하는 칸에도 누적되는 방식으로 확산이 됩니다. 2. 미세먼지 이동 3. 위 과정(1. ~ 2.) T번 반복 문제를 풀다가 미세먼지를 시계/반시계 방향으로 이동시키는 부분을 깔끔하게 구현하는 ..

모델 학습 시, 작은 Batch Size로 학습 시키는 것이 Regularization 효과를 낼 수 있다고 합니다. [1] 작은 Batch Size로 학습 시킬 때, 유의할 점이 있습니다. 일반적으로 Batch Size가 작을 수록 학습 단계에서 Gradient의 Variance가 커집니다. 이에 따라 Learning Rate를 작게 설정하는 것을 권장합니다. 하지만, Batch Normalization Layer가 모델에 포함된 경우에 학습 시 극도로 작은 Batch Size(< 8) 는 오히려 성능을 크게 저하 시킬 수 있습니다. [2] 메모리의 한계로 큰 Batch Size로 학습 시키기 힘든 경우, Group Normalization Layer를 Batch Normalization Layer 대..

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 브루트포스 알고리즘을 사용하여 풀었습니다. 그런데 모든 경우를 일일히 탐색하는 것은 불가능합니다. NxN 체스판에 퀸 N 개를 놓을 수 있는 경우의 수는 \({{}_{N^2}\mathrm{C}_{N}}\) 이며 N = 15 일때, 91,005,567,811,177,478,095,440 가지의 경우를 고려해야합니다. 그렇기 때문에 우리는 퀸을 놓으며 걸러낼 수 있는 경우의 수는 최대한 걸러내야 합니다. 먼저, 문제 및..

www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 본 문제는 구현 및 시뮬레이션 문제입니다. 푸는데 2일 가량 걸렸을 정도로 저에게는 너무 어려운 문제였습니다. 제가 어려웠던점은 말을 쌓아야할때, 연결 관계를 코드로 구현해야하는 점이 어려웠습니다. 처음에는, 말이 쌓이며, 경우에따라 순서도 바뀌어야하니 데이터의 삽입과 Reverse 가 쉽게 가능한 자료구조를 생각해보았습니다. 좀 더 생각해보니 말이 얼마나 혹은 어떻게 쌓이든 바닥에 놓인 말과 가장 높이 놓인..

행렬: 수 또는 다항식 등을 직사각형 모양으로 배열한 것 m x n 행렬은 m개의 행과 n개의 열을 가진 행렬을 의미합니다. 아래와 같이 표기할 수 있습니다. $$\begin{pmatrix} x_{1,1} & x_{1,2} & \cdots & x_{1,n} \\ x_{2,1} & x_{2,2} & \cdots & x_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m,1} & x_{m,2} & \cdots & x_{m,n} \end{pmatrix}$$ 행렬에서, 행(Row)은 가로, 열(Column)은 세로 줄을 의미합니다. 참고로 Column은 기둥이라는 뜻을 가진 단어입니다. 이를 알고 있으면 Row와 Column을 구분하는데 도움이 될것입니다. 행벡터(Row ..