Abstract

본 논문에서 우리는 거대한 이미지 인지 환경에서 합성곱 신경망 깊이가 정확도에 미치는 효과를 조사했다.

본 연구의 주요 기여는 매우 작은 (3x3) 컨볼루션 필터를 사용하는 구조에서 네트워크의 깊이를 증가시키며 실험한 것이며, 이는 레이어 수를 16~19개의 가중치 층까지 깊게 만들면 기존의 방법들보다 주요한 성능 향상을 얻을 수 있다는 것을 보여준다.

이러한 발견은 우리 팀이 ImageNet Challenge 2014에 제출한 결과의 기반이 되었으며, 그 결과 우리 팀이 localization 에서 1위, classification 에서 2위를 달성했다.

우리는 또한 우리의 결과물이 잘 일반화되어 다른 데이터셋에서도 좋은 결과를 달성하는 것을 보여준다.

우리는 우리의 두가지 최고 성능 CNN 모델을 이후 연구에서 용이하게 사용할 수 있도록 공공적으로 사용가능하게 만들었다.

1 Introduction

CNN은 최근 거대한 이미지, 영상 인지에서 좋은 성과를 거두었으며, 이는 거대 공공 이미지 데이터와 GPU 또는 대규모 분산 클러스터와 같은 고성능 연산 시스템 덕분에 가능하게 되었다.

특히, 심층 시각 인지 아키텍처의 발전에서 ImageNet 대규모 시각 인식 챌린지가 중요한 역할을 하였으며, 이는 고차원 얕은 특징 인코딩 부터 심층 CNN까지 거대 이미지 분류 시스템의 몇 세대를 위한 테스트베드를 제공했다.

컴퓨터 비전 분야에서 CNN이 보편화됨에 따라 더 나은 정확도를 달성하기 위해 Krizhevsky et al.의 아키텍쳐를 향상시키기 위한 여러 시도가 이루어졌다.

예를 들어, ILSVRC-2013에서 가장 좋은 성능을 보인 제출은 첫번째 컨볼루션 레이어에서 더 작은 윈도우 사이즈와 더 작은 스트라이드를 활용했다.

다른 방향의 발전은 네트워크를 전체 이미지와 여러 스케일에 걸쳐 빽빽하게 학습하고 테스트하는 것을 다루었다.

본 논문에서는 CNN 아키텍쳐 설계의 다른 주요한 측면인 깊이를 다룬다.

마지막으로, 우리는 아키텍쳐의 다른 파라미터를 수정하고 더 많은 컨볼루션 레이어를 추가하는 것으로 네트워크의 깊이를 점진적으로 증가시켰으며, 이는 모든 레이어레서 매우 작은 컨볼루션 필터를 사용하기 때문에 실행가능하다.

결과적으로, 우리는 훨씬 더 정확한 CNN 아키텍쳐를 생각해냈고, 이는 ILSVRC 분류와 로컬라이제이션에서 최신의 정확도를 달성한 것 뿐만 아니라 다른 이미지 인식 데이터셋에서도 사용가능하게 했으며, 심지어 상대적으로 간단한 파이프라인(예: 미세조정되지 않은 선형 SVM으로 분류된 심층 특징)의 일부로 사용될 때도 최고의 성능을 달성했다.

본 논문의 나머지는 다음과 같이 구성되어 있다.

Section 2에서 우리는 우리의 CNN 구성을 설명한다.

이미지 분류 학습과 평가의 세부사항은 Section 3에 있고, Section 4에 ILSVRC 분류 작업에서의 구성을 비교한다.

Section 5는 논문의 결론이 있다.

완성도를 위해, 우리는 부록 A에서 우리의 ILSVRC-2014 객체 로컬라이제이션 시스템을 설명하고 평가하며, 부록 B에서 다른 데이터셋에서의 심층 특징의 일반화를 설명한다.

마지막으로, 부록 C는 논문의 주요 수정 사항 목록이 포함하고 있다.

2 ConvNet Cofiguration

같은 설정에서 CNN 깊이를 증가시키는 것에 따른 향상을 측정하기 위해 우리의 모든 CNN 레이어 구성은 Ciresan et al.(2011)과 Krizhevsky et al.(2012) 에서 가져온 같은 원칙을 사용하여 설계되었다.

현재 섹션에선, 우리는 설명한다 / 일반적인 틀을 / 우리의 CNN 구성의 / 그리고 세부화한다 / 특정한 구성(섹션 2.1)을 / 평가(섹션 2.2)에서 사용된

현재 섹션에서, 우리는 우리의 CNN 구성의 일반적인 틀을 설명하고 (섹션 2.1), 평가에서 사용된 특정한 구성을 세부화한다(섹션 2.2).

섹션 2.3에서 우리의 설계를 설명하고 기존의 방법과 비교한다.

2.1 Architecture

학습에서, 우리의 CNN의 입력은 고정된 크기의 224x224 RGB 이미지이다.

우리가 진행한 유일한 전처리는 학습 세트의 각 픽셀로부터 계산된 평균 RGB 값을 빼는 것이다.

이미지는 3x3의 매우 작은 수용적인 영역(이는 상하좌우, 중앙의 개념을 잡기위한 가장 작은 크기이다.)을 가진 필터를 사용하는 컨볼루션 레이어 스택을 지나간다.

구성 중 하나에서 우리는 1x1 컨볼루션 필터도 사용하는데, 이는 입력채널의 선형 변환(뒤에 비선형성 적용) 으로 볼 수 있다.

컨볼루션 스트라이드는 1 픽셀로 고정되어 있으며, 컨볼루션 레이어 입력의 패딩은 컨볼루션 연산 이루에 해상도가 유지되도록 한다. 즉, 3x3 레이어의 패딩은 1 픽셀이다.

풀링은 5개의 맥스 풀링에 의해 수행되며, 이는 몇몇의 컨볼루션 레이어 뒤에 따른다. (모든 컨볼루션 레이어 뒤에 맥스 풀링이 따르는 것은 아니다.)

맥스 풀링은 2x2 픽셀 윈도우와 스트라이드 2로 수행된다.

컨볼루션 레이어 스택 (다른 아키텍쳐에서 다른 깊이를 가지는) 뒤레는 세 개의 완전 연결 층이 있으며, 처음 두 레이어는 각각 4096개의 채널을 가지고, 세번째 레이어는 1000-way ILSVRC 분류를 숳행하고 또한 1000개의 채널을 포함한다. (각 클래스만다 하나씩)

마지막 레이어는 소프트맥스 레이어이다.

완전 연결층의 구성은 모든 네트워크에서 같다.

모든 은닉층은 정류 비선형 함수 (ReLU)를 가지고 있다.

우리는 우리의 네트워크들은 Local Response Normalization (LRN)을 포함하지 않으며 (하나를 제외하고), 섹션 4에 서술되어 있듯이 이러한 정규화는 ILSVRC 데이터셋에서의 성능을 향상시키지 않고, 메모리 소모와 연산 시간을 증가시킨다.

사용하는 경우에는, LRN 레이어의 파라미터는 Krizhevsky et al. (2012)의 파라미터를 따른다.

2.2 Configurations

본 논문에서 평가된 CNN의 구성은 표 1에 나와있다.

우리가 언급할 네트워크의 이름은 (A-E)이다.

모든 구선은 섹션 2.1에 나와있는 일반적인 설계를 따르고, 네트워크 A에 있는 11개의 가중치 레이어부터 (컨볼루션 레이어 8개와 완전 연결층 3개) 네트워크 E에 있는 19개의 가중치 레이어까지 (컨볼루션 레이어 16개와 완전 연결층 3개)까지 깊이만 다르다.

컨볼루션 레이어의 너비(채널의 수)는 첫번째 레이어에서 64로 시작하여 상당히 작으며, 512에 도달할 때까지 각 맥스 풀링 레이어를 지날때 마다 2배씩 증가한다.

표 2에는 각 구성의 파라미터 수가 서술되어 있다.

이러한 깊이에도 불구하고, 우리의 네트워크의 가중치의 수는 더 큰 컨볼루션 레이어 너비와 수용 영역을 가진 얕은 네트워크의 가중치 수보다 많지 않다.

2.3 Discussion

우리의 CNN 구성들은 ILSVRC-2012 (Krizhevsky et al., 2012)와 ILSVRC-2013 (Zeiler & Fergus, 2013; Sermanet et al., 2014)에서 가장 좋은 성능을 보였던 것과는 꽤 다르다.

첫 컨볼루션 레이어에서 상대적으로 큰 수용영역을 사용하는 것 대신(예: 11x1, 스트라이드 4(Krizhevsky et al., 2012) 또는 7x7, 스트라이드 2(Zeiler & Fergus, 2013; Sermanet et al., 2014)), 우리는 전체 네트워크에서 매우 작은 3x3 수용영역을 사용하며, 이는 모든 픽셀에서 입력과 컨볼루션 된다. (스트라이드 1)

두 개의 3x3 컨볼루션 레이어(사이에 풀링 없음)는 효율적인 5x5 수용영역을 가지고, 세 개의 이러한 레이어는 효율적인 7x7 수용영역을 가진다.

그래서 예를 들어, 7x7 레이어 하나 대신 3x3 컨볼루션 레이어 세 개를 쌓아서 사용하면 무엇을 얻을 수 있는가?

먼저, 우리는 한 개 대신 세 개의 비선형함수 레이어를 포함하며, 이는 결정 함수를 더 차별적으로 만든다.

두번째로, 파라미터의 수를 줄인다. 세 개의 3x3 컨볼루션 레이어 스택의 입력과 출력 둘 다 $C$ 채널을 가진다고 가정하면, 스택은 $3(3^2C^2) = 27C^2$개의 가중치로 파라미터화되며, 하나의 7x7 컨볼루션 레이어는 $7^2C^2=49C^2$개의 파라미터들을 필요로한다. 즉, 81% 더 많이 필요로한다.

이것은 7x7 컨볼루션 필터에 규제를 거는 것으로 볼 수 있으며, 3x3 필터로 분해되게 강제한다. (사이에 비선형성이 주입된다.)

1x1 컨볼루션 레이어의 통합은 (구성 C, 표 1) 컨볼루션 레이어의 수용영역에 영향을 끼치지 않으며 결정 함수의 비선형성을 증가시키는 방법이다.

비록 우리 경우에는 1x1 컨볼루션이 본질적으로 동일한 차원의 공간으로의 선형 투영이지만(입력과 출력 채널의 수가 같음), 추가적인 비선형성은 정류 함수에 의해 도입된다.

이는 1x1 컨볼루션 레이어가 최근 Lin et al.(2014)의 "Network in Network" 아키텍쳐에서 활용되었다는 것은 주목되어야 한다.

작은 컨볼루션 필터는 이전부터 Ciresan et al. (2011)에서 사용되었지만, 그들의 네트워크는 훨씬 덜 깊었고, 매우 큰 ILSVRC 데이터셋에서 평가하지 않았다.

Goodfellow et al. (2014)에서 거리 숫자 인지 작업에 깊은 CNN을 (11개의 가중치 레이어) 적용했으며, 증가된 깊이는 더 나은 성능을 이끈다는 것을 보여줬다.

ILSVRC-2014 분류에서 최고의 성능을 보여준 GooLeNet (Szegedy et al., 2014)는 우리의 것과 독립적으로 개발되었지만, 매우 깊은 CNN(22개의 가중치 레이어)와 작은 컨볼루션 필터(3x3 외에도 1x1과 5x5 또한 사용함)에 기반한다는 것은 비슷하다.

그러나 그들의 네트워크는 우리의 것보다 더 복잡하고, 연산의 양을 줄이기 위해 특징 맵의 공간 해상도는 첫번째 레이어에서 더 공격적으로 줄어든다.

섹션 4.5에 서술되어 있으며, 우리의 모델은 단일 네트워크 분류 정확도에서 Szegedy et al. (2014)보다 더 좋은 성능을 보인다.

3 Classification Framework

이전 섹션에서 우리는 우리의 네트워크의 구성들의 세부사항에 대해 서술했다.

이번 섹션에서는, 우리는 분류 CNN 학습과 평가의 세부사항에 대해 서술한다.

3.1 Training

CNN 학습 절차는 일반적으로 Krizhevsky et al. (2012)를 따른다. (다양한 스케일의 학습 이미지로부터 입력을 추출하는 샘플링 작업을 제외한다. 이는 뒤에 설명되어 있다.)

