헤헤

안녕하세요.

오늘은 Anomaly Detection 분야의 논문 중, 최근에 나온 논문으로 제가 관심 있게 본 논문이라서 논문 review를 남기고자 합니다.

대학원에 있을 때는 새로운 논문이 나오면 바로 바로바로바로 follow-up 하곤 했는데, 회사에 다니고 나니 논문을 읽는 것 외에도 워낙 할게 많으니 바로바로 따라가기는 쉽지가 않네요.

그래도 제가 가장 관심 있는 분야라 시간이 되면 틈틈히 새로운 논문들 review 해보도록 하려고 합니다.

Official 코드가 나와있지 않은 관계로, 사람들이 unofficial로 implementation 코드를 만드시는 것 같은데 어느 정도 시간이 흐르고 결과가 유사하게 나오는 시점쯤이 되면 code review도 함께 진행해 보도록 하겠습니다.

https://arxiv.org/abs/2303.14535

1. Abstract

본 논문에서, 저자들은 computational efficiency에 집중하여 현대 GPU에서 1ms 이내로 이미지를 처리할 수 있는 lightweight feature extractor를 제안합니다. 그리고 anomalous feature를 검출하기 위해 stduent-teacher approach를 사용합니다.

저자들은 정상 이미지에서 추출된 feature를 예측하는 student network를 학습시킵니다.

Test time에서 anomaly의 검출은 student network가 추출된 feature를 예측하는데 실패하는 것을 통해 진행됩니다.

저자들은 정상이 아닌 이미지에 대해서 student network가 teacher network를 따라하지 못하도록 만드는 training loss를 제안합니다. 이는 student-teacher model의 computational cost를 대폭 감소시키면서 anomalous feature를 탐지하는 능력은 향상하게 됩니다.

저자들은 추가적으로 물건이 잘못 배치되는 것과 같은 logical anomaly를 잡아내는 문제 또한 다루고 있습니다. 저자들은 이러한 문제를 이미지를 전역적으로(globally) 분석하는 autoencoder를 효율적으로 활용해 검출하게 됩니다.

2. Introduction

최근 classification architecture들은 latency, throughput, memory consumption, 학습 가능한 파라미터의 수와 같은 특성들에 초점을 두고 있습니다. 이는 network들이 real-world application에 적용할 수 있다는 것을 보장하게 됩니다.

하지만, State-of-the-art anomaly detection 방법론들은, anomaly detection 성능을 증가시키기 위해서 computational efficiency를 희생하곤 합니다. 자주 사용되는 기법으로는 앙상블, large backbone의 사용, input image의 resolution을 768x768 사이즈로 올리는 방법들이 있습니다.

Real-world anomaly detection application에서는 방법론의 computational requirement에 제약이 있는 경우들이 많은데, 이는 anomaly를 너무 늦게 찾게 되면 상당한 경제적 피해를 가지고 오기 때문입니다. 예를 들어서, 금속 물질이 경작 기계의 내부에 들어간다거나, 혹은 기계를 작동하는 사람의 신체가 칼날에 접근하는 경우가 발생할 수 있습니다.

게다가 산업 현장에서의 환경은 높은 생산률을 유지하기 위해서 엄격한 runtime limit을 가지고 있는 경우가 많습니다. 따라서, 이러한 제약을 고려하지 않게 되면 생산성 감소를 만들 수 있고, 경제적 가능성을 감소시키게 됩니다. 

그러므로, anomaly detection 방법론이 real-world에서 사용되려면 computational cost에 대해서 필수적으로 고려해야 합니다.

본 논문에서, 저자들은 anomaly detection 성능을 내면서도 inference runtime까지 동시에 고려하는, 새로운 표준이 될 방법론인 EfficientAD를 제안합니다. 

첫 번째로, modern GPU에서 1ms 이내로 expressive feature를 계산하기 위한 efficient network architecture를 도입합니다. 

두 번째로, anomalous feature를 검출하기 위해, student-teacher approach를 사용합니다.

저자들은 정상 이미지에 대해서 pretrained teacher network를 가지고 계산된 feature를 예측하는 student network를 학습합니다. Anomalous image에 대해서는 student network가 학습되지 않았기 때문에, 이러한 이미지에 대해서는 teacher network를 따라 하는 것에 실패하게 됩니다. 따라서, test time때 student network와 teacher network의 output 사이의 큰 distance를 기반으로 anomalous image를 검출하게 됩니다. 

이러한 효과를 더 증가시키기 위해서, 'Asymmetric student-teacher networks for industrial anomaly detection' 논문에서는 teacher network와 student network간 architectural asymmetry를 사용하였는데요. 저자들은 대신에, 정상 이미지가 아닌 이미지에 대해서 student network가 teacher network를 따라 하지 못하게 만드는 training loss를 도입하여 loss-induced asymmetry를 도입하였습니다. 

이 loss는 test time에서 computational cost에도 영향을 주지 않고, architecture design에 제약을 주지 않으며, anomalous feature를 정확히 검출하면서도 student network와 teacher network 모두에 efficient network architecture를 사용할 수 있게 만듭니다.

Anomalous local feature를 확인하는 것은 생산된 제품에 오염이나 얼룩과 같이, 정상 이미지와 구조적으로 다른(structurally different) anomaly를 검출하게 합니다. 하지만, 어려운 문제는 정상 이미지의 position, size, arrangement와 관련된 logical constraint에 대한 이상 여부를 찾아내는 것입니다. 이러한 문제를 해결하고자, EfficientAD는 'Beyond Dents and Scratches: Logical Constraints in Unsupervised Anomaly Detection and Localization' 논문에서 제안된 autoencoder를 사용합니다. 이 autoencoder는 test time에서 학습 이미지의 logical constraint를 학습하고, violation을 탐지하게 됩니다.

저자들은 autoencoder의 구조와 학습 protocol을 단순화 하면서, 어떻게 이를 student-teacher model과 효율적으로 통합할 수 있는지를 논문에서 설명합니다. 또한, autoencoder와 student-teacher model의 detection result를 합치기 전에 보정해서 anomaly detection 성능을 향상할 수 있는 방법 또한 제안합니다.

저자들의 contribution은 다음과 같이 요약해볼 수 있습니다.

- 이미지 한 장당 2ms 이내의 latency를 보여주면서, industrial benchmark에 대해서 anomaly detection과 localization에서 SOTA 대비 상당히 성능을 향상했습니다.

- 최근 anomaly detection 방법론들과 비교했을 때 feature extraction의 속도를 몇 배 향상할 수 있는 efficient network architecture를 제안합니다.

- Inference runtime에 영향을 미치지 않으면서 student-teacher model의 이상 탐지 성능을 상당히 향상시킬 수 있는 training loss를 도입합니다.

- autoencoder 기반으로 효율적으로 logical anomaly를 검출하고, student-teacher model의 검출 결과와 통합한 후 보정할 수 있는 방법을 제안합니다.

3. Related Work

3.1 Anomaly Detection Tasks

간단한 내용이라서, 해당 글에서는 생략하겠습니다. 

3.2 Anomaly Detection Methods

전통적인 컴퓨터 비전 알고리즘은 수십 년간 산업용 이상 탐지 문제에 성공적으로 적용되어 왔습니다. 이러한 알고리즘들은 흔히 이미지 한 장당 몇 ms 이내에 이미지를 처리해야 하는 요구사항을 충족해 왔습니다. Bergmann는 이러한 방법론들을 평가해 보았고, 사물이 똑바로 위치해있지 않은 경우에는 실패한다는 것을 확인하였습니다.

딥러닝 기반의 방법론들은 이러한 케이스에서도 강건하게 작동한다는 것을 보여왔습니다. 최근에 성공적인 방법론들은 pretrained 되고 frozen 된 CNN의 feature space에서 밀도 추정을 하거나 outlier를 검출합니다. 만약 feature vector가 input pixel에 매핑될 수 있다면, 이들의 outlier score를 각각의 pixel에 할당해서 2D anomaly map을 만들 수 있게 됩니다.

최근 방법들은 다변량 정규 분포, Gaussian Mixture Models, Normalizing Flow, kNN 알고리즘을 사용하곤 합니다. kNN은 Nearest Neighbor를 찾는 것에 있어서 runtime을 많이 잡아먹게 되는데, PatchCore는 이를 해결하고자 군집된 feature vector들의 reduced database를 만들어서 여기서만 kNN을 진행하도록 합니다. 

