1. 논문 소개

'Very Deep Convolutional Networks for Large-Scale Image Recognition'

Karen Simonyan, Andrew Zisserman (ICLR 2015)

 

 

(1) Abstract

- Convolution network 깊이가 large-scale image recognition에 미치는 영향에 대한 연구를 진행함

- 매우 작은 convolution filters (3 x 3)16 ~ 19 layers 아키텍처를 구성하여 상당한 성능 개선을 이룸

- 2014년 ILSVRC에서 1, 2위를 차지함

- 다른 데이터셋에서도 잘 일반화되어 sota 결과를 얻을 수 있었음

 

 

(2) Introduction

- ConvNet이 컴퓨터 비전 분야에서의 성능 향상에 도모하는 바가 커지면서, 2012년 AlexNet의 성능을 뛰어넘기 위한 노력을 많이 하고 있음

- 본 논문에서는 'depth'에 집중하기로 함. convolutional layer를 추가함으로써 점차 깊이를 증가시켜나간다.

 

 

(3) ConvNet Configurations

1) Architecture

- input : 224 x 224 RGB image (학습 데이터의 평균으로 빼주기)

 

- kernel : 3 x 3, stride : 1, padding : 1

- MaxPooling : 2 x 2, stride : 2

 

- FC layers : 4096 channels 2개, 마지막엔 1000-way (softmax layer)

- ReLU 사용

- LRN 사용 안 함 (오히려 그런 normalization이 성능 향상에 도움이 안 되었고, 메모리 소모와 연산 시간만 늘렸다고 함)

 

 

2) Configuration

Table 1 : conv<kernel 크기>-<채널 개수>

- 깊이 11 (8 conv, 3 FC) ~ 깊이 19 (16 conv, 3 FC)

 

- 깊이에 따른 파라미터 개수인데, 크게 차이나지 않음

 

- VGG16 구조 도식화

 

 

 

3) Discussion

- VGGNet은 이전의 ILSVRC 대회에서 우수한 성능을 보인 모델들과의 상당한 차이가 있음

- 첫번째 conv layer뿐만 아니라 전체 네트워크에 걸쳐 3 x 3의 매우 작은 receptive field를 사용한다.

 

- 작은 receptive field을 사용하는 것의 이점?

1) 작은 kernel을 여러 개 사용하는 것과 큰 kernel 한 개를 사용하는 것이 동일한 크기의 피처맵을 얻을 수 있음

2) decision function을 더 discriminative하게 만들 수 있음

3) 더 적은 파라미터가 필요함

 

 

예) 2개의 3 x 3 커널을 사용하는 것과 1개의 5 x 5 커널은 동일한 크기의 피처맵 생성!

 

입력 채널, 출력 채널 모두 C개라고 가정하면,

- 2개의 3 x 3 커널 : 2 * (3 * 3 * C * C) = 18C*C

- 1개의 5 x 5 커널 : (5 * 5 * C * C) = 25C * C

 

2개의 3 x 3 커널의 파라미터보다 1개의 5 x 5 커널의 파라미터 개수가 더 많다.

 

- 1 x 1 conv. layers 사용 : receptive field에 영향을 주지 않으면서, non-linearity 증가시키기 위해서 사용 (by. ReLU)

 

- GoogLeNet도 small convolutional filters (1 x 1, 5 x 5, 3 x 3)를 사용했다는 점이 유사하지만, VGGNet 보다 훨씬 복잡하여 계산량이 어마어마하다.

 

 

 

(4) Classification Framework

1) Training

- Mini batch gradient descent (batch size : 256, momentum : 0.9)

- L2 regularization : $5 \cdot 10 ^{-4}$

- Dropout : 0.5

- 초기 learning rate : $10^{-2}$ → validation score 개선 없는 경우 10배 감소시킴 (총 3회 감소)

 

- 네트워크 가중치의 초기화가 중요하므로, 얕은 모델부터 학습 시작하고, 학습 중에 레이어가 변경될 수 있도록 했음

- Random Initialization은 정규 분포 상에서 weight를 샘플링했음 (평균 0, 표준편차 $10^{-2}$)

 

 

2) Testing

- 입력 이미지의 크기에서 training scale을 S, testing scale을 Q라고 했을 때, 둘이 서로 같을 필요는 없음

- input image 크기에 따라 variable spatial resolution을 출력하기 때문에, class score map을 'sum-pooled'을 통해 spatially average 한다.

 

 


 

2. Summary

- 네트워크의 깊이와 모델 성능 영향에 집중

- Convolution 커널 사이즈를 3 x 3으로 고정

- 커널 사이즈가 크면 이미지 사이즈 축소가 급격하게 이뤄져서 더 깊은 층을 만들기 어렵고, 파라미터 개수와 연산량도 더 많이 필요

- 여러 개의 3X3 Convolution 연산을 수행하는 것이 더 뛰어난 Feature 추출 효과를 나타냄

 

- 개별 Block내에서는 동일한 커널 크기와 Channel 개수를 적용하여 동일한 크기의 feature map들을 생성

- 이전 Block 내에 있는 Feature Map 대비 새로운 Block내에 Feature Map 크기는 2배로 줄어 들지만 채널 수는 2배로 늘어남 (맨 마지막 block 제외)

https://pub.towardsai.net/the-architecture-and-implementation-of-vgg-16-b050e5a5920b

 

 


 

3. Code

!pip install torchsummary

import numpy as np
import pandas as pd
import os
import matplotlib.pyplot as plt

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

from torch.utils.data import DataLoader, Dataset, random_split
from torch.utils.data import random_split

from torchsummary import summary

import torchvision
from torchvision.utils import make_grid
import torchvision.transforms as tr

from tqdm import trange
# mean
tr_meanRGB = [ np.mean(x.numpy(), axis=(1, 2)) for x, _ in cifar10_tr ]

tr_meanR = np.mean([m[0] for m in tr_meanRGB])
tr_meanG = np.mean([m[1] for m in tr_meanRGB])
tr_meanB = np.mean([m[2] for m in tr_meanRGB])

# std
tr_stdRGB = [ np.std(x.numpy(), axis=(1, 2)) for x, _ in cifar10_tr ]

tr_stdR = np.std([m[0] for m in tr_stdRGB])
tr_stdG = np.std([m[1] for m in tr_stdRGB])
tr_stdB = np.std([m[2] for m in tr_stdRGB])