즉, 학습은 모멘텀과 함께 mini-batch 경사하강법(역전파에 기반한 (LeCun et al., 1989)을 사용하여 다중 로지스틱 회귀 객체를 최적화하는 것으로 수행된다.

배치 크기는 256으로 설정되었으며, 모멘텀은 0.9로 설정되었다.

학습은 가중치 감소($L_2$ 페널티는 $5\cdot10^{-4}$로 설정되었다.)와 처음 두 개의 완전 연결층에서 드롭아웃 규제(드롭아웃은 0.5로 설정되었다.)로 규제되었다.

학습률은 처음에 $10^{-2}$로 설정되었고, 검증 세트 정확도가 향상되는 것을 멈췄을 때 10으로 나누었다.

전체적으로, 학습률은 3번 감소하였고, 학습 파라미터는 37만번의 반복(74 에포크) 이후에 멈췄다.

우리는 (Krizhevsky et al., 2012)에 비해 파라미터의 수가 더 많고 네트워크의 깊이가 더 깊음에도 불구하고 네트워크가 수렴하는 데 필요한 에포크 수가 더 적은 이유는 (a) 더 깊은 깊이와 더 작은 컨볼루션 필터 크기로 인한 암묵적인 규제, (b) 특정 레이어의 사전 초기화 때문이라고 추측한다.

네트워크 가중치의 초기화는 중요한데, 잘못된 초기화는 깊은 네트워크에서 경사의 불안정성때문에 학습을 멈출 수 있기 때문이다.

이 문제를 피하기 위해, 우리는 구성 A의 학습을 시작했으며, 이는 무작위한 초기화에서도 학습되기에 충분히 얕다.

더 깊은 아키텍쳐를 학습할 때는, 우리는 네트워크 A의 레이어와 함께 처음 네 개의 컨볼루션 레이어와 마지막 세 새의 완전 연결층을 초기화했다. (중간 레이어는 무작위로 초기화됨.)

우리는 사전 초기화된 레이어에서는 학습률을 감소시키지 않았으며, 이것들이 학습동안 바꾸도록 하였다.

무작위 초기화에서는(이에 해당하는), 우리는 평균 0, 분산 0.01인 정규분포에서 가중치를 샘플링하였다.

바이어스는 0으로 초기화되었다.

논문 제출 후 Glorot & Bengio (2010)의 무작위 초기화 절차를 사용하는 것으로 사전 학습 없이 가중치를 초기화 할 수 있다는 것을 알게되었다는 것은 주목할만 하다.

고정된 크디의 224x22x CNN 입력 이미지를 얻기 위해 그들은 리스케일된 학습 이미지에서 무작위로 추출했다. (SGD 반복마다 하나의 이미지 추출)

학습 세트를 증강시키기 위해, 추출은 무작위 좌우 반전과 무작위 RGB 색상 이동을 거쳤다.

학습 이미지는 스케일링은 아래에 설명되어있다.

Training image size

$S$를 리샘플링된 학습 이미지의 가장 짧은 변이라고 두고, 여기서 CNN 입력이 추출된다. (우리는 또한 $S$를 학습 스케일이라고 부른다.)

추출된 이미지의 크기가 224x224로 고정된 반면에, 원칙적으로 $S$는 224보다 작지 않은 어떤 값이든 가질 수 있으며, $S=224$인 경우 추출은 학습 이미지의 가장 짧은 변을 완전히 포함하여 전체 이미지 객체를 포착할 것이고, $S≫224$인 경우 추출은 작은 객체 또는 객체의 일부를 포함하는 이미지의 작은 부분에 해당할 것이다.

우리는 학습 스케일 $S$의 설정을 위해 두가지 접근을 고려한다.

첫번째 방법은 $S$를 고정하는 것이며, 이는 single-scale training에 해당한다. (추출된 이미지 안에는 여전히 다양한 크기의 객체가 포함될 수 있다는 것에 주목해라)

우리의 실험에서는 두가지 고정된 스케일로 모델을 평가했으며, 하나는 $S=256$이고 (이는 기존방법 (Krizhevsky et al., 2012; Zeiler & Fergus, 2013; Sermanet et al., 2014)에서 널리 사용되었다.), 다른 하나는 $S=384$이다.

주어진 CNN 구성에서 우리는 처음엔 $S=256$으로 네트워크를 학습시켰다.

$S=384$ 네트워크의 학습 속도를 높이기 위해, $S=256$으로 사전 학습된 가중치로 초기화되었으며, 초기 학습률을 $10^{-3}$으로 더 작게 설정했다.

$S$를 설정하는 두번째 방법은 multi-scale training이며, 이는 특정 범위 $[S_{min}, S_{max}]$에서 $S$를 무작위로 샘플링하여 각 학습 이미지를 독립적으로 리스케일하는 것이다. (우리는 $S_{min}=256$, $S_{max}=512$를 사용하였다.)

이미지 속 객체는 크기가 다를 수 있기 때문에, 이는 학습 과정에서 이것을 고려하는 것이 유익하다.

이것은 scale jittering에 의한 학습 데이터 증강으로 볼 수도 있으며, 이는 하나의 모델이 매우 다양한 크기의 객체들을 인식하도록 학습된다.

속도의 이유로, 고정된 $S=384$로 사전 학습된 single-scale 모델의 모든 레이어를 같은 구성으로 미세 조정하는 것으로 multi-scale 모델을 학습시켰다.

3.2 Testing

테스트 시에는, 학습된 CNN과 입력 이미지가 주어지면, 다음과 같이 분류한다.

먼저, 사전에 정의된 가장 짧은 이미지의 변의 길이 $Q$가 되도록 비율을 유지하여 리스케일한다. (우리는 이것을 테스트 스케일 이라고 부른다.)

우리는 $Q$가 학습 스케일 $S$와 반드시 같을 필요가 없다는 것에 주목했다. (우리는 섹션 4에서 성능 향상을 위해 각각의 $S$에 몇몇의 $Q$ 값을 사용한 것을 보여줄 것이다.

그 다음, (Sermanet et al., 2014)과 비슷한 방법으로 리스케일된 테스트 이미지에 네트워크를 빽빽하게 적용한다.

즉, 완전 연결층은 컨볼루션 레이어로 변환된다. (첫 완전 연결층은 7x7 컨볼루션 레이어로, 마지막 두 개의 완전 연결층은 1x1 컨볼루션 레이어가 된다.)

최종 fully-convolutional 네트워크는 전체 (추출되지 않은) 이미지에 적용된다.

결과적으로 클래스 점수 맵이 생성되며, 채널 수는 클래스 수와 같고, 해상도는 입력 이미지 크기에 따라 달라진다.

마지막으로, 이미지 클래스 점수의 고정된 벡터를 얻기 위해 클래스 점수 맵은 공간적으로 평균화된다.(sum-pooled 된다)

우리는 또한 이미지 좌우반전으로 테스트 세트를 증강시켰고, 이미지의 최종 점수를 얻기 위해 원본과 반전된 이미지의 소프트 맥스 클래스 값을 평균화한다.

fully-convolutional 네트워크는 이미지 전체에 적용되므로, 테스트 시에는 여러 개의 crop을 샘플링할 필요가 없으며, 이는 각각의 재연산해야하기 때문에 비효율적이다.

한편, 방대한 crop 셋을 사용하는 것은 Szegedy et al.에 의해 수행되었으며, 이는 정확도 향상을 이끌 수 있고 이것은 fully-convolutional 방식보다 입력 이미지를 더 촘촘하게 샘플링한다.

또한 다중 crop 평가는 다른 컨볼루션 경계 상태 때문에 밀집 평과 방식돠 보완적인데, 이는 crop에 컨볼루션 레이어를 적용할 시킬 때 계산된 특징 맵은 0으로 패딩되는 반면, 밀집 평가의 경우엔 같은 crop에 대해 이미지의 자연적으로 오는 이웃한 부분으로 패딩된다.(컨볼루션 연산과 부분 풀링때문에) 이는 대체로 전체 네트워크의 수용 영역을 증가시키므로 더 많은 맥락을 포착할 수 있다.

우리가 여러 개의 crop들에 따른 증가된 연산 시간 실행은 정확도의 잠재적인 이익을 정당화하지 않는다고 믿지 않지만, 참고로 우리는 또한 스케일 별로 50개의 crop(5x5 그리드와 2개의 반전)을 사용하여 우리의 네트워크를 평가했으며, 이는 총 150개의 crop을 3개의 스케일에 걸쳐 사용한 것으로 Szegedy et al(2014)에서 사용한 144 crop을 4개의 스케일에 걸쳐 사용한 것과 유사하다.

3.3 Implementation Details

우리의 구현은 공적으로 사용가능한 C++ Caffe toolbox로부터 파생되었으나, 이는 우리가 하나의 시스템에 설치된 여러 개의 GPU에서 학습과 평가를 수행할 수 있도록하고 전체 크기의 이미지(추출되지 않으)를 다양한 스케일로 학습과 평가할 수 있도록하는 몇몇 개의 주요한 수정이 포함되어 있다.(위에 설명된 것과 같이)

여러 개의 GPU 학습은 데이터 병렬화를 말하며, 각각의 GPU에서 병렬로 처리된 학습 이미지의 각 배치를 여러 개의 GPU 배치로 나누는 것으로 수행된다.

GPU 배치 그레디언트가 연산된 후에, 이들은 전체 배치의 그레디언트를 얻기 위해 평균화된다.

그레디언트 연산은 GPU들에 걸쳐 동기화되며, 따라서 결과는 하나의 GPU에서 연산될 때와 정확하게 같다. 최근 컨볼루션 네트워크 학습을 가속화하는 더 정교한 방법이 제안되었는데, 이는 네트워크의 다른 레이어에 대해 모델과 데이터 병렬화를 사용한다.

또한 우리는 우리의 개념적으로 더 간단한 방법이 하나의 GPU만을 사용했을 때와 비교하였을 때 off-the-shelf 4-GPU 시스템이 3.75배 가속을 이미 제공한다는 것을 알아냈다.

4개의 NVIDIA Titan Black GPU가 장비된 시스템은 아키텍쳐에 의존하여 하나의 네트워크를 학습시키는 데에 2-3주가 걸렸다.

4 Classification Experiments

Dataset

이번 섹션에선, 우리는 ILSVRC-2012 데이터셋(ILSVRC 2012-2014 challenge에서 사용된)에서 설명한 CNN 아키텍쳐가 달성한 이미지 분류 결과를 서술한다.

데이터 셋은 1000개의 클래스의 이미지를 포함하고 3개의 세트로 분리되어 있으며, 이는 학습세트(1.3백만 이미지), 검증 세트 (5만 이미지), 테스트 세트 (10만 이미지)로 이루어져있다.

분류 성능은 두개의 측정법을 사용하여 평가되었으며, 이는 top-1, top-5 오류이다.

전자는 다중 클래스 분류 오류, 즉 장못 분류된 이미지의 비율이며, 후자는 ILSVRC에서 사용되는 주요 평가 방법으로, 실제 카테고리가 예측된 top-5 카테고리에 포함되지 않는 이미지의 비율로 계산된다.

다수의 실험을 위해, 우리는 검증 세트를 테스트 세트로서 사용했다.

특정 실험은 테스트 세트에서 수행되었고, ILSVRC-2014 경진대회에서 "VGG" 팀으로 공식 ILSVRC 서버에 제출되었다.

4.1 Single Scale Evaluation

우리는 단일 스케일로 섹션 2.2의 레이어 설정이 사용된 각각의 CNN 모델의 성능 평가를 시작했다.

테스트 이미지 크기는 다음을 따른다: 고정된 $S$는 $Q=S$이고, 변동되는 $S∈[S_{min}, S_{max}]$는 $Q=0.5(S_{min}+S_{max})$이다.

결과는 표 3에서 볼 수 있다.

먼저, 우리는 정규화 레이어가 없는 모델 A에서 local response normalization (A-LRN 네트워크)를 사용하는 것은 향상시키지 않는다는 것을 알아냈다.

우리는 또한 깊은 아키텍쳐 (B-E)에서도 정규화를 사용하지 않았다.

두번째로, 우리는 증가하는 CNN 깊이(A의 11개 레이어부터 E의 19개 레이어까지)에서 분류 오류가 감소한다는 것을 관찰했다.

특히, 같은 깊이임에도 불구하고, 설정 C(3개의 1x1 컨볼루션 레이어를 포함하는)는 3x3 컨볼루션 레이어를 사용하는 설정 D보다 나쁜 결과를 보여주었다.

이는 추가적인 비선형성이 도움을 주는 반면에(B보다 C에서 더), 이는 또한 사소하지 않은 수용 영역을 가진 컨볼루션 필터를 사용함으로써(C보다 D에서 더) 공간적인 맥락을 포착하는 데에 중요하다.

우리의 아키텍쳐의 오류율은 깊이가 19 레이어에 도달했을 때 포화하지만, 더 깊은 모델은 아마 방대한 데이터셋에서 이득일 것이다.

우리는 또한 네트워크 B를 5x5 컨볼루션 레이어를 가진 얕은 네트워크와 비교했으며, 이는 각 쌍의 3x3 컨볼루션 레이어를 하나의 5x5 컨볼루션 레이어로 대체하는 것으로 B로부터 파생되었다. (이는 섹션 2.3에서 설명한 것과 같이 같은 수용 영역을 가진다.)

얕은 네트워크의 top-1 오류는 B보다 (center crop에서) 7% 더 높게 측정되었으며, 이는 작은 필터를 가진 깊은 네트워크가 큰 필터를 가진 얕은 네트워크를 능가한다는 것을 보여준다.

마지막으로, 학습 시에 스케일 jittering($S∈[256;512]$)은 테스트 시에 고정된 가장 짧은 변으로 ($S=256;or;S=384)$ 단일 스케일이 사용되더라도 훨씬 나은 결과를 이끈다.

이는 스케일 jittering을 통한 학습 세트 증강이 다중 스케일 이미지 통계를 포착하는 데에 필수적으로 도움을 준다는 것이 확인된다.

4.2 Multi-Scale Evaluation

단일 스케일에서 CNN 모델을 평가한 이후에, 우리는 이제 테스트 시 스케일 jittering의 효과를 평가한다.

이는 테스트 이미지의 여러가지 재스케일링된 버전(다른 $Q$값에 해당)에서 모델을 실행한 후, 결과로 나온 클래스 사후 확률을 평균내는 것으로 구성된다.

학습과 테스트 스케일의 큰 차이가 성능 저하를 이끈다는 것을 고려하여, 고정된 $S$로 학습된 모델은 학습 때와 비슷한 세가지 테스트 이미지 크기에서 평가되었다.: $Q={S-32,S,S+32}$

이때 학습 시 스케일 jittering은 테스트 시에 더 넓은 범위의 스케일에 네트워크가 적응하도록 하며, $S∈[S_{min};S_{max}]$로 학습된 모델은 더 넓은 크기 $Q={S_{min},0.5(S_{min}+S_{max}),S_{max}}$ 로 평가되었다.

결과는, 표 4에 제시된 것과 같이, 테스트 시 스케일 jittering이 더 나은 성능을 이끈다는 것을 말한다. (표 3에 제시된 단일 스케일로 같은 모델을 평가한 것과 비교)

이전에, 가장 깊은 구성(D와 E)이 가장 좋은 성능을 보였으며, 스케일 jittering은 가장 짧은 변에 고정된 $S$로 학습했을 때보다 더 나은 성능을 보였다.

검증 세트에서의 우리의 가장 좋은 단일 네트워크 성능은 24.8%/7.5%의 top-1/top-5 오류율이다.

테스트 세트에서는, 구성 E가 7.3%의 top-5 오류율을 달성했다.

4.3 Multi-Crop Evaluation

표 5에서 우리는 밀집 CNN 평가와 다중 crop 평가를 비교했다.

우리는 또한 이들의 소프트맥스 출력을 평균내는 것으로 두 가지 평가 기술의 상호보완성을 평가했다.

보이는 것과 같이, 다중 crop을 사용하는 것이 밀집 평가보다 약간 더 나은 성능을 보였으며, 그것들의 결합이 각각의 방법을 능가한 것에 따라 두 방법은 상호보완적이다.

위에서 언급한 것과 같이, 우리는 이것이 컨볼루션 경계 조건에 대한 서로 다른 처리 방식 때문이라고 가정한다.

4.4 ConvNet Fusion

위에서부터 지금까지, 우리는 각각의 CNN 모델들의 성능을 평가했다.

이번 실험에선, 우리는 이들의 소프트맥스 사후 확률을 평균내는 것으로 여러가지 모델의 출력을 결합한다.

이것은 모델들의 상호보완성때문에 성능이 향상되었으며, 2012, 2013년에 상위 ILSVRC 제출로 사용되었다.

결과는 표 6에 제시되어 있다.

ILSVRC 제출 당시에는 단일 스케일 네트워크와 다중 스케일 모델 D(모든 레이어가 아닌 완전 연결층만 미세조정)만 학습시킨 상태였다.

7개의 네트워크를 앙상블한 결과는 7.3%의 ILSVRC 테스트 오류율이다.

제출 후에, 우리는 두 개의 가장 좋은 성능을 보인 다중 스케일 모델들(구성 D와 E)의 앙상블을 고려했으며, 이는 밀집 평가를 사용했을 때 7.0%의 테스트 오류율로 감소시켰고 밀집 평가와 다중 crop 평가 방식을 결합하여 사용했을 때 6.8%까지 감소시켰다.

참고로, 우리의 가장 좋은 단일 모델은 7.1% 오류율을 달성했다.(모델 E, 표 5)

4.5 Comparision with The State of The Art

마침내, 표 7에서 우리는 우리의 결과를 이전 방법들과 비교한다.

ILSVRC-2014 challenge의 분류 작업에서 우리 "VGG"팀은 7개 모델 앙상블을 사용하여 7.3%의 테스트 오류율로 2등을 달성했다.

제출 후에, 우리는 2개 모델 앙상블을 사용하여 오류율을 6.8%로 감소시켰다.

표 7에서 제시된 것과 같이, 우리의 매우 깊은 CNN은 이전 세대의 모델들을 능가했으며, 이는 ILSVRC-2012와 ILSVRC-2013 경진대회에서 최고의 결과를 달성했다.

우리의 결과는 분류 작업 우승 결과(GooLeNet, 6.7% 오류율)와 비교해도 경쟁력 있으며, ILSVRC-2013 우승 결과인 Clarifai를 상당히 능가하는 성능으로, Clarifai는 외부 훈련 데이터를 사용했을 때 11.2%, 사용하지 않았을 때는 11.7%의 성능을 보였다.

단지 두 개의 모델을 결합하는 것으로 대부분의 ILSVRC 결과보다 주요하게 작은 최고의 결과를 달성했다는 것을 고려하면 이는 주목할만하다.

단일 네트워크 측면에서 우리의 아키텍쳐는 단일 GooLeNet을 0.9%로 능가하면서 최고의 결과를 달성했다.

특히, 우리는 클래식한 CNN 아키텍쳐 LeCun er al. (1989)에서 출발하지 않았으며, 그러나 대체적으로 깊이를 증가시키는 것으로 이를 향상시켰다.

5 Conclusion

우리는 큰 규모의 이미지 분류에서 매우 깊은 컨볼루션 네트워크(19개의 가중치 레이어까지) 평가했다.

이는 분류 정확도에서 깊이가 이득이라는 것이 증명되었으며, Imagenet challenge 데이터셋에서의 이전 방법의 성능은 대체적으로 증가된 깊이의 컨볼루션 CNN 아키텍쳐를 사용하는 것으로 달성될 수 있다는 것도 증명되었다.

부록에는, 우리는 또한 넓은 범위의 작업과 데이터셋에 우리의 모델이 잘 일반화한다는 것을 보여주며, 이는 덜 깊은 이미지 표현에서 만들어진 더 복잡한 인지 파이프라인에 잘 맞고 능가한다는 것을 보여준다.

우리의 연구 결과는 시각적 표현에서 깊이의 중요성을 다시 한번 확인시켜 준다.

Reference

https://arxiv.org/pdf/1409.1556

Abstract

AlexNet은 LSVRC-2010 대회에서 Top-1 오류율과 Top-5 오류율에서 37.5%와 17.0%를, ILSVRC-2012 대회에서 Top-5 오류율 15.3%를 달성하였다.

이 신경망은 6천만개의 파라미터와 65만개의 뉴런을 가졌으며, 5개의 Convolution layer, Max-pooling layer 일부, 3개의 FC-layer, 마지막엔 1000-way softmax로 구성되어 있다.

학습을 빠르게하기 위해 non-saturating neuron(ReLU)과 GPU 기반 Convolution 연산을 사용하였다.

FC-layer에서의 과적합을 방지하기 위해 Dropout 기법을 사용하였다.

1 Introduction

• 본 논문의 기여

  • 가장 큰 CNN 중 하나를 ImageNet subset으로 학습시켜 ILSVRC-2010, ISVRC-2012 대회에서 가장 좋은 성능을 달성.
  • 2D Convolution을 포함한 CNN 학습 전반에 고도로 최적화된 GPU 구현 및 공개적으로 제공.
  • 학습시간 단축, 성능 향상을 위한 새롭고 일반적이지 않은 특징 포함. (Section 3)
  • 120만장의 데이터에서 과적합을 방지하기 위한 효과적인 기술 사용. (Section 4)

• 최종 신경망 구조

  • 5개의 Convolution layer, 3개의 FC-layer
  • 이들의 깊이는 매우 중요함. (모델의 전체 파라미터의 1%도 포함하지 않지만 하나라도 제거하면 성능 저하)

• 모델 크기의 한계

  • GPU 메모리 양
  • 감당가능한 학습시간

2 The Dataset

• 데이터 셋 특징

  • ImageNet은 약 22000개의 카테고리에 속한 150만장 이상의 라벨링된 고해상도 이미지들로 이루어짐.
  • 이미지들은 웹에서 수집되었고, 인간들에 의해 라벨링됨.

• ILSVRC

  • ILSVRC 대회에서 각 1000개 카테고리에 속한 약 1000장의 이미지로 이루어진 ImageNet의 subset을 사용함.
  • 전체적으로 약 120만장의 학습 이미지, 5만장의 검증 이미지, 15만장의 테스트 이미지로 이루어짐.
  • ImageNet에서는 일반적으로 Top-1 오류율과 Top-5 오류율 제시.

• 입력 전처리

  • 우리의 신경망은 일정한 입력차원을 필요로 하지만 ImageNet은 다양한 해상도의 이미지들로 구성됨.
  • 따라서 256x256 크기로 down-sampling.
  • 직사각형 이미지 → 짧은 변의 길이가 256이 되도록 rescale 후 이미지 중앙의 256x256 추출.
  • 전체 학습 이미지의 평균 픽셀값을 substract, 추가적인 전처리 X
  • 기본 RGB 값 그대로 학습에 사용.

3 The Architecture

신경망은 5개의 Convolution layer, 3개의 FC-layer로 구성되어 있으며, Section 3.1 ~ 3.4는 중요도 순으로 정렬되어 있다.

3.1 ReLU Nonlinearity

• 활성화 함수

  • 기존 신경망의 활성화 함수는 $f(x) = tanh(x)$ 또는 $f(x) = (1+e^{-1})^{-1}$(sigmoid) 이다.
  • 학습 시간 측면에서 경사 하강법을 사용할 경우, 위와 같은 saturating nonlinearity는 $f(x) = max(0,x)$(ReLU)와 같은 non-saturating nonlinearity보다 느리다.
  • ReLU를 사용하는 깊은 CNN은 tanh 함수를 사용할 때보다 몇 배 더 빠르게 학습한다.

위 그림은 4-layer CNN이 CIFAR-10 데이터셋에서 학습 오류 25%에 도달할 때까지 필요한 반복의 수를 보여준다.

이때 ReLU(실선)을 사용한 CNN이 tanh(점선)을 사용한 CNN보다 6배 빠르게 25% 학습 오류에 도달하는 것을 볼 수 있다.

이는 기존의 saturating neuron을 사용했다면 대규모 CNN 학습은 불가능했을 것이다.

• 기존 연구와 차별점

  • Jarrett et al.
  • $f(x) = |tanh(x)|$ + contrast normalization + local average pooling 방법이 Caltech-101 데이터셋에서 좋은 성능을 보임.
  • 그러나 여기서 핵심은 과적합 방지.
  • 본 논문에서의 ReLU의 효과는 학습 시간 단축.

3.2 Training on Multiple GPUs

• GPU 병렬화

  • GTX 580 GPU는 3GB의 메모리를 가지고 있으며, 이는 120만개의 학습 예제를 하나의 GPU로 학습시키기에 부족하다.
  • 따라서 두 개의 GPU 사용.
  • 최신 GPU는 직접적으로 다른 메모리에 읽고 쓰기 가능.

• 병렬화 구조

  • 커널을 절반씩 GPU에 배치.
  • GPU는 특정 레이어에서만 통신한다.
  • ex) 레이어 3의 커널들은 레이어 2의 모든 커널 맵으로부터 입력을 받음.
  • ex) 레이어 4의 커널들은 동일한 GPU에 있는 레이어 3의 커널 맵에서만 입력을 받음.

