CS231n 강의 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

참조

CS231n 유튜브 강의 CS231n 강의 노트 https://doromi.tistory.com/112?category=849309

Loss Functions and Optimization

Reminder Previous Lecture

Linear Classification은 위와 같이 입력 이미지와 W값의 곱으로 생각할 수 있다. 이 결과는 클래스의 개수와 같은 차원을 가진다. 이 중 가장 큰 결과값을 가지는 클래스로 예측한다. 다음은 가중치 W값을 랜덤으로 설정한 뒤 3개의 이미지에서 얻은 결과이다. 이 중 2가지는 가장 큰 값이 나타나는 예측된 클래스가 정답 클래스와 일치하지 않은 것을 확인할 수 있다. 그렇다면 올바른 가중치 W값을 어떻게 찾는 것일까?

Loss Function

Loss Function: 손실함수라고 불리며, 현재 사용하고 있는 이미지 분류기(모델)가 얼마 만큼의 손실을 가지고 있는지를 나타내는 함수이다.어떤 Loss Function을 $$L_{i}$$라고 하자. 각 N개의 데이터에서 구해지는 손실값들을 더한 뒤 N으로 나눈 평균값을 Loss 값으로 사용하는 것을 확인할 수 있다. $$L_{i}$$ 함수에는 어떤 종류가 있는지 알아보자.

Multiclass SVM loss

Multiclass SVM loss를 설명하자면 다음과 같다.

• Linear Classification인 $$f(x_{i}, W)$$ 에서 나온 결과를 $$s$$ 라고 하자.
• 정답인 클래스의 $$s$$ 값을 $$s_{y_{i}}$$라고 하고 나머지 클래스와 이 값을 비교한다.
• 정답인 클래스와 나머지를 비교했을 때, 정답보다 다른 클래스의 점수가 더 높다면 이 차이만큼이 Loss인 것이다.
• 위에서 구한 Loss값에서 safety margin이라는 값을 추가한다. 이는 정답 클래스가 적어도 다른 클래스보다 safety margin 값 만큼은 커야 한다는 의미이며 본 예시에서 safety margin = 1 이다.
• Loss 값이 0보다 작은 음수 값인 경우에는 포함하지 않는다.
• 위 그래프에서 가로축은 $$s_{y_{i}}$$ 값이고 세로축은 $$L_{i}$$의 값인 Loss 값을 표현하였다.

다음은 3개의 그림에 대한 Linear Classification 결과이다. 이 중 고양이 사진에 대한 Loss Function을 계산해보았다. 고양이는 3.2값을 가지며 나머지 자동차와 개구리에 대한 Loss 값은 다음과 같다.

• Loss(class:cat) = 0
• Loss(class:car) = max(0, 5.1-3.2+1) = 2.9
• Loss(class:frog) = max(0, -1.7-3.2+1) = 0 고양이 사진의 전체 Loss = 0 + 2.9 + 0 = 2.9

나머지 두 사진도 위와 같은 방법으로 계산한다. 이 Loss 값들을 모두 더하고 사진 개수 만큼 나눈 값을 Multiclass SVM loss 라고 한다.

Multiclass SVM loss의 특징

• 정답 스코어가 safety margin = 1 을 만족하는 범위라면 Loss 값에 변화를 주지 않는다.
• 만약 Loss 값이 0이라고 할 때, W: weight parameter 값에 임의의 상수를 곱해도 Loss 값은 0이다.
• 위 점에서 Multiclass SVM loss는 유일하지 않다.
• 모든 $$s$$값이 0이라고 하면 Loss = class 수 - 1 값을 가진다. 이러한 특성은 Loss function의 작동을 Debug 하기에 적절하다.
• Loss의 최솟값은 0이며 최대값은 무한대이다.

Regularization

그렇다면 Loss function의 값이 줄어들수록 좋은 성능을 가질까? 정답은 '좋을 수도 있고 아닐 수도 있다' 이다.

Loss가 줄어든다는 것은 Train 데이터에 대해서 좋은 성능을 가지게 된다는 뜻이다. 하지만 이것은 Test 데이터에 대해 좋은 성능을 가진다는 것을 보장해 주지 않는다. 이 문제와 관련된 것이 바로 overfitting(과적합) 이다.

overfitting이란 Train 데이터에 대해서는 좋은 성능을 가지도록 학습되지만, Test 데이터에 대해서는 오히려 성능이 떨어지는 현상을 말한다.

그렇다면 이 문제를 어떻게 해결해야 할까? 정답은 Regularization 에 있다. Regularization 은 W 값에 제약을 가한다. 위 그림을 보면 파란색은 Train 데이터, 초록색은 Test 데이터이다. 예측한 파란색 선은 Train 데이터에 overfitting 되어 있는 것을 확인할 수 있다.

W의 값이 복잡한 값을 가지지 않게 하기 위해, W 값에 대해서 평가하는 함수를 추가하는 것을 Regularization 이라고 한다. Regularization 을 통해 모델은 더 단순한 W를 선택할 수 있다. (모델에 soft한 제약을 줌, penalty)

• "weight decay" : 특정 가중치가 비이상적으로 커지는 것을 방해하는것 이다.
• "local noise"와 outlier(특이점)의 영향을 적게 받도록 한다.

아래는 Regularization 에서 사용하는 function의 예시이다. 먼저 $$\lambda$$: Regularization strength 는 Regularization 값을 어느 정도로 사용할지를 정하는 값이고 그 이후 나오는 $$R(W)$$ 는 Regularization 함수이다. 종류는 L2 regularization, L1 regularization, Batch normalization, Elastic net, Dropout, Stochastic depth 등 다양한 Regularization 방법이 있다.