mean = [tr_meanR, tr_meanG, tr_meanB]
std = [tr_stdR, tr_stdG, tr_stdB]


tr_transform = tr.Compose([
    tr.ToTensor(),
    tr.Resize(128),  # 크기 조정
    tr.RandomHorizontalFlip(p=0.7), 
    tr.Normalize(mean=[0.49139965, 0.48215845, 0.4465309], std=[0.060528398, 0.061124973, 0.06764512])
])

te_transform = tr.Compose([
    tr.ToTensor(),
    tr.Resize(128),  # 크기 조정
    tr.Normalize(mean=[0.49139965, 0.48215845, 0.4465309], std=[0.060528398, 0.061124973, 0.06764512])
])

tr_meanRGB, tr_stdRGB 값을 구해서 이후에는 직접 Normalize에 넣어주는 방식으로 진행했음.

 

torch.manual_seed(11)

cifar10_tr = torchvision.datasets.CIFAR10(root='./data', download=True, train=True, transform=tr_transform)

val_size = 10000
train_size = len(cifar10_tr) - val_size
cifar10_tr, cifar10_val = random_split(cifar10_tr, [train_size, val_size])

cifar10_te = torchvision.datasets.CIFAR10(root='./data', download=True, train=False, transform=te_transform)

train 데이터를 train, valid로 나누어주었고, random_split을 사용했음

 

trainloader = DataLoader(cifar10_tr, batch_size=64, shuffle=True)
valloader = DataLoader(cifar10_val, batch_size=64, shuffle=False)
testloader = DataLoader(cifar10_te, batch_size=64, shuffle=False)

train, valid, test 데이터셋을 데이터로더로 넣어주고,

 

 

시각화

for images, _ in trainloader:
    print('images.shape:', images.shape)
    
    plt.figure(figsize=(16,8))
    plt.axis('off')
    plt.imshow(make_grid(images, nrow=16).permute((1, 2, 0)))
    
    break

 

데이터 확인

images, labels = next(iter(trainloader))
print(labels)
print(images.shape, labels.shape)

 

 

VGGNet 모델 구현

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