이는 GPU간 통신 비용과 연산량 사이의 밸런스 (통신을 많이하면 느려지고, 너무 적으면 성능이 떨어짐.)를 맞추기 위함이고, 이는 cross-validation으로 최적 연결 구조를 찾을 수 있었다.

• 기존 연구와 차별점

  • Ciresan et al.
  • column들이 모두 독립적
  • 그러나 AlexNet의 경우 부분적으로 연결되어 있음.

하나의 GPU를 사용했을 때보다 Top-1, Top-5 오류율이 1.7%, 1.2% 감소되었으며, 학습 시간도 단축되었다.

3.3 Local Response Normalization

ReLU 함수는 입력 정규화를 필요로 하지 않으며, 양의 입력 들어왔을때 해당 뉴런에서 학습이 이루어진다. 그러나 다음과 같은 로컬 정규화 방법은 일반화에 도움이 된다는 것을 알 수 있다.

$$ b_{x,y}^i=a_{x,y}^i/\bigg(k+\alpha\sum_{j=max(0,i-n/2)}^{min(N-1,i+n/2)}(a_{x,y}^j)^2\bigg)^{\beta} $$

$$ k=2, n=5, \alpha=10^{-4}, \beta=0.75 $$

• 로컬 정규화 방법

  • 어떤 뉴런이 크게 활성화되면 주변 뉴런들이 억제되도록 하는 방식.
  • 따라서 인접한 뉴런들을 경쟁시키는 방식이다.
  • $b_{x,y}^i$: 정규화 된 최종 출력
  • $a_{x,y}^i$: ReLU를 통과한 원래 값
  • $j$: $i$ 주변의 인접한 뉴런들
  • $N$: 전체 뉴런 수
  • $k$, $n$, $\alpha$, $\beta$: 하이퍼파라미터

• 기존 연구와 차별점

  • Jarret et al.
  • contrast normalization과 달리 평균을 빼지 않음.
  • brightness normalization이라고 표현.

이 정규화 방법을 사용했을 때 ImageNet에서 Top-1, Top-5 오류율 1.4%, 1.2% 감소, CIFAR-10에서 정규화하지 않았을 때 테스트 오류율 13%에서 11%로 감소

3.4 Overlapping Pooling

풀링(Pooling)은 근처 뉴런들을 요약하는 연산이다. $s$: stride $z$: 풀링 윈도우 크기

• non-Overlapping Pooling

  • $s=z$로, 윈도우가 겹치지 않음.

• Overlapping Pooling

  • $s < z$로, 윈도우가 겹침.
  • AlexNet에선 $s=2$, $z=3$

Overlapping Pooling이 적용되었을 때 Top-1, Top-5 오류율 0.4%, 0.3% 감소, 그리고 과적합에 더 강한 모습을 보임.

3.5 Overall Architecture

Conv Layer 5개, FC-Layer 3개, 1000-way softmax (출력), Multinomial Logistic Regression

• Conv1 Layer

  • 입력: 224x224x3 (실제 입력은 227x227x3이다.)
  • 출력: 55x55x96 ($(227-11)/4 + 1=55)$)
  • 11x11x3 필터 96개, stride 4

• Conv2 Layer

  • 입력: LRN, MaxPooling 거친 (55x55x96 → 27x27x96) Conv1 Layer의 출력
  • 출력: 27x27x256
  • 5x5x48 필터 256개, stride 1
  • 같은 GPU에 있는 Layer와 연결

• Conv3 Layer

  • 입력: LRN, MaxPooling 거친 (27x27x256 → 13x13x256) Conv2 Layer의 출력
  • 출력: 13x13x384
  • 3x3x192 필터 384개, stride 1
  • 모든 Layer와 연결

• Conv4 Layer

  • 입력: Conv3 Layer의 출력
  • 출력: 13x13x384
  • 3x3x192 필터 384개, stride 1
  • 같은 GPU에 있는 Layer와 연결

• Conv5 Layer

  • 입력: Conv4 Layer의 출력
  • 출력: 13x13x256
  • 3x3x192 필터 256개, stride 1
  • 같은 GPU에 있는 Layer와 연결

• FC1 Layer

  • 입력: MaxPooling 거친 (13x13x256 → 6x6x256) Conv5 Layer의 출력을 Flatten한 9216차원
  • 출력: 4096개
  • 모든 Layer와 연결

• FC2 Layer

  • 입력: FC1 Layer의 입력
  • 출력: 4096개
  • 모든 Layer와 연결

• FC3 Layer

  • 입력 FC2 Layer의 출력
  • 출력: 1000개 → softmax를 통해 확률분포 출력
  • 모든 Layer와 연결

4 Reducing Overfitting

AlexNet은 6천만개의 파라미터를 가지며, 아래는 과적합을 방지하기 위한 방법을 소개한다.

4.1 Data Augmentation

데이터 증강에 있어서 필요한 연산은 GPU가 학습하는 동안 CPU에서 변형된 이미지가 생성되기 때문에 연산 비용 측면에서 자유롭다.

• translation & hrizontal reflection

  • 256x256 크기의 원본 이미지에서 무작위의 224x224 크기의 패치를 잘라냄. (좌우 반전 추가)
  • 이는 신경망의 첫번째 입력이 224x224x3인 이유이다.
  • 결과적으로 데이터셋의 크기를 2048배 키운 효과.
  • 테스트 시에는 각 모서리와 중간 5개에 각각 반전시킨 이미지 총 10개에 대해 softmax 결과 평균.
  • 저자들은 이 방법이 없었다면 신경망의 크기를 줄여야 했을것이라고 하였다.

• RGB color PCA

  • 객체의 정체성은 빛 밝기나 색상의 변화에 따라 다양해지지 않는다.
  • 전체 데이터셋의 RGB 픽셀값에 PCA 수행
  • 이후 각 픽셀 $I_{xy}=[I_{xy}^R,I_{xy}^G,I_{xy}^B]^T$ 에 $[p_1,p_2,p_3][α_1λ_1,α_2λ_2,α_3λ_3]^T$를 더함
  • $p_i$: RGB 픽셀값의 3x3 공분산 행렬의 $i$번째 고유 벡터
  • $λ_i$: RGB 픽셀값의 3x3 공분산 행렬의 $i$번째 고유값
  • $α_i$: 평균 0, 표준편차 0.1인 가우시안 분포에서 추출한 난수 (이미지마다 새로 추출)
  • 원래 이미지에 자연스러운 조명 변화 추가
  • Top-1 오류율 1% 이상 감소

4.2 Dropout

성능을 올리는 가장 좋은 방법은 앙상블이다. 그러나 AlexNet과 같이 큰 신경망에서는 시간과비용적인 측면에서 현실적으로 불가능하다. 그래서 사용한 방법이 Dropout.

• Dropout

  • 각 뉴런의 출력을 0.5의 확률로 0으로 두는 것.
  • Dropout된 뉴런은 순전파, 역전파 모두 참여 X
  • 따라서 뉴런 간의 co-adaption 방지 → 더욱 견고한 특징 학습
  • → 매 반복마다 신경망은 다른 구조로 학습되지만, 가중치는 공유한다.
  • 비교적 적은 비용으로 앙상블 효과.
  • 테스트 시에는 모든 뉴런을 사용하지만, 출력에 0.5를 곱한 값을 사용. (매우 많은 Dropout network 예측의 기하평균)

Dropout 없이는 매우 심한 과적합이 발생했으며, 여기선 처음 두 FC-Layer에서 적용하였다.

5 Details of learning

• optimizer: stochastic gradient descent
• batch size: 128
• momentum: 0.9
• weight decay: 0.0005
• weight init: 평균 0, 표준편차 0.01 가우시안 분포
• bias init: Conv 2, 4, 5, FC-Layer → 1, 나머지 0
• LR init: 0.01
• epochs: 약 90

$$ v_{i+1} ;;; := ;;; 0.9 \cdot v_i - 0.0005 \cdot \epsilon w_i - \epsilon \cdot \bigg< \frac{\partial L}{\partial w} |{w_i} \bigg>{D_i} $$

$$ w_{i+1} ;;; := ;;; w_i + v_{i+1} $$

• weight decay

  • 가중치 감소는 단지 규제가 아닌 학습 오류도 줄여준다.

• Bias 초기화

  • Conv 2, 4, 5와 FC-Layer의 Bias 1로 초기화
  • 이는 ReLU 함수에 양의 입력을 제공함으로써 학습의 초기 단계 속도 가속.

• Learing Rate

  • validation 성능이 개선되지 않으면 learing rate 10으로 나눔.
  • 0.01로 초기화되었으며, 종료전에 3번 감소됨.

구현

import torch
import torch.nn as nn
import torch.optim as optim
import torch.nn.functional as F

from torchsummary import summary

from torch.utils import data
import torchvision.datasets as datasets
import torchvision.transforms as transforms

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')

# ReLU 활성화 함수 (Section 3.1) - 학습 시간 단축
# LRN (Section 3.3) - 과적합 방지
# Overlapping Pooling (Section 3.4) - 과적합 방지
# Dropout (Section 4.2) - 과적합 방지
# Bias Initialization (Section 5) - ReLU 함수에 양의 입력 -> 초기 단계 학습 가속
class AlexNet(nn.Module):
    def __init__(self, num_classes=1000): # Section 3.5
        # 입력 크기: (b x 3 x 227 x 227)
        # 논문 상에선 입력 크기가 224라고 작성되어 있지만 실제론 227
        super().__init__()

        self.conv = nn.Sequential(
            nn.Conv2d(in_channels=3, out_channels=96, kernel_size=11, stride=4), # (b x 96 x 55 x 55)
            nn.ReLU(), # Section 3.1
            nn.LocalResponseNorm(size=5, alpha=0.0001, beta=0.75, k=2), # Section 3.3
            nn.MaxPool2d(kernel_size=3, stride=2), # Section 3.4 (b x 96 x 27 x 27)
            nn.Conv2d(in_channels=96, out_channels=256, kernel_size=5, stride=1, padding=2), # (b x 256 x 27 x 27)
            nn.ReLU(),
            nn.LocalResponseNorm(size=5, alpha=0.0001, beta=0.75, k=2),
            nn.MaxPool2d(kernel_size=3, stride=2), # (b x 256 x 13 x 13)
            nn.Conv2d(in_channels=256, out_channels=384, kernel_size=3, stride=1, padding=1), # (b x 384 x 13 x 13)
            nn.ReLU(),
            nn.Conv2d(in_channels=384, out_channels=384, kernel_size=3, stride=1, padding=1), # (b x 384 x 13 x 13)
            nn.ReLU(),
            nn.Conv2d(in_channels=384, out_channels=256, kernel_size=3, stride=1, padding=1), # (b x 256 x 13 x 13)
            nn.ReLU(),
            nn.MaxPool2d(kernel_size=3, stride=2) # (b x 256 x 6 x 6)
        )

        self.fc = nn.Sequential(
            nn.Dropout(p=0.5), # Section 4.2
            nn.Linear(in_features=(256 * 6 * 6), out_features=4096),
            nn.ReLU(),
            nn.Dropout(p=0.5),
            nn.Linear(in_features=4096, out_features=4096),
            nn.ReLU(),
            nn.Linear(in_features=4096, out_features=num_classes)
        )

        self.init_wb()

    def init_wb(self): # Section 5
        for layer in self.conv:
            if isinstance(layer, nn.Conv2d):
                nn.init.normal_(layer.weight, mean=0, std=0.01)
                nn.init.constant_(layer.bias, 0)

        nn.init.constant_(self.conv[4].bias, 1)
        nn.init.constant_(self.conv[10].bias, 1)
        nn.init.constant_(self.conv[12].bias, 1)

        for layer in self.fc:
            if isinstance(layer, nn.Linear):
                nn.init.normal_(layer.weight, mean=0, std=0.01)
                nn.init.constant_(layer.bias, 1)

    def forward(self, x):
        x = self.conv(x)
        x = torch.flatten(x, 1)
        x = self.fc(x)
        return x

# Details of Learning (Section 5)
# weight decay: 학습 오류 감소
model = AlexNet().to(device)
criterion = nn.CrossEntropyLoss()
optimizer = optim.SGD(
    params=model.parameters(),
    lr=0.01,
    momentum=0.9,
    weight_decay=0.0005
)

lr_scheduler = optim.lr_scheduler.StepLR(
    optimizer=optimizer,
    step_size=30,
    gamma=0.1
)

summary(model, input_size=(3, 227, 227), batch_size=128)

----------------------------------------------------------------
        Layer (type)               Output Shape         Param #
================================================================
            Conv2d-1          [128, 96, 55, 55]          34,944
              ReLU-2          [128, 96, 55, 55]               0
 LocalResponseNorm-3          [128, 96, 55, 55]               0
         MaxPool2d-4          [128, 96, 27, 27]               0
            Conv2d-5         [128, 256, 27, 27]         614,656
              ReLU-6         [128, 256, 27, 27]               0
 LocalResponseNorm-7         [128, 256, 27, 27]               0
         MaxPool2d-8         [128, 256, 13, 13]               0
            Conv2d-9         [128, 384, 13, 13]         885,120
             ReLU-10         [128, 384, 13, 13]               0
           Conv2d-11         [128, 384, 13, 13]       1,327,488
             ReLU-12         [128, 384, 13, 13]               0
           Conv2d-13         [128, 256, 13, 13]         884,992
             ReLU-14         [128, 256, 13, 13]               0
        MaxPool2d-15           [128, 256, 6, 6]               0
          Dropout-16                [128, 9216]               0
           Linear-17                [128, 4096]      37,752,832
             ReLU-18                [128, 4096]               0
          Dropout-19                [128, 4096]               0
           Linear-20                [128, 4096]      16,781,312
             ReLU-21                [128, 4096]               0
           Linear-22                [128, 1000]       4,097,000
================================================================
Total params: 62,378,344
Trainable params: 62,378,344
Non-trainable params: 0
----------------------------------------------------------------
Input size (MB): 75.48
Forward/backward pass size (MB): 1885.10
Params size (MB): 237.95
Estimated Total Size (MB): 2198.54
----------------------------------------------------------------

# Data Augmentation (Section 4.1) - 과적합 방지
# mean substraction only, PCA color augmentation, 10 crop test 구현 X
TRAIN_DIR = ''
VAL_DIR = ''
TEST_DIR = ''

train_transform = transforms.Compose([
    transforms.Resize(256),
    transforms.RandomCrop(227),
    transforms.RandomHorizontalFlip(),
    transforms.ToTensor(),
    transforms.Normalize(
        mean=[0.485, 0.456, 0.406],
        std=[0.229, 0.224, 0.225]
    )
])

train_dataset = datasets.ImageFolder(TRAIN_DIR, transform=train_transform)

train_loader = data.DataLoader(
    train_dataset,
    batch_size=128,
    shuffle=True,
    num_workers=8,
    pin_memory=True
)