Train 데이터 $$x$$가 있고 서로 다른 $$w$$ 행렬 $$\omega_{1}$$과 $$\omega_{2}$$가 있다. $x$와 $w$의 내적을 구함으로써 Linear classification을 수행할 수 있다. Linear Classification 관점에서 $$\omega_{1}$$과 $$\omega_{2}$$는 같다.

$L_{1}$ 에서는 $$\omega_{1}$$ 을 선호한다. 왜냐하면, $L_{1}$ 은 행렬에서 0이 아닌 요소가 많을 때 복잡하다고 생각한다.

$L_{2}$ 에서는 $$\omega_{2}$$ 을 선호한다. 왜냐하면, $L_{2}$는 분류기의 복잡도를 각 값들이 얼마나 차이가 없는지로 비교하기 때문이다. Linear Classification에서 W는 얼마나 $x$가 output class와 비슷한지를 계산한다. 따라서 $L_{2}$는 변동이 심한 어떤 입력 $x$가 있고 그 특정요소에 의존하기 보다는 모든 $x$의 요소가 골고루 영향을 미치길 원할 때 사용한다.

어떤 문제를 가지고 있을 때, 그 문제에서 '복잡하다'를 어떻게 정의할 것인지를 고민하여 적절한 Regularization을 사용하는 것이 중요하다.

+) L1 regularization을 적용했을 때 두 weight 값은 같은 Loss를 가진다. 하지만 L2 regularization을 적용하면 $$\omega_{1}$$와 같은 경우는 1의 값을 가지지만, $$\omega_{2}$$와 같은 경우 4 x (1/4)^2 = 1/4 의 Loss를 가진다.

• L1 regularization

  • weight 값이 0으로 수렴하는 것이 많은 형태이다. 이를 Sparse matrix(희소행렬)이라고 부른다. 다시 말해, W 값이 희소행렬이 될 수 있도록 한다.
  • 위에서 0의 값이 많다는 이야기는 어떤 특징들을 무시하겠다는 것으로 볼 수 있다.

• L2 regularization

  • 가장 보편적인 방법으로 Euclidean Norm에 패널티를 주는 것이다.
  • weight 값이 큰 값은 점점 줄이며 대부분의 값들이 0의 가까운 값인 가우시안 분포를 가진다.
  • weight가 0이 아니라는 점에서 모든 특징들을 무시하지 않고 조금씩은 참고하겠다는 것으로 볼 수 있다.

• Elasticnet은 L1과 L2를 합친 것이다.

Softmax Classifier

Softmax는 스코어를 가지고 클래스별 확률 분포를 계산하는 방법이다. 또한, Multinomial Logistic Regression(다항 로지스틱 회귀)이라고도 불린다.

각 스코어에 지수를 취해 양수가 되게 만든 뒤에 지수들의 합으로 정규화를 한다. 이 과정을 통해, 확률 분포를 얻을 수 있고 이것이 바로 해당 클래스일 확률이 된다. 이 값은 확률이기 때문에 0-1 사이의 값을 가지며 모든 확률들의 합은 1이다. 정답 클래스의 확률값은 1에 가까운 값이며, Loss는 -log(해당 클래스일 확률) 로 정의된다.

손실함수는 얼마나 좋은지가 아니라 얼마나 '구린지'를 측정하는 것이기 때문에 log에 -를 붙인다. 해당 클래스 확률일 확률이 0에 가까울수록 loss값은 무한대로 커지고 1에 가까울수록 loss는 0에 가까워진다.

이론적으로 softmax의 최댓값은 무한대, 최솟값은 0이다. 하지만, 컴퓨터가 무한대 연산을 잘 못하기 때문에(유한정밀도) Loss가 0인 경우는 절대 없다.

스코어들이 모두 0근처에 모여 있는 작은 수일 경우 Loss는 어떻게 될까? 스코어들이 비슷하다면 -log(1/클래스 개수) 가 된다. (0에 가까운 스코어 값이 지수를 취해 지수들의 합으로 정규화하면 1에 가까운 확률값을 얻을 수 있음) log는 분자와 분모를 뒤집을 수 있기 때문에, 이점을 활용하면 log(클래스 개수) 가 된다. 이 점은 오류가 발생해 문제점을 찾고자 *디버깅할 때 유용하다. *

SVM loss와 같은 형태는 hinge loss, Softmax의 경우 cross entropy loss 라고도 불린다.

SVM loss와 Softmax의 차이

• SVM loss는 정답과 그 외의 클래스 간 margin 만이 최종 결과값에 영향을 주기 때문에 스코어가 조금 변한다고 해서 SVM loss가 변하거나 하지 않는다.
• Softmax는 0-1 사이의 확률값만을 도출하기 때문에 정답 스코어가 충분히 높고 다른 클래스 스코어가 충분히 낮아도 최대한 정답 클래스에 확률을 몰아 넣으려고 한다.

다시 말해, SVM loss는 일정 margin만 넘기면 더이상 성능 개선에 신경을 쓰지 않는 반면, softmax는 계속해서 성능을 높이려고 노력한다.

Optimization

Loss를 줄이는 가중치 w를 찾는 것을 최적화라고 한다.

Random Search