class VGGNet(nn.Module):
    
    def __init__(self, n_classes=10):
        super().__init__()
        
        self.conv1 = nn.Sequential(
            nn.Conv2d(3, 64, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.Conv2d(64, 64, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.MaxPool2d(2, 2)
        )
        
        self.conv2 = nn.Sequential(
            nn.Conv2d(64, 128, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.Conv2d(128, 128, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.MaxPool2d(2, 2)
        )
        
        self.conv3 = nn.Sequential(
            nn.Conv2d(128, 256, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.Conv2d(256, 256, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.MaxPool2d(2, 2)
        )
        
        self.conv4 = nn.Sequential(
            nn.Conv2d(256, 512, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.Conv2d(512, 512, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.MaxPool2d(2, 2)
        )
        
        self.conv5 = nn.Sequential(
            nn.Conv2d(512, 512, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.Conv2d(512, 512, kernel_size=3, stride=1, padding=1),
            nn.ReLU(),
            nn.MaxPool2d(2, 2)
        )
        
        self.fc6 = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(512*4*4, 4096),
            nn.ReLU(),
        )
        
        self.fc7 = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(4096,4096),
            nn.ReLU(),
        )
        
        self.fc8 = nn.Sequential(
            nn.Linear(4096, n_classes),
        )
    
    def forward(self, x):
        x = self.conv1(x)
        x = self.conv2(x)
        x = self.conv3(x)
        x = self.conv4(x)
        x = self.conv5(x)
        x = x.view(x.size(0), -1)
        x = self.fc6(x)
        x = self.fc7(x)
        x = self.fc8(x)
        
        return x

 

 

학습 준비

model = VGGNet().to(device)
criterion = nn.CrossEntropyLoss()

optimizer = optim.Adam(model.parameters(), lr=1e-3, weight_decay=1e-4)
scheduler = optim.lr_scheduler.ReduceLROnPlateau(optimizer, mode='min', factor=0.1, patience=5, verbose=True)

# early stopping
early_stopping_epochs = 5
best_loss = float('inf')
early_stop_counter = 0

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

PyTorch에서는 early stopping을 제공하고 있지 않기 때문에, 직접 구현해주었음

 

 

학습

epochs = 30

for epoch in range(epochs):
    model.train()
    train_loss, correct, total = 0.0, 0, 0
    
    # Train
    for data in trainloader:
        images, labels = data[0].to(device), data[1].to(device)
        
        outputs = model(images)
        
        optimizer.zero_grad()
        loss = criterion(outputs, labels)
        loss.backward()
        optimizer.step()

        train_loss += loss.item()
        predicted = torch.argmax(outputs, 1)
        
        total += labels.size()[0]
        correct += (predicted == labels).sum().item()
        
    print(f'Epoch [{epoch+1}/{epochs}] || Loss:{train_loss / len(trainloader)} || Accuracy:{100 * correct / total}')


    
    # Valid
    model.eval()
    valid_loss = 0.0
    
    for data in valloader:
        images, labels = data[0].to(device), data[1].to(device)
        outputs = model(images)
        loss = criterion(outputs, labels)
        valid_loss += loss.item()
    
    if valid_loss > best_loss:
        early_stop_counter += 1
    else:
        best_loss = valid_loss
        early_stop_counter = 0
    
    if early_stop_counter >= early_stopping_epochs:
        print("Early Stopping!")
        break

 

 

Test

correct, total = 0, 0

with torch.no_grad():
    model.eval()
    test_loss = 0.0
    
    for data in testloader:
        images, labels = data[0].to(device), data[1].to(device)
        outputs = model(images)
        test_loss += loss.item()
        
        _, predicted = torch.max(outputs.data, axis=1)
        total += labels.size(0)
        correct += (predicted == labels).sum().item()
        
print(f"Test loss : {test_loss / len(testloader)}")
print(f"Accuracy : {correct / total:.2f}")

1. 문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 한다.

 

어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주한다.

 

00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산한다.

- 누적 주차 시간이 기본 시간 이하라면, 기본 요금을 청구한다.

- 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구한다.

(단, 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림한다.)

 

차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 반환하라.

 

 

 

2. 코드

import math

def solution(fees, records):
    default_time, default_fee, unit_time, unit_fee = fees[0], fees[1], fees[2], fees[3]
    
    record_dict = {}
    answer = {}
    
    # 출입 기록 저장
    for record in records:
        a, b, _ = record.split(' ')
        
        if b in record_dict.keys():
            record_dict[b].append(a)
        else:
            record_dict[b] = [a]    

    
    # 정산
    for car, in_out in record_dict.items():
        park_m = 0

        while in_out:
            if len(in_out) == 1:
                in_h, in_m = map(int, in_out[0].split(':'))
                out_h, out_m = 23, 59
                
                if out_m >= in_m:
                    park_m += (out_h - in_h) * 60 + (out_m - in_m)
                else:
                    park_m += (out_h - 1 - in_h) * 60 + (out_m + 60 - in_m)
                break
            
            else:
                in_h, in_m = map(int, in_out[0].split(':'))
                out_h, out_m = map(int, in_out[1].split(':'))
                
                if out_m >= in_m:
                    park_m += (out_h - in_h) * 60 + (out_m - in_m)
                else:
                    park_m += (out_h - 1 - in_h) * 60 + (out_m + 60 - in_m)
                    
                in_out = in_out[2:]
        
        
        if park_m <= default_time:
            answer[car] = default_fee
        else:
            answer[car] = default_fee + math.ceil((park_m - default_time) / unit_time) * unit_fee
        

    return [v for k,v in sorted(answer.items())]

 

 

 

3. 설명

우선 출입 차량에 대해서 딕셔너리로 기록하는데, 이때 in과 out은 순서가 정해져있기 때문에 신경쓰지 않았다.

 

만약 이미 딕셔너리에 저장되어있는 차량이라면, 딕셔너리 value인 리스트에 값을 추가하고,

그렇지 않은 경우에는 리스트를 추가한다.

 

저장한 출입 기록을 for문으로 돌면서 정산을 한다.

만약 in_out이 1인 경우에는 in 만 하고 out을 안 한 경우이기 때문에 나간 시간을 23:59으로 설정해준다.

 

math 라이브러리의 ceil 함수를 사용해서 올림 처리해준다.

LG Aimers에서 연세대학교 정승환 교수님 강의를 듣고 정리한 내용입니다.

틀린 부분이 있다면 댓글 부탁드립니다!

 


 

1. 품질의 정의

품질은 10개의 성질로 정의할 수 있다.

 

(1) 품질의 10가지 성질

- 고객 만족도 : 제품 출시를 앞두고 철저한 사용자 조사를 통해 기능 반영, 높은 만족도 달성

- 일관성 : 동일한 품질의 부품을 만들고, 모든 제품이 동일한 성능과 신뢰성을 유지

- 적합성 : 목적에 적합해야 함. 냉장고는 냉장 기능에 최적화 되어야 함

- 신뢰성 : 제품의 내구성을 높이기 위해 반복적으로 테스트와 개선 작업을 함

- 성능 : 소비자들의 요구를 반영하여 고성능 제품을 개발함

- 안정성 : 품질 검사를 통해 안전하고 믿을 수 있는 제품을 제공함

- 지속 가능성 : 기업, 사회, 환경적 지속 가능한 품질 관리에 앞장섬

- 효율성 : 사용자의 피드백을 반영하여 사용 편의성을 높이고, 처리 속도를 개선함

- 유지 보수성 : 유지 보수가 용이하도록 설계하며, 오랜 기간 동안 품질을 유지함

- 혁신 : 혁신적인 제품을 지속적으로 개발하고 경쟁력을 유지함

 

 

(2) 품질 관리 성공 사례 - SAMSUNG

- 첨단 기술 활용 : AI와 머신러닝을 활용한 자동 검사 시스템, IoT를 통한 예측, 유지보수 등을 도입하여 품질 문제를 사전에 예방함

- 전사적 품질 관리 문화 : 모든 직원이 품질 향상에 기여하도록 하는 문화를 구축하여, 전반적인 품질 관리 수준을 높임

- Six Sigma 도입 : 삼성은 1990년대부터 Six Sigma를 도입하여 공급망 관리를 혁신하고, 제품 결함을 줄여 운영 효율성을 극대화함

- 지속적인 개선 노력: 고객 불만 분석, 루트 원인 분석, 성과 지표 추적 등을 통해 지속적으로 품질을 개선해 옴

 


 

2. 품질 경영의 발전 과정

(1) 산업혁명과 초기 변화

- 산업 혁명은 대규모 분업을 초래하였고, 작업자들은 제품의 일부분만 담당

- 효율성은 증가했지만, 작업자들이 최종 제품을 확인하기 어려워짐에 따라 품질에 대한 책임이 작업조장에게 넘어감

- 초기 품질 검사는 비계획적이고 불완전하게 수행되어, 품질을 떨어뜨리는 결과를 낳음

 

 

(2) 2차 세계대전과 품질관리의 진전

- 2차 세계대전의 영향으로, 품질 관리의 중요성이 증대되었음. 전쟁 중 군수 물자 납품을 빠른 속도로 해야했기 때문

- 샘플링 검사법을 도입하며 품질 보증의 기초를 마련함

- 1950년대 중반에는 품질관리의 영역이 제조 과정에서 제품 설계, 원자재 입고 과정까지 확대됨

- 제품의 전체 라이프사이클을 고려한 품질관리가 시작되었음

 

 

(3) 전략적 접근과 현대적 의미

- 1970년대 후반에는 품질보증에서 전략적 품질경영으로 변화함

- 품질이 기업의 장기적인 성공에 필수적 요소로 인식되었음

- 품질은 기업 이익에 직접적인 영향을 미치며, 전사적 노력이 필요함.

 


 

3. 품질 표준

(1) ISO 9000 국제 품질 표준

https://ko.wikipedia.org/wiki/ISO_9000

- 국제적 인정 : ISO 9000 시리즈는 전 세계적으로 인정받는 품질 관리 표준임

- 품질관리 절차 : ISO 표준은 품질 관리 절차, 세부 문서, 작업 지침, 기록 유지 장려

- ISO 9001:2015 : 최신 버전은 다른 관리 시스템과의 호환성을 높이는 구조를 따름. risk-based thinking을 강조함

- 글로벌 인증 : 전 세계 201개 국가에서 160만 개 이상의 인증을 받은 글로벌 경영에 필수적인 표준임

 

 

(2) ISO 9000 관리 원칙

- 최고 경영진의 리더십

- 고객 만족

- 지속적인 개선 (PDCA, Plan Do Check Act)

- 전 조직 구성원의 참여

- 프로세스 접근법

- 데이터 기반 의사결정

- 시스템적 접근방식

- 상호 이익 공급 관계

 

 

(3) 말콤 볼드리지 국가 품질상

- 1988년 미국 정부에 의해 제정됨 : 당시 미국 경제상황은 제 2차 세계대전으로 인해 최악의 상태였음. 한편, 일본의 경제 및 상품경쟁력은 전성기를 맞고 있었는데, 이에 대해 미국은 일본의 경쟁력에 대해 다방면으로 검토

 

- Total Quality Management (TQM) 실행을 향상시키기 위해 설계됨

- 국가적 차원의 품질상이 필요함을 인식하고 성과 우수성을 달성한 조직을 인정함

 

 

(4) 볼드리지 지표 (Baldridge Criteria)

- 리더십 (120점) + 전략 (85점) + 고객 중심 (85점) + 측정, 분석, 지식 경영 (90점) + 고용 (85점) + 운영 (85점)

- 종합적으로 평가되어 조직의 품질 관리 성과를 판단함

 


 

4. 품질 비용

- 목표는 적은 비용으로 높은 품질 얻기!

 

(1) 품질 비용의 구성요소

- 평가 비용 (Appraisal Costs) : 품질 검사, 테스트 장비 비용 등

- 예방 비용 (Prevention Costs) : 직원 교육, 품질 개선 프로그램, 유지보수 비용 등

- 내부 실패 비용 (Internal Failure Costs) : 재작업 비용, 폐기 비용 등

- 외부 실패 비용 (External Failure Costs) : 고객 불만 처리 비용, 제품 반환 및 교체 비용 등

 

 

(2) 품질 비용의 관리 방법

- 평가 비용 : 효율적인 검사 및 테스트 프로세스 도입. 자동화된 검사 시스템 도입으로 오류 최소화

- 예방 비용 : 품질 교육 및 훈련 프로그램을 통해 직원의 품질 인식 향상. 품질 개선 프로젝트를 통해 결함 발생 가능성 감소

- 내부 실패 비용 : 결함 발생 시 신속한 문제 해결과 재작업으로 비용 최소화. 원인 분석을 통해 재발 방지 대책 마련

- 외부 실패 비용 : 고객 피드백 시스템을 통해 문제를 조기에 발견하고 해결. 제품 보증 및 애프터 서비스 강화로 고객 신뢰 유지

 


 

5. 품질의 리더

1. 문제 설명

선행 스킬 : 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬

 

예) 스파크 → 라이트닝 볼트 → 썬서

- 썬더를 배우려면 라이트닝 볼트를 먼저 배워야 함

- 라이트닝 볼트를 배우려면 스파크를 먼저 배워야 함

 

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 반환하라.

 

 

 

2. 코드

def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees:
        s = ''
        
        for i in skill_tree:
            if i in skill:
                s += i

        if skill[:len(s)] == s:
            answer += 1
    
    return answer

 

 

 

3. 설명

skill_tree의 문자 하나씩을 조사해가면서 그 문자가 skill에 존재할 경우 s에 잠시 저장한다.

skill의 처음부터 s의 길이만큼의 문자열이 s와 같다면, 선행 스킬이 잘 반영된 문자열이다.

1. 논문 소개

'ImageNet Classification with Deep Convolutional Neural Networks'

Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton (NIPS 2012)

 

 

(1) Abstract

- ILSVRC(ImageNet Large-Scale Visual Recognition Challenge)-2010 : 120만 개의 고해상도 이미지를 1000개의 서로 다른 class로 분류하는 대회

 

- 테스트 데이터에서 top-1, top-5 error rates가 각각 37.5%, 17.0%를 기록하며, 기존의 sota보다 훨씬 우수한 결과를 얻었다.

(top-5 error rate란 모델이 예측한 최상위 5개 범주 가운데 정답이 없는 경우의 오류율이다.)

 

- 6,000만 개의 파라미터, 65만 개의 뉴런으로 신경망을 구성하였으며, 5개의 convolutional layers, 그 중에서 일부는 max pooling layer를 가진다. 마지막에 1000-way softmax fully connected layers 3개로 구성되어 있다.

 

- 훈련 속도를 높이기 위해 non-saturating neurons를 사용하였으며, GPU로 구현하였다.

 

- Fully connected layers에서 overfitting을 줄이기 위해 'Dropout'이라는 정규화 방법을 사용하였고, 이는 매우 효과적이었다.

 

- Dropout을 적용한 모델은 ILSVRC-2012 대회에서 top-5 test error rate를 15.3%를 달성하였는데, 이는 2위 error rate인 26.2%와의 간격이 매우 큰 결과이다.

https://medium.com/coinmonks/paper-review-of-alexnet-caffenet-winner-in-ilsvrc-2012-image-classification-b93598314160

 

 

 

 

(2) Introduction

- 현재 object recognition에서는 machine learning 방법을 많이 사용하고 있다. 이러한 object recognition 성능을 높이기 위해서는 1) larger dataset이 필요하며, 2) more powerful model을 학습시키고, 3) overfitting을 방지하기 위한 기술을 사용해야 한다.

 

- 이전까지의 label의 개수는 그래봤자 10개 남짓이었다. 이러한 simple recognition task에서는 적은 양의 데이터셋과 label-preserving transformation을 통한 augmentation으로도 충분한 인간 정도의 성능을 보였다.

 

- 대규모 데이터셋 (수백만 장의 이미지와 수천개의 objects)을 학습하기 위한 모델로, CNN을 제안한다.

standard feedforward neural networks에 비교했을 때, connections, parameters가 적기 때문에 훈련이 더 쉽다.

 

- CNN의 장점에도 불구하고, high resolution (고해상도) images에 대규모로 적용하기에는 비용이 많이 든다.

따라서, 'highly-optimized GPU implementation of 2D convolution'를 활용하여 매우 큰 deep learning CNN을 학습할 수 있도록 한다.

 

- 5개의 convolutional, 3개의 fully-connected layers를 가지고 있다. (이 중 하나의 레이어만 제거하더라도 떨어지는 성능이 나온다.)

 

 

 

 

(3) The Dataset

1) ImageNet

- 1,500만 장의 labeled high-resolution images

- 약 22,000개의 카테고리

 

 

2) ILSVRC (실제 사용한 데이터셋)

- ImageNet의 subset을 데이터셋으로 사용

- 각 카테고리 별로 1,000개의 이미지가 포함된 총 1,000개의 카테고리

- 약 120만 장의 training images + 5만 장의 validation images + 15만 장의 testing images

https://oi.readthedocs.io/en/latest/computer_vision/conf&dataset.html

 

 

 

3) 데이터 전처리