Bergmann은 이상 탐지를 위한 student-teacher (S-T) framework를 제안하였습니다. 여기서 teacher network는 pretrained frozen CNN입니다. 해당 연구에서는 3가지 다른 receptive field 크기를 가진 teacher network를 사용합니다. 각 teacher network는 학습 이미지에서 teacher network의 output을 따라 하는 3개의 student network를 학습시킵니다. 

student network는 이상이 있는 이미지를 학습하는 동안에 본 적 없기 때문에, 이들에 대해서는 teacher network의 output을 예측하는 것에 실패하기 때문에 이를 기반으로 이상 탐지가 가능합니다. Bergmann은 student network의 output의 variance와 teacher network의 output 간의 distance를 가지고 anomaly score를 계산하였습니다. 

S-T framework의 다양한 변형 버전들이 제안되어 왔는데요. Rudolph는 teacher network의 구조를 invertible neural network로 제한시켜서 PatchCore에 버금가는 이상 탐지 성능에 도달하는 데 성공하기도 하였습니다. 본 논문에서는 Asymmetric Student Teacher (AST)  모델과 original S-T method, 그리고 EfficientAD를 비교합니다.

autoencoder나 GAN과 같은 생성 모델 또한 이상 탐지를 위해서 범용적으로 사용되어 왔습니다. 최근 autoencoder 기반의 방법들은 정상 이미지에 대해서는 정확한 복원을, 비정상 이미지에 대해서는 부정확한 복원을 한다는 것에 의존하고 있습니다. 이는 input image에 대한 복원 결과와 비교해서 이상 이미지를 찾아낼 수 있게 만들어줍니다.

이러한 접근법에서 발생하는 흔한 문제는 정상 이미지에 대한 부정확한 복원으로 인해 발생하는 false-positive detection 문제입니다. (정상인데 비정상으로 탐지되는 것이라고 이해하시면 됩니다.) 이를 피하고자, Bergmann은 autoencoder가 pretrained network의 feature space에서 이미지를 복원하도록 하였습니다. 게다가 해당 논문에서는 autoencoder의 output을 예측하는 neural network를 학습시켰는데, 이 network는 normal image에 대한 systematic reconstruction error도 학습하게 됩니다. (논문에서 이 systematic reconstruction error에 대한 설명이 막 자세하진 않은데, 제가 이해하기로는 autoencoder의 output에서 나타나는 global한/거시적인 경향성을 의미하는 것 같습니다. autoencoder의 복원 결과가 전반적으로 흐릿하다면, 이것의 output을 예측하도록 학습된 모델 또한 전반적으로 흐릿한 결과를 뽑게 된다는 것입니다.)

4. Method

저자들은 다음 subsection들에서 EfficientAD의 각 요소들을 설명하고 있습니다. 4.1에서는 pretrained neural network로부터 나오는 feature를 어떻게 효율적으로 추출할 것인지를 다룹니다. 4.2에서는 test time에서 student-teacher model을 사용해서 어떻게 anomalous feature를 검출하는지에 대해서 다룹니다. 주된 난관은 전체적인 runtime을 낮게 가져가면서도 경쟁력 있는 이상 탐지 성능을 가지는 것이었는데요. 이를 위해 student-teacher network를 학습하기 위한 loss function을 도입하였습니다. 이는 inference 시 연산량에 영향을 주지 않으면서 이상 탐지의 성능을 향상하게 됩니다.

4.3에서는 autoencoder 기반의 접근법을 사용해서 어떻게 logical anomaly를 잡는지를 설명합니다. 4.4에서는 student-teacher model과 autoencoder의 탐지 결과를 어떻게 결합하고 보정하는지에 대해서 설명하게 됩니다.

4.1 Efficient Patch Descriptors

최근 이상 탐지 방법들은 보통 WideResNet-101와 같은 pretrained network를 사용하는데요. 저자들은 깊이가 극단적으로 줄여진 네트워크를 feature extractor로 사용합니다. 이는 단 4개의 conv layer로 구성됩니다. 구조는 아래 Figure 2를 참고하시면 됩니다.

각 output 뉴런은 33x33 pixel의 receptive field를 가지고 있기 때문에, output feature vector의 각 요소들은 33x33 patch를 설명하게 됩니다. 이렇게 명확하게 대응되기 때문에, 저자들은 이 네트워크를 patch description network (PDN)이라고 명명했습니다. PDN는 한 번의 forward pass에 가변적인 사이즈의 이미지에서도 feature vector를 뽑아낼 수 있습니다.

'Uninformed Students: Student-Teacher Anomaly Detection With Discriminative Latent Embeddings' 논문에서도 유사하게 몇 개의 conv layer로만 이루어진 네트워크를 사용해서 feature를 뽑았는데요. 이러한 네트워크는 downsampling과 pooling이 없다 보니 꽤 높은 연산량을 요구했습니다. 

해당 논문에서 사용된 네트워크의 파라미터 수가 1.6 million에서 2.7 million 정도로 비교적 낮았지만, GCAD에서 사용했던 31 million 파라미터를 가진 U-Net보다도 시간도 오래 걸리고 메모리도 더 요구하는 것을 실험적으로 확인했습니다. 이는 파라미터의 수가 특정 방법론의 latency, throughput, memory footprint에 대한 적절치 못한 metric이라는 것을 의미한다고 합니다. 

최근 classification architecture들은 대부분 downsampling을 초기에 적용해서 feature map 사이즈를 줄이고, 시간 및 공간 복잡도를 감소시키는 편입니다. 저자들도 유사한 방식을 PDN에 적용, NVIDIA RTX A6000 GPU 기준 256x256 사이즈 이미지에서 feature를 얻는데 800μs가 소요된다고 합니다. (800μs = 0.8ms라고 보시면 됩니다.)

PDN이 expressive feature를 만들게 하기 위해서, 저자들은 deep pretrained classification network를 활용해 knowledge distillation를 적용합니다. ImageNet에 있는 이미지에 대해서 pretrained network에서 뽑은 feature와 PDN의 output 간의 MSE가 최소화되도록 학습이 진행됩니다. 

PDN은 매우 효율적인 것 외에도, 일반 deep network를 사용하는 것과 비교했을 때 또 다른 이점이 있는데요. PDN에서 만들어진 feature vector는 각 픽셀에 대응되는 33x33 patch에만 의존한다는 것입니다. 반면에, pretrained classifier에서 나온 feature는 이미지의 다른 부분에도 long-range dependency를 가지게 되죠. 이는 Figure 3을 보면 확인할 수 있습니다.

Figure 3의 위쪽 행은 output의 중심부에 위치한 1개의 feature vector에 대해서 각 input pixel에 대한 gradient를 나타낸 것입니다. 예를 들어서 모델의 output이 28x28이라고 하면, 아마 (14, 14)에 위치한 feature vector를 얘기하는 것 같은데요. 해당 vector 값에 대한 각 input pixel의 gradient 값을 시각화한 것으로 보입니다. 

DenseNet이나 WideResNet을 보시면, 해당 feature vector에 대한 gradient가 input image의 정중앙 pixel 외에도 꽤나 넓은 범위에 걸쳐서 분포해 있는 것을 알 수 있습니다. 위에서 언급된 대로, 이미지의 다른 부분에도 dependency가 있다는 게 바로 이런 의미입니다. 반면에, PDN은 매우 국소 부위만 영향을 미치는 것을 알 수 있으며, 이미지의 나머지 부위들은 gradient가 아주 작은 값인 것으로 보입니다.

이렇게 PDN은 well-defined receptive field를 가지고 있기 때문에, 이미지의 다른 부분들로 인해서 anomaly localization에 악영향을 주는 경우가 없을 것이라고 밝히고 있습니다.

4.2 Reduced Student-Teacher

anomalous feature vector를 탐지하기 위해서 teacher network로는 distilled PDN을 사용하고, 동일한 architecture를 student에도 그대로 적용합니다. 이를 통해서 1ms 이내로 feature를 뽑을 수 있게 됩니다.

그런데, 최근 모델들이 anomaly detection performance를 증가시키고자 사용한 방법들, 예를 들어 여러 개의 teacher network와 student network를 앙상블 한다던가, student와 teacher 간의 architectural asymmetry를 활용한다거나 하는 테크닉이 적용되지 않았습니다. 따라서, 저자들은 연산량에 영향을 주지 않으면서도 성능을 높이는 training loss를 도입했습니다.