val_transform = transforms.Compose([
    transforms.Resize(256),
    transforms.CenterCrop(227),
    transforms.ToTensor(),
    transforms.Normalize(
        mean=[0.485, 0.456, 0.406],
        std=[0.229, 0.224, 0.225]
    )
])

val_dataset = datasets.ImageFolder(VAL_DIR, transform=val_transform)

val_loader = data.DataLoader(
    val_dataset,
    batch_size=128,
    shuffle=False,
    num_workers=8,
    pin_memory=True
)

test_transform = transforms.Compose([
    transforms.Resize(256),
    transforms.CenterCrop(227),
    transforms.ToTensor(),
    transforms.Normalize(
        mean=[0.485, 0.456, 0.406],
        std=[0.229, 0.224, 0.225]
    )
])

test_dataset = datasets.ImageFolder(TEST_DIR, transform=test_transform)

test_loader = data.DataLoader(
    test_dataset,
    batch_size=128,
    shuffle=False,
    num_workers=8,
    pin_memory=True
)

# Epoch (Section 5) - Roughly 90
best_acc = 0
for epoch in range(90):
    model.train()

    train_loss = 0
    correct = 0
    total = 0

    for img, cls in train_loader:
        img, cls = img.to(device), cls.to(device)

        output = model(img)
        loss = criterion(output, cls)

        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

        train_loss += loss.item() * img.size(0)
        _, preds = torch.max(output, 1)
        correct += (preds == cls).sum().item()
        total += cls.size(0)

    train_loss /= total
    train_acc = correct / total

    model.eval()

    val_loss = 0
    correct = 0
    total = 0

    with torch.no_grad():
        for img, cls in val_loader:
            img, cls = img.to(device), cls.to(device)

            output = model(img)
            loss = criterion(output, cls)

            val_loss += loss.item() * img.size(0)
            _, preds = torch.max(output, 1)
            correct += (preds == cls).sum().item()
            total += cls.size(0)

    val_loss /= total
    val_acc = correct / total

    if (epoch + 1) % 10 == 0:
        print(f'Epoch: {epoch + 1}/90 - Train Loss: {train_loss:.4f} - Train Acc: {train_acc:.4f} - Val Loss {val_loss:.4f} - Val Acc {val_acc:.4f}')

    if val_acc > best_acc:
        best_acc = val_acc
        torch.save(model.state_dict(), "best_alexnet.pth")
        print("Best Model Updated")

    torch.save({
        'epoch': epoch,
        'model_state_dict': model.state_dict(),
        'optimizer_state_dict': optimizer.state_dict(),
        'best_acc': best_acc
    }, "alexnet_checkpoint.pth")

    lr_scheduler.step()

model.load_state_dict(torch.load("best_alexnet.pth"))
model.to(device)

model.eval()

test_loss = 0
correct = 0
total = 0

with torch.no_grad():
    for img, cls in test_loader:
        img, cls = img.to(device), cls.to(device)

        output = model(img)
        loss = criterion(output, cls)

        test_loss += loss.item() * img.size(0)
        _, preds = torch.max(output, 1)
        correct += (preds == cls).sum().item()
        total += cls.size(0)

test_loss /= total
test_acc = correct / total

print(f'Test Loss {test_loss:.4f} - Test Acc {test_acc:.4f}')

Reference

https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf

Abstract

우리는 대회에서 1000개의 다른 클래스를 가진 120만개의 고해상도 이미지를 분류하기 위해 크고 깊은 CNN을 학습시켰다.

테스트 데이터에서, 우리는 상위 1개와 상위 5개 오류율에서 이전보다 나은 37.5%와 17.0%를 달성했다.

6천만개의 파라미터와 65만개의 층을 가진 신경망은 5개의 컨볼루션 레이어로 구성되어 있으며, 그 중 일부는 맥스 풀링 레이어가 뒤따르고, 3개의 완전 연결층과 마지막으로 1000 갈래의 소프트맥스 레이어가 있다.

학습을 더 빠르게 만들기 위해, 우리는 비포화 뉴런을 사용했으며 매우 효율적인 GPU 기반 컨볼루션 연산을 사용했다.

우리는 완전 연결층에서 과적합을 줄이기 위해 매우 효과적이라고 증명괸 드롭 아웃이라고 불리는 최근 개발된 규제 방법을 사용했다.

우리는 이 모델의 변형 버전을 ILSVRC-2012 대회에 출품하여 15.3%의 테스트 오류율로 5위 안에 드는 성과를 거두었으며, 이는 2위로 선정된 팀의 26.2%에 비해 훨씬 낮은 수치이다.

1 Introduction

현재 객체 인식에서의 접근은 머신 러닝 기법들의 필수적으로 사용한다.

우리는 성능을 향상시키기 위해서 더 방대한 데이터셋을 수집할 수 있고, 더 강력한 모델을 학습시킬 수 있다. 그리고 과적합을 방지하기 위해 더 나은 기술을 사용할 수 있다.

최근까지, 라벨링된 이미지의 데이터셋은 수만정정도의 규모로 상대적으로 작았다.

특히 만약 그것들이 레이블 보존 변환과 함께 증강되었다면 이러한 크기의 데이터 셋으로도 간단한 인지 작업은 꽤 잘 해결할 수 있다.

예를 들어, MNIST 숫자 인식 작업에서의 최고의 오류율은 인간의 수준까지 접근한다,

그러나 현실의 객체는 많은 다양성을 보여준다. 그래서 이들을 인지하는 것을 학습하기 위해 더 큰 학습 데이터셋을 사용하는 것은 필수적이다.

그리고 물론, 작은 이미지 데이터셋의 단점은 널리 인지되고 있다. 그러나 수백만장의 이미지로 이루어진 라벨링된 데이터셋을 모으는 것이 오직 최근에 가능해졌다.

새로운 더 큰 데이터셋은 수백 수천장의 완전 분할된 이미지로 이루어진 LabelMe와 22000개 이상의 카테고리에 걸쳐 150만개 이상의 라벨링된 고해상도 이미지로 이루어진 ImageNet을 포함한다.

수백만장의 이미지로부터 약 수천개의 객체를 학습하기 위해 우리는 방대한 학습 능력을 가진 모델이 필요하다.

그러나, 객체 인식 작업의 엄청난 복잡도는 ImageNet의 거대한 데이터셋조차 이 문제를 명확하게 할 수 없다는 것을 의미한다. 구래서 우리의 모델은 우리가 가지고 있지 않은 모든 데이터를 보상하기 위해 선행되는 지식을 가지고 있어야한다.

CNN은 이러한 모델의 한 종류를 구성한다.

그들의 성능은 이들의 깊이와 너비를 다양하게 하는 것으로 제어될 수 있다. 그리고 이들은 또한 이미지의 본질에 대해 강력하고 대부분 정확한 가정을 만든다.

또한, CNN은 비슷한 크기의 레이어로 이루어진 표준 feedforward 신경망과 비교했을 때 더 적은 연결과 파라미터를 가진다. 그래서 이러한 점은 학습을 더 쉽게하고 이론적으로 최고의 성능은 약간 떨어질 수 있다.

CNN의 매력적인 성능과 이들의 로컬 구조의 상대적인 효율성에도 불구하고, 이들은 여전히 방대한 고해상도 이미지에 적용하기에 비용이 많이 든다.

운이 좋게도, 최신 GPU는 고도로 최적화된 2D 컨볼루션 구현돠 결합하여 매우 큰 CNN을 학습할 수 있을 만큼 충분하며, ImageNet과 같은 최근 데이터셋은 이러한 모델이 심각한 과적합 없이 학습하기에 라벨링된 예제들을 충분히 포함하고 있다.

이 논문의 구체적인 기여는 다음과 같다: 우리는 두 대회에서 ImageNet의 서브셋으로 현재까지 가장 큰 CNN 중 하나를 학습시켰다. 그리고 이 데이터셋에서 보고된 결과 중 가장 좋은 결과를 달성했다.

우리는 2D 컨볼루션과 신경망 연산에 필요한 다른 모든 연산에 고도로 최적화된 GPU 구현을 개발했으며, 이를 공공적으로 사용가능하게 하도록 한다.

우리의 신경망은 학습시간을 줄이고 성능을 향상시킨 여러가지 새롭고 일반적이지 않은 특징을 포함하고 있으며, 이는 섹션 3에 자세히 서술되어있다.

우리의 신경망의 크기는 120만장의 라벨링된 학습 예제에서 과적합을 주요 문제로 하였으며, 우리는 과적합을 방지하기 위해 섹션 4에 묘사된 몇몇의 효과적인 기술을 사용했다.

우리의 최종 신경망은 다섯개의 컨볼루션 레이어와 3개의 완전 연결층을 포함하고 있으며 이들의 깊이는 중요하다: 우리는 컨볼루션 레이어를 제거하는 것은 (각각 모델의 파라미터의 1% 이하를 포함한다.) 성능저하를 야기하는 것을 알아냈다.

마지막엔, 신경망의 크기는 주요하게 최신 GPU의 메모리의 양과 우리가 인내할 수 있는 학습시간에 의해 제한적이다.

우리의 신경망은 두 개의 GTX 580 3GB GPU에서 학습시키기 위해 5일에서 6일 정도 걸렸다.

우리의 모든 실험은 더 빠른 GPU와 더 큰 데이터셋을 사용하게 되는 것을 기다리는 것으로 간단하게 우리의 결과가 향상될 수 있다고 생각한다.

2 The Dataset

ImageNet은 대략 22000개의 카테고리에 속한 150만개 이상의 라벨링된 고해상도 이미지들로 이루어진 데이터셋이다.

이미지들은 웸에서 수집되었으며 Amazon의 Mechanical Turk crowd sourcing tool을 사용하여 사람들에 의해 라벨링되었다.

2010년부터 Pascal Visual Object Challenge의 일환으로 ImageNet Large-Scale Visual Recognition Challenge(ILSVRC)라는 연례 대회가 개최되고 있다.

ILSVRC는 각 1000개의 카테고리에 속한 대략 1000개의 이미지로 이루어진 ImageNet의 서브셋을 사용한다.

전체적으로, 대략 120만개의 학습 이미지들과 5만개의 검증 이미지, 그리고 15만개의 테스트 이미지가 있다.

ILSVRC-2010은 테스트셋의 레이블이 사용가능한 ILSVRC의 단 하나의 버전이며, 이는 우리의 대부분의 실험을 보여준 버전이다.

우리는 ILSVRC-2012 대회에도 모델을 제출했으므로, 섹션 6에서는 테스트 세트 레이블을 사용할 수 없는 이 버전의 데이터셋에 대한 결과도 보고한다.

ImageNet에서는 일반적으로 두 가지 오류율을 보고한다. top-1 오류율과 top-5 오류율이다. 여기서 top-5 오류율은 모델이 가장 가능성이 높다고 판단한 다섯 가지 레이블 중 하나에 해당하지 않는 테스트 이미지의 비율을 나타낸다.

우리의 시스템이 일정한 입력 차원을 필요로 하는 반면, ImageNet은 다양한 해상도의 이미지들로 구성되어 있다.

그러므로, 우리는 이미지를 256x256의 고정된 해상도로 다운샘플링하였다.

직사각형 이미지가 주어지면, 우리는 가장 처음으로 짧은 변의 길이가 256이 되도록 이미지의 크기를 rescale 하였고, 결과 이미지 중앙의 256x256 부분을 잘라냈다.

우리는 이미지를 각 픽셀에서 전체 훈련 세트의 평균 활동량을 빼는 것을 제외하곤 다른 방법으로 전처리하지 않았다.

그래서 우리는 우리의 신경망을 픽셀들의 기본 RGB 값으로 학습시켰다.

3 The Architecture

우리의 네트워크의 구조는 Figure 2에 요약되어 있다.

이것은 5개의 컨볼루션 레이어와 3개의 완전 연결층으로 이루어진 8개의 학습된 층을 가진다.

아래에, 우리의 신경망 구조의 몇몇 특이하고 일반적이지 않은 특징을 설명한다.

섹션 3.1에서 3.4는 가장 중요한 것이 먼저 오도록 정렬되어 있다.

3.1 ReLU Nonlinearity

입력 $x$의 함수로써 신경망의 출력 $f$를 모델링하는 표준 방법은 $f(x) = tanh(x)$ 또는 $f(x) = (1+e^{-1})^{-1}$이다.

훈련 시간 측면에서 경사 하강법을 사용할 경우, 이러한 포화 비선형 함수는 $f(x) = max(0,x)$와 같은 비포화 비선형 함수보다 훨씬 느립니다.

Nair and Hinton에 따라, 우리는 이러한 비선형성을 가진 뉴런을 ReLU라고 부른다.

ReLU 함수를 사용하는 깊은 CNN은 tanh 함수를 사용할 때보다 몇 배 더 빠르게 학습한다.

이것은 그림 1에 묘사되어 있으며, 이는 특정 4개의 층의 컨볼루션 신경망이 CIFAR-10 데이터셋에서 25% 훈련 오류율에 도달하기 위해 필요한 반복의 수를 보여준다.

이 플랏은 만약 우리가 기존의 포화 신경 모델을 사용했다면 이러한 거대한 신경망을 사용하는 작업을 실험할 수 없었을 것이라는 것을 보여준다.

우리가 CNN에서 기존의 모델에 대한 대안을 고려한 것이 처음이 아니다.

예를 들어, Jarrettet al은 $f(x) = |tanh(x)|$ 와 같은 비선형함수가 Caltech-101 데이터셋에서 이들의 대비 정규화 방법과 이에 따른 로컬 평균 풀링 방법과 함께 특히 잘 작동한다고 주장한다.

그러나, 이 데이터셋에서 가장 중요한 것은 과적합을 방지하는 것이며, 그들이 관찰한 효과는 우리가 보고하는 ReLU를 사용하여 훈련 데이터셋을 학습하기 위한 가속 성능과 다르다.

더 빠른 학습은 거대한 데이터 셋에서 학습된 거대한 모델의 성능에서 큰 영향을 가진다.

그림 1

ReLU 함수를 사용하는 4개 층의 CNN은 CIFAR-10 데이터셋에서 $tanh$ 함수를 사용하였을 때보다 6배 빠르게 25% 훈련 오류율에 도달한다.

각 네트워크의 학습률은 학습을 가능한 빠르게 만들기위해 독립적으로 선택된다.

아무런 규제도 적용되지 않았다.

이곳에 나타난 효과의 크기는 신경망 구조에 따라 다양하며, ReLU 함수를 사용한 신경망은 일관적으로 포화 신경망보다 몇 배 더 빠르게 학습한다.

3.2 Training on Multiple GPUs

하나의 GTX 580 GPU는 3GB 메모리를 가지고 있으며, 이는 학습할 수 있는 신경망의 최대 크기를 제한한다.

이는 120만개의 훈련 예제로 신경망을 하나의 GPU에서 학습시키기에는 너무 크다고 밝혀졌다.

그러므로 우리는 두 개의 GPU로 신경망을 퍼뜨렸다.

최신 GPU는 GPU간 병렬화에 특히 잘 맞으며, 이들은 호스트 머신 메모리를 거치는 것 없이 직접적으로 다른 메모리에 읽고 쓸 수 있다.

우리가 채택한 병렬화 구조는 주요하게 하나의 추가적인 트릭과 함께 각 GPU에 커널(또는 신경망)의 절반을 넣는다: GPU는 특정 층에서만 통신한다.

이것은 예를 들어 레이어 3의 커널들은 레이어 2의 모든 커널 맵으로부터 입력을 받는다는 것을 의미한다.

그러나 레이어 4의 커널들은 동일한 GPU에 있는 레이어 3의 커널 맵에서만 입력을 받는다.

패턴을 선택하는 것은 cross-validation의 연결성의 문제이며, 이것은 우리가 연산량의 허용가능한 비율이 될 때까지 통신의 양을 정밀하게 튜닝할 수 있도록 한다.

결과적으로 얻어진 구조는 우리의 column은 독립적이지 않다는 것을 제외하면 Ciresanet al이 사용한 "columnar" CNN과 비슷하다.

이 구조는 하나의 GPU에서 각 컨볼루션 레이어가 학습된 절반의 커널을 사용하는 네트워크와 비교했을 때, 우리의 top-1, top-5 오류율을 1.7%, 1.2% 줄인다.

두 개의 GPU 신경망은 하나의 GPU 신경망보다 학습시키는 데에 약간 적은 시간이 걸린다.

3.3 Local Response Normalization

ReLU 함수는 이들을 포화 상태로부터 방지하기위한 입력 정규화를 필요로 하지 않는 이상적인 특징을 가진다.

만약 최소 몇몇 훈련 예제가 ReLU 함수에 양의 입력을 제공한다면, 학습은 해당 뉴런에서 발생할 것이다.

그러나, 우리는 다음과 같은 로컬 정규화 방법은 일반화에 도움이 된다는 것을 알 수 있다.

커널 $i$를 위치 $(x,y)$에 적용한 후 ReLU 비선형 함수를 적용하여 계산한 뉴런의 활동을 $a_{x,y}^i$ 로 나타낼 때, 응답으로 정규화된 활동 $b_{x,y}^i$는 다음과 같이 주어진다.

표현식

여기서 같은 공간에 위치한 인접한 $n$개의 커널 맵에서 덧셈이 이루어지며, $N$ 은 레이어 안에 있는 커널의 총 수이다.

커널맵의 순서는 학습이 시작되기 전엔 임의적으로 결정된다.

응답 정규화 방식은 실제 신경 속에서 영감을 받은 측면 억제 형태를 구현하며, 이는 다른 커널을 사용하여 계산된 뉴런 출력 간의 큰 활동에 대한 경쟁을 만든다.