- ImageNet은 variable-resolution images로 구성되어 있음 (각 이미지 별로 해상도 차이가 있음)

: 일정한 입력 차원을 받기 위해서 256 x 256의 fixed resolution으로 down-sampling 진행

 

- 각각의 픽셀에서 training set의 평균값을 빼어 centered raw RGB 값으로 모델 학습

 

 

 

 

(4) The architecture

1) ReLU Nonlinearity

- 일반적으로 tanh, sigmoid를 활성화 함수로 사용했었는데, gradient descent에서의 saturating 문제로 ReLU를 처음 사용하였음

https://bskyvision.com/421

 

- tanh에서는 출력값이 [-1, 1] 범위에서 존재하여, 논문에서 말하는 'saturating' 상태가 된다.

입력값이 ∞ 또는 -∞가 될수록 기울기가 0에 가까워져 weight 학습이 잘 되지 않는다.

 

- 반면, ReLU는 [0, ∞] 범위에서 존재하여, non-saturating 함수이다.

입력값이 ∞이더라도 기울기가 0이 아니라 빠르게 수렴된다.

 

saturating 정의

 

 

Figure 1

 

- 실선은 ReLU를 사용했을 때, 점선은 tanh를 사용했을 때 25%의 error rate에 도달하기까지의 epoch을 나타낸 그래프이다.