아무런 기준 없이 무작위로 w값을 변경해보며 가장 좋은 성능을 가지는 값을 찾는 것이다. Random Search를 사용하면 약 15.5%의 성능을 가지는 것을 확인할 수 있으나 현재 최고 성능인 SOTA가 95%인 점을 보면 좋은 방법이 아니라는 걸 알 수 있다.

Local Geometry

기하학적 특성을 이용하여 최적화 방법을 수행할 수 있다. 눈을 감고 가장 낮은 지대를 찾아 걸어 이동할 때를 상상해보자. 우리는 발로 경사를 느끼고 어느 방향으로 내려가야 하는지를 직감적으로 알 수 있다. 경사를 느끼고 방향을 정해서 내려가는 것을 반복하다 보면 가장 낮은 지대를 찾을 수 있을 것이다. 이 방법은 NN이나 Linear Classifier를 훈련시킬 때 일반적으로 사용된다.

어떤 점 x에서 도함수(derivative)를 계산해보면 작은 스텝 h가 있고 그 스텝 간의 함수 차이를 비교하기 위해 뺄셈을 하여 스텝 간격을 0에 가깝게 만들면 이것이 바로 그 점에서의 경사가 된다.

이 개념은 다변수 함수(multi-variable function)로도 확장시킬 수 있다. 실제로 x는 스칼라가 아니라 벡터로 x가 벡터이기 때문에 이 개념을 다변수로 확장시켜야 한다. 다변수인 상황에서 미분으로 일반화하면 gradient이고 gradient는 벡터 x의 각 요소의 편도함수들의 집합이다. (*편도함수는 독립변수가 2개 이상인 다변수함수에서의 도함수를 의미함) 입력이 3개면 gradient도 3개가 된다. gradient는 편도함수들의 벡터가 되고 방향은 함수에서 가장 많이 올라가는 방향이다.

특정 방향에서 얼마나 경사가 가파른지 알고 싶을 때 그 방향의 unit 벡터와 gradient 벡터를 내적하면 된다. gradient는 임의의 어떤 점에서의 선형 1차 근사 함수를 알려주기 때문에 많은 딥러닝 알고리즘들이 gradient를 계산하고 파라미터 벡터를 반복적으로 업데이트 하는 데에 사용한다.

컴퓨터로 gradient를 유용하게 사용할 수 있는 방법은 유한차분법(finite difference method)를 이용하는 것이다. 예시를 보면, 벡터의 두 번째 요소에 아주 작은 값 h(0.0001)을 더하고 loss를 구해보자. 기존 w에서의 loss와 h를 더했을 때의 loss의 차이를 계산하여 위 식에 나온 것처럼 극한 값을 이용해 gradient를 구할 수 있다. 이것을 각 요소마다 반복하면 된다. 벡터 요소마다 반복해서 수행하면 시간이 많이 걸리지만, 미분을 이용하면 바로 gradient를 수할 수 있다.

얻은 gradient의 반대 방향으로 w를 업데이트하고 아주 조금씩 이동하여 loss가 최저인 지점에 수렴하게 하는 것이 목표이다. step size를 정하는 하이퍼파라미터 learning rate를 올바른 값으로 설정하는 것도 중요하다.

손실함수를 정의한 것을 생각해보면, Loss를 구할 때 전체 Train 데이터 세트의 loss 평균으로 사용하였다. 하지만 실제로는 데이터의 개수 N이 매우 커질 수 있기 때문에 시간이 오래 걸리게 된다. (ImageNet의 경우 데이터 수가 130만개)

gradient를 계산하는 과정을 살펴보면 Loss는 그저 각 데이터의 loss의 gradient 합이라는 것을 알 수 있다. 그렇기 때문에 N개의 전체 Train 데이터 세트를 한 번 더 돌면서 계산해야 한다. 그래서 실제로는 Stochastic Gradient Descent 방식을 사용한다.

Stochastic Gradient Descent

전체 데이터 세트의 gradient와 loss를 계산하기 보다는 Minibatch라는 작은 트레이닝 샘플로 나누어서 학습하는 방식이다. 보통 2의 제곱으로 정해지며 32,64,128를 주로 쓰는 편이다. Minibatch를 이용하여, Loss의 전체 합의 추정치와 실제 gradient의 추정치를 계산할 수 있다. SGD 방식은 거의 모든 DNN 알고리즘에서 사용되는 기본적인 학습 알고리즘이다.

특징 변환

Linear Classification은 이미지에서 좋은 방법은 아니다. 그래서 DNN이 유행하기 전에는 Linear Classification을 이용하기 위해 두가지 과정을 거쳤다.

1. 이미지의 여러가지 특징표현을 계산 : 모양새, 컬러 히스토그램, edge 형태와 같은 특징 표현을 연결한 특징벡터 2. 이 특징벡터를 Linear Classification의 입력값으로 사용

컬러 히스토그램

각 이미지에서 Hue 값만을 뽑아 각 색깔별 픽셀의 개수 를 세는 것이다. 개구리의 경우 초록색이 많음을 볼 수 있다.

Histogram of Oriented Gradient

이미지를 8*8 픽셀로 나눠서 각 픽셀의 지배적인 edge 방향을 계산한다.

Bag of Words

NLP에서 영감을 받은 방식으로 어떤 문장에서 여러 단어들의 발생 빈도를 세서 특징벡터로 사용하는 방식을 이미지에 적용한 것이다. 이미지들을 임의로 조각내고 각 조각들을 k-means 알고리즘을 이용해 군집화한다. 다양하게 구성된 각 군집들은 다양한 색과 다양한 방향에 대한 edge도 포착할 수 있다. 이러한 것들을 시각 단어(visual words)라고 부른다.