이 방식은 Jarrett et al의 로컬 대비 정규화 방법과 약간의 유사점을 가지고 있지만, 우리의 방식은 평균 활동을 빼지 않기 때문에 "밝기 정규화"라고 부르는 것이 더 정확할 것이다.

응답 정규화 방식은 우리의 top-1, top-5 오류율을 1.4%, 1.2% 줄인다.

우리는 CIFAR-10 데이터셋에서 이 방식의 효과를 검증했다: 4개의 층으로 이루어진 CNN은 정규화 없이 13%의 테스트 오류율을 달성했으며, 정규화를 적용했을 때는 11%를 달성했다.

3.4 Overlapping Pooling

CNN의 풀링 레이어는 같은 커널 맵 안에세 뉴런의 가까운 그룹의 출력을 요약한다.

기존에는, 이웃들은 덮어씌워지지 않은 인접한 풀링 유닛에 의해 요약됐다.

더 정밀하게 하기 위해, 풀링 레이어는 $s$ 픽셀 간격으로 배치된 풀링 유닛의 그리드로 구성되어 있다고 생각할 수 있으며, 각각은 풀링 유닛의 중심에 있는 크기 $z$ x $z$인 이웃을 요약한다.

만약 우리가 $s = z$라고 두었을 때, 우리는 CNN에서 일반적으로 채택하는 기존의 로컬 풀링을 얻는다.

만약 우리가 $s < z$라고 둔다면, 우리는 오버래핑 풀링을 얻는다.

이것은 우리가 우리의 신경망에 $s = 2$와 $z = 3$으로 사용하는 것이다.

이 방식은 동일한 차원에서 $s = 2$, $z = 2$인 오버래핑이 아닌 방식이 제공하는 결과와 비교했을 때, top-1, top-5 오류율을 0.4%, 0.3% 줄인다.

우리는 일반적으로 오버래핑 풀링이 적용된 모델이 학습하는 동안 이것이 약간 더 과적합되기 어렵다는 것을 알아냈다.

3.5 Overall Architecture

이제 우리는 우리의 CNN의 전체 구조에 대해 설명할 준비가 되었다.

그림 2에 묘사된 것과 같이, 신경망은 가중치가 있는 8개 레이어를 가지고 있으며, 처음 5개는 컨볼루션 레이어, 나머지 3개는 완전 연결층으로 이루어져 있다.

마지막 완전 연결층의 출력은 1000-way 소프트맥스 함수에 입력되어 1000개가 넘는 레이블 분포를 제공한다.

우리의 신경망은 다중 로지스틱 회귀를 최대화하며, 이는 예측 분포 하에서 정확한 레이블의 로그 확률의 전체 학습 예제 평균을 최대화하는 것과 동일하다.

두번째, 네번째, 다섯번째 컨볼루션 레이어의 커널들은 동일한 GPU에 있는 이전 레이어의 커널 맵들과 연결되어 있다.

세번째 컨볼루션 레이어의 커널은 두번째 레이어의 모든 커널맵과 연결되어 있다.

완전 연결층에 있는 뉴런들은 이전 레이어의 모든 뉴런들과 연결되어 있다.

응답 정규화 레이어는 첫번째와 두번째 컨볼루션 레이어 다음에 온다.

섹션 3.4에서 말했듯이, 맥스 풀링 레이어는 응답 정규화 레이어와 다섯번째 컨볼루션 레이어 다음에 온다.

ReLu 활성화 함수는 모든 컨볼루션 레이어와 완전 연결층의 출력에 적용되었다.

첫번째 컨볼루션 레이어는 224x224x3 크기의 입력 이미지를 11x11x3 크기의 커널 96개로 필터링하며, 스트라이드는 4 픽셀이다. (이는 커널맵에서 인접한 뉴런의 수용 영역 중심 사이의 거리이다.)

두번째 컨볼루션 레이어는 첫번째 컨볼루션 레이어의 (응답 정규화되고 풀링된) 출력으로 입력을 받으며, 5x5x48 크기의 커널 256개로 필터링한다.

세번째, 네번째, 다섯번째 컨볼루션 레이어는 중간에 풀링 레이어나 정규화 레이어 없이 서로 연결되어 있다.

세번째 컨볼루션 레이어는 3x3x256 크기의 커널 384개를 가지며, 두번째 컨볼루션 레이어의 (정규화되고 풀링된) 출력과 연결된다.

네번째 컨볼루션 레이어는 3x3x192 크기의 커널 384개를 가지고, 다섯번째 컨볼루션 레이어는 3x3x192 크기의 커널 256개를 가진다.

완전 연결층은 각각 4096개의 뉴런들을 가진다.

4 Reducing Overfitting

우리의 신경망 구조는 6천만개의 파라미터를 가진다.

ILSVRC의 1000개 클래스는 각 훈련 세트가 이미지에서 레이블로의 매핑에 10 비트의 제약을 가하도록 만들지만, 이는 과도학 과적합 없이 매우 많은 파라미터를 학습하기에는 불충분하다는 것이 드러났다.

아래에, 우리는 우리가 과적합에 맞선 두 가지 주요한 방법을 설명한다.

4.1 Data Augmentation

이미지 데이터에서 과적합을 줄이는 가장 쉽고 일반적인 방법은 레이블 보존 변형을 사용하여 데이터셋을 인공적으로 커지게 하는 것이다

우리는 두 가지 다른 형태의 데이터 증강 기법을 사용하는데, 두 기법 모두 원본 이미지로부터 매우 적은 연산으로 변형된 이미지를 생성할 수 있게 하므로 변형된 이미지를 디스크에 저장할 필요가 없다.

우리의 방법에서, 이미지의 이전 배치를 GPU가 학습하는 동안 CPU 안에 있는 파이썬 코드에서 변형된 이미지가 생성된다.

그래서 이 데이터 증강 기법은 연산적으로 자유롭다

데이터 증강의 첫번째 형태는 이미지 이동과 수평 반사를 생성하는 것으로 구성되어 있다.

우리는 256x256 크기의 이미지로부터 무작위의 224x224 패치들을 (그리고 이들의 수평 반사를) 추출하며, 이러한 추출된 패치들로 우리의 신경망을 학습시키는 것이다. (이는 그림 2의 입력 이미지가 224x224x3차원인 이유이다.)

이것은 우리의 훈련 세트의 크기를 2048배로 증가시키며, 결과적으로 훈련 예제들은 당연히 매우 상호 의존적이다.

이 방법 없이는, 우리의 신경망은 상당한 과적합으로부터 시달리며, 이는 우리에게 더 작은 신경망을 사용하도록 할 것이다.

테스트 시에는, 신경망은 5개의 224x224 크기의 패치(4개의 모서리 패치와 하나의 중간 패치)들과 이들의 수평 반사를 추출하며 (따라서 총 10개의 패치), 신경망의 소프트맥스 레이어가 10개 패치에 대한 예측의 평균을 내어 예측을 수행한다.

데이터 증강의 두 번째 방법은 학습이미지의 RGB 채널의 강도를 변환시키는 것으로 구성되어 있다.

특히, 우리는 모든 ImageNet 훈련 세트의 RGB 픽셀값의 집합에 PCA를 수행한다.

각각의 학습 이미지에 울리는 발견된 주성분들의 배수를 더하는데, 이때 배수의 크기는 평균이 0이고 표준 편차가 0.1인 가우시안 분포에서 추출한 난수를 해당 고윳값에 곱한 것과 비례한다.

그러므로 각 RGB 이미지 픽셀 $I_{xy}=[I_{xy}^R,I_{xy}^G,I_{xy}^B]^T$에 다음 값을 더한다. $[p_1,p_2,p_3][α_1λ_1,α_2λ_2,α_3λ_3]^T$

여기서 $p_i$와 $λ_i$는 RGB 픽셀값의 3 x 3 공분산 행렬의 $i$번째 고유 벡터와 고유값이며, $α_i$는 앞서 언급한 난수이다

각 $α_i$는 특정 학습 이미지의 모든 픽셀에 대해 한 번만 그려지며, 해당 이미지가 다시 학습에 사용될 때까지 유지되다가, 다시 사용될 때 그려진다.

이 방식은 자연 이미지의 주요한 속성을 근사적으로 포착한다. 즉, 객체의 정체성은 조명의 강도와 색생의 변화에 따라 다양해지지 않는다.

이 방법은 줄인다 / 상위 1개 오류율을 1% 이상으로

이 방법은 top-1 오류율을 1% 이상 줄인다.

4.2 Dropout

많은 모델들의 예측을 결합하는 것은 테스트 오류율을 줄이는 데에 매우 성공적인 방법이나, 이는 학습에 이미 몇일이 걸린 큰 신경망에서 너무 비용이 많이 드는 것으로 나타난다.

그러나 이는 학습에 오직 두배정도 밖에 들지 않는 모델 결합의 매우 효율적인 방법이다,

드롭아웃이라고 불리는 최근 소개된 기술은 0.5의 확률로 각 은닉층의 출력을 0으로 두는 것이다.

이 방법으로 드롭아웃된 뉴런은 순전파에 기여하지 않으며, 역전파에 참여하지 않는다.

그래서 매번 입력이 전달되었을 때, 신경망은 다른 구조로 샘플링되지만, 이 구조는 가중치를 공유한다.

이 기술은 뉴런의 복잡한 상호 적응을 줄이는데, 이는 뉴런이 특정 다른 뉴런의 존재에 의존할 수 없기 때문이다.

이는 따라서, 다른 뉴런들의 많은 다른 무작위 부분집합과 함께 유용하게 사용될 수 있는 더욱 견고한 특징들을 학습해야 한다.

테스트 시에, 우리는 모든 뉴런을 사용하지만, 출력에 0.5ㄹ를 곱하는데, 이는 기하급수적으로 많은 드롭아웃 네트워크에서 제공된 예측 분포의 기하 평균을 취하는 것에 대한 의미있는 근사치이다.

우리는 그림 2의 처음 두 개의 완전 연결층에서 드롭아웃을 사용한다.

드롭아웃 없이는, 우리의 신경망은 상당한 과적합을 보여준다.

드롭아웃은 수렴에 필요한 반복의 수를 대략 두 배 증가시킨다.

5 Details of learning

우리는 크기 128의 배치와 0.9의 모멘텀으로 확률적 경사하강법을 사용하여 우리의 모델을 학습시켰으며, 가중치 감소는 0.0005로 하였다.

우리는 모델이 학습하기 위해 이 작은 양의 가중치 감소가 중요하다는 것을 알아냈다.

다시 말해, 이 가중치 감소는 단지 규제가 아니다: 이것은 모델의 학습 오류를 줄인다.

가중치 $w$의 갱신 규칙은 다음과 같으며, (수식) $i$는 반복 인덱스, $v$는 모멘텀 변수, $ϵ$는 학습률이고, 미분식은 $w$에 대한 목적 함수의 미분값의 $i$번째 배치 $D_i$에 대한 평균이며, $w_i$에서 평가된다.

우리는 각 레이어에서 가중치를 표준편차 0.01, 평균이 0인 가우시안 분포로부터 초기화했다.

우리는 두번째, 네번째, 다섯번째 레이어와 완전 연결 은닉층에 있는 바이어스를 상수 1로 초기화했다.

이 초기화는 ReLU 함수에 양의 입력을 제공함으로써 학습의 초기 단계를 가속한다.

우리는 나머지 레이어에 있는 바이어스를 상수 0으로 초기화했다.

우리는 모든 레이어에 대해 동일한 학습률을 사용했으며, 이는 우리가 학습에 걸쳐 수동적으로 조정한 것이다.

우리가 따른 휴리스틱은 검증 오류율이 현재 학습률에서 향상되는 것을 멈췄을 때 학습률을 10으로 나누는 것이다.

학습률은 0.01로 초기화되었으며, 종료전에 3번 감소되었다.

우리는 NVIDIA GTX 580 3GB GPU로 약 90 사이클 동안 120만개의 이미지로 신경망을 학습시켰으며, 이는 5~6일 걸렸다.

6 Results

ILSVRC-2010에서의 우리의 결과는 표 1에 요약되어 있다.

우리의 신경망은 상위 1개, 상위 5개 항목 테스트 세트에서 37.5%와 17.0% 오류율을 달성했다.

ILSVRC-2010 대회동안 달성된 가장 좋은 성능은 서로 다른 특징으로 학습된 6개의 츼소 코딩 모델의 예측을 평균내는 접근을 사용한 47.1%와 28.2% 였으며, 이후로 발표된 가장 좋은 결과는 두 유형의 밀집 샘플링된 특징으로부터 계산된 Fisher Vector(FVs)로 학습된 두 개의 분류기의 예측을 평균내는 접근을 사용한 45.7%와 25.7% 였다.

우리는 또한 우리의 모델로 ILSVRC-2012대회에 제출하였으며, 이에 대한 결과는 표 2에 제시되어있다.

ILSVRC-2012 테스트 세트 레이블은 사용할 수 없으므로, 우리는 우리가 시도했던 전체 모델에 대한 테스트 오류율을 작성할 수 없다.

이 단락의 마지막부분에, 우리는 검증 오류율과 테스트 오류율을 상호 교환적으로 사용했다. 왜냐하면 우리의 경험에서 이들은 0.1% 이상만큼 다르지 않았기 때문이다. (표 2)

이 논문에서 소개된 CNN은 상위 5개 항목 오류율에서 18.2%를 달성했다.

5개이 비슷한 CNN의 예측을 평균낸 것은 16.4%의 오류율을 달성했다.

마지막 풀링 레이어 위에 6번째 컨볼루션 레이어를 추가하여 하나의 CNN을 학습시키는 것은 전체 ImageNet Fall 2011 이미지들을 분류하기 위한 것이며, 이를 ILSVRC-2012로 파인 튜닝 한 것은 16.6%의 오류율을 달성했다.

앞서 언급한 5개의 CNN을 사용하여 전체 Fall 2011 데이터로 사전학습된 두 개의 CNN의 예측을 평균낸 것은 15.3%의 오류율을 달성했다.

두번재로 좋았던 대회 결과는 서로 다른 밀집 샘플링 특징으로 계산된 FVs로 학습된 몇 개의 분류기의 예측을 평균내는 접든법으로 26.2%의 오류율을 달성했다.

마지막으로 우리는 10184개의 카테고리와 890만개 이미지가 있는 ImageNet의 Fall 2009 버전에서의 우리의 오류율을 제시한다.

이 데이터셋에서 우리는 문헌에서 통용되는 관례에 따라 절반의 이미지는 학습으로, 나머지는 테스트용으로 사용했다.

확립된 테스트 세트가 없기 때문에, 우리의 데이터 분할은 이전 저자들이 사용한 데이터 분할과 필연적으로 다르지만, 이는 결과에 눈에 띄는 영향은 없다.

이 데이터 셋에서의 상위 1개, 상위 5개 항목 오류율은 67.4%와 40.9% 이며, 이는 위에서 설명한 신경망의 마지막 풀링 레이어 위에 6번째 컨볼루션 레이어를 추가한 결과이다.

이 데이터 셋에서 발표된 가장 좋은 결과는 78.1%와 60.9%이다.

6.1 Qualitative Evaluations

그림 3은 신경망의 두 개의 데이터 연결 레이어로 학습된 컨볼루션 커널을 보여준다.

신경망 다양한 주파수 및 방향 선택적 커널과 다양한 colored blob들로 학습되었다.

섹션 3.5에서 설명한 제한된 연결성으로 인한 결과는 두 GPU가 보이는 특수화 현상에 주목해라.

GPU 2에 있는 커널들이 색상에 특화된 것과 달리, GPU 1에 있는 커널들은 색상에 구애받지 않는다.

이러한 특수화는 모든 실행동안 발생하며, 어떤 특정한 무작위 가중치 초기화와는 독립적이다. (GPU 번호 재지정은 제외)

그림 4

(왼쪽) 8개의 ILSVRC-2010 테스트 이미지와 우리 모델이 가장 가능성이 높다고 판단한 5개의 레이블.

각 이미지 아래에는 정답 레이블이 적혀 있으며, 정답 레이블에 할당된 확률도 표시된다.

(상위 5개 안에 드는 경우) 빨간색 막대로 표시된다.

(오른쪽) 첫 번째 열에는 5개의 ILSVRC-2010 테스트 이미지가 있다.

나머지 열에는 마지막 은닉층에서 테스트 이미지의 특징 벡터와 유클리드 거리가 가장 작은 특징 벡터를 생성하는 6개의 훈련 이미지가 표시된다.

그림 4의 왼쪽은 8개 이미지에 대한 상위 5개 예측을 계산하는 것으로 신경망이 학습된 것을 질적으로 평가한다.

왼쪽 상단의 진드기와 같이 중앙에서 벗어난 객체조차도 신경망이 인지할 수 있다는 점에 주목해야한다.

대부분의 상위 5개 레이블은 의미있는 것으로 나타났다.

예를 들어, 고양이의 다른 유형들은 표범을 지칭하는 데에 그럴듯한 레이블로 고려되었다.

그릴, 체리와 같은 몇몇 케이스에서는 사진의 의도된 초점에 의한 모호성이 있다.

신경망의 시각적 지능을 증명하는 다른 방법은 이미지가 마지막 4096 차원의 은닉층에서 유도하는 특징 활성화를 고려하는 것이다.

만약 두 이미지가 작은 유클리드 분할과 함께 특징 활동 벡터를 제공한다면, 우리는 신경망의 더 높은 수준은 그들을 비슷하게 고려한다고 말할 수 있다.