확실히 실선인 ReLU가 더 빠른 속도로 도달했음을 확인할 수 있다.

 

 

 

2) Training on Multiple GPUs

- GPU 한 개로는 모델의 최대 크기에 제한이 있기 때문에, 모델을 두 개의 GPU로 나눠준다.

- host machine memory 없이도 GPU 간의 메모리에서 직접 read, write가 가능하다.

 

- 병렬 GPU은 기본적으로 kernel의 절반을 각 GPU에 배치하고, 특정 layer에서만 communicate한다.

(layer 3는 두 GPU에서 모든 커널을 입력 받고, layer 4는 본인 GPU에서만 입력을 받음)

Figure 2의 일부

- 교차 검증을 통해 GPU 연결 패턴을 결정한다.

 

Figure 3

- 224 x 224 x 3 이미지를 kernel size=11로 학습하여 나온 결과인 96개의 결과이다.

위쪽의 48개의 결과는 GPU1, 아래쪽의 48개의 결과는 GPU2로 학습된 결과이다.

GPU1은 색상보다는 형태에, GPU2는 색상과 관련된 피처를 학습하고 있다는, 즉 독립적으로 학습한다는 것을 보여준다.

 

 

 

3) Local Response Normalization

- Local Response Normalization을 통해 generalization을 더 높인다. (현재는 Batch Normalization)

 

- ReLU를 활성화 함수로 사용했을 때, 양수 입력에 대해서는 그대로 내보내지만 음수 입력에 대해서는 0을 내보낸다.

이렇게 되면, 그 다음 계층에 큰 값이 전달되고, 주변의 작은 값들은 덜 전달되어 학습이 잘 이뤄지지 않는다.

 

- 이런 현상을 방지하기 위해 LRN이 사용되었다.

 

 

- $a_{x,y}^{i}$ : 픽셀 (x, y)에 커널 i를 적용한 결과

- $b_{x,y}^{i}$ : LRN 결과

- $i$ : 현재 kernel

- $N$ : 총 kernel 개수

- $n$ : 이웃한 normalization 크기

 

n개의 이웃한 필터에서의 (x,y)의 결과를 제곱하여 더하면,

값이 클수록 원래 값보다 작게 만들어주고, 작을수록 원래 값보다 크게 만들어주는 normalization 작업인 것이다.

 

 

 

4) Overlapping Pooling

- 일반적으로 pooling은 겹치지 않게 하지만, AlexNet에서는 overlapping 해주었다. 

https://bskyvision.com/421

 

 

 

5) Overall Architecture

 

- 5개의 convolutional layers + 3개의 fully connected layers (1000-way softmax)

[ Input layer - Conv1 - MaxPool1 - Norm1 - Conv2 - MaxPool2 - Norm2 - Conv3 - Conv4 - Conv5 - MaxPool3 - FC1 - FC2 - Output layer ]

 

 

왼쪽은 가장 초기의 CNN 모델인 LeNet-5이며, 오른쪽은 AlexNet이다.

훨씬 더 복잡하고 커진 것을 알 수 있다.

 

(나중에 사람들이 다시 계산해보니 input layer에서 224 x 224가 아니라 227 x 227이 맞는 크기였다.)

 

 

 

 

(5) Reducing Overfitting

1) Data Augmentation

- overfitting을 막을 수 있는 가장 쉬운 방법은 label-preserving transformation을 활용한 dataset 확장이다.

 

- 본 논문에서 사용한 data augmentation 방법으로는 다음 두 가지가 있다.

: horizontal reflections (수평 반전), PCA를 활용한 RGB 픽셀 값 변화

 

- horizontal reflections

https://learnopencv.com/understanding-alexnet/

 

 

- PCA 활용한 RGB 픽셀값 변경

: 각 RGB 이미지 픽셀 벡터 $[I^R_{xy}, I^G_{xy}, I^B_{xy}]$에 대해서, 모든 이미지 픽셀에 대해 공분산 행렬을 계산한다.

고유값 $\lambda_i$은 RGB 공간의 주성분을 나타내고, 고유벡터 $p_i$은 각 성분의 분산을 나타낸다.

 

 

각 픽셀에 위의 값을 더해서, 주성분 방향으로 픽셀 값을 랜덤하게 변형한다.

 

 

2) Dropout

 

- 확률 0.5로 특정 hidden neuron의 출력값을 0으로 만들어준다.