저자들은 일반적인 S-T framework에서 학습 이미지의 수를 증가시키면 이상 이미지에 대해서 teacher network를 모방하는 능력이 향상되는 것을 확인했다고 합니다. 이는 이상 탐지 성능을 악화시키죠. 그렇다고 해서 학습 이미지 수를 너무 많이 줄이면 정상 이미지에 대한 중요한 정보를 얻지 못하게 될 수 있죠. 그래서 저자들은 student network에 충분한 이미지를 제공해서 정상 이미지에 대해서는 teacher network를 잘 모방하도록 만들면서, 동시에 anomalous image에 대해서 generalization 하지 못하도록 만들어보고자 했다고 합니다.

Online Hard Example Mining과 유사하게, 저자들은 student network가 teacher network를 가장 잘 못 따라 하는 부분만 loss에 영향을 주도록 했습니다. 즉, 가장 높은 loss값을 가진 output element만을 loss에 활용한다는 것입니다.

이를 수식으로 표현하자면, teacher network $T$와 student network $S$가 있고 training image $I$가 있으면, 각각은 $T(I) \in R^{C \times W \times H}$, $S(I) \in R^{C \times W \times H}$를 만들어 내게 됩니다. 각 $(c, w, h)$에 대해서 squared difference는 $D_{c, w, h} = (T(I)_{c, w, h} - S(I)_{c, w, h})^2$로 계산됩니다. 

mining factor $p_{hard} \in [0, 1]$을 기반으로, $D$에서 $p_{hard}$ quantile을 계산합니다. 이를 $d_{hard}$로 표현하고요. 위에서 구한 $D_{c, w, h}$에서 $d_{hard}$보다 크거나 같은 요소들의 평균을 training loss인 $L_{hard}$로 사용하게 됩니다. 

$p_{hard}$의 의미를 생각해 보면, 이를 0으로 했을 땐 일반적인 S-T loss라고 이해할 수 있죠. 실제로 저자들의 실험에서는, 이 값을 0.999로 지정했다고 합니다. 99.9 분위수라고 하니, 매우 높은 값 일부만 사용한 것을 알 수 있습니다. 이 $p_{hard}$의 효과는 Figure 4에서 볼 수 있습니다. 

hard feature loss를 사용하는 효과를 위 사진에서 볼 수 있는데요. 밝기는 backprop을 위해 사용된 feature vector의 차원이 얼마나 사용되었는지를 나타내고 있습니다. 못과 관련이 없는 background에는 하얀 요소들이 없는 것을 확인할 수 있으며, 이는 backprop에 사용되는 요소들이 없다는 것을 의미하고, stduent network의 output과 teacher network의 output 간의 difference가 적다는 것을 확인할 수 있습니다. 그래서 우리가 학습해야 할 사물 쪽 요소만 학습을 진행하게 됩니다.

Inference를 진행할 때 2D anomaly map $M \in R^{W \times H}$은 $M_{w, h} = C^{-1}\Sigma_{c}D_{c, w, h}$로 계산되며, 이는 채널 기반으로 평균을 낸 것이라고 이해하시면 되겠습니다. (표기상 $C^{-1}$로 표기 되어 마치 matrix처럼 보일 수 있지만, 실제로 $C$는 차원의 수 이기 때문에 512와 같은 int입니다. 그래서 실제로는 1/512와 같이 int 값의 역수라고 이해하시면 됩니다.) 

추가적으로, hard feature loss를 적용하면 normal image에 대해서 false-positive detection이 발생하는 경우를 피할 수 있는 장점도 있습니다. (정상이 anomaly로 탐지되는 것을 의미합니다.)

hard feature loss 외에도, 저자들은 loss penalty라는 것을 추가로 적용했는데요. 이는 학습 중에 student가 normal training image에 없는 이미지에 대해서 teacher를 따라 하는 것을 방해하기 위해 적용한다고 합니다. 제가 생각하기에는 조금 독특하다고 느꼈는데, student network의 학습 도중에 teacher network의 pretraining때 사용된 이미지를 학습에 사용합니다. 즉 ImageNet에 있는 이미지 중에 랜덤 하게 뽑아서 이를 학습에 활용한다는 것이지요.

이를 반영한 loss를 계산하면, $L_{ST} = L_{hard} + (CWH)^{-1}\Sigma_{c} \parallel S(P)_{c}\parallel^{2}_{F}$로 계산이 됩니다. 이 penalty는 out-of-distribution image에 대해서 student network가 teacher network를 모방하지 못하게 막는 역할을 합니다. 수식이 조금 어려워 보일 순 있지만, ImageNet에서 뽑은 임의의 이미지가 $P$이고, student network가 $S$이니, $S(P)$는 이미지를 넣어서 나온 output이라고 보시면 됩니다. 이를 제곱을 해주고 channel 기준으로 sum한 다음, $CWH$로 나눠줍니다. 앞에서도 언급드렸지만, $CWH$는 matrix가 아니고 int입니다.

4.3 Logical Anomaly Detection

anomaly 중에서 logical anomaly가 발생할 가능성을 배제할 수는 없는데요. logical anomaly는 물체가 잘못 위치해 있다거나 하는 경우를 얘기합니다. 그래서 이런 경우들까지 탐지할 수 있어야 합니다. 'Beyond Dents and Scratches: Logical Constraintsin Unsupervised Anomaly Detection and Localization.' 논문에서 제안된 것처럼, 저자들은 이를 잡아내기 위한 용도로 autoencoder를 사용합니다. Figure 5에 EfficientAD의 전체 방법론을 나타내주고 있습니다.

Figure 5를 확인해 보면, 앞에서 언급했던 student-teacher pair가 있고, 방금 전에 얘기한 autoencoder를 활용하는 것을 볼 수 있죠. autoencoder는 teacher network의 output을 예측하도록 학습된다고 합니다. 이를 수식으로 표현하자면, 이렇게 표현할 수 있습니다. Autoencoder는 $A$, training image $I$, 이를 활용하면 $A(I) \in R^{C \times W \times H}$를 output으로 뽑게 되죠. 그리고 autoencoder를 학습하는 데 사용할 loss는 $L_{AE} = (CWH)^{-1}\Sigma_{c}\parallel T(I)_{c} - A(I)_{c} \parallel^2_{F}$로 계산할 수 있습니다. $T$는 teacher network라고 하였으니, teacher network의 output과 autoencoder의 output 간 차이를 제곱해서 이를 평균 낸 값이라고 볼 수 있죠. 일반적인 autoencoder 학습에 사용하는 loss와 동일합니다.

student는 PDN이라는 것을 앞에서 언급했었는데요. student는 patch 기반의 network지만, autoencoder는 이미지 전체를 encode 하고 decode 하고 있습니다. 그래서 logical anomaly가 발생한 이미지에 대해서는 autoencoder가 복원을 제대로 못합니다. 하지만, 이러한 문제가 정상 이미지에도 발생하는데요. 이는 autoencoder가 fine-grained pattern 복원을 어려워하기 때문입니다. 이는 Figure 5에서도 확인할 수 있죠.

앞에서 언급했듯이, autoencoder는 teacher network의 output을 유사하게 따라가도록 학습되어 있는데요. 보시면 autoencoder에서 나온 output은 background에 있는 패턴들은 복원이 안된 걸 볼 수 있습니다. 이 부분을 얘기한다고 이해하시면 됩니다.

이런 문제 때문에 teacher network의 output과 autoencoder의 output 간 차이를 그대로 anomaly map으로 활용하기에는 false-positive가 발생할 수 있다고 합니다. 따라서, 저자들은 student network의 output channel의 수를 두배로 늘리고, 이를 autoencoder의 output과 teacher network의 output를 예측하도록 학습하도록 한다고 합니다.

이를 수식으로 표현하자면, $S'(I) \in R^{C \times W \times H}$가 student의 추가적인 output channel이라고 했을 때, student의 추가적인 loss는 다음과 같이 정의됩니다. $L_{STAE} = (CWH)^{-1}\Sigma_{c}\parallel A(I)_{c}-S'(I)_{c}\parallel^{2}_{F}$. 결론적으로 전체 training loss는 $L_{AE}$, $L_{ST}$, $L_{STAE}$의 합이라고 합니다.

이렇게 학습하면 student network는 autoencoder의 정상 이미지에 대한 systematic reconstruction error(예를 들면, 전체적으로 blurry 하게 복원되는 것)은 학습하면서, 동시에 anomaly에 대해서 발생하는 reconstruction error는 학습을 못하게 됩니다. 따라서, autoencoder의 output과 student network의 output 간 차이는 anomaly map으로 활용할 수 있게 됩니다. 이는 global anomaly map으로 부르게 되고요.