그림 4는 이 측정에 따라 가장 비슷한 테스트 세트의 5개 이미지와 훈련 세트의 6개의 이미지를 보여준다.

픽셀 수준에서, 검색된 훈련 이미지는 일반적으로 첫번째 열의 쿼리 이미지와 L2 해상도에서 가깝지 않다는 것에 주목해야 한다.

예를 들어, 검색된 강아지와 코끼리는 다양한 자세로 나타난다.

우리는 보충 재료에서 더 많은 테스트 이미지에 대한 결과를 보여준다.

4096 차원인 실수 벡터 두 개의 유사도를 유클리드 거리를 이용해 계산하는 것은 불충분하지만, 이는 이러한 벡터를 짧은 이진 코드로 압축하기 위해 오토 인코더를 학습함으로써 효율적이게 될 수 있다.

이것은 이미지 레이블을 사용하지 않고 의미적으로 유사한지 여부에 관계없이 유사한 에지 패턴을 가진 이미지를 검색하는 경향이 있는 원시 픽셀에 오토인코더를 적용하는 것보다 훨씬 더 나은 이미지 검색 방법을 생성해야 한다.

7 Discussion

우리의 결과는 순수 지도 학습을 사용하여 매우 도전적인 데이터 셋에서 기록을 깨는 결과는 크고, 깊은 CNN이 달성할 수 있다는 것을 보여준다.

만약 하나의 컨볼루션 레이어라도 제거한다면 우리의 신경망의 성능은 저하될 수 있다는 것은 주목할만 하다.

예를 들어, 신경망의 아무 중간 레이어를 제거하는 것은 상위 1개 항목 성능에서 약 2%의 손실을 야기한다.

그래서 우리의 결과를 달성하는 것에서 깊이는 매우 중요하다.

우리의 실험을 단순화하기 위해, 우리는 비지도 사전학습이 비록 도움이 될 것이라고 예상했지만, 특히 레이블된 데이터의 양의 증가 없이 신경망의 크기를 주요하게 증가시키기 위한 충분한 연산 성능을 얻더라도, 아무런 비지도 사전학습을 사용하지 않았다.

또한 지금까지, 우리의 결과는 우리가 신경망을 더 크게하고 더 오래 학습시킴으로 향상되었지만, 우리는 인간 시각 시스템의 하측두 피질을 따라잡기 위해 갈길이 멀다.

궁극적으로 우리는 영상 시퀀스에 매우 크고 깊은 CNN을 사용하고자 하며, 이는 시간적 구조가 정적인 이미지에서는 놓치고 훨씬 덜 명백한 매우 도움되는 정보를 제공한다.

Reference

https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf

💡 문제

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다. 다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

최초의 대장균 개체의 PARENT_ID 는 NULL 값입니다.

분화된 연도(YEAR), 분화된 연도별 대장균 크기의 편차(YEAR_DEV), 대장균 개체의 ID(ID) 를 출력하는 SQL 문을 작성해주세요. 분화된 연도별 대장균 크기의 편차는 분화된 연도별 가장 큰 대장균의 크기 - 각 대장균의 크기로 구하며 결과는 연도에 대해 오름차순으로 정렬하고 같은 연도에 대해서는 대장균 크기의 편차에 대해 오름차순으로 정렬해주세요.

💭 접근

이 문제를 해결하기 위해선 먼저 연도별 가장 큰 대장균 크기를 구한 뒤, 모든 행에 대해 각자의 연도에 맞는 대장균 크기를 빼주면 된다. 이를 위해선 JOIN 절에 서브쿼리를 사용해야 한다.

SELECT  YEAR(DIFFERENTIATION_DATE) AS DIFF_YEAR
        ,MAX(SIZE_OF_COLONY) AS MAX_SIZE
  FROM  ECOLI_DATA
 GROUP
    BY  DIFF_YEAR;

위 코드를 실행시키면 연도와 연도별 가장 큰 대장균의 크기를 구할 수 있다.

이를 ECOLI_DATA와 연도를 KEY로 JOIN하여 연도별 가장 큰 대장균의 크기에서 연도에 맞는 각각의 대장균의 크기를 빼주면 해결할 수 있다.

📒 코드

SELECT  YEAR(A.DIFFERENTIATION_DATE) AS YEAR
        ,B.MAX_SIZE - A.SIZE_OF_COLONY AS YEAR_DEV
        ,A.ID
  FROM  ECOLI_DATA AS A
  LEFT
  JOIN  (SELECT  YEAR(DIFFERENTIATION_DATE) AS DIFF_YEAR
                 ,MAX(SIZE_OF_COLONY) AS MAX_SIZE
           FROM  ECOLI_DATA
          GROUP
             BY  DIFF_YEAR) AS B
    ON  YEAR(A.DIFFERENTIATION_DATE) = B.DIFF_YEAR
 ORDER
    BY  YEAR(A.DIFFERENTIATION_DATE) ASC
        ,YEAR_DEV ASC;

💭 후기

JOIN 절에 서브쿼리를 사용할 수 도 있다는 것을 알게되었다.

🔗 문제 출처

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

💡 문제

HR_DEPARTMENT 테이블은 회사의 부서 정보를 담은 테이블입니다. HR_DEPARTMENT 테이블의 구조는 다음과 같으며 DEPT_ID, DEPT_NAME_KR, DEPT_NAME_EN, LOCATION은 각각 부서 ID, 국문 부서명, 영문 부서명, 부서 위치를 의미합니다.

HR_EMPLOYEES 테이블은 회사의 사원 정보를 담은 테이블입니다. HR_EMPLOYEES 테이블의 구조는 다음과 같으며 EMP_NO, EMP_NAME, DEPT_ID, POSITION, EMAIL, COMP_TEL, HIRE_DATE, SAL은 각각 사번, 성명, 부서 ID, 직책, 이메일, 전화번호, 입사일, 연봉을 의미합니다.

HR_GRADE 테이블은 2022년 사원의 평가 정보를 담은 테이블입니다. HR_GRADE의 구조는 다음과 같으며 EMP_NO, YEAR, HALF_YEAR, SCORE는 각각 사번, 연도, 반기, 평가 점수를 의미합니다.

HR_DEPARTMENT, HR_EMPLOYEES, HR_GRADE 테이블에서 2022년도 한해 평가 점수가 가장 높은 사원 정보를 조회하려 합니다. 2022년도 평가 점수가 가장 높은 사원들의 점수, 사번, 성명, 직책, 이메일을 조회하는 SQL문을 작성해주세요.

2022년도의 평가 점수는 상,하반기 점수의 합을 의미하고, 평가 점수를 나타내는 컬럼의 이름은 SCORE로 해주세요.

💭 접근

이 문제는 두개의 서브쿼리를 이용하여 해결할 수 있는 문제이다. 실행되는 서브쿼리의 순서에 따라 살펴보자.

1. HR_GRADE 테이블에서 YEAR 이 2022인 데이터 중 EMP_NO 별 SCORE의 합을 구하는 서브쿼리

   SELECT  SUM(SUB1.SCORE) AS `SCORE_SUM`
   FROM  HR_GRADE AS SUB1
   WHERE  SUB1.YEAR = 2022 
   GROUP
    BY  SUB1.EMP_NO) AS SUB2

   해당 서브쿼리를 실행하면 아래 예시와 같은 테이블이 출력된다.

ex.

2. 위 테이블을 다음 서브쿼리의 FROM 절에 전달하여 SCORE_SUM의 최대값을 구한다.

   SELECT  MAX(SUB2.SCORE_SUM) AS `SCORE_MAX`
   FROM  (SELECT  SUM(SUB1.SCORE) AS `SCORE_SUM`
           FROM  HR_GRADE AS SUB1
          WHERE  SUB1.YEAR = 2022       
          GROUP
             BY  SUB1.EMP_NO) AS SUB2)

해당 서브 쿼리는 MAX 함수를 사용하여 이전 서브쿼리에서 구한 SCORE_SUM의 최대값을 출력한다. 결과는 아래 예시와 같다.

ex.

이제 이렇게 구한 SCORE_MAX 값을 HAVING 절에 전달하여 SCORE의 합이 SCORE_MAX와 같은 사원의 정보를 출력하면 된다.

📒 코드

SELECT  SUM(B.SCORE) AS `SCORE`
        ,B.EMP_NO AS EMP_NO
        ,A.EMP_NAME AS EMP_NAME
        ,A.POSITION AS POSITION
        ,A.EMAIL AS EMAIL
  FROM  HR_EMPLOYEES AS A
  LEFT
  JOIN  HR_GRADE AS B
    ON  A.EMP_NO = B.EMP_NO
 WHERE  B.YEAR = 2022
 GROUP
    BY  B.EMP_NO
HAVING  `SCORE` = (SELECT  MAX(SUB2.SCORE_SUM) AS `SCORE_MAX`
                     FROM  (SELECT  SUM(SUB1.SCORE) AS `SCORE_SUM`
                              FROM  HR_GRADE AS SUB1
                             WHERE  SUB1.YEAR = 2022
                             GROUP
                                BY  SUB1.EMP_NO) AS SUB2);

💭 후기

두개의 서브쿼리를 사용하는 문제는 처음이라 까다로웠다.

🔗 문제 출처

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

💡 문제

오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.

• 막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C
• 게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.
• 모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.
• 한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.
• 게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.
• 되도록 최소로 움직여야 한다.

막대 A, 막대 B, 막대 C에 놓여져 있는 원판의 상태가 주어졌을 때, 게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주어진다. 막대의 상태는 밑에 있는 원판부터 주어진다.

각 막대의 상태는 A, B, C로만 이루어진 문자열이며, 모든 막대에 놓여져 있는 원판 개수의 합은 1보다 크거나 같고, 10보다 작거나 같다.

출력

게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 출력한다.

💭 접근

이 문제는 BFS를 사용하여 간단하게 해결할 수 있다.

다만 입력으로 주어지는 막대의 상태를 저장할 때 해당 막대에 원판이 하나도 없는 경우 따로 원판에 대해 입력이 없기 때문에 해당 막대의 원판의 개수가 0인 경우는 ''를 저장하고 아닌 경우에 입력으로 주어지는 원판의 상태를 저장하면 된다.

s = []
for _ in range(3):
    disc = list(input().split()) 
    if disc[0] == '0':
        s.append('')
    else:
        s.append(disc[1])

이제 bfs() 함수를 보자.

def bfs():
    q = deque()
    q.append([s[:], 0])

    visited.add(s[0] + ' ' + s[1] + ' ' + s[2])

    while q:
        sticks, cnt = q.popleft()

        if check(sticks[0], sticks[1], sticks[2]):
            return cnt

        for curr in range(3):
            if len(sticks[curr]) == 0:
                continue
            for next in range(3):
                if curr != next:
                    n_sticks = sticks[:]

                    n_sticks[next] += n_sticks[curr][-1]
                    n_sticks[curr] = n_sticks[curr][:len(n_sticks[curr]) - 1]

                    v = n_sticks[0] + ' ' + n_sticks[1] + ' ' + n_sticks[2]
                    if v not in visited:
                        visited.add(v)
                        q.append([n_sticks[:], cnt + 1])

여기선 간단하게 막대 3개를 순회하며 동일한 막대에서 움직이는 경우를 제외하고 다른 막대로 옮길 수 있는 경우만 확인한다.

이때 3개의 막대의 상태가 중복되지 않도록 방문 처리를 하는 visited를 set() 자료형으로 선언하여 중복 체크를 해주면 된다.

📒 코드

from collections import deque

def bfs():
    q = deque()
    q.append([s[:], 0])

    visited.add(s[0] + ' ' + s[1] + ' ' + s[2])

    while q:
        sticks, cnt = q.popleft()

        if check(sticks[0], sticks[1], sticks[2]):
            return cnt

        for curr in range(3):
            if len(sticks[curr]) == 0:
                continue
            for next in range(3):
                if curr != next:
                    n_sticks = sticks[:]

                    n_sticks[next] += n_sticks[curr][-1]
                    n_sticks[curr] = n_sticks[curr][:len(n_sticks[curr]) - 1]

                    v = n_sticks[0] + ' ' + n_sticks[1] + ' ' + n_sticks[2]
                    if v not in visited:
                        visited.add(v)
                        q.append([n_sticks[:], cnt + 1])

def check(a, b, c):
    if 'B' not in a and 'C' not in a:
        if 'A' not in b and 'C' not in b:
            if 'A' not in c and 'B' not in c:
                return True
    return False

s = []
for _ in range(3):
    disc = list(input().split()) 
    if disc[0] == '0':
        s.append('')
    else:
        s.append(disc[1])
visited = set()

print(bfs())

💭 후기

오랜만에 간단한 BFS 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/12906

💡 문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

💭 접근

이 문제는 입력으로 주어진 숫자들을 이진화하여 벽의 유무를 파악한 뒤 탐색을 이어나가는 문제이다.

사실 이 부분만 해결된다면 나머지는 이제까지 많이 만나왔던 문제 유형이다.

하나씩 차근차근 살펴보자.

1. 우선 서로 구별되어 있는 방의 개수를 구해야 하므로 각 칸에 존재하는 숫자를 이진화하여 각 방들을 그룹화한다.

   # 서 북 동 남
   dx = [0, -1, 0, 1]
   dy = [-1, 0, 1, 0]
   

group_num = 0 for x in range(m): for y in range(n): if grouped[x][y] == -1: size = 1 bfs(x, y) group_num += 1 group_size.append(size)