- 순전파, 역전파 전달이 되지 않으므로 입력이 주어질 때마다 다른 아키텍처를 샘플링하는 것과 동일한 효과를 낸다. 즉, 여러 모델이 가중치를 학습하는 앙상블과 동일한 것이다!

 

 

 

(6) Results

- ILSVRC2010 test set의 Top-1 error rate, Top-5 error rate 결과이다.

Table 1

 

 

- ILSVRC-2012 validation and test sets에서의 Top-1 error rate, Top-5 error rate 결과이다.

(*는 2011 ImageNet으로 pretrained model)

Table 2

 

 


 

2. Summary

- Activation 함수로 ReLU 함수를 첫 사용

- MaxPooling 으로 Pooling 적용 및 Overlapping Pooling 적용

- Local Response Normalization (LRN) 사용

- Overfitting을 개선하기 위해서 Drop out Layer와 Weight의 Decay 기법 적용

- Data Augmentation 적용 (좌우 반전, Crop, PCA 변환 등)

 

https://unerue.github.io/computer-vision/classifier-alexnet.html

 

- 11x11, 5x5 사이즈의 큰 사이즈의 Kernel 적용. 이후 3x3 Kernel을 3번 이어서 적용

- Receptive Field가 큰 사이즈를 초기 Feature map에 적용하는 것이 보다 많은 feature 정보를 만드는데 효율적이라고 판단

- 하지만 많은 weight parameter 갯수로 인하여 컴퓨팅 연산량이 크게 증가 함. 이를 극복하기 위하여 병렬 GPU를 활용할 수 있도록 CNN 모델을 병렬화

 

 


 

 

3. Code

import numpy as np
import pandas as pd
import os

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

from torch.utils.data import DataLoader, Dataset, random_split
from torchsummary import summary

import torchvision
import torchvision.transforms as tr

from tqdm import trange

 

 

- 데이터 불러오기 (CIFAR10 데이터셋)

cifar10_tr = torchvision.datasets.CIFAR10(root='./data', download=True, train=True, transform=tr.Compose([tr.ToTensor()]))
cifar10_te = torchvision.datasets.CIFAR10(root='./data', download=True, train=False, transform=tr.Compose([tr.ToTensor()]))

meanRGB = [ np.mean(x.numpy(), axis=(1, 2)) for x, _ in cifar10_tr ]
stdRGB = [ np.std(x.numpy(), axis=(1, 2)) for x, _ in cifar10_tr ]

meanR = np.mean([m[0] for m in meanRGB])
meanG = np.mean([m[1] for m in meanRGB])
meanB = np.mean([m[2] for m in meanRGB])

stdR = np.mean([s[0] for s in stdRGB])
stdG = np.mean([s[1] for s in stdRGB])
stdB = np.mean([s[2] for s in stdRGB])

tr_transform = tr.Compose([
    tr.ToTensor(),
    tr.Resize(227),  # 크기 조정
    tr.RandomHorizontalFlip(),  # 좌우 반전
    tr.Normalize([meanR, meanG, meanB], [stdR, stdG, stdB])
])

te_transform = tr.Compose([
    tr.ToTensor(),
    tr.Resize(227),  # 크기 조정
    tr.Normalize([meanR, meanG, meanB], [stdR, stdG, stdB])
])

cifar10_tr.transform = tr_transform
cifar10_te.transform = te_transform

trainloader = DataLoader(cifar10_tr, batch_size=64, shuffle=True)
testloader = DataLoader(cifar10_te, batch_size=64, shuffle=False)

 

images, labels = next(iter(trainloader))
images.shape, labels.shape

(torch.Size([64, 3, 227, 227]), torch.Size([64])

 

 

- AlexNet

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

class AlexNet(nn.Module):

    def __init__(self, n_classes=10):
        super().__init__()

        self.conv1 = nn.Sequential(
            nn.Conv2d(3, 96, kernel_size=11, stride=4, padding='valid'),
            nn.ReLU(inplace=True),
            nn.LocalResponseNorm(size=5, alpha=0.0001, beta=0.75, k=2), 
            nn.MaxPool2d(kernel_size=3, stride=2),
        )

        self.conv2 = nn.Sequential(
            nn.Conv2d(96, 256, kernel_size=5, stride=1, padding='same'),
            nn.ReLU(inplace=True),
            nn.LocalResponseNorm(size=5, alpha=0.0001, beta=0.75, k=2),
            nn.MaxPool2d(kernel_size=3, stride=2),
        )

        self.conv3 = nn.Sequential(
            nn.Conv2d(256, 384, kernel_size=3, stride=1, padding='same'),
            nn.ReLU(inplace=True),
        )

        self.conv4 = nn.Sequential(
            nn.Conv2d(384, 384, kernel_size=3, stride=1, padding='same'),
            nn.ReLU(inplace=True),
        )

        self.conv5 = nn.Sequential(
            nn.Conv2d(384, 256, kernel_size=3, stride=1, padding='same'),
            nn.ReLU(inplace=True),
            nn.MaxPool2d(kernel_size=3, stride=2),
        )

        self.fc6 = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(256 * 6 * 6, 4096),
            nn.ReLU(inplace=True),
        )

        self.fc7 = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(4096, 4096),
            nn.ReLU(),
        )

        self.fc8 = nn.Sequential(
            nn.Linear(4096, 10),

        )

    def forward(self, x):
        x = self.conv1(x)
        x = self.conv2(x)
        x = self.conv3(x)
        x = self.conv4(x)
        x = self.conv5(x)
        x = x.view(x.size(0), -1)

        x = self.fc6(x)
        x = self.fc7(x)
        x = self.fc8(x)

        return x
model = AlexNet().to(device)
criterion = nn.CrossEntropyLoss()
optimizer = optim.Adam(model.parameters(), lr=1e-3, weight_decay=1e-4)
scheduler = optim.lr_scheduler.ReduceLROnPlateau(optimizer, mode='min', factor=0.2, patience=5, verbose=True)
summary(model, input_size=(3, 227, 227), batch_size=64)

 

 

- Training

epochs = 20
l_ = []
pbar = trange(epochs)