5-10년 전에는 대부분 이렇게 특징 벡터를 뽑아 Linear Classification의 input으로 사용하였다. 이 개념들은 CNN과 DNN으로 넘어간다고 크게 달라지지 않는다. 유일하게 다른 점이 있다면, 이미 만들어 놓은 특징을 쓰기 보다는 데이터로부터 특징을 직접 학습하려 한다는 점이다.

디지털 신호 처리 연구의 기반이 되는 선수과목, '신호및시스템' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

시스템이란?

• 한 신호를 다른 신호로 변환하는 규칙(mapping)이 정해진 물리적, 전자기적 요소들의 집합
• LPF(Low Pass Filter)는 낮은 주파수를 통과시키고 높은 주파수는 통과시키지 않음
• input 함수는 $x(t)$, output 함수는 $y(t)$, system 함수는 $h(t)$
• $y(t)=x(t)\circledast h(t)$ ➡️ convolution

시스템 유형(Types of Systems)

1. Linear Systems and Nonlinear Systems

• Linear System은 Superposition(sum)과 Homogeneity(product) 성질을 만족해야 함 예시를 들자면,
• $x_1(t)+x_2(t)$와 $(x_1(t)+x_2(t))^2$의 결과값이 다름 ➡️ $y(t)=x^2(t)$는 Non-linear 함
• 반대로 적분의 경우, 합법칙에 의해 두 값이 동일하기 때문에 linear 함
• 합과 곱의 결과값이 동일하여야 함
  

2. Stable Systems and Unstable Systems

• Bounded Signal: 모든 시간 t에 대해 유한한 값을 가짐
• Unbounded Signal: 임의의 순간에 대해 무한한 값을 가짐
• Stable System이라면, 아래 조건 식을 만족해야 함 예시를 바탕으로 정리하자면,
• 조건식을 만족하면 Stable, 조건식을 만족하지 못하지만 모든 시간 t에 대해 일정한 값을 가질 경우 Marginally Stable, 조건식을 만족하지도 못하면서 무한한 값을 가질 경우 Unstable
  

3. Static Systems and Dynamic Systems

• Static System ➡️ Memoryless
• Dynamic System ➡️ Memory
• Static은 현재의 input 값 만을 고려함
• Dynamic은 과거와 미래 input 값까지 모두 고려함
  ### 4. Casual Systems and Non-casual Systems
• Casual System ➡️ 현재 input 값, 과거 input 값, 과거&현재 input 값 모두를 고려함
• 모든 Static System은 Casual System임
• 하지만, 그 역의 경우는 성립하지 않음

디지털 신호 처리 연구의 기반이 되는 선수과목, '신호및시스템' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

Classification of signals

1. Continuous time & Discrete time ✅
2. Real & Imaginary ✅
3. Periodic & NonPeriodic ✅
4. Even & Odd ✅
5. ** Energy & Power ✅**
6. Deterministic & Random ✅

🧡 Even and Odd signals

• $$x(t)=x(-t)$$ 부호가 같다면 even signal 이다.
• $$x(t)=-x(-t)$$ 부호가 다르다면 odd signal 이다.

• $$x(t)=2rect(\frac{t}{4})$$의 경우, 세로 축을 기준으로 folding 하면 기존의 함수식과 동일한 것을 확인할 수 있다. ➡️ $$x(t)=x(-t)$$ ➡️ even signal

• $$x(t)=2sin(t)$$의 경우, 세로 축과 가로 축(t축)을 기준으로 folding 하면 기존의 함수식과 동일한 것을 확인할 수 있다. ➡️ $$x(t)=-x(-t)$$ ➡️ odd signal
• $$x(t)=cos(t)$$의 경우, 가로 축(t축)을 기준으로 folding 하면 기존의 함수식과 동일한 것을 확인할 수 있다. ➡️ $$x(t)=x(-t)$$ ➡️ even signal

• 위와 같은 unit step function인 $u(t)$는 even signal도 아니고 odd signal도 아니다.

Problems on Even and Odd signal

$x(t)=x_{e}(t)+x_{o}(t)$ $x(-t)=x_{e}(t)-x_{o}(t)$ 을 가정해보자.

두 식을 더하면, $2x_{e}(t)=x(t)+x(-t)$ 란 식이 나온다. 위 식은 even, odd signal에 따라 다음과 같이 분리 될 수 있다.

• $x_{e}(t)=\frac{x(t)+x^*(-t)}{2}$
• $x_{o}(t)=\frac{x(t)-x^*(-t)}{2}$

+) * 는 conjugate operation을 나타낸다. conjugate에는 '짝으로 결합한'이라는 뜻으로, a+bi와 a-bi가 '짝으로 결합해' 있는 것을 예시로 볼 수 있다.

위 그래프에서 첫 번째 두 번째 식은 even, odd signal을 나타내고 있지 않다. 3번째 식은 even signal을, 4번째 식은 odd signal을 각각 나타내고 있는 것을 확인할 수 있다.

• $x(t)=e^{jt}$의 경우, $x(t)=x^(-t)$이므로 *even signal이다.**
• $x(t)=te^{jt}$의 경우, $x(t)=-x^(-t)$이므로 *odd signal이다.**

🧡 Energy and Power signal

에너지 값은 위와 같은 식으로 나타낼 수 있다. ($$\alpha=\infty$$) 에너지는 0 < E < $\alpha$ 조건식을 만족해야 한다.