```python
def bfs(x, y):
    global size

    q = deque()
    q.append([x, y])

    grouped[x][y] = group_num
    while q:
        x, y = q.popleft()

        curr = graph[x][y]
        for i in range(3, -1, -1): # 남 동 북 서
            if curr >= 2**i:
                curr -= 2**i
            else:
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < m and 0 <= ny < n and grouped[nx][ny] == -1:
                    grouped[nx][ny] = group_num
                    size += 1
                    q.append([nx, ny])

이때 코드를 잘보면 각 방을 그룹화하면서 각 방의 크기까지 동시에 저장해야 불필요한 계산을 방지할 수 있다.

각 방의 숫자를 통해 벽을 찾고, 탐색하는 코드를 살펴보자

curr = graph[x][y]
for i in range(3, -1, -1): # 남 동 북 서
    if curr >= 2**i:
        curr -= 2**i
    else:
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < m and 0 <= ny < n and grouped[nx][ny] == -1:
            grouped[nx][ny] = group_num
            size += 1
            q.append([nx, ny])

위 코드가 핵심인데, 각 칸에 적혀있는 숫자를 8, 4, 2, 1 순으로 비교하며 크다면 벽이 존재하는 것이므로 탐색X, 만약 작다면 벽이 존재하지 않는 것이므로 탐색을 진행한다.

예를 들어 임의의 한 칸에 11이라는 숫자가 적혀있다고 가정해보자.

ex. curr = 11 i = 3 -> 11은 8보다 크므로 벽 존재 남쪽 방향 벽 존재, 11에서 8을 뺀다. i = 2 -> 3은 4보다 작으므로 벽 존재 X 동쪽 방향 벽 없음, 탐색 진행 i = 1 -> 3은 2보다 크므로 벽 존재 북쪽 방향 벽 존재, 3에서 2를 뺀다. i = 0 -> 1은 0보다 크므로 벽 존재 서쪽 방향 벽 존재
따라서 11은 (1011) 이므로 동쪽 방향에서만 탐색을 진행한다.

위 과정을 거치면 예제를 예시로 들었을 때 아래 그림과 같이 저장된다.

2. 이제 마지막으로 인접한 서로 다른 두 그룹의 크기를 더하여 벽을 하나 허물었을 때 구할 수 있는 가장 큰 그룹의 크기를 구하면 된다.

   merged_size = 0
   for x in range(m):
    for y in range(n):
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
   
            if 0 <= nx < m and 0 <= ny < n and grouped[x][y] != grouped[nx][ny]:
                merged_size = max(merged_size, 
                                  group_size[grouped[x][y]] + group_size[grouped[nx][ny]])

📒 코드

from collections import deque

def bfs(x, y):
    global size

    q = deque()
    q.append([x, y])

    grouped[x][y] = group_num
    while q:
        x, y = q.popleft()

        curr = graph[x][y]
        for i in range(3, -1, -1): # 남 동 북 서
            if curr >= 2**i:
                curr -= 2**i
            else:
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < m and 0 <= ny < n and grouped[nx][ny] == -1:
                    grouped[nx][ny] = group_num
                    size += 1
                    q.append([nx, ny])

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
grouped = [[-1 for _ in range(n)] for _ in range(m)]
group_size = []

# 서 북 동 남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

group_num = 0
for x in range(m):
    for y in range(n):
        if grouped[x][y] == -1:
            size = 1
            bfs(x, y)
            group_num += 1
            group_size.append(size)

merged_size = 0
for x in range(m):
    for y in range(n):
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n and grouped[x][y] != grouped[nx][ny]:
                merged_size = max(merged_size, 
                                  group_size[grouped[x][y]] + group_size[grouped[nx][ny]])
print(len(group_size))
print(max(group_size))
print(merged_size)

💭 후기

벽의 존재 유뮤를 숫자로 나타내어 재밌었던 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/2234

💡 문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. #는 문이 설치된 곳으로 항상 두 곳이며, .은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. !은 거울을 설치할 수 있는 위치를 나타내고, *은 빛이 통과할 수 없는 벽을 나타낸다.

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

💭 접근

이 문제를 처음 풀었을 때 다익스트라와 비슷한 방식으로 나아가며 현재까지 설치한 거울의 개수를 저장하고, 개수가 적을 때만 동일한 칸을 다시 방문 할 수 있도록 구현하였지만 메모리초과가 발생하였다.

따라서 따로 방문 체크를 하지않고 단순히 거울을 최대한 설치하지 않는 방향으로 나아가고, BFS를 사용하여 가장 먼저 도착할 때 최적해를 구할 수 있도록 구현하였다.

1. 먼저 시작 지점에서 나아갈 수 있는 모든 방향을 탐색한다.

   ans = float('inf')
   for i in range(4):
    nx = start_x + dx[i]
    ny = start_y + dy[i]
   
    if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
        start_dir = i
        bfs(start_x, start_y, start_dir, 0)

2. 빛의 특성 상, 벽이나 거울을 만나지 않는 한 계속해서 앞으로 나아가므로 벽과 거울을 만날 때까지 현재 방향을 유지하며 나아간다.

   while q:
    x, y, dir, cnt = q.popleft()
   
    mirror = False
    while True:
        if x == end_x and y == end_y:
            ans = min(ans, cnt)
            return
   
        x += dx[dir]
        y += dy[dir]
   
        if 0 <= x < n and 0 <= y < n:
            if graph[x][y] == '*':
                break
            if graph[x][y] == '!':
                mirror = True
                break
        else:
            break

3. 만약 거울을 만났다면 다음으로 나아갈 수 있는 방향을 정한다.

   if mirror:
    if dir == 0: back = 1
    elif dir == 1: back = 0
    elif dir == 2: back = 3
    elif dir == 3: back = 2
   
    for i in range(4):
        if i != back:
            nx = x + dx[i]
            ny = y + dy[i]
   
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
                if i == dir:
                    q.appendleft([x, y, i, cnt])
                else:
                    q.append([x, y, i, cnt + 1])

거울을 만났을 때 빛이 나아갈 수 있는 방향은 현재방향유지(거울 설치 X) 또는 거울을 설치하여 굴절되는 방향이며, 다시 반대로 반사될 수 없다.

이때, 설치한 거울의 최소를 구해야 하므로 거울을 설치하지 않고 현재 방향을 유지하며 나아가는 것을 우선적으로 탐색한다.

📒 코드

from collections import deque

def bfs(x, y, dir, cnt):
    global ans

    q = deque()
    q.append([x, y, dir, cnt])

    while q:
        x, y, dir, cnt = q.popleft()

        mirror = False
        while True:
            if x == end_x and y == end_y:
                ans = min(ans, cnt)
                return

            x += dx[dir]
            y += dy[dir]

            if 0 <= x < n and 0 <= y < n:
                if graph[x][y] == '*':
                    break
                if graph[x][y] == '!':
                    mirror = True
                    break
            else:
                break

        if mirror:
            if dir == 0: back = 1
            elif dir == 1: back = 0
            elif dir == 2: back = 3
            elif dir == 3: back = 2

            for i in range(4):
                if i != back:
                    nx = x + dx[i]
                    ny = y + dy[i]

                    if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
                        if i == dir:
                            q.appendleft([x, y, i, cnt])
                        else:
                            q.append([x, y, i, cnt + 1])

n = int(input())
graph = [list(input()) for _ in range(n)]
door = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == '#':
            door.append([i, j])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

start_x, start_y = door[0]
end_x, end_y = door[1]

ans = float('inf')
for i in range(4):
    nx = start_x + dx[i]
    ny = start_y + dy[i]

    if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
        start_dir = i
        bfs(start_x, start_y, start_dir, 0)
print(ans)

💭 후기

BFS 문제를 풀며 방문처리를 하지 않는 경우가 드물기에 풀이 방법을 떠올리는 것이 까다로웠던 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/2151

💡 문제

다음은 어느 의류 쇼핑몰에서 판매중인 상품들의 상품 정보를 담은 PRODUCT 테이블과 오프라인 상품 판매 정보를 담은 OFFLINE_SALE 테이블 입니다. PRODUCT 테이블은 아래와 같은 구조로 PRODUCT_ID, PRODUCT_CODE, PRICE는 각각 상품 ID, 상품코드, 판매가를 나타냅니다.

상품 별로 중복되지 않는 8자리 상품코드 값을 가지며, 앞 2자리는 카테고리 코드를 의미합니다.

OFFLINE_SALE 테이블은 아래와 같은 구조로 되어있으며 OFFLINE_SALE_ID, PRODUCT_ID, SALES_AMOUNT, SALES_DATE는 각각 오프라인 상품 판매 ID, 상품 ID, 판매량, 판매일을 나타냅니다.

동일한 날짜, 상품 ID 조합에 대해서는 하나의 판매 데이터만 존재합니다.

PRODUCT 테이블과 OFFLINE_SALE 테이블에서 상품코드 별 매출액(판매가 * 판매량) 합계를 출력하는 SQL문을 작성해주세요. 결과는 매출액을 기준으로 내림차순 정렬해주시고 매출액이 같다면 상품코드를 기준으로 오름차순 정렬해주세요.

💭 접근

이 문제는 간단한 JOIN, GROUP BY를 사용한 문제이다.

먼저 오프라인 판매량을 알기위해 PRODUCT 테이블과 OFFLINE_SALE 테이블을 JOIN 해준다.

이때 주의해야할 점으론, PRODUCT 테이블을 기준으로 JOIN 할 경우 오프라인으로 판매되지 않은 상품까지 집계될 수 있으므로 OFFLINE_SALE 테이블을 기준으로 JOIN하여 오프라인으로 판매된 상품들에 대해서만 집계될 수 있도록한다.

이후엔 GROUP BY 절을 사용하여 PRODUCY_CODE 별 매출액을 구해주면 된다.

📒 코드

SELECT  A.PRODUCT_CODE
        ,A.PRICE * SUM(B.SALES_AMOUNT) AS SALES
  FROM  PRODUCT AS A
 RIGHT
  JOIN  OFFLINE_SALE AS B
    ON  A.PRODUCT_ID = B.PRODUCT_ID
 GROUP
    BY  A.PRODUCT_CODE
 ORDER
    BY  SALES DESC
        ,PRODUCT_CODE ASC;

💭 후기

테이블을 JOIN 할 때 기준이되는 테이블을 잘 설정해야하는 문제였다.

🔗 문제 출처

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

💡 문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

💭 접근

이 문제를 처음 보았을 때 단순히 BFS를 통해 가장 먼저 도착하는 더러운 지점, 이곳에서 그 다음으로 가까운 더러운 지점까지의 거리를 더하는 방식으로 구현하였지만 실패하였다.

이유는 간단했는데, 아래의 경우를 보자.

. . .
. o *
* * *

이 경우 오른쪽 x를 먼저 방문하는 경우 정답으로 4를, 아래쪽 x를 먼저 방문하는 경우 정답으로 5를 출력하는 것을 알 수 있었다. 따라서 BFS 방문 순서에 따라 정답이 달라질 수 있다는 것을 간과하였던 것이다.

따라서 다른 방법을 생각했는데, 먼저 로봇청소기의 시작지점을 0으로, 나머지 더러운 지점을 1 ~ n까지 번호를 메긴 후, 각 지점에서 다른 모든 지점까지의 거리를 구하여 마지막에 순열을 통해 더러운 지점을 방문할 순서를 정하는 것이다. ** *(더러운 지점의 개수가 10을 넘지 않기에 순열을 사용할 수 있을 것이라고 생각했다.)***

예시와 코드를 보며 이해해보자. 입력으로 아래와 같이 주어졌다고 가정해보자.

. . . . .
. o . * .
. . . . .
. * . * .
. . . . .

1. 입력으로 주어진 graph에 번호를 메기고 각 칸을 저장한다.

spots = []
num = 1
for i in range(h):
    for j in range(w):
        if graph[i][j] == 'o':
            spots.append([i, j])
            graph[i][j] = 0
        if graph[i][j] == '*':
            spots.append([i, j])
            graph[i][j] = num
            num += 1

위 단계를 거치면 graph는 다음과 같이 변경된다.

. . . . .
. 0 . 1 .
. . . . .
. 2 . 3 .
. . . . .

2. 각 지점에 대해 서로 간의 거리를 구한다. (BFS)

spot_dist = [[float('inf') for _ in range(num)] for _ in range(num)]
for spot in spots:
    x, y = spot
    start_num = graph[x][y]
    spot_dist[start_num][start_num] = 0
    bfs(x, y, start_num)

# BFS 함수
def bfs(x, y, start_num):
    q = deque()
    q.append([x, y, 0])

    visited = [[0 for _ in range(w)] for _ in range(h)]
    visited[x][y] = 1
    while q:
        x, y, cnt = q.popleft()

        if type(graph[x][y]) == int:
            spot_dist[start_num][graph[x][y]] = cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] != 'x' and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append([nx, ny, cnt + 1])

위 단계를 거치면 spot_dist는 다음과 같이 저장된다.

[0, 2, 2, 4]
[2, 0, 4, 2]
[2, 4, 0, 2]
[4, 2, 2, 0]

spot_dist[1][2]는 1번 지점에서 2번지점까지의 거리를 의미한다.

3. 순열을 구하여 더러운 지점을 방문할 순서를 정하고, 정답을 갱신한다. (DFS)

def dfs(curr, cnt, depth):
    global ans

    if depth == num - 1:
        ans = min(ans, cnt)
        return

    for next in range(num):
        if visited[next] == 0:
            visited[next] = 1
            dfs(next, cnt + spot_dist[curr][next], depth + 1)
            visited[next] = 0

이렇게 되면 ans에 모든 더러운 지점을 방문하기 위한 최소 이동 횟수를 구할 수 있으며, 만약 방문 불가능한 칸이 있다면 spot_dist에는 inf 값이 저장되기 때문에 모든 과정을 거친 후에도 ans에 inf값이 저장되어 있다면 -1을 출력한다.

📒 코드

import sys
input = sys.stdin.readline
from collections import deque

def bfs(x, y, start_num):
    q = deque()
    q.append([x, y, 0])

    visited = [[0 for _ in range(w)] for _ in range(h)]
    visited[x][y] = 1
    while q:
        x, y, cnt = q.popleft()

        if type(graph[x][y]) == int:
            spot_dist[start_num][graph[x][y]] = cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] != 'x' and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append([nx, ny, cnt + 1])

def dfs(curr, cnt, depth):
    global ans

    if depth == num - 1:
        ans = min(ans, cnt)
        return

    for next in range(num):
        if visited[next] == 0:
            visited[next] = 1
            dfs(next, cnt + spot_dist[curr][next], depth + 1)
            visited[next] = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    graph = [list(input()) for _ in range(h)]

    spots = []
    num = 1
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 'o':
                spots.append([i, j])
                graph[i][j] = 0
            if graph[i][j] == '*':
                spots.append([i, j])
                graph[i][j] = num
                num += 1

    spot_dist = [[float('inf') for _ in range(num)] for _ in range(num)]
    for spot in spots:
        x, y = spot
        start_num = graph[x][y]
        spot_dist[start_num][start_num] = 0
        bfs(x, y, start_num)

    ans = float('inf')
    visited = [0 for _ in range(num)]
    visited[0] = 1
    dfs(0, 0, 0)

    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

💭 후기

BFS를 사용하여 각 지점 간의 최단거리를 구하고, DFS르 사용하여 각 지점을 방문할 순서를 정하여 정답을 구하는 문제로, 코드 구현은 어렵지 않았지만 아이디어를 떠올리기 까다로운 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/4991

💡 문제

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다.

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 09:00부터 19:59까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

💭 접근

이 문제는 간단하게 HOUR() 함수를 사용하여 GROUP BY를 한 뒤, 09시부터 19시 사이에 있는 입양 건수를 구하면 되는 문제이다.

이때 한가지 살펴볼 점으론, WHERE 절과 HAVING 절의 차이를 볼 수 있다는 점이다.

WHERE 절로 조건을 적용할 시, WHERE절은 GROUP BY 절보다 먼저 실행되어 Row by Row로 각각의 행들을 살펴보는 보기때문에 ALIAS를 사용할 수 없다.

그러나 HAVING 절의 경우 GROUP BY 이후에 실행되기 때문에 먼저 시간대 별로 그룹이 만들어 진 후 조건에 따라 레코드를 필터링 한다. 따라서 ALIAS를 사용할 수 있다.

📒 코드

# WHERE 절
SELECT  HOUR(DATETIME) AS HOUR
        ,COUNT(*) AS COUNT
  FROM  ANIMAL_OUTS
 WHERE  HOUR(DATETIME) BETWEEN 9 AND 19
 GROUP
    BY  HOUR
 ORDER
    BY  HOUR ASC;

# HAVING 절
SELECT  HOUR(DATETIME) AS HOUR
        ,COUNT(*) AS COUNT
  FROM  ANIMAL_OUTS
 GROUP
    BY  HOUR
HAVING  HOUR BETWEEN 9 AND 19
 ORDER
    BY  HOUR ASC;

💭 후기

SQL의 코드 실행 순서를 간단하게 볼 수 있는 문제였다.

🔗 문제 출처

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

💡 문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

💭 접근

이 문제는 간단한 BFS 문제로, 입력으로 주어진 모든 상어의 위치에서 모든 칸의 최소 거리를 구하고, 이 중 최댓값을 구하면 되는 문제이다.

1. 먼저 입력으로 주어진 모든 상어의 위치를 큐에 넣는다.

   for x in range(n):
    for y in range(m):
        if graph[x][y] == 1:
            visited[x][y] = 0
            q.append([x, y])

2. 큐에 입력된 각 상어의 위치를 시작으로 각 칸에 상어와 떨어진 거리를 구한다. 이때 각 칸은 모든 상어와 떨어진 거리의 최솟값을 저장한다.

   while q:
    x, y = q.popleft()
   
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
   
        if 0 <= nx < n and 0 <= ny < m:
            if visited[nx][ny] >= visited[x][y] + 1:
                visited[nx][ny] = visited[x][y] + 1
                q.append([nx, ny])

3. 마지막으로 모든 칸에 대해 최댓값을 구한다.

   ans = 0
   for i in range(n):
        ans = max(ans, max(visited[i]))

📒 코드

from collections import deque

def bfs():
    q = deque()
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 1:
                visited[x][y] = 0
                q.append([x, y])

    while q:
        x, y = q.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if visited[nx][ny] >= visited[x][y] + 1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx, ny])

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[float('inf') for _ in range(m)] for _ in range(n)]

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

bfs()

ans = 0
for i in range(n):
        ans = max(ans, max(visited[i]))
print(ans)

💭 후기

오랜만에 간단한 BFS 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/17086

💡 문제

다음은 어느 자동차 대여 회사에서 대여중인 자동차들의 정보를 담은 CAR_RENTAL_COMPANY_CAR 테이블입니다. CAR_RENTAL_COMPANY_CAR 테이블은 아래와 같은 구조로 되어있으며, CAR_ID, CAR_TYPE, DAILY_FEE, OPTIONS 는 각각 자동차 ID, 자동차 종류, 일일 대여 요금(원), 자동차 옵션 리스트를 나타냅니다.

자동차 종류는 '세단', 'SUV', '승합차', '트럭', '리무진' 이 있습니다. 자동차 옵션 리스트는 콤마(',')로 구분된 키워드 리스트(옵션 리스트 값 예시: '열선시트', '스마트키', '주차감지센서')로 되어있으며, 키워드 종류는 '주차감지센서', '스마트키', '네비게이션', '통풍시트', '열선시트', '후방카메라', '가죽시트' 가 있습니다.

CAR_RENTAL_COMPANY_CAR 테이블에서 '통풍시트', '열선시트', '가죽시트' 중 하나 이상의 옵션이 포함된 자동차가 자동차 종류 별로 몇 대인지 출력하는 SQL문을 작성해주세요. 이때 자동차 수에 대한 컬럼명은 CARS로 지정하고, 결과는 자동차 종류를 기준으로 오름차순 정렬해주세요.

💭 접근

우선 OPTIONS 컬럼에 '통풍시트', '열선시트', '가죽시트' 중 하나 이상의 옵션을 포함하고 있는 데이터만을 WHERE 절에 LIKE를 사용하여 추출해주고,

이렇게 조건에 맞는 데이터들만 추출되었다면 CAR_TYPE으로 GROUP BY 해준 뒤 각 CAR_TYPE의 개수를 세주면 되는 문제이다.

📒 코드

SELECT  CAR_TYPE
        ,COUNT(*) AS CARS
  FROM  CAR_RENTAL_COMPANY_CAR
 WHERE  OPTIONS LIKE '%통풍시트%'
    OR  OPTIONS LIKE '%열선시트%'
    OR  OPTIONS LIKE '%가죽시트%'
 GROUP
    BY  CAR_TYPE
 ORDER
    BY  CAR_TYPE ASC;

💭 후기

LIKE와 GROUP BY를 사용한 간단한 문제였다.

🔗 문제 출처

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

💡 문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.

근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.

이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

출력

첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

💭 접근

이 문제를 해결하기 위해선 상하좌우로 움직이는 원숭이와 여러칸을 뛰어넘을 수 있는 말의 이동방법을 모두 고려해야한다.

이때 도착점에 도달하기 위한 동작수의 최솟값을 찾는 문제라서 말의 이동방법으로 먼저 움직이고 이후 남은 칸을 원숭이의 이동방법으로 움직이면 될 것이라고 생각할 수 있다.

그러나 만약 문제가 k가 1로 주어지고 다음과 같은 격자판이 주어졌다고 가정해보자

k = 1

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

이렇게 되면 한번밖에 쓸 수 없는 말의 이동방법으로 움직이고 나면 도착지점에 도달할 수 있음에도 도착할 수 없게된다.

또한 방문처리를 할 때 단순히 0과 1로만 체크를 한다면 말의 이동방법을 사용하였을 때 원숭이보다 반드시 빨리 도달할 수 밖에 없기 때문에 원숭이가 갈 수 있는 칸임에도 불구하고 갈 수 없게 된다.

따라서 위 두 경우를 모두 고려하여 방문처리를 할 때 *"해당 칸에 도달하기 위해 사용한 말의 이동방법의 횟수"*를 기록하며 나아가야 한다.

예시를 들어 살펴보자.

만약 어떤 칸에 도달하기 위해 사용한 말의 이동방법의 횟수가 3번이라고 하자. 이때 visited의 해당 칸에는 3이 기록될 것이고, 추후 해당칸에 올 수 있는 경우는

• 말의 이동방법을 3번 미만으로 사용한 원숭이
• 말의 이동방법을 2번 미만으로 사용한 말

이 두 경우에만 도달할 수 있다.

이렇게하면 말의 이동방법을 사용하여 먼저 도달한 칸이 있더라도 말의 이동방법을 사용하지 않고 도달한 원숭이가 해당 칸을 방문할 수 있게 되어 위에서 들었던 예시 격자판과 같은 경우에도 도착점에 도달할 수 있게 된다.

📒 코드

from collections import deque

MONKEY = 1
HORSE = 2

def bfs():
    q = deque()
    q.append([0, 0, 0, 0])


    visited[0][0] = 0
    while q:
        x, y, cnt, move = q.popleft()

        if x == h - 1 and y == w - 1:
            return move

        for animal in [MONKEY, HORSE]:
            if animal == MONKEY:
                for i in range(4):
                    nx = x + monkey_dx[i]
                    ny = y + monkey_dy[i]

                    if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 0:
                        if visited[nx][ny] > cnt:
                            visited[nx][ny] = cnt
                            q.append([nx, ny, cnt, move + 1])

            elif animal == HORSE and cnt < k:
                for i in range(8):
                    nx = x + horse_dx[i]
                    ny = y + horse_dy[i]

                    if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 0:
                        if visited[nx][ny] > cnt + 1:
                            visited[nx][ny] = cnt + 1
                            q.append([nx, ny, cnt + 1, move + 1])
    return -1

k = int(input())
w, h = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(h)]
visited = [[k + 1 for _ in range(w)] for _ in range(h)]

monkey_dx = [-1, 1, 0, 0]
monkey_dy = [0, 0, -1, 1]

horse_dx = [-2, -1, 1, 2, 2, 1, -1, -2]
horse_dy = [1, 2, 2, 1, -1, -2, -2, -1]

print(bfs())

💭 후기

말의 이동방법을 사용한 횟수로 방문 체크를 하는 것이 핵심인 문제이다.

🔗 문제 출처

https://www.acmicpc.net/problem/1600

💡 문제

다음은 종합병원의 진료 예약정보를 담은 APPOINTMENT 테이블 입니다. APPOINTMENT 테이블은 다음과 같으며 APNT_YMD, APNT_NO, PT_NO, MCDP_CD, MDDR_ID, APNT_CNCL_YN, APNT_CNCL_YMD는 각각 진료예약일시, 진료예약번호, 환자번호, 진료과코드, 의사ID, 예약취소여부, 예약취소날짜를 나타냅니다.

APPOINTMENT 테이블에서 2022년 5월에 예약한 환자 수를 진료과코드 별로 조회하는 SQL문을 작성해주세요. 이때, 컬럼명은 '진료과 코드', '5월예약건수'로 지정해주시고 결과는 진료과별 예약한 환자 수를 기준으로 오름차순 정렬하고, 예약한 환자 수가 같다면 진료과 코드를 기준으로 오름차순 정렬해주세요.

💭 접근

이 문제를 처음 보았을 때 간단한 GROUP BY 문제인 줄 알고 쉽게 해결하였지만 계속 오답이 나왔다.

원인을 찾아본 결과 정렬을 하기 위해 ORDER BY 절에 '5월예약건수'를 전달해 주었지만 이는 잘못된 구문이었다.

그냥 ''(따옴표) 로 Alias를 감싸서 ORDER BY 절에 전달해 준다면 이를 그냥 단순한 문자열로 인식하고 아무 의미가 없어진다.

따라서 ORDER BY 절에 Alias를 전달해 줄때는 (특히 한글일 때) 따옴표가 아닌 백틱(`) 기호를 사용해야 한다.