student network의 output과 teacher network의 output간 square difference를 계산하고, 이를 channel 기준으로 평균을 내서 이를 local anomaly map으로 활용합니다. 이 두 anomaly map을 결합해서 활용하고, maximum value를 image-level anomaly score로 활용합니다.

4.4 Anomaly Map Normalization

local과 global anomaly map이 있기 때문에, 이 둘을 통합해서 사용하기 전에 유사한 scale로 변경이 필요합니다. 이는 Figure 5에 나타난 것처럼, 양쪽 anomaly map 중에서 한쪽에서만 anomaly가 검출되었을 경우 중요하게 된다고 합니다. 그 외에도, 한 map에서의 noise가 결합된 map에서 정확하게 탐지하는 것이 어렵게 만들 수 있습니다.

정상 이미지에서의 noise의 scale을 추정하기 위해서 validation image를 별도로 사용한다고 합니다. 이들은 학습 셋에는 없는 이미지고요. 두 가지 anomaly map 각각에 대해서, validation image 전체에 대해서 모든 pixel anomaly score를 계산합니다. 그러고 나서 각각 계산된 pixel anomaly score(local, global)에 대해서 두 개의 $p$ qunatiles를 계산하는데, $q_{a}$는 anomaly score 0에 맵핑되고, $q_{b}$는 0.1에 맵핑되는 값입니다. test time에는, 계산된 각각의 맵핑에 맞춰서 normalized 된다고 보시면 됩니다. 뒤에 experiment 부분에서 보면, $q_{a}$는 0.9 quantile, $q_{b}$는 0.995 quantile을 선택해서 사용하는 것을 알 수 있습니다.

5. Experiments

실험 부분은 아주 간단하게만 정리하고 넘어가려고 합니다. 크게 EfficientAD-S와 EfficientAD-M이 있다는 점만 알아두시면 되고, EfficientAD-M은 conv layer의 커널 수를 두배로 늘린 것입니다. 뒤에 보시면 S와 M 각각 레이어 구성에 대해서도 다 자세히 나와 있습니다. 실험은 MVTec AD, VisA, MVTec LOCO 데이터셋에서 진행하였고요.

Table 1은 3개의 데이터 셋 전체에 대해서 평균 성능을 보여주고 있고, 나머지 방법론에 비해서 EfficientAD가 좋은 성능을 낸다는 점을 확인할 수 있습니다. 

Table 1에 대한 세부적인 내용이 Table 2에 적혀있네요. MVTec AD에 대해서는 PatchCore, PatchCore ensemble, AST 모두 98 후반대가 나오고 있어서 이미 성능 기준으로는 saturation 된 상황인데, MVTec AD LOCO 데이터셋에 대해서 성능 차이가 심합니다. 아마 LOCO는 logical anomaly가 많아서, 기존 방법론으로는 탐지가 어려운 것이 아닐까 생각됩니다. 그래서 3개 데이터 셋에 대한 평균을 내니까 EfficientAD가 SOTA로 찍히는 모습입니다.

여러 가지 GPU에 대해서 Latency를 비교한 표입니다. EfficientAD가 가장 낮은 수준을 나타내고 있습니다. 

Table 4는 GCAD라는 모델에서 Ablation study를 진행한 모습입니다. 각각의 요소를 반영할 때마다 성능의 변화와, Latency의 변화를 보여주고 있습니다. 이 부분을 제대로 이해하려면 GCAD라는 모델에 대해서도 자세히 알면 더욱 이해하기가 쉽겠네요. 저는 아직 읽어본 논문이 아니라서 대략 감만 잡는 정도로 읽고 넘어갔습니다.

6. Conclusion

강력한 이상 탐지 성능과 매우 높은 연산 효율성으로 무장한 EfficientAD를 소개하는 논문이었습니다. 이는 logical anomaly와 structural anomaly를 모두 탐지하는 새로운 표준이 될 것으로 보이고요. 

강력한 이상 탐지 성능과 높은 연산 효율성을 기반으로 하면 이를 실제 application 환경에서 적용하기에 좋을 것으로 보이네요. 추가로 논문에서 제안한 PDN를 활용하면, 다른 이상 탐지 방법론에서도 latency를 줄이는데 도움이 될 것이라고 합니다.

7. Limitations

Student-teacher model과 autoencoder는 각각 다른 유형의 anomaly를 탐지하도록 설계가 되어 있는데요. Autoencoder는 logical anomaly를, student-teacher network는 fine-grained structural anomaly를 탐지하는 역할입니다. 하지만, fine-grained logical anomaly는 여전히 도전적인 문제로 남아 있는데요. 예를 들면 2mm만큼 더 긴 나사 같은 게 있겠죠. 이런 것들을 잡아내려면, 전통적인 측량 방법론들을 사용해야 한다고 합니다.

최근 이상 탐지 방법론들과 비교했을 때 한계점으로는, kNN 기반 방법론들과는 대조적으로 autoencoder를 별도로 학습해야 합니다. 

여기까지 해서 EfficientAD 논문을 정리해 보았습니다.

기존 방법론들이 단순히 pretrained CNN model에서 feature extraction을 하던 것에서 knowledge distillation을 통해 더 단순한 모델을 활용해서 feature extraction이 가능하도록 만들었다는 점이 굉장히 인상적이었고요.

또 일반적인 결함 외에도 logical anomaly까지 잡아내기 위해서 autoencoder까지 end-to-end로 연결한 process를 만들었다는 점도 흥미로웠던 것 같습니다.

논문 내용을 어느 정도 이해하셨다면, 논문 뒤에 있는 Appendix A을 확인해 보시면 전체 프로세스를 pseudo-code 형식으로 정리한 내용이 있습니다. 논문에서 언급된 요소들이 실제 어떤 흐름으로 진행되는지를 확인하실 수 있습니다.

추후 또 흥미로운 이상 탐지 논문을 발견하게 되면 리뷰를 진행해 보겠습니다.

감사합니다.

안녕하세요. 오늘은 크레인 인형뽑기 게임이라는 문제를 풀어보려고 합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/64061

해당 문제는 2019 카카오 개발자 겨울 인턴십 코딩테스트에 나왔던 문항입니다.

문제 풀이:

def solution(board, moves):
    answer = 0
    crab_lst = []
    
    for m in moves:
        for i in range(len(board)):
            if board[i][m-1] != 0:
                crab_lst.append(board[i][m-1])
                board[i][m-1] = 0 # 인형을 뽑았으니 0으로 처리
                
                # 뽑은 인형이 2개 이상일 때만 터짐 발생
                if len(crab_lst) > 1:
                    if crab_lst[-1] == crab_lst[-2]: # last 2개가 같으면
                        crab_lst.pop()
                        crab_lst.pop()
                        answer += 2
                        
                break # 한 번 뽑았다면 다음 move로 넘어가야 함
                        
    return answer

먼저 우리가 몇 번째 위치에서 인형을 집을지 저장해 둔 moves에서 for문을 진행합니다.

주의해야 할 점은, moves는 n번 위치를 나타내기 때문에 실제로 우리가 board 배열에서 해당 위치를 찾을 때는 -1 해줘야 한다는 점입니다. (list에서는 첫 번째가 index 기준 0이므로)

다음으로는 board의 길이 만큼 for문을 진행하게 되는데, 이는 moves에서 지정된 위치에서 board의 맨 위부터 내려가면서 인형이 있는 위치를 찾아가는 것이라고 생각해 주시면 됩니다.

그래서 if board[i][m-1] != 0이 나오게 됩니다. 즉, 0이 아닌 경우(인형이 있는 경우)에 도달하면 if문에 걸리게 되는 것이죠.

인형이 있으면, 이를 뽑힌 인형이 저장되는 crab_lst에 저장해 주고, 인형이 뽑혔으므로 해당 위치는 인형이 없어지게 되니 이 자리를 0으로 채워줍니다.

그리고 문제에서 만약 뽑힌 인형이 동일한 두개가 연달아 있으면 인형이 사라진다고 했으므로, crab_lst가 2 이상은 되어야 인형이 터지는 일이 발생합니다. 이를 반영해 if len(crab_lst) > 1 : 의 조건을 걸어줍니다.

list이므로 가장 마지막과 마지막에서 두 번째는 [-1]와 [-2]로 index 접근이 가능하며, 둘이 같으면 pop으로 빼주고 answer에 2를 더해줍니다.