for i in pbar:
    train_loss, correct, total, = 0.0, 0, 0

    for data in trainloader:
        images, labels = data[0].to(device), data[1].to(device)
        outputs = model(images)

        optimizer.zero_grad()
        loss = criterion(outputs, labels)
        loss.backward()
        optimizer.step()

        train_loss += loss.item()
        _, predicted = torch.max(outputs.detach(), 1)

        total += labels.size()[0]
        correct += (predicted == labels).sum().item()

    l = train_loss / len(trainloader)
    l_.append(l)
    acc = 100 * correct / total
    
    pbar.set_postfix({
        'loss' : l,
        'train acc' : acc
    })
    

print(l_)

 

성능이 잘 나오지 않아서 tr.Resize(128)로 바꿔서 진행했다. (cifar 데이터셋 이미지 크기가 32 x 32로 작은 편임)

그대신 아래와 같이 fc6을 바꿔줘야 한다.

self.fc6 = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(1024, 4096),
            nn.ReLU(inplace=True),
        )

loss = 0.772, train accuracy : 74.3

 

 

- Testing

correct, total = 0, 0

with torch.no_grad():
    model.eval()
    test_loss = 0.0
    
    for data in testloader:
        images, labels = data[0].to(device), data[1].to(device)
        outputs = model(images)
        test_loss += loss.item()
        
        _, predicted = torch.max(outputs.data, axis=1)
        total += labels.size(0)
        correct += (predicted == labels).sum().item()
        
print(f"Test loss : {test_loss / len(testloader)}")
print(f"Accuracy : {correct / total:.2f}")

loss : 0.813, test accuracy : 71.80

 

1. 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해, 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환하라.

 

 

- 제한 사항

1. scoville의 길이는 2 이상 1,000,000 이하

2. K는 0 이상 1,000,000,000 이하

3. scoville의 원소는 각각 0 이상 1,000,000 이하

4. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return

 

 

 

2. 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    if scoville[0] >= K:
        return answer
    
    while len(scoville) > 1:
        answer += 1

        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        
        heapq.heappush(scoville, min1 + (min2 * 2))
        
        if scoville[0] >= K:
            return answer
        else:
            continue
        
    return -1

 

 

 

3. 설명

heap을 쓴다는 것을 안다면 쉽게 풀 수 있는 문제였다.

최솟값을 반환해야 하기 때문에 힙을 사용한다.

 

중간에 한 개의 테스트 케이스에서 오답이 나오는 경우가 있었는데,

이는 처음부터 모든 스코빌 지수가 K보다 큰 경우 (섞을 필요가 없는 경우) 0을 반환해야 하는 케이스였다.

 

import heapq

heapq.heapify(list)

heapq.heappop(list)

heapq.heappush(list, value)

 

이 문법만 알면 python에서의 heap은 문제 없을 것 같다.

 

참고로, heapq는 최소힙이 기본이다. 따라서 최대힙은 다음과 같이 선언한다.

# heappush
for value in values:
	heapq.heappush(heap, -value)
 
# heappop
for i in range(5):
	print(-heapq.heappop(heap))

1. 문제 설명

땅따먹기 게임을 하려고 한다.

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있다.

 

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다.

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있다.

 

예)

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

1행에서 네번째 칸 (5)를 밟았다면, 2행의 네번째 칸 (8)은 밟을 수 없다.

 

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라.

 

 

 

2. 코드

(1) 1차 시도 - 런타임 에러

answer = 0

def dfs(land, row, col, tot):
    global answer
    tot += land[row][col]

    if row == len(land) - 1:
        if answer < tot:
            answer = tot
        return 
    

    for i in range(4):
        if i == col:
            continue
        dfs(land, row+1, i, tot)
    
    
def solution(land):
    global answer
    
    for col in range(4):
        dfs(land, 0, col, 0)
    
    return answer

 

 

(2) 2차 시도 - DP

def solution(land):
    for i in range(1, len(land)): # 행 반복
        for j in range(4): # 열 반복
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
    
    return max(land[-1])

 

 

 

3. 설명

우선 처음에 짠 코드는 깊이 우선 탐색 (DFS) 방법을 사용해서 구현했다.

재귀 함수로 열을 반복하며 (단, 연속된 동일한 열은 제외) sum을 누적하는 방식으로 했는데,

재귀로 호출되면서 알 수 없는 런타임 에러가 떴다.. (반례도 다 조사했을 때 문제 없었다ㅠㅠ)

 

그래서 다이나믹 프로그래밍으로 다시 구현했다.

이전 행에서의 최댓값을 뽑아서 현재 행에 더하는 방식으로 하여,

맨 마지막 행에서의 최댓값을 택하면 답이 된다!

1. 문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 한다. 

- U : 위쪽으로 한 칸 가기

- D : 아래쪽으로 한 칸 가기

- R : 오른쪽으로 한 칸 가기

- L : 왼쪽으로 한 칸 가기

 

캐릭터는 좌표평면의 (0, 0) 위치에서 시작하고, 좌표평면의 경계는 (-5, -5), (-5, 5), (5, 5), (5, -5)이다.

예) "ULURRDLLU"

 

 

게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 한다.

위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 된다.

(8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길)

 

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 반환하라.

 

 

 

2. 코드

(1) 내 코드

def solution(dirs):
    dx = [0, 0, 1, -1] # UDRL
    dy = [1, -1, 0, 0] # UDRL
    x, y = 0, 0
    
    garo = [ [False for _ in range(10)] for _ in range(11) ]
    saero = [ [False for _ in range(10)] for _ in range(11) ]
    
    answer = 0
    for dir in dirs:
        if dir == 'U':
            new_x = x + dx[0]
            new_y = y + dy[0]
        elif dir == 'D':
            new_x = x + dx[1]
            new_y = y + dy[1]
        elif dir == 'R':
            new_x = x + dx[2]
            new_y = y + dy[2]
        elif dir == 'L':
            new_x = x + dx[3]
            new_y = y + dy[3]
        
        if new_x < -5 or new_x > 5 or new_y < -5 or new_y > 5:
            continue
        
        if dir == 'R':
            if garo[5 - new_y][5 + x] == False:
                garo[5 - new_y][5 + x] = True
                answer += 1
        elif dir == 'L':
            if garo[5 - new_y][5 + new_x] == False:
                garo[5 - new_y][5 + new_x] = True
                answer += 1
        elif dir == 'U':
            if saero[5 + new_x][5 - new_y] == False:
                saero[5 + new_x][5 - new_y] = True
                answer += 1
        elif dir == 'D':
            if saero[5 + new_x][5 - y] == False:
                saero[5 + new_x][5 - y] = True
                answer += 1
        
        x, y = new_x, new_y
        
        
    return answer

 

 

 