아래 두 코드의 ORDER BY 절을 비교해보면 더욱 직관적으로 비교해 볼 수 있다.

🔥 처음 작성한 코드 (오답)

SELECT  MCDP_CD AS '진료과코드'
        ,COUNT(DISTINCT PT_NO) AS '5월예약건수'
  FROM  APPOINTMENT
 WHERE  APNT_YMD LIKE '2022-05%'
 GROUP
    BY  MCDP_CD
 ORDER
    BY  '5월예약건수' ASC
        ,MCDP_CD ASC;

📒 코드

SELECT  MCDP_CD AS '진료과코드'
        ,COUNT(DISTINCT PT_NO) AS '5월예약건수'
  FROM  APPOINTMENT
 WHERE  APNT_YMD LIKE '2022-05%'
 GROUP
    BY  MCDP_CD
 ORDER
    BY  `5월예약건수` ASC
        ,MCDP_CD ASC;

💭 후기

SQL에서 백틱의 사용법을 익힐 수 있었던 문제였다.

🔗 문제 출처

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

💡 문제

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

보호소의 동물이 중성화되었는지 아닌지 파악하려 합니다. 중성화된 동물은 SEX_UPON_INTAKE 컬럼에 'Neutered' 또는 'Spayed'라는 단어가 들어있습니다. 동물의 아이디와 이름, 중성화 여부를 아이디 순으로 조회하는 SQL문을 작성해주세요. 이때 중성화가 되어있다면 'O', 아니라면 'X'라고 표시해주세요.

💭 접근

이 문제는 동물의 중성화 여부를 출력하는 문제로, CASE WHEN 절을 사용하여 해결할 수 있다.

주어진 조건으로 SEX_UPON_INTAKE 컬럼에 'Neutered' 또는 'Spayed'라는 단어가 들어있다면 중성화 컬럼에 O를, 들어있지 않다면 X를 출력하면 되므로 중성화 컬럼을 다음과 같이 작성할 수 있다.

CASE
   WHEN  SEX_UPON_INTAKE LIKE 'NEUTERED%'
     OR  SEX_UPON_INTAKE LIKE 'SPAYED%'
   THEN  'O'
   ELSE  'X'
 END AS '중성화'

📒 코드

SELECT  ANIMAL_ID
        ,NAME
        ,CASE
            WHEN  SEX_UPON_INTAKE LIKE 'NEUTERED%'
              OR  SEX_UPON_INTAKE LIKE 'SPAYED%'
            THEN  'O'
            ELSE  'X'
          END AS '중성화'
  FROM  ANIMAL_INS
 ORDER
    BY  ANIMAL_ID ASC;

💭 후기

CASE WHEN 절을 활용하는 기본적인 문제였다.

🔗 문제 출처

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

💡 문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

💭 접근

처음 이 문제를 풀었을 때는 아래의 처음 작성한 코드에서 볼 수 있듯이, 입력으로 주어진 graph가 1인 지점에서 인접한 네 지점을 1로 바꾼 뒤, BFS를 통해 인접한 모든 1의 개수를 구하는 방식으로 구현하였었다.

그러나 이러한 풀이에는 문제가 있었는데, 1이 있는 지점마다 최대 4번씩 계속해서 BFS 함수를 호출하게되어 시간초과가 발생한다는 것이었다. 이는 이미 확인했던 지점도 계속 반복해서 확인하기 때문이다.

이를 보완하기 위해 다른 방법을 사용하였다.

1. 먼저 입력으로 주어진 graph에 1이 인접해 있는 것들끼리 그룹을 묶어주고, 크기를 저장한다.

   idx = 1
   for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == 0:
            cnt = 1
            tmp = [[i, j]]
            bfs(i, j)
   
            for x, y in tmp:
                graph[x][y] = cnt
            idx += 1

   위 코드를 그림으로 설명하면 다음과 같이 나타낼 수 있다.

먼저 입력으로 주어진 graph에 인접한 1끼리 그룹으로 묶어 그룹의 크기를 저장해준다. 그리고 visited에는 각 그룹의 번호(1 ~ n)를 저장해준다.

2. 이후 1번 단계에서 만든 그룹들의 정보를 활용하여 값이 0인 임의의 지점에서 인접한 그룹들의 크기를 더하여 정답을 구한다.

   ans = 0
   for x in range(n):
    for y in range(m):
        if graph[x][y] == 0:
            cnt = 1
            idx_set = set()
   
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
   
                if 0 <= nx < n and 0 <= ny < m:
                    if visited[nx][ny] not in idx_set:
                        cnt += graph[nx][ny]
                        idx_set.add(visited[nx][ny])
            ans = max(ans, cnt)

   위 코드를 그림으로 나타내면 아래와 같다.

이처럼 현재 [0, 2] 위치의 0이 선택되었다면, 인접하고 있는 서로 다른 그룹들의 크기를 더하여 인접한 1의 개수를 구할 수 있다.

🔥 처음 작성한 코드 (시간초과)

from collections import deque

def bfs(x, y):
    q = deque()
    q.append([x, y])

    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[x][y] = 1

    cnt = 1
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += 1
                q.append([nx, ny])
    return cnt

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

pos = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            pos.append([i, j])

ans = 0
checked = [[0 for _ in range(m)] for _ in range(n)]
for x, y in pos:
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and checked[nx][ny] == 0:
            checked[nx][ny] = 1
            graph[nx][ny] = 1
            ans = max(ans, bfs(nx, ny))
            graph[nx][ny] = 0
print(ans)

📒 코드

from collections import deque

def bfs(x, y):
    global cnt

    q = deque()
    q.append([x, y])

    visited[x][y] = idx

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                    visited[nx][ny] = idx
                    q.append([nx, ny])
                    tmp.append([nx, ny])
                    cnt += 1

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

idx = 1 # 그룹 정보 저장
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == 0:
            cnt = 1
            tmp = [[i, j]]
            bfs(i, j)

            for x, y in tmp:
                graph[x][y] = cnt
            idx += 1

ans = 0 # 정답 구하기
for x in range(n):
    for y in range(m):
        if graph[x][y] == 0:
            cnt = 1
            idx_set = set()

            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]

                if 0 <= nx < n and 0 <= ny < m:
                    if visited[nx][ny] not in idx_set:
                        cnt += graph[nx][ny]
                        idx_set.add(visited[nx][ny])
            ans = max(ans, cnt)
print(ans)

💭 후기

이전에 지도 상의 섬에 번호를 매기고 이들을 연결하는 비슷한 문제를 풀었던 기억이 떠올라 생각보다 쉽게 아이디어를 떠올릴 수 있었다.

🔗 문제 출처

https://www.acmicpc.net/problem/16932

💡 문제

다음은 어느 의류 쇼핑몰에서 판매중인 상품들의 정보를 담은 PRODUCT 테이블입니다. PRODUCT 테이블은 아래와 같은 구조로 되어있으며, PRODUCT_ID, PRODUCT_CODE, PRICE는 각각 상품 ID, 상품코드, 판매가를 나타냅니다.

상품 별로 중복되지 않는 8자리 상품코드 값을 가지며, 앞 2자리는 카테고리 코드를 의미합니다.

PRODUCT 테이블에서 상품 카테고리 코드(PRODUCT_CODE 앞 2자리) 별 상품 개수를 출력하는 SQL문을 작성해주세요. 결과는 상품 카테고리 코드를 기준으로 오름차순 정렬해주세요.

💭 접근

이 문제에서 요구하는 카테고리는 PRODUCT_CODE의 앞 2자리에 나타나 있으므로 LEFT() 함수를 사용하여 문자열의 왼쪽부터 원하는 길이까지 구할 수 있다.

우선 PRODUCT_CODE의 앞 두자리를 추출한 후, 이를 바탕으로 그룹을 만든다.

이후, COUNT() 함수를 사용하여 해당 그룹에 속하는 상품의 개수를 세주면 된다.

1. SUBSTRING(문자열, 시작위치, 길이): 문자열을 시작위치부터 길이만큼 자른다.

ex. SUBSTRING('PYTHON', 2, 3) == 'YTH'
2. LEFT(문자열, 길이): 문자열을 왼쪽부터 길이만큼 자른다. ex. LEFT('PYTHON', 4) == 'PYTH'
3. RIGHT(문자열, 길이): 문자열을 오른쪽부터 길이만큼 자른다. ex. RIGHT('PYTHON', 5) == 'YTHON'

📒 코드

SELECT  LEFT(PRODUCT_CODE, 2) AS CATEGORY
        ,COUNT(*) AS PRODUCTS
  FROM  PRODUCT
 GROUP
    BY  CATEGORY
 ORDER
    BY  CATEGORY ASC;

💭 후기

문자열 함수와 GROUP BY 를 사용하는 조금 고민이 필요한 문제였다.

🔗 문제 출처

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

💡 문제

각각 부피가 A, B, C(1 ≤ A, B, C ≤ 200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

💭 접근

이 문제는 A, B, C 물통의 정보가 주어졌을때 각 물통이 가질 수 있는 물의 모든 경우를 구한 뒤, A 물통이 비어있을때 C 물통이 가질 수 있는 물의 양의 모든 경우의 수를 출력하는 문제이다.

따라서 A, B, C 물통의 모든 가능한 경우의 수를 구하기 위해 BFS를 사용할 수 있다.

BFS를 돌 때, 다른 물통에 물을 나눠줄 물통과 이 물을 받을 물통을 고른다.

for i in range(3):
    if curr[i] == 0:
        continue
    for j in range(3):
        next = curr[:]
        if i == j or next[j] == v[j]:
            continue

이때 만약 두 물통을 같은 물통을 선택한 경우와 물을 받을 물통(next[j])가 이미 최대로 물이 담겨져 있을 때는 건너뛴다.

이후 다음 조건에 따라 물을 옮기면 되는데, 물을 나눠줄 물통의 물과 물을 받을 물통의 합이 물을 받을 물통의 최대치보다 작다면 나눠줄 물통을 0으로 하고 받을 물통은 단순히 더한다.

if next[i] + next[j] <= v[j]:
    next[j] += next[i]
    next[i] = 0

반면에, 최대치를 넘어 물을 모두 나눠줄 수 없는 경우는 다음과 같이 계산한다.

elif next[i] + next[j] > v[j]:
    next[i] -= (v[j] - next[j])
    next[j] = v[j]

이후, 물을 옮기는 작업이 끝났다면 이미 세 물통의 상태가 처음이라면 큐에 append해준다.

if tuple(next) not in visited:
    q.append(next)
    visited.add(tuple(next))

이렇게 BFS 함수가 종료되면 A 물통이 비어있는 경우 C 물통에 존재할 수 있는 물양의 경우를 구하면 된다.

ans = set()
for a, b, c in visited:
    if a == 0:
        ans.add(c)
print(*sorted(list(ans)))

📒 코드

from collections import deque

def bfs(start):
    q = deque()
    q.append(start)

    visited.add(start)

    while q:
        curr = list(q.popleft())

        for i in range(3):
            if curr[i] == 0:
                continue

            for j in range(3):
                if i == j or curr[j] == max_v[j]:
                    continue

                next = curr[:]
                if next[i] + next[j] > max_v[j]:
                    next[i] = curr[i] - (max_v[j] - curr[j])
                    next[j] = max_v[j]
                elif next[i] + next[j] <= max_v[j]:
                    next[i] = 0
                    next[j] = curr[i] + curr[j]

                if (next[0], next[1], next[2]) not in visited:
                    visited.add((next[0], next[1], next[2]))
                    q.append(next)

max_v = list(map(int, input().split()))

visited = set()
bfs((0, 0, max_v[2]))

ans = set()
for aw, bw, cw in visited:
    if aw == 0:
        ans.add(cw)

print(*sorted(ans))

💭 후기

각 물통의 상태를 저장하며 물을 옮기면되는 간단한 BFS 문제였다.

🔗 문제 출처

https://www.acmicpc.net/problem/2251

💡 문제

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

동물 보호소에 들어온 동물 이름 중 두 번 이상 쓰인 이름과 해당 이름이 쓰인 횟수를 조회하는 SQL문을 작성해주세요. 이때 결과는 이름이 없는 동물은 집계에서 제외하며, 결과는 이름 순으로 조회해주세요.

💭 접근

이 문제는 GROUP BY 절로 NAME 컬럼으로 그룹을 만든 후, 각 NAME에 속하는 행의 수를 구하는 문제이다.

이때, WHERE 절에 NAME 값이 NULL이 아닌 값만을 세도록 조건을 추가하고, HAVING 절에선 중복되는 이름이 2개 이상인 행만을 걸러내도록 코드를 작성하면 된다.

📒 코드

SELECT  NAME
        ,COUNT(NAME) AS COUNT
  FROM  ANIMAL_INS
 WHERE  NAME IS NOT NULL
 GROUP
    BY  NAME
HAVING  COUNT(NAME) >= 2
 ORDER
    BY  NAME ASC;

💭 후기

GROUP BY를 사용하는 기본적인 문제였다.

🔗 문제 출처

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