오른방향 -> 아래방향 -> 왼쪽 방향 -> 윗방향 -> 오른방향 .. 이런식으로 진행한다
다음의 값이 0이 아닌 것을 체크하여 진행한다.
def solution(n):
answer = [[0 for i in range(n)] for j in range(n)]
num = 1
i,j = 0,0
dir = "right"
while num < (n * n + 1):
answer[i][j] = num
# 오른쪽으로 진행
if dir == "right":
if (j < n - 1) and (answer[i][j+1] == 0):
j += 1
else:
dir = "down"
i += 1
elif dir == "down":
if (i < n - 1) and (answer[i+1][j] == 0):
i += 1
else:
dir = "left"
j-= 1
elif dir == "left":
if (j > 0) and (answer[i][j-1] == 0):
j -= 1
else:
dir = "up"
i -= 1
else:
if (i > 0) and (answer[i-1][j] == 0):
i -= 1
else:
dir = "right"
j += 1
num += 1
#print(answer)
return answer
효과적인 이유 : input image is bigger → the network needs more layer to increase the receptive field and more channels to capture more fine-grained patterns on the bigger image.
3. Compound Model Scaling
3.1. Problem Formulation
3.2. Scaling Dimensions
Depth (d): 자주 사용하는 방식
depth 를 깊이 할 경우 high level의 feature를 뽑을 수 있고 generalize 잘 되고 성능이 올라간다
하지만 어느 정도 까지 갈 경우 saturate 상태가 된다.
The intuition is that deeper ConvNet can capture richer and more complex features, and generalize well on new tasks.
하지만 , networks 가 깊어지면 깊어질수록 학습하기 어렵고 vanishing gradient problem이 있다.
skip connection, batch normalization 으로 학습 문제를 완화하지만 매우 깊은 network의 정확도 이득은 감소한다. 예를 들어 ResNet-1000은 ResNet-101 비슷한 정확도를 가진다.
width(w) : small size models에 자주 사용
fine-grained features 쉽게 뽑아내고 train을 쉬운 경향이 있다.
channel을 널리면 network depth를 줄이기 때문에 higher level features이 덜 얻게 되는 문제가 있을 수 있다.
Resolution (r):capture more fine-grained patterns
Resolution
224x224
early ConvNets
299x299
Rethinking the inception architecture for computer vision
331X331
Learning transferable architectures for scalable image recognition. CVPR, 2018. NasNet
480x480
Gpipe: Efficient training of giant neural networks using pipeline parallelism.
600x600
Mask-RCNN, FPN
너무 크면 정확도도 떨어지고 계산량도 많아진다.
위의 그림을 보시면 width scaling, depth scaling 은 비교적 이른 시점에 정확도가 saturation 되며 그나마 resolution scaling이 키우면 키울수록 정확도가 잘 오르는 것을 확인할 수 있다.
Observation 1 – 네트워크의 width, depth, resolution 중 어느 차원을 scale up 시켜도 성능은 향상된다. 그러나 너무 큰 모델에 있어서는 그 성능 향상이 saturate된다.
3.3. Compound Scaling
직관적으로 생각해보면 Input image가 커지면 그에 따라서 receptive field도 늘려줘야 하고 더 많은 layer가 필요하고 , resolution 이 커져서 특징들을 뽑아낼려면 더 많은 channel이 필요한 것
resolution 키우면 그것에 맞게 depth와 width도 키워야 될 것이다.
Observation 2 –성능과 효율성을 높이기 위해서 ConvNet scaling을 진행할 때, width, depth, resolution의 모든 차원의 밸런스를 맞추는게 중요하다.
compound scaling method
4. EfficientNet Architecture
MnasNet과 비슷한데 latency가 들어있지 않는다.
5. Experiments
5.1. Scaling Up MobileNets and ResNet
기존에 존재한 모델 baseline, depth, width, resolution, compound scale를 변경하여 하였지만 그중에서 compound scale의 정확도가 높았다.
5.2. ImageNet Results for EfficientNet
MnasNet: Platform-aware neural architecture search for mobile. CVPR, 2019 RMSProp optimizer with decay 0.9 and momentum 0.9 batch norm momentum 0.99 weight decay $1e^{-5}$ initial learning rate 0.256 that decays by 0.97 every 2.4 epochs SiLU (Swish-1) activation AutoAugment stochastic depth (Huang et al., 2016) with survival probability 0.8 As commonly known that bigger models need more regularization, we linearly increase dropout (Srivastava et al., 2014) ratio from 0.2 for EfficientNet-B0 to 0.5 for B7.
Table 2
정확도는 비슷하지만 parameter 수와 FLOPS수 가 적다.
parameters-accuracy and FLOPS-accuracy
our EfficientNet models are not only small, but also computational cheaper.
latency을 검증하기 위해 inference latency 도 측정 → Table 4
5.3. Transfer Learning Results for EfficientNet
Table 5 shows the transfer learning performance:
(1) Compared to public available models, such as NASNet-A (Zoph et al., 2018) and Inception-v4 (Szegedy et al., 2017),
(2) Compared to stateof-the-art models, including DAT (Ngiam et al., 2018) that dynamically synthesizes training data and GPipe (Huang et al., 2018)
Figure 6 compares the accuracy-parameters curve for a variety of models.
6. Discussion
Figure 8 Compound scaling에서 2.5%
Figure 7 class activation map (Zhou et al., 2016),
해당 통계는 Table 7에서 보여준다.
Images는 random으로 ImageNet validation set에서 선택되였다.
Figure 7에서 볼 수 있듯이 compound scaling 이 있는 model은 object details 정보가 더 많은 관련 region에 focus을 맞추는 경향이 있는 반면, 다른 models은 object details 정보가 부족하거나 이미지의 모든 objects를 capture 할 수 없다.
3. 마지막에 중요하다고 느낀 것은 이부분이다. 아래로 미루는 부분에서 많이 틀린 경우가 많다. 이 경우 초반에 잘못해서 5,10이 틀렸다.
def solution(m, n, board):
answer = 0
board = [[j for j in i ] for i in board ]
while True:
list_= []
# 4개 있는 점 찾기
for i in range(m-1):
for j in range(n-1):
if board[i][j] != ' ' and (board[i][j] == board[i+1][j] == board[i+1][j+1] == board[i+1][j+1]== board[i][j + 1]):
list_.append((i+1,j+1))
list_.append((i+1,j))
list_.append((i,j+1))
list_.append((i,j))
# 4개 있는 곳 지워주기
answer += len(set(list_))
if len(list_) == 0:
return answer
for i,j in list_:
board[i][j] = ' '
# 보드를 아래 루 내리기
while True:
moved = False
for i in range(1, m):
for j in range(n):
if board[i-1][j] != ' ' and board[i][j] == ' ':
board[i][j] = board[i-1][j]
board[i-1][j] = ' '
moved = True
if not moved:
break
return answer
m = 4
n = 5
board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]
solution(m, n, board)
5점
보드를 아래 루 내리기 한 부분에서 while문을 하여 중간에 있는 부분을 채워줘야 한다.
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예kdungeonsresult
80
[[80,20],[50,40],[30,10]]
3
입출력 예 설명
현재 피로도는 80입니다.
만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
※ 공지 - 2022년 2월 25일 테스트케이스가 추가되었습니다.
아래 소스를 참고 하고 수정하였다.
answer = 0
def enter_dungen(dungeons, k, idx, visited):
global answer
k -= dungeons[idx][1] # 소모 피로도를 줄인다.
answer = max(answer, sum(visited))
for idx_2, val_2 in enumerate(dungeons):
#print(idx, idx_2, val_2)
if not visited[idx_2] and k >= val_2[0]: # 방문하지 않고 소모도가 클 경우
visited[idx_2] = 1
enter_dungen(dungeons, k, idx_2, visited)
visited[idx_2] = 0
return answer
def solution(k, dungeons):
for idx, val in enumerate(dungeons):
visited = [0] * len(dungeons) # 합을 계산하기 쉽게 하였다
if k >= val[0]:# 처음이여서 소모도가 클 경우
visited[idx] = 1
enter_dungen(dungeons, k, idx, visited)
visited[idx] = 0
return answer
k = 80
dungeons = [[80,20],[50,40],[30,10]]
solution(k, dungeons)
YOLO9000 bounding box를 예측하는데 dimension clusters anchor boxes로 사용한다.
4 coordinates for each bounding box
loss : sum of squared error loss
predicts an objectness score for each bounding box using logistic regression
threshold of .5
Faster RCCN과 달리 우리 시스템은 각 ground truth object 에 대해 하나의 bounding box를 할당한다.
2.2. Class Prediction
multilabel classification를 사용하여 bounding box에 포함될 수 있는 class를 예측한다.
softmax를 상요하지 않고 대신 단순한 independent logistic classifiers를 사용한다. softmax를 사용하면 각 bounding box가 겹치는 레이블이 많을 경우 잘 안된다.
학습하는 동안 class predictions 을 위해 binary cross entropy loss을 사용한다.
A multilabel approach better models the data. ⇒ 겹치는 label에 대하여
2.3. Predictions Across Scales
boxes는 3가지 다른 scale에 대해서 예측한다.
we predict 3 boxes at each scale so the tensor is N × N × [3 ∗ (4 + 1 + 80)] for the 4 bounding box offsets, 1 objectness prediction, and 80 class predictions.
다음으로 우리는 previous layer 2개에서 feature map을 가져와 2x upsample 한다. 또한 network의 초기에서 feature map을 가져와 연결을 사용하여 upsampled 된 feature와 concatenation한다. ⇒ 이 방법을 사용하여 upsampled feature에서 더 의미 있는 의미 정보를 얻고 이전 feature map에서 더 세분화된 정보를 얻을 수 있다.
Feature Pyramid Network
We then add a few more convolutional layers to process this combined feature map, and eventually predict a similar tensor, although now twice the size.