(2) set 활용한 코드

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny
            
    return len(s)//2

 

 

 

3. 설명

(1) 내 코드

우선 내가 짠 코드는.. 정말 있는 그대로의 날 것의 코드이다.. ㅎ 좀 창피하긴 한데, set을 활용할 생각을 못했어서 이렇게 풀 수밖에 없었다ㅜㅠ

 

흔히 다이나믹 프로그래밍에서 하는 것처럼 방문 여부를 저장하기 위해 배열을 만들어준다.

단, UP, DOWN은 'garo[11][10]' 배열을,

LEFT, RIGHT는 'saero[11][10]' 배열이다.

 

배열의 인덱스와 좌표를 맞춰주기 위해서 규칙을 찾아봤을 때,

각각 5-x 또는 5+x, 5-y, 5+y를 해주면 맞춰진다.

 

각각의 경우를 조건문으로 해서 하나씩 조사해 나가면 된다.

 

 

 

(2) set 활용한 코드

우선 UDRL을 딕셔너리로 선언하고, 좌표 범위를 넘어서는지 조사한다.

 

그리고는 (시작좌표 x, 시작좌표 y, 도착좌표 x, 도착좌표 y)와 (도착좌표 x, 도착좌표 y, 시작좌표 x, 시작좌표 y)를 모두 집합에 넣는다.

 

- 집합에 넣는 이유 : 중복되는 이동 쌍이 없도록

- 마지막에 2로 나눠주는 이유 : 시작과 도착 좌표를 모두 넣어줬기 때문에, 그 절반 값이 이동 횟수임

 

 

배울 점이 많았던 코드였다. 이동 경로를 string으로 저장하지 않고, 시작과 끝 좌표 쌍을 모두 저장하는 방식,

그리고 집합을 사용하여 중복 제거하는 것까지!

 

 

 

1. 문제 설명

정수로 이루어진 배열 numbers가 있다.

배열에서 자신보다 뒤에 있는 숫자 중에서, 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 한다.


정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 반환하라.

단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다.

 

예시)

- numbers = [2, 3, 3, 5]

정답 : [3, 5, 5, -1]

 

- numbers = [9, 1, 5, 3, 6, 2]

정답 : [-1, 5, 6, 6, -1, -1]

 

 

 

 

2. 코드

(1) 1차 시도

def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                break
        if len(answer) != (i+1):
            answer.append(-1)
    
    return answer

 

 

 

(2) 2차 시도

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]
    stack = []
    
    for i in range(len(numbers)):
    
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        
        stack.append(i)
        
    return answer

 

 

 

3. 설명

이 문제가 되게 단순해 보였지만, 시간 초과를 극복하려면 새로운 관점이 필요하기 때문에 어려웠다.

 

많은 사람들의 코드를 봤을 때, 2차 시도 코드와 비슷하거나 동일하다.

그래서 나는 어떻게 stack을 도입할 시도를 하게 되었는지를 생각해보기로 했다.

처음에는 절대로 저런 생각이 나지 않기 때문이다..

 

 

index 하나 하나씩을 해결해나가는 식이 아니라, 바로 뒤에 큰 수가 없다면 잠시 스택에 넣고 대기하는 형식이다.

시간 초과가 나는 방식

이렇게 하나씩 뿌시는 경우에는 현재 인덱스에서 그 뒤의 인덱스 이후를 다 비교해봐야 하기 때문에, $O(n^2)$이 된다.

 

 

검토하고 있는 인덱스의 그 다음 인덱스 시점에서 바라본다.

만약 그 인덱스가 큰 수를 찾지 못했다면 스택에 넣는다!

 

기본적으로 현재 인덱스를 스택에 넣어주고, 조건 맞을 시에 pop() 하도록 구현한다.

위의 그림이 단계를 거치면서 스택의 변화를 보여준다.

 

즉, for 문이 돌아가는 그 시점의 인덱스는 answer 값이 변하는 시점의 인덱스가 아니라, 비교대상이라고 생각하면 된다!

1. 문제 설명

철수와 동생은 롤케이크를 나눠 먹으려고 한다.

두 사람은 롤케이크 길이, 토핑의 개수보다 토핑 종류를 더 중요하게 생각한다.

 

topping 배열이 주어졌을 때, "동일한 가짓수의 토핑"을 나눠 먹을 수 있도록 하는 방법의 가짓수를 반환하라.

 

예를 들어, [1, 2, 1, 3, 1, 4, 1, 2] 토핑은 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]로 나눌 수 있으므로, 총 2가지이다.

[1, 2, 3, 1, 4]는 어떻게 나누든 공평한 토핑의 종류를 가질 수 없으므로, 0이다.

 

 

 

2. 코드

(1) 1차 시도

def solution(topping):
    answer = 0
    
    for i in range(1, len(topping)):
        a = topping[:i]
        b = topping[i:]
        
        if len(set(a)) == len(set(b)):
            answer += 1
    
    return answer

 

 

(2) 2차 시도

from collections import Counter

def solution(topping):
    topping_dict = Counter(topping)
    topping_set = set()
    answer = 0
    
    for i in topping:
        topping_dict[i] -= 1
        topping_set.add(i)
        
        if topping_dict[i] == 0:
            topping_dict.pop(i)
        
        if len(topping_set) == len(topping_dict):
            answer += 1
    
    return answer

 

 

 

3. 설명

배열 슬라이싱이 $O(N)$이 걸려서, 결국 $O(N^2)$ 수행시간이 걸리게 된다. 그래서 시간 초과가 났던 것이다ㅜ

 

슬라이싱을 안 하고, 한번의 검토로 기준선 앞, 뒤를 모두 검토할 수 있는 방식으로 다시 코드를 짰다.

Counter dictionary를 사용해서 토핑 종류에 대한 개수를 저장하고, 기준 앞쪽에 대해서 원소를 하나씩 지워나간다.

그러면서 집합에 넣어서 unique한 원소들의 개수를 구한다.

 

topping_set과 topping_dict 길이가 같다면 answer + 1 해준다.

+ Recent posts