• Continous time ➡️ $$\int_{-\alpha}^{\alpha}|{x(t)|^2dt}$$
• Discrete time ➡️ $$\sum_{n=-\alpha}^{\alpha}|{x(n)|^2}$$

Power의 평균값은 $$\frac{Energy}{Time}$$ 을 통해 구할 수 있다.

• Continous time ➡️ $$\lim_{T \to \alpha}\frac{1}{T}\int_{T}|{x(t)|^2dt}$$
• Discrete time ➡️ $\lim_{N \to \alpha}\frac{1}{2N+1}\sum_{n=N}^{N}|{x(n)|^2}$

• 0 < E < $\alpha$ 이면 *Energy signal이다. *
• E = $\alpha$ 이고 0 < $Pow_{g}$ < $\alpha$ 이면, Power signal이다. (power signal의 energy는 $\alpha$ 이다.)
• E = $\alpha$ 이고 $Pow_{g}$ 도 $\alpha$ 라면, energy도 아니고 power signal도 아니다.

Problems on Energy and Power signal

위 식의 결과값이 $E=\frac{1}{2a}$로 이 값은 $\alpha(=\infty)$보다 작으므로 위 함수식은 Energy signal을 나타낸다.

위 식의 결과값이 $E=\alpha$, $Pow_{g}$ < $\alpha$를 만족하므로 위 함수식은 Power Signal을 나타낸다.

위 식의 결과값이 $E=\alpha$, $Pow_{g}=\alpha$를 만족하므로 위 함수식은 Engergy Singal도 아니고 Power Signal도 아니다.

순서대로 위 문제들의 나타낸 그래프이다.

• Energy Signal은 0을 향해 나아간다.
• Power Signal은 0이 아닌 특정 값으로 일정(constant)하게 나아간다.
• NENP(Engergy도 Power Signal도 아님)는 무한대를 향해 나아간다.

Problems on discrete time signal

무한 등비 급수 공식을 이용하여 위 식이 나타내는 신호가 무엇인지를 알 수 있다.

무한등비 급수 공식 : $\sum_{n=0}^{\alpha}{x^n}=\frac{1}{1-x}; |x|<1$

$x(n)=a^n u(n)$ 을 가정해보자.

• $a<1$ 이면, Energy Signal이다. (0 < E < $\alpha$)
• $a>1$ 이면, NENP 이다. ($E=\alpha$, $Pow_{g}=\alpha$)
• $a=1$ 이면, Power Signal이다. ($E=\alpha$, 0 < $Pow_{g}$ < $\alpha$)

🧡 Deterministic and Random signal

• 'Deterministic'이란 의미는 식으로 정립이 가능하고 이를 통해 예측 가능하다는 뜻이다.

random signal은 예측 불가능하며 식으로 나타낼 수 없다. 신호는 다음과 같이 분류할 수 있다.

프로그래머스 '모음사전(완전탐색)' 문제 보기

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

문제 설명 👩‍🏫

두 가지 입력 예시를 통해 문제를 어떻게 풀어야 할지 생각해보자.

#1 입력(word): "AAAAE" 출력(result): 6 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

#2 입력(word): "AAAE" 출력(result): 10 "AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

코드 👩‍💻

Solution 1

from itertools import product  # 중복순열

def solution(word):
    lst = list()

    for i in range(1,6):
        for j in product(['A','E','I','O','U'], repeat = i):
            lst.append(''.join(j))
    lst.sort()  # 문자정렬
    return lst.index(word)+1

중복을 허용한 순열을 통해 문제를 풀 수 있다. (product와 repeat) i가 1일 때: A, E, I, O, U로 만든 순열 ➡️ A, E, I, O, U i가 2일 때: A, E, I, O, U로 만든 순열 ➡️ AA, AE, AI, AO, AU, EE, EI, ... i가 3일 때: A, E, I, O, U로 만든 순열 ➡️ AAA, AAE, AAI, AAO, AEA, AEI, AEO, ... ... join을 통해 문자 리스트들을 하나의 문자열로 바꿔주고 lst에 저장한다. ''.join(['A'],['E'])는 'AE'이다. sort()함수를 이용하면 문자가 알파벳 순으로 정렬된다. 이후, 해당 word값이 몇 번째인지 찾아 1을 더하고 정답을 출력한다.

Solution 2

from itertools import product

# lambda를 이용한 solution 함수
solution = lambda word: sorted([''.join(j) for i in range(5) for j in product('AEIOU', repeat=i+1)]).index(word)+1

lambda 표현식

• 함수를 한 줄로 표기할 때 쓰인다. lambda 매개변수 : 표현식

sort함수와 sorted 함수 차이

• sorted 함수는 정렬된 새로운 리스트를 리턴한다.
• sort 메소드는 아무것도 리턴시켜주지 않는다. (None을 리턴)

프로그래머스 '숫자 문자열과 영단어(level 1)' 문제 보기

네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다.

다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다.

• 1478 → "one4seveneight"
• 234567 → "23four5six7"
• 10203 → "1zerotwozero3"

이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ s의 길이 ≤ 50
• s가 "zero" 또는 "0"으로 시작하는 경우는 주어지지 않습니다.
• return 값이 1 이상 2,000,000,000 이하의 정수가 되는 올바른 입력만 s로 주어집니다.

문제 설명 👩‍🏫

두 가지 입력 예시를 통해 문제를 어떻게 풀어야 할지 생각해보자.

#1 입력: "2three45sixseven" 출력: 234567

#1 입력: "123" 출력: 123

1. 문자열 입력을 받는다.
2. 받은 문자열 안에 영단어가 있으면 대치하는 숫자로 바꿔준다.
3. 정수로 출력한다.

코드 👩‍💻

Solution 1

words = ('zero','one','two','three','four','five','six','seven','eight','nine')

def solution(s):
    answer = s
    for idx, word in enumerate(words):
        answer = answer.replace(word, str(idx))
    return int(answer)

enumerate 함수와 replace 함수를 이용하여 idex값과 words 튜플의 원소값을 바꿔준다.

Solution 2

keys = ('zero','one','two','three','four','five','six','seven','eight','nine')
values = ('0','1','2','3','4','5','6','7','8','9')
dic = dict(zip(keys, values))

def solution(s):
    answer = s
    for key, value in dic.items():
        answer = answer.replace(key, value)
    return int(answer)

딕셔너리 함수인 dic.items()를 이용해 key, value에 각각 숫자 문자열, 인덱스 값으로 불러온다.

Solution 3

keys = ('zero','one','two','three','four','five','six','seven','eight','nine')
values = ('0','1','2','3','4','5','6','7','8','9')
dic = dict(zip(keys, values))

def solution(s):
    answer = ''
    word = ''
    for i in s:
        if i.isdigit():
            answer += i
        else:
            word += i
            if word in keys:
                answer += dic[word]
                word = ''
    return int(answer)

기본적인 딕셔너리 구조를 이용해 숫자이면 정답 문자열에 포함하고, 숫자가 아니라면 딕셔너리의 key값(문자열)에 해당하는 value(숫자)를 가져와 정답 문자열에 포함한다.

디지털 신호 처리 연구의 기반이 되는 선수과목, '신호및시스템' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

Classification of signals

1. Continuous time & Discrete time ✅ 2. Real & Imaginary ✅ 3. Periodic & NonPeriodic ✅ 4. Even & Odd 5. Energy & Power 6. Deterministic & Random

🧡 Continuous time & Discrete time

Continuous time

• 모든 시간 t에 대해 함수가 정의된다.

  Discrete time

• 특정 시간 t에 대해 일정한 간격으로 함수가 정의된다.
  

🧡 Real & Imaginary

• $x(t)=3$일 때, $x^(t)=3^=3$ ➡️ Real Signal
• $x(t)=3j$일 때, $x^(t)=3j^=-3j=-x(t)$ ➡️ Odd Signal
• Real Signal이라면 허수부가 0이 되어야하고 Imaginary Signal이라면 실수부가 0이 되어야 한다.

• Complex Signal은 실수부와 허수부를 모두 가지고 있는 신호이다.
• 공식을 통해 $e^{j\Theta}=cos(\Theta)+jsin(\Theta)$를 유도할 수 있다.
  

🧡 Periodic and Aperiodic(AP) signal

• Periodic Signal: 주기성을 가지고 있는 신호
• Aperiodic(AP) Signal: 주기성을 가지고 있지 않고 패턴화 되지 않는 신호

• T는 Time Period를 의미하며 $T=\frac{2\pi}{w}$

• $x(t)=2sin(100\pi t)+3cos(300\pi t)$ ➡️ 2개 이상의 함수들로 이루어진 신호의 주기를 구해보자!

  1. 각 함수별 시간 주기를 구한다. $T_1, T_2, T_3 ...$
  2. $T_1$을 각 주기로 나눈다. $\frac{T_1}{T_2}, \frac{T_1}{T_3}, \frac{T_1}{T_4}$ 이때 유리수(rational number)로 나타낼 수 있으면 $x(t)$는 periodic 함수이다.
  3. 과정 2에서 구한 값에 $T_1$을 곱한 값이 $T_0$이 된다.

  

• 과정 2의 결과가 유리수($\frac{3}{1}$)이므로 Periodic signal이다.

• 과정 2의 결과가 무리수($\frac{2}{\pi}$)이므로 Aperiodic signal이다.

• 과정 2에서 분모의 최소공배수가 2이므로 과정 3에서 $T_1$값에 2가 곱해진다.

Periodity of Discrete time signals

• Discrete time의 경우 m은 N을 정수로 변환하는데 필요한 최소 정수값, N은 time period 안에 존재하는 샘플들의 개수를 의미한다.
• $\frac{m}{N}=\frac{w}{2\pi}$의 값이 유리수(rational number)라면 신호가 periodic한 성질을 갖는다고 할 수 있으며 m과 N의 추정값을 구할 수 있다.
• 식의 결과값이 무리수이므로 AP 신호이다.
• $e^{j\pi}=cos(\pi)+jsin(\pi)=-1$ ➡️ $x[n]=(-1)^n$을 $e^{j\pi}$로 바꿀 수 있다.
• $x[n]=(-1)^n=e^{j\pi n}$ ➡️ $\pi$는 $w$로 바꿀 수 있다.
• $\frac{m}{N}=\frac{\pi}{2\pi}=\frac{1}{2}$로 유리수가 나오므로 이 신호는 Periodic하다.

디지털 신호 처리 연구의 기반이 되는 선수과목, '신호및시스템' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

🧡 Shifting

• $$x(t+t_0)$$ 이면 왼쪽으로 그래프를 이동
• $$x(t-t_0)$$ 이면 오른쪽으로 그래프를 이동

🧡 Time Scaling

• $a$ 가 1보다 크면 확장(Expansion)
• $a$ 가 1보다 작으면 압축(Compression)

🧡 Folding(Time Reversal)

• 세로 축을 기준으로 회전

• 세로 축을 기준으로 대칭이면 변함 없음

• 복합 연산일 경우, Shifting 먼저 적용 후에 Scaling과 Folding 적용
  

🧡 Adding, Subtraction

- Adding

- Subtraction

• gate signal을 step signal 함수 표기 방식으로 나타낼 수 있음
• $Arect(\frac{t}{T})=A[u(t+\frac{T}{2})-u(t-\frac{T}{2})]$
  

🧡 Multiplication

🧡 Differentiation

• unit Ramp function 미분 ➡️ unit Step function 미분 ➡️ unit Impulse function 미분

디지털 신호 처리 연구의 기반이 되는 선수과목, '신호및시스템' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

Signals

• 정보를 전달하기 위한 물리적인 파형
• 수학적 정의
  • 독립변수(Independent variable): Time
  • 종속변수(dependent variable): Function

Basic Signals

• Step Signal
• Ramp Signal
• Impulse Signal
• Parabolic Signal

🧡 Step Signals

• 일정 시간 동안 값이 일정함
  

🧡 Impluse Signals

• 특정 시간 t에 값의 변화가 있음
• 자극으로 인한 짧은 입력 신호가 제공될 때의 출력
• 현실적으로 불가능한 표현

• 신호의 면적이 1
• 현실적인 표현

🧡 Ramp Signals and Parabolic Signals

🧡 All Signals Summary

• Singularity Function: 자연계에서 존재할 수 없는 함수이나, 수학적으로 근사화시킬 수 있는 함수 형태

🧡 Standard Signals

🧡 Gate Signal or Rectangular Signal

• signum function: 수의 부호를 판별하는 함수
  

🧡 Sampling Signal or Sync Signal

• Operations on Signals ➡️ Basic Signal, Standard Signal에 적용
  • Shifting
  • Scaling
  • Folding(time reversal)
  • Add | Sub | Mul
  • Differentiation

인공지능 연구의 기반이 되는 선수과목, '확률및통계' 내용을 복습하기 위해 쓴 글입니다. 내용에 오류가 있을 시, 조언 및 지적해주시면 감사하겠습니다.

1.1 사건

• 통계적 실험(statistical experiment): 통계적 목적 아래 관찰이나 측정을 얻어내는 일련의 과정

• 관찰값(observation): 측정되거나 관찰된 값

• *표본공간(sample space): *측정 가능한 모든 결과들의 집합

  • sample space을 이루는 개개의 실험 결과를 element 또는 sample point라고 함
  • 추출 방법에 따라 비복원추출(without replacement), 복원추출(replacement)로 나눠짐

• 사건(event): 표본 공간의 부분집합으로 어떤 조건을 만족하는 특정한 표본점들의 집합

  • 하나의 표본점으로 구성된 사건 ➡️ 단순사건(simple event), 근원사건(elementary event)
  • 두 개의 표본점으로 구성된 사건 ➡️ 복합사건(compound event)
  • 표본점이 하나도 들어있지 않은 사건 ➡️ 공사건(empty event)
  • $$A \cup B$$ ➡️ A와 B의 합사건(union of events)
  • $$A \cap B$$ ➡️ A와 B의 공집합(intersection of events)
  • $$A - B$$ ➡️ A에는 있으나 B에는 없는 차사건(difference of events)
  • $A^c$ ➡️ **A 안에 있지 않은 표본점으로 구성된 여사건(complementary event)

• *

  • $$A \cap B= \emptyset$$ ➡️ 공통의 표본점을 갖지 않음. 배반사건(exclusive),
    • n 개의 사건 중에서 쌍마다 배반사건(pairwisely mutually exclusive)일 경우도 존재함, 이 합 사건이 표본공간 S인 사건을 분할(partition)이라 함

1.2 확률

• ** 확률(probability)**: 동일한 조건 아래서 동일한 실험을 무수히 반복하여 실시할 때, 어떤 특정한 사건이 발생하는 비율

• 조건부 확률: P(A) > 0 인 어떤 사건 A가 주어졌다는 조건 아래서, 사건 B가 나타날 확률

  • $$P(A \cap B)=P(A)P(B|A)$$

  • $$P(A \cap B \cap C)=P(A \cap B)P(C|A \cap B)=P(A)P(B|A)P(C|A \cap B)$$

  • P(A) > 0 또는 P(B) > 0 일 때 사건 A의 발생여부가 사건 B의 발생에 영향을 미치지 않는 경우 ➡️ A와 B는 독립(independent)

    • $P(A \cap B)=P(A)P(B)$
    • $P(A|B)=P(A), P(B|A)=P(B)$

  • 독립이 아닌 경우 ➡️ A와 B는 종속(dependent)

1.3 베이즈 정리

• 전확률 공식(formula of total probability)
• 베이즈 정리(Bayes' theorem)
  • 베이즈 정리는 사전확률을 통해 더 많은 정보를 수집하는 수단으로 사용될 수 있다는 점에서 중요함

프로그래머스 캐시 문제 보기

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

[입력]

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

[출력]

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

문제 설명 👩‍🏫

두 가지 입력 예시를 통해 문제를 어떻게 풀어야 할지 생각해보자.

#1 캐시 크기 : 3 도시이름 : ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 실행시간 : 50

#2 캐시 크기 : 3 도시이름 : ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] 실행시간 : 21

코드 👩‍💻

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    cache = deque(maxlen=cacheSize)  # maxlen: deque의 길이의 최댓값을 설정

    for c in cities:
        c = c.lower()   # 대소문자 구분 X

        # cache hit - 캐시 내 데이터가 존재할 경우
        # 같은 데이터가 중복해서 들어갈 수 없으므로 remove 후 다시 append 작업
        if c in cache:
            cache.remove(c)
            cache.append(c)
            answer += 1
        # cache miss - 캐시 내 데이터가 존재하지 않을 경우
        else:
            cache.append(c)
            answer += 5
    return answer

백준 1253번 문제 보기

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.

[입력] 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

[출력] 좋은 수의 개수를 첫 번째 줄에 출력한다.

** input #1 ** 10 1 2 3 4 5 6 7 8 9 10
** output #1 ** 8

** input #2 ** 6 0 0 3 3 3 3
** output #2 ** 4

문제 설명 👩‍🏫

문제 설명이라 적고 입력 예제 설명이라 쓴다

두 개의 수의 합으로 나타낼 수 있는 수 = 좋은 수 input #1의 경우 주어진 숫자들 중에서, 1 2 3 4 5 6 7 8 9 10 1과 다른 수를 더했을 때 나올 수 있는 수 : 3,4,5,6,7,8,9,10 2와 다른 수를 더했을 때 나올 수 있는 수 : 3,5,6,7,8,9,10 3과 다른 수를 더했을 때 나올 수 있는 수 : 4,5,7,8,9,10 4와 다른 수를 더했을 때 나올 수 있는 수 : 5,6,7,9,10 5와 다른 수를 더했을 때 나올 수 있는 수 : 6,7,8,9 6과 다른 수를 더했을 때 나올 수 있는 수 : 7,8,9,10 7과 다른 수를 더했을 때 나올 수 있는 수 : 8,9,10 8과 다른 수를 더했을 때 나올 수 있는 수 : 9,10 9와 다른 수를 더했을 때 나올 수 있는 수 : 10
좋은 수는 3,4,5,6,7,8,9,10으로 총 8개

기본 예제인 input #1만 보고 완전 탐색 풀이법을 시도했다. 두 수를 더해서 나올 수 있는 모든 경우를 구한 후, set 자료형을 이용해 중복을 배제하여 좋은 수를 카운트 했는데 낮은 정답률에 이유가 있듯 보기 좋게 틀렸다. 처음에는 이유를 몰라 헤맸었는데 input #2를 보고 어떻게 풀어야 하는지 감이 왔다. 더한 두 수를 제외했을 때, 좋은 수의 존재 여부를 고려해야 했었다.

input #2 의 경우 주어진 숫자들 중에서, 0 0 3 3 3 3 0+0=0인데 만족하는 좋은 수가 존재하지 않는다. 0+3=3으로 각각 4개의 경우의 수가 존재한다. 그러므로 출력값은 4가 된다.

코드 👩‍💻

# 좋은 수의 개수를 세는 함수
def solve():
    cnt = 0
    nums.sort()
    for i in range(len(nums)):
        if search(i, nums[i]):
            cnt += 1
    print(cnt)


# 좋은 수가 들어있는지 탐색하는 함수
def search(i, target):
    temp = nums[:i] + nums[i+1:]  # 타겟이 되는 nums[i]를 제외하고 탐색
    # print(temp)
    left = 0
    right = n-2  # 마지막 인덱스 n-1에서 타겟값 하나 더 빼서 n-2
    while left < right:
        sum = temp[left] + temp[right]
        if target < sum:
            right -= 1
        elif target > sum:
            left += 1
        else:
            # print(i,target)
            return True
    return False


import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
solve()

target 값을 정하고 nums[i] (= target) 값을 제외한 배열에서 left, right 투 포인터를 이용한 탐색을 진행한다. 이런 식으로 풀이하면 input #2에서 두 수의 합이 배열 내에 존재하지 않을 경우를 고려하여 문제를 해결할 수 있다.

어느 왕국의 이웃 나라 외동딸 공주가 숲 속의 괴물에게 잡혀갔습니다. 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매기고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가게 동그랗게 앉게 합니다. 그리고 1번 왕자부터 시계 방향으로 돌아가며 1부터 시작하여 번호를 외치게 합니다. 한 왕자가 K(특정 숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 됩니다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외칩니다.

이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있습니다.

input 8 3

output 7

문제 설명 👩‍🏫

k=3번째 수만 빼준다. 1,2,3,4,5,6,7,8 - 뺀 수 1,2,4,5,6,7,8 - 3 1,2,4,5,7,8 - 6 2,4,5,7,8 - 1 2,4,7,8 - 5 4,7,8 - 2 4,7 - 8 7 - 4

코드 👩‍💻

from collections import deque

def solution(n, k):
    dq = list(range(1, n+1))
    prince = deque(dq)
    while prince:
        for i in range(k-1):
            cur = prince.popleft()
            prince.append(cur)
        prince.popleft()
        if len(prince) == 1:
            return prince[0]


n, k = map(int, input().split())
print(solution(n,k))

양방향에서 더하고 뺄 수 있는 deque 모듈을 이용해서 풀었다. k번째 전까지는 남아있어야 하는 원소이므로 왼쪽의 원소를 빼고 다시 오른쪽에 이어붙인다. k번째 수는 문제에서 설명했던 대로 그냥 빼준다. 이 작업은 deque가 비어있지 않는 동안 계속 반복되고, deque의 길이가 1이 될때 함수 결과값을 return 해줌으로써 끝이 난다.