그리고 break를 꼭 해줘야 하는데, 이는 해당 번째 위치에서 인형은 한 번만 뽑기 때문입니다. 해당 break가 없으면 moves에 해당하는 m 번째 위치에서 인형을 계속 뽑게 됩니다.

이번 문제는 여기까지 정리하도록 하겠습니다.

감사합니다.

안녕하세요. 오늘은 키패드 누르기라는 문제를 정리해 보도록 하겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/67256

크게 어려운 문제는 아니나, 카카오 스러운(?) 문제라서 정리해보고자 합니다.

전체 풀이:

def distance(start, end):
    mat = [["1", "2", "3"],
          ["4", "5", "6"],
          ["7", "8", "9"],
          ["*", "0", "#"]]
    start_loc = []
    end_loc = []
    dist = 0
    for idx, r in enumerate(mat):
        if str(start) in r:
            start_loc.append(idx)
            start_loc.append(r.index(str(start)))
        
        if str(end) in r:
            end_loc.append(idx)
            end_loc.append(r.index(str(end)))

    dist = abs(end_loc[0]-start_loc[0]) + abs(end_loc[1]-start_loc[1])
    return dist
    
    

def solution(numbers, hand):
    answer = ''
    left_list = ["1", "4", "7"]
    right_list = ["3", "6", "9"]
    center_list = ["2", "5", "8", "0"]
    r_loc = "#"
    l_loc = "*"
    
    for idx, num in enumerate(numbers):
        if str(num) in left_list:
            answer += "L"
            l_loc = str(num)
        elif str(num) in right_list:
            answer += "R"
            r_loc = str(num)
        else: # center에 해당하는 경우
            dist_l = distance(l_loc, num)
            dist_r = distance(r_loc, num)
            if dist_l < dist_r:
                answer += "L"
                l_loc = str(num)
            elif dist_l > dist_r:
                answer += "R"
                r_loc = str(num)
            else:
                if hand == 'left':
                    answer += "L"
                    l_loc = str(num)
                else:
                    answer += "R"
                    r_loc = str(num)
    
    
    
    return answer

문제에서 정의하기로는 좌측에 위치한 1, 4, 7인 경우는 무조건 왼손으로, 3 6 9인 경우는 무조건 오른손으로 타이핑하면 된다고 했기 때문에, 이런 경우는 단순히 if문을 통해서 해결하면 됩니다.

이때, answer만 갱신하는 것이 아니라, 왼손과 오른손의 위치 또한 갱신해주어야 합니다.

2, 5, 8, 0의 경우는 오른손과 왼손 중 가까운 손을 사용해야 하기 때문입니다.

만약 왼손이나 오른손으로 확정되지 않는, 2, 5, 8, 0의 경우는 거리를 계산해야 하는데요.

이 부분은 별도로 distance라는 함수로 빼서 정의하였습니다.

def distance(start, end):
    mat = [["1", "2", "3"],
          ["4", "5", "6"],
          ["7", "8", "9"],
          ["*", "0", "#"]]
    start_loc = []
    end_loc = []
    dist = 0
    for idx, r in enumerate(mat):
        if str(start) in r:
            start_loc.append(idx)
            start_loc.append(r.index(str(start)))
        
        if str(end) in r:
            end_loc.append(idx)
            end_loc.append(r.index(str(end)))

    dist = abs(end_loc[0]-start_loc[0]) + abs(end_loc[1]-start_loc[1])
    return dist

해당 함수는 start 지점부터 end 지점까지의 거리를 계산해 주는 함수입니다.

먼저 키패드에 해당하는 matrix를 문자열로 정의하였습니다. *와 #이 존재하므로, 일괄적으로 문자열로 정의하는 게 낫다고 판단했습니다.

그리고 matrix를 row 단위로 돌면서, 해당 row에 start나 end가 있으면 해당 위치를 (x, y)의 형태로 저장하도록 했습니다.

마지막으로는 |x1-x0| + |y1-y0|을 계산해서 return 하도록 했습니다. 

어차피 한 칸을 이동하는게 1로 계산되고, 별도의 제약이 없기 때문에 이렇게 계산해도 충분하다고 판단했습니다. 

일반적인 distance를 계산하는 방식처럼 루트를 사용하거나 하지 않기 때문에, 1칸씩 격자로 이동하기 때문이죠.

이 distance라는 함수를 활용해서 start를 왼손 위치로 잡고, end는 우리가 쳐야 하는 숫자로 입력하면 왼손 기준의 거리를 계산할 수 있고, start를 오른손 위치로 잡고, end를 우리가 쳐야 하는 숫자로 입력하면 오른손 기준의 거리를 계산할 수 있습니다.

이 둘 간의 거리를 바탕으로 왼손과 오른손을 결정하면 됩니다.

문제에 나와 있듯이, 만약 두 거리가 같을 경우는 왼손잡이인지 오른손잡이인지만 판단해서 결정해 주면 되겠죠.

사실상 문제 자체가 어려운 케이스는 아닌데, 2, 5, 8, 0인 경우에 각각 왼손, 오른손으로 부터 해당 키패드까지의 거리를 구하는 코드만 잘 짜면 되는 문제라고 보입니다.

이번 문제는 여기까지 정리하도록 하겠습니다.

감사합니다.

안녕하세요. 오늘은 Level 1 문제인 기사단원의 무기 문제를 풀어보려고 합니다.

문제 자체가 어렵진 않지만, 소수의 개수를 구하는 문제로 소수 구하는 방법에 대해서 다뤄보고자 합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/136798

풀이:

def solution(number, limit, power):
    # number : 기사단원의 수
    # limit: 공격력 제한 수치
    # power: 제한 수치를 초과한 기사가 사용할 무기
    answer = 0
    num_lst = []
    
    # 약수 개수 구하기
    for n in range(1, number + 1):
        prime_num = []
        for i in range(1, int((n**0.5) + 1)):
            if n % i == 0:
                prime_num.append(i) # 앞쪽
                if i != n // i:
                    prime_num.append(n // i) # 뒤쪽

        num_lst.append(len(prime_num)) # 약수 개수 정리
    
    # 약수 개수 모아놓고 limit 넘으면 교체
    for idx, p in enumerate(num_lst):
        if p > limit:
            num_lst[idx] = power
        
    return sum(num_lst)

약수를 구할 때, 1부터 n까지 다 따지면서 나눠지는지 여부를 확인하는 것이 소수의 원리에 맞는 방법입니다.

하지만, 코딩테스트에서 다루는 문제들은 대부분 시간복잡도 문제가 있어 이를 그대로 다 계산하면 시간복잡도 제한에 걸리게 됩니다.

위 문제도 당연히 시간복잡도 이슈에 직면하게 됩니다.

하나의 수는 보통 약수의 짝이 존재합니다.

예를 들어, 8의 약수를 구한다고 한다면 1, 2, 4, 8가 되는데, 1과 8 / 2와 4는 각각 짝으로 생각할 수 있습니다.

따라서, 약수를 구할 때 1부터 8까지 모두 따지는 것보다 짝이 있다는 개념을 활용해서 이를 조금 더 빠르게 판단할 수 있습니다.

그래서 보통 사용하는 방법은, 구하려고 하는 수의 제곱근을 계산하여 제곱근 까지만 계산해 보는 방법입니다.

제곱근이 직관적인 16을 예시로 들겠습니다.

16의 약수는 1, 2, 4, 8, 16입니다. 위에서 설명드린 바와 같이, 1과 16 / 2와 8은 짝입니다. 4는 4와 짝이지만 같은 수 이므로 한 번만 카운팅 하게 되지요.

이처럼 어떤 수의 약수를 생각할 때는, 어떤 수의 제곱근 까지만 생각하면 모든 약수를 구할 수 있다는 것입니다.

이를 코드로 구현한 부분이 이것입니다.

for i in range(1, int((n**0.5) + 1)):
    if n % i == 0:
        prime_num.append(i) # 앞쪽
        if i != n // i:
            prime_num.append(n // i) # 뒤쪽

우리가 구하려는 수는 n이고, n의 제곱근 까지만 반복문을 진행한다는 사실을 알 수 있습니다.

n이 i로 나눠지면, 이를 prime_num이라는 list에 저장합니다.

그리고 이 경우에, 만약 i가 n을 i로 나눈 몫과 같지 않으면, n을 i로 나눈 몫을 소수로 추가합니다.

이를 16을 예시로 들어 설명 드리겠습니다.

for i in range(1, 4+1) 이 될 것이고, 첫 번째로 16이 1로 나눠지는지를 검토합니다. 이때 나눠지므로, 소수로 인정합니다.

그리고 1이 16을 1로 나눴을 때의 값과 다른지 확인합니다. 이 때는 다르므로, 16을 1로 나눈 16도 소수로 인정합니다.

두 번째로 16이 2로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.

그리고 2가 16을 2로 나눴을 때의 값(8)과 다른지 확인, 다르므로 8도 소수로 인정합니다.

세 번째로 16이 3으로 나눠지는지를 검토합니다. 안되므로 넘어갑니다.

네 번째로 16이 4로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.

그리고 4가 16을 4로 나눴을 때의 값과 다른지 확인합니다. 이 때는 같기 때문에 소수에 추가하지 않습니다.

if i != n // i를 하는 이유를 4의 케이스를 생각해 보시면 이해가 빠를 것 같습니다.

문제에서 일단 약수의 개수를 list로 만들어주고, limit보다 큰 경우는 power라고 하는 변수 값으로 바꿔준 다음 sum 해주면 문제 풀이는 끝이 납니다.

사실상 시간 복잡도의 제약에 걸리지 않고 소수의 개수를 구할 수 있는지가 관건인 문제라고 보시면 됩니다.

오늘 문제는 여기까지 하겠습니다.

안녕하세요. 오늘은  Level 1 문제인 덧칠하기 문제를 풀어보려고 합니다.

처음에 굉장히 단순하게 풀었으나, 시간 복잡도 이슈 때문에 추가적으로 고민이 필요했던 문제였습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/161989

처음에 풀었던 풀이:

def solution(n, m, section):
    answer = 0
    
    while section: # section이 남은 경우만 반복
        start_point = section[0] # 출발 지점
        
        # 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
        if start_point + (m-1) > n:
            start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
        
        # m만큼 진행하기 
        for i in range(m):
            arrival = start_point + i
            if arrival in section:
                section.remove(arrival) # 있으면 제거
        
        answer += 1    
    return answer

일단 section이 남은 경우에만 계속 진행하면 되기 때문에, while에서 section의 길이를 받아 1보다 클 때만 반복문이 진행되도록 하였습니다.

그 후, section은 오름차순 정렬 되어 있으므로, 첫 번째 요소를 start_point로 잡았습니다.

단, start_point에서 m만큼 갔을 때 이것이 n을 넘는 경우가 발생할 수 있습니다.

이런 경우 if 문으로 따로 빼서, start_point의 값을 조정해 주는 작업을 진행하였습니다.

예를 들어, n이 3이고 m이 3이면서 section이 [2]라면, start_point가 2로 잡힐 것이고, 여기서 3칸을 칠하게 되면 2, 3, 4의 3 칸을 칠해야 하는 상황이 되므로 n을 넘게 됩니다.

그래서, 넘친 만큼인 1 만큼을 빼줘서 start_point를 1로 조정하고, 여기서 3칸을 칠하게 만들면 됩니다.

다음으로는, m만큼 칠해야 하니 반복문을 통해서 진행해 주고, 도착지점을 arrival로 저장, 만약 arrival이 section에 있다면 이를 remove 해주는 방식으로 진행하였습니다.

하지만, 약 6개 정도의 test case에서 시간 에러가 나는 문제가 발생했습니다.

그래서 어떤 부분이 문제일까.. 하고 고민해 보니 arrival이 section에 있는지 판단하는 in이 문제가 될 수 있겠다고 판단했습니다.

왜냐하면 in의 경우 list 안의 위치를 찾아야 하는데, 만약 section이 매우 크다면 한번 작업에 많은 연산을 요구하게 됩니다.

문제에서 1 <= section의 길이 <= n로 되어 있는데, n이 최대 10만이 가능하니 remove 연산은 10만 개짜리 list에서 하나를 찾는 작업을 계속해서 반복해야 합니다.

따라서 이 부분을 개선하는 방향으로 고민하였습니다.

개선된 풀이:

def solution(n, m, section):
    answer = 0
    
    while section: # section이 남은 경우만 반복
        start_point = section[0] # 출발 지점
        
        # 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
        if start_point + (m-1) > n:
            start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
                
        target_section = section[:m] # section에서 최대한 지워져도 m개 까지만 가능하니까.
        
        # target_section에서 m개 범위 안에 들면 제거
        for tar in target_section:
            if start_point <= tar <= start_point + m - 1:
                section.remove(tar)

        answer += 1

    return answer

일단 모든 section을 다 돌지 않아야 한다는 게 이전 풀이에서의 교훈이기 때문에, 그럼 과연 section을 다 돌지 않으려면 어떻게 해야 하는가 를 고민했습니다.

start_point 지점 기준으로 결국 m개만 칠하게 되는 것이고, 이는 결국 section에서 m개만 검토하면 된다는 결론이 나옵니다. 왜냐면 section은 이미 오름차순 정렬이 되어 있기 때문에, m개보다 더 많은 양은 검토할 필요가 없습니다.

따라서 지울지 말지 검토해야 하는 section을 target_section으로 만들고, m개만 뽑아냈습니다.

section[:m]으로 하게 되면, 혹시라도 section이 m개 보다 작더라도 에러가 나지 않습니다. 

그리고 target_section에 있는 각각 요소들을 start_point 기준으로 m개 색칠하는 범위 내에 들어가 있는지를 판단해서 제거해 주는 방식으로 진행했습니다.

이렇게 수정하였더니, 시간 복잡도 문제가 해결되었습니다.

오늘 문제는 여기까지 하겠습니다.

안녕하세요.

이번에는 다트 게임이라고 하는 문제를 풀어보려고 합니다.

저는 문제에 나온 그대로 구현을 해봤는데, 다른 답안을 보니 정규표현식을 이용해서 푼 답안이 있어 이를 같이 소개해드리고자 합니다.

정규식은 다양한 문자열 관련 문제에 활용될 수 있는 만큼, 이번 기회에 잘 알아두면 도움이 많이 될 것 같습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/17682

제가 푼 풀이:

def solution(dartResult):
    answer = 0
    
    num = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    s_ = [] # score 저장
    b_ = [] # 보너스 저장
    o_ = [] # 옵션 저장
    
    # 문자열이 존재하는 경우 while문
    while dartResult:
        # 숫자 관련
        if len(dartResult) >= 2 and str(dartResult[:2]) == '10':
            s_.append(10); dartResult = dartResult[2:] # 첫 번째 숫자 10으로 빼고 문자열 밀기
        elif int(dartResult[0]) in num:
            s_.append(int(dartResult[0])); dartResult = dartResult[1:]
            
        # 보너스 관련
        if str(dartResult[0]) == 'S':
            b_.append('S')
        elif str(dartResult[0]) == 'D':
            b_.append('D')
        elif str(dartResult[0]) == 'T':
            b_.append('T')
        dartResult = dartResult[1:] # 얘는 공통이라
        
        # 옵션 관련
        if len(dartResult) >= 1 and str(dartResult[0]) == '*':
            o_.append('*')
            dartResult = dartResult[1:]
        elif len(dartResult) >= 1 and str(dartResult[0]) == '#':
            o_.append('#')
            dartResult = dartResult[1:]
        else:
            o_.append(" ")
    
    sol_ = []
    
    for i in range(3):
        # 제곱 작업 우선 진행
        if b_[i] == 'S':
            sol_.append(s_[i] ** 1)
        elif b_[i] == 'D':
            sol_.append(s_[i] ** 2)
        elif b_[i] == 'T':
            sol_.append(s_[i] ** 3)
    
    
    for i in range(3):
        # 아무것도 없는 경우, 아무 작업 안함
        if o_[i] == " ":
            continue
        
        # 첫 번째 나오고 스타상인 경우
        if o_[i] == '*' and i == 0:
            sol_[i] = sol_[i] * 2
        elif o_[i] == '*' and i != 0:
            sol_[i-1] = sol_[i-1] * 2 # 전에 얻은 점수 2배
            sol_[i] = sol_[i] * 2 # 해당 점수 2배
        
        # 아차상
        if o_[i] == '#':
            sol_[i] = sol_[i] * -1    
    
    return sum(sol_)

딱 봐도 문제 풀이 자체가 매우 긴 것을 확인하실 수 있습니다.

정직하게 문제에 나온 그대로를 코드로 구현한 것이라고 볼 수 있는데요.

score와 보너스, 옵션을 저장할 list를 별도로 지정하고 문자열에 대해서 while문을 돌면서 이 문자열을 score와 보너스, 옵션으로 분해하는 작업을 우선적으로 진행합니다.

먼저 숫자 관련 부분을 보시면, 

 while dartResult:
        # 숫자 관련
        if len(dartResult) >= 2 and str(dartResult[:2]) == '10':
            s_.append(10); dartResult = dartResult[2:] # 첫 번째 숫자 10으로 빼고 문자열 밀기
        elif int(dartResult[0]) in num:
            s_.append(int(dartResult[0])); dartResult = dartResult[1:]

문자열의 길이가 2 이상이고(해당 조건 없으면 dartResult [:2]에서 index 에러가 발생합니다), 앞에 두 글자가 10인 경우는 score 부분을 10으로 append 하고, 문자열을 밀어줍니다.

10이 아닌 0부터 9인 경우는 in num으로 조건을 걸어서 숫자를 빼는 식으로 진행했습니다.

# 보너스 관련
        if str(dartResult[0]) == 'S':
            b_.append('S')
        elif str(dartResult[0]) == 'D':
            b_.append('D')
        elif str(dartResult[0]) == 'T':
            b_.append('T')
        dartResult = dartResult[1:] # 얘는 공통이라

보너스 관련해서는 그다음 문자열이 S D T 중 하나이면 이를 보너스 관련 list에 추가해 주고, 문자열을 하나 밀었습니다.

S D T 중 뭐든 간에 1칸을 밀어주니 if 문에 넣지 않고 if문 바깥쪽에 미는 코드를 위치했습니다.

# 옵션 관련
        if len(dartResult) >= 1 and str(dartResult[0]) == '*':
            o_.append('*')
            dartResult = dartResult[1:]
        elif len(dartResult) >= 1 and str(dartResult[0]) == '#':
            o_.append('#')
            dartResult = dartResult[1:]
        else:
            o_.append(" ")

옵션 관련해서는 * 이거나 #인 경우 이를 옵션 관련 list에 추가하도록 했습니다.

len을 점검하는 코드가 있는 이유는, 옵션은 선택사항이라 옵션 자체가 아예 없는 경우가 있습니다. 이럴 때는 dartResult에 문자열 자체가 안 남아버려서 dartResult [0]로 접근이 안되고 index 에러가 발생합니다. 따라서 이를 방지하고자 문자열이 1개 이상 남은 경우에만 뽑아내도록 했습니다.

sol_ = []
    
    for i in range(3):
        # 제곱 작업 우선 진행
        if b_[i] == 'S':
            sol_.append(s_[i] ** 1)
        elif b_[i] == 'D':
            sol_.append(s_[i] ** 2)
        elif b_[i] == 'T':
            sol_.append(s_[i] ** 3)

그다음 부분은 먼저 제곱 작업을 우선적으로 진행해서, 값들을 sol_에 추가했습니다.

for i in range(3):
        # 아무것도 없는 경우, 아무 작업 안함
        if o_[i] == " ":
            continue
        
        # 첫 번째 나오고 스타상인 경우
        if o_[i] == '*' and i == 0:
            sol_[i] = sol_[i] * 2
        elif o_[i] == '*' and i != 0:
            sol_[i-1] = sol_[i-1] * 2 # 전에 얻은 점수 2배
            sol_[i] = sol_[i] * 2 # 해당 점수 2배
        
        # 아차상
        if o_[i] == '#':
            sol_[i] = sol_[i] * -1    
    
    return sum(sol_)

옵션에 별도로 없는 경우는 아무 작업 안 하고 continue로 넘어가도록 하였고,

*이 첫 번째 나오는 경우는 자기 자신의 값만 2배, *이 첫 번째가 아닌 곳에 나오는 경우는 전에 얻은 점수와 지금 점수를 모두 2배 하도록 했습니다.

그리고 #이 나오는 경우는 -1을 곱해주도록 했고, 마지막에는 sum 해서 결과가 나오도록 했습니다.

어떻게 보면 문제에 나온 내용을 말 그대로 충실히 진행해서 나온 코드라고 보시면 될 것 같습니다.

하지만 코드 수가 길고, 효율적이지는 못해서 더 효율적인 코드가 필요합니다.

개선된 코드:

import re

def solution(dartResult):
    bonus = {'S' : 1, 'D' : 2, 'T' : 3}
    option = {'' : 1, '*' : 2, '#' : -1}
    p = re.compile('([0-9]+)([SDT])([*#]?)')
    dart = p.findall(dartResult)
    for i in range(len(dart)):
        if dart[i][2] == '*' and i > 0: # i가 0보다 클때는 전에꺼 2배 해줌
            dart[i-1] *= 2
        dart[i] = int(dart[i][0]) ** bonus[dart[i][1]] * option[dart[i][2]] # 보너스로 제곱해주고 option에 맞게 곱해줌

    answer = sum(dart)
    return answer

개선된 코드는 정규표현식을 활용한 코드입니다.

이는 p = re.compile() 코드를 보시면 알 수 있습니다.

정규표현식을 compile하는 re.compile은 ( )를 통해 구분이 되는데요. 즉, 해당 코드에서는 크게 ([0-9]+) 부분과 ([SDT]) 부분, ([*#]?) 부분으로 총 3 부분으로 나눠집니다.

[0-9]는 0부터 9까지 숫자 중에 일치되는 경우를 찾는 정규표현식입니다. 여기서 +는 1개 이상을 뜻하므로, ([0-9]+)는 숫자이면서 1개 이상인 경우를 찾게 됩니다.

+가 들어가서 0~9인 숫자 뿐만 아니라 10인 경우도 찾을 수 있게 됩니다.

다음으로 ([SDT])는 S D T 중에 일치되는 경우를 찾게 되는 정규표현식입니다.

마지막으로 ([*#]?)는 두 번째 정규표현식 파트와 비슷하니 대충 유추하실 수 있겠지만, *이나 #인 경우를 찾습니다.

단, ? 는 나오지 않을 수도 있고, 1번 나올 수도 있습니다.

문제에서 옵션의 경우 *이거나 #이고, 혹은 아예 없을 수 있다고 했기 때문에, 이를 구현하기 위해 ?를 사용했다고 볼 수 있습니다.

1개 이상일 때는 +를, 0개 혹은 1개 일 때는 ?를 사용한다고 기억하면 좋겠습니다.

그러고 나서 p.findall()를 활용해 dartResult에서 compile 한 정규표현식 규칙을 만족하는 경우를 모두 찾은 것을 dart에 저장합니다.

 dart를 print 해보면 다음과 같이 나오는 것을 확인할 수 있습니다.

보시면 전체적으로는 list이고, 안에는 3개의 element로 이루어진 튜플인 것을 알 수 있습니다.

이에 대해서 for문을 수행하게 됩니다.

다음으로 if dart[i][2] == '*' and i > 0: 부분인데요. 이는 i가 0보다 클 때는 *이 적용되었을 때 이전 score에도 2배를 해줘야 하기 때문에 dart[i-1] *= 2를 해준다고 보시면 됩니다.

그리고 dart[i] = int(dart[i][0]) ** bonus[dart[i][1]] * option[dart[i][2]]로 구현을 해서 최종 마지막 점수를 내는 것을 확인할 수 있습니다.

score 값에 bonus에 해당하는 dictionary에서 찾아 이를 제곱으로 곱해주고, 마지막으로 option에 해당하는 *이나 #인 경우는 2배 혹은 -1배를 적용해 주는 코드입니다.

마지막으로는 sum을 해서 결과를 내주면 됩니다.

확실히 정규표현식을 활용하면 조금 더 손쉽게 score와 보너스, 옵션을 찾을 수 있었고, 이를 dictionary를 활용해서 간편하게 최종 점수를 계산할 수 있었습니다.

이번 문제는 여기까지 하도록 하겠습니다.

안녕하세요. 오늘은 Level 1 문제인 실패율 문제를 풀어보려고 합니다.

이번 문제는 어떻게 접근하느냐에 따라서 시간 복잡도 관점에서 차이가 많이 있어 이 부분을 중점적으로 보려고 합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42889#

제가 푼 풀이:

def solution(N, stages):
    fail = {}
    
    for i in range(1, N+1):
        pass_cnt = 0
        succ_cnt = 0
        for s in stages:
            # stage가 i보다 크면 지나왔고, 해당 스테이지도 성공한 것
            if s > i:
                pass_cnt += 1
                succ_cnt += 1
            # 같기만 하면 지나오기만 한 것
            elif s == i:
                pass_cnt += 1
        
        # 한번도 안 지나간 stage는 0으로 처리해야 하므로 별도로 if문으로 뺀다
        if pass_cnt != 0:
            fail[i] = (pass_cnt - succ_cnt) / pass_cnt
        else:
            fail[i] = 0
    
    fail_rate = sorted(fail, key=lambda x: fail[x], reverse = True)
    
    return fail_rate

스테이지가 N개 있으므로, N개에 대해서 for문을 진행해야 하는 문제입니다.

반복문을 진행할 때, pass를 몇 명 했는지, 스테이지를 깬 사람은 몇 명인지 저장하기 위해서 변수를 설정해 줍니다.

그리고 결과에 대한 list인 stages에 대해서 반복문을 적용하면서, 각각이 i보다 크면 해당 stage를 지나왔고 성공한 것이므로 각각을 1개씩 올려주며, 같은 경우는 지나오기만 했으므로 pass_cnt를 하나 올려주는 방식으로 접근합니다.

그리고 실패율을 저장하는 dictionary인 fail에 대해서 값들을 저장해 줍니다.

만약 pass_cnt가 0인 경우는 해당 stage에 도달한 사람이 아무도 없으므로, 실패율을 0으로 저장합니다.

마지막으로 fail은 dictionary인데, 이를 for문으로 print 하면 key값이 나오게 됩니다.

그런데 fail의 키 값은 1, 2, 3... 등의 각 stage의 이름이므로, fail의 각 stage를 key로 잡아서 sort를 하면 문제에서 얘기하는 대로 실패율이 높은 순으로 배열을 return 할 수 있습니다.

하지만 위 풀이는 시간 복잡도 관점에서 간당간당하게 풀어진 케이스라, 조금 더 시간 복잡도 관점에서 생각해 볼 필요가 있어서 다양한 코드들을 참고해서 더욱 효과적인 풀이를 만들어냈습니다.

새로 만든 풀이:

from collections import Counter
def solution(N, stages):
    # stage 사람 수 저장
    cnt = len(stages)
    stage_dict = Counter(stages)
    failure = {}
    for i in range(1, N + 1):
        if cnt != 0: 
            # 딱 i인 경우라면 도전은 했지만 못 깬 경우니까 실패율의 분자가 됨.
            failure[i] = stage_dict[i] / cnt
            # stage i에 있는 인원은 그만큼 차감해줌(이미 해당 stage에서 count 했으니까)
            cnt -= stage_dict[i]
        else:
            failure[i] = 0
    
    # dictionary를 그냥 뽑으면 key가 나오게 된다.
    # 그래서 failure[i]를 하면 value 기준으로 sort 되고, 나오는 것은 key가 된다.
    return sorted(failure, key=lambda i: failure[i], reverse=True)

collections 패키지에 있는 Counter라는 함수는 중복된 데이터가 저장된 list에 사용하면 각 원소가 몇 번씩 나오는지 저장된 객체를 만들어 냅니다.

여기서 stages의 경우 중복된 값이 존재하는 경우가 많을 수 있고, 이럴 때는 굳이 모든 요소들을 다 for문으로 살펴볼게 아니라 Counter를 활용하게 되면 말 그대로 stages에 존재하는 요소의 가짓수 정도만 for문을 돌리면 되니까, 최소한 전체를 for문으로 돌리는 것보다는 시간 복잡도를 줄일 수 있게 됩니다.

그리고 풀이 아이디어 관점에서도 변경이 있었습니다.

먼저 stages에 있는 개수를 cnt로 저장하고, stages를 Counter 함수를 이용해서 dictionary 형태의 객체를 만들어냅니다.

그리고 동일하게 N개의 stage에 대해서 for문을 진행합니다.

cnt가 0인 경우는 해당 stage에 도달한 케이스가 0개 이므로, 이는 실패율을 0으로 저장해 줍니다.

그렇지 않은 경우는, stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하고, cnt를 분모로 사용합니다.

저도 처음에 이 내용이 이해가 안 갔는데, 예시를 들어서 생각해 보겠습니다. (첫 번째 Test case)

for문에서 i가 1인 경우 (stage 1인 경우), 현재 stages에서 1인 경우가 1개 있으므로 stage_dict[1]은 1이 될 것이고, cnt는 8이 됩니다. 따라서 이 경우에는 실패율이 1/8로 계산됩니다.

for문에서 i가 2인 경우 (stage 2인 경우), 현재 stages에서 2인 경우가 3개 있으므로 stage_dict[2]은 3이 될 것이고, cnt는 stage 1에서 한 명 있었으니 이를 제외하고 7이 될 것입니다. 따라서 이 경우에는 실패율이 3/7로 계산됩니다.

여기서 stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하는 이유는, stages에서 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타내기 때문입니다.

즉, 해당 스테이지를 도전하고 있는 사람의 수 이기 때문에, 이를 정의된 실패율의 분자인 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수와 동일한 것이죠.

그리고 여기서 카운팅 된 만큼은 전체 인원수에서 빼줘야 하므로, cnt에서 그만큼을 빼주면 됩니다.

마지막으로 실패율이 저장된 dictionary를 value 기준으로 내림차순으로 저장해 주면 정답이 됩니다.

처음 제가 풀었던 답안의 경우 시간 복잡도가 가장 높은 테스트 22에서 8116.53ms를 받았고, 개선한 답안의 경우 테스트 22에서 12.09ms를 받았으니, 거의 600배 이상 시간 복잡도 차이를 보였습니다.

Counter라고 하는 함수를 잘 활용하면, 여러모로 다른 문제에서도 시간 복잡도를 줄일 수 있을 것 같습니다.

오늘 문제는 여기까지 하겠습니다.

안녕하세요.

이번에 다뤄볼 문제는 K번째수 라는 문제입니다.

사실 문제 자체가 어렵지는 않아서, 풀이가 어렵지는 않은데요.

참고한 답안이 워낙 깔끔해서, 이를 한번 짚고 넘어가 보기 위해 글로 정리하게 되었습니다.

문제는 다음과 같습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42748

문제를 한번 보시고, 어떻게 풀면 좋을지 고민해 보신 후 봐주시면 좋을 것 같습니다.

제가 푼 풀이:

def solution(array, commands):
    answer = []
    
    for c in commands:
        answer.append(sorted(array[c[0]-1:c[1]])[c[2]-1])
    
    return answer

문제에서 commands가 주어졌을 때, commands의 모든 원소에 대해서 연산을 적용해야 한다고 했으므로 여기에 대해서 for문을 돌린다고 생각했습니다. 각 요소를 c로 정의했고요.

array에서 c[0]번째 숫자부터 c[1]번째 숫자까지 잘라야 하므로, 이를 array[c[0]-1:c[1]]로 구현했습니다.

우리가 n번째라고 말하지만, python에서는 index가 0부터 시작이므로 -1을 해주어야 합니다.

그리고 이를 정렬한 후, c[2]번째 있는 수를 빼내야 하므로 sorted(array[c[0]-1:c[1]])[c[2]-1]로 구현하였고, answer에 append해서 답을 냈습니다.

참고한 답안:

def solution(array, commands):
    return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

한 줄의 코드로 표현한 답안입니다.

사실 제가 푼 것과 동일하지만, 이를 map과 lambda를 통해서 구현한 코드라고 보시면 될 것 같습니다.

일단 lambda 함수에 대해서 설명해 보자면, def를 활용해서 어떤 이름을 주고 함수를 만들 필요가 없는 경우 사용을 하게 됩니다. 즉, 결국 함수에 해당한다는 것이죠.

이 코드에서 lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1]에 해당하는 것은 x라는 입력이 들어왔을 때, 출력을 sorted(array[x[0]-1:x[1]])[x[2]-1]로 내겠다는 의미입니다.

그리고 map의 경우는, map(함수, list) 형식으로 사용하게 되는데 list에 있는 각 요소들에 대해서 함수를 일괄 적용하겠다는 의미입니다.

즉, 위 코드는 lambda라는 함수를 commands라는 list 안에 있는 요소들에게 모두 적용하겠다. 그리고 이것을 list로 만들어서 return 하겠다는 코드로 보시면 될 것 같습니다.

이번 문제는 여기서 마무리하도록 하겠습니다.

감사합니다.