문제:

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력:

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

풀이방법:

**이 문제는 pypy3으로 통과했습니다.**

 이 문제는 for(bfs)라고 생각했다. 우선 bfs를 사용한 이유는 한 나라로부터 인접한 국가들을 찾는 방법은 bfs가 가장 적당하다고 생각했기 때문이다. 하지만 이러한 bfs를 NxN 크기의 땅에 모두에 대해서 수행해야 했기 때문에 for(bfs)라고 생각했다. 그리고 이러한 문제때문에 시간초과가 발생할 수 있을 것 같다는 걱정이 들었는데, 실제로 python3으로는 시간초과가 발생하여서 pypy3으로 이 문제를 해결하였다.

 bfs를 통해서 국경이 열리는 나라들을 찾으며 인구 수를 더하며 count를 센다. 한 번의 bfs 탐색이 끝나게 되면, 업데이트를 하는 과정을 거치고, 다시 이어서 bfs를 수행하도록 한다. 

 이러한 과정을 인구 이동이 발생하지 않을 때까지 반복한다.

문제링크:

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

Relational Graph Attention Network for Aspect-based Sentiment Analysis

• 최근에는 ABSA를 attention-based neural network을 사용해서 해결하고자 한다.
  • 하지만 언어의 복잡성과 한 문장에서 복수의 aspect가 존재할 수 있기 때문에 연결성에 혼란을 가진다.
• 이 논문에서는 이 문제를 구문정보의 효과적인 인코딩을 사용해 해결하고자 한다.
  • 기존의 dependency tree를 reshape, pruning해서 target aspect를 root로 가지는 aspect-oriented dependency tree 구조를 정의한다.
  • sentiment prediction을 위해서 새 tree 구조를 encode 할 R-GAT를 제안한다.
• 이 방법이 더 연결성을 잘가지고 있는 것을 보임

1. Introduction

• 두 개의 aspect가 서로 다른 sentiment를 나타낼 수 있기 때문에 sentence-level sentiment polarity 를 적용하는 것은 부적절하다.

• Attention 메커니즘을 가지는 구조에는 가까운 단어에 더 attend하는 특성을 가지고 있는데, 이는 잘못된 결과를 초래할 수 있다.

• Syntactic structure를 이용하려는 많은 시도가 있었고, Dependency-based parse는 comprehensive syntactic information을 제공한다.

  • 최근에는 GNN + dependency tree를 시도함

• 이러한 구조들은 다음과 같은 단점을 가지고 있다.

  1. 측면과 의견 단어 사이의 연관성을 나타낼 수 있는 의존 관계는 무시된다.
  2. 트리의 일부부만 필요한 것이지, 전체 트리 구조가 필요한 것은 아니다.
  3. encoding process가 트리 종속적이기 때문에 batch operation이 불편한다.

• 이 논문에서는 syntax information을 재검토하고, task-related syntactic 구조를 알아내는 것이 중요하다.

  • 따라서 novel aspect-oriented dependency tree 구조를 세 단계로 제안한다.
    • 기존의 parser를 사용해서 sentence의 dependency tree를 얻는다.
    • 질문의 target aspect로 root가 되게 dependency tree를 reshape한다.
    • aspect와 직접 연결된 edge들만 남긴다.

• 이러한 unified tree 구조는 aspect와 가능성 있는 opinion word 사이의 관계성에 집중할 뿐만 아니라 batch와 parallel 연산도 이용할 수 있다.

• 또한 이러한 새 tree를 encode하기 위해 R-GAT(relational graph attention network)를 제안함

2. Related Work

pass

3. Aspect-Oriented Dependency Tree

3.1 Aspect, Attention and Syntax

• syntactic 구조는 문법 구조를 나타내는 종속성 트리를 생성하는 작업인 종속성 구문 분석을 통해 알아낼 수 있다.
  • 단어 사이의 관계는 directed edge와 label로 나타낸다.

• 위 그림은 aspect, attention, syntax 간의 관계를 그림으로 그린 것이다.
• (a)의 경우 like는 동사로 사용되었으며, aspect recipe에 대해 positive를 표현한다.
  • 즉 이는 attention-based LSTM에 의해 성공적으로 attend되었다는 것을 알 수 있다.
• (b)에서의 like는 다른 의미로 사용되었지만 여전히 recipe와 연결되어 있어 잘못된 예측을 했다.
• (c)는 두 개의 aspect가 등장하는 경우다.
  • chicken같은 경우에는 but, dried와 강하게 연결되었고, 잘못된 예측을 하도록 했다.
    • attention-based 모델의 약점을 보여주는 예시임

3.2 Aspect-Oriented Dependency Tree

• 3.1의 내용을 보면 aspect와 related opinion이 직접적으로 연결된 dependency 관계에 더 직접적으로 집중한다.

• 하지만 ABSA에서는 target aspect에 더 집중해야 할 것이다.

  • 그래서 target aspect를 root로 하는 aspect-oriented dependency tree를 제안한다.

    1. 기존 Dependency Tree를 구축
    2. target aspect를 root로 구축
    3. aspect에 직접 연결되어 있는 connection을 children으로 set한다.
    4. n:con이라는 가상 관계를 부여한다. 이 때, n은 두 노드 사이의 거리를 나타낸다.
    5. 이 과정을 aspect가 여러개라면 각각 만든다.

  • 그러면 다음과 같이 dependency tree가 바뀌게 된다.

    

  • aspect-oriented 구조는 다음과 같은 2가지 장점을 가진다.

    1. 각 aspect는 고유의 dependency tree를 가진다. 따라서 관계없는 node나 관계에 덜 영향을 받는다.
    2. aspect가 하나 보다 더 많은 단어로 구성되어 있어도 분석이 가능하다.

  • 이 아이디어는 aspect와 관계 있는 일부 단어들만 사용해도 가능하다는 것 때문에 가능하다.

  • batch, parallel 연산을 가능하게 한다.

  • n:con 관계가 좀 더 robust하게 만든다.

4. Relational Graph Attention Network

• 새 트리 구조를 encoding 하기 위해서 GAT를 확장한 relational graph attention network를 제안한다.

4.1 Graph Attention Network

• Dependency tree는 n개의 노드를 가지고 있는 graph G로 표현된다.
• graph G의 edge는 워드간의 dependency를 N_i는 neighborhood 노드를 나타낸다.
• multi-head attention을 사용해서 이웃 노드 representation을 취합해 node representation을 업데이트 한다.

4.2 Relational Graph Attention Network

• GAT는 dependency relation을 잃어버릴 수 있다.

• 다른 의존 관계를 가지고 있는 neighborhood는 서로 다른 영향을 준다.

• GAT에 relation head를 추가하는데 이는 neighborhood로 부터 오는 정보 흐름을 조절하는 relation-wise gate 역할을 수행한다.

• Dependency relation을 vector representation으로 map하고, relation head는 아래 식과 같이 계산한다.

  

4.3 Model Training

• BiLSTM을 사용해서 tree node의 word embedding을 encode하고, 또 다른 BiLSTM을 사용해서 aspect 단어를 encode하고 이를 평균내서 초기 root representation으로 사용한다.
• Aspect-oriented tree의 R-GAT를 적용한 후에, fc layer와 softmax를 활용해서 sentiment를 예측한다.

5. Experiment

5.1 Datasets

• SemEval 2014 Task의 Laptop과 Restaurant 리뷰 데이터셋을 사용한다.
• 이와 함께 Twitter 데이터셋도 같이 사용

5.1.1 Implementation Details

• dependency parsing을 위해서 Biaffine Parser를 사용한다.
  • 차원은 300으로 고정
• R-GAT는 GLoVe를 사용, R-GAT+BERT는 BERT의 last hidden state를 사용한다.

5.2 Baseline Methods

• Syntax-aware models
  • LSTM+SynATT, AdaRNN, PhraseRNN, AS-GCN, CDT, GAT, TD-GAT
• Attention-based models
  • ATAE-LSTM, IAN, RAM, MGAN, attention-equipped LSTM and fine-tuned BERt
• Other recent method
  • JCI, TNET

5.3 Results and Analysis

5.3.1 Overall Performance

• R-GAT 모델이 다른 baseline들보다 성능이 좋음
  • 특히 일반 GAT를 쓸 때 보다 큰 성능향상이 있었다.
• BERT를 사용했을 떄, ABSA에서 좋은 성능을 기록했는데 여기에 R-GAT를 같이 사용하면 더 좋아졌다.

5.3.2 Effect of Multiple Aspects

• 한 문장에서 multiple aspect가 나올 수 있다.
• 만약 두 개 이상의 asepct가 나오면 각 aspect 별로 Euclidean distance를 구한다.
• GAT, R-GAT, R-GAT+BERT를 골라서 distance에 따라 정확도를 측정한 것.

• 거리가 가까운 측면이 정확도 점수를 낮추는 경향이 있다는 것을 관찰할 수 있으며, 이는 문장에서 의미 유사성이 높은 측면이 모델을 혼동할 수 있음을 나타낸다.
  • R-GAT는 이 문제를 완화했다.

5.3.3 Effect of Differnet Parsers

• Dependency parsing을 다르게 하면서 성능을 비교해본다.

• Biaffine을 사용할 때 성능이 더 좋음

5.3.4 Ablation Study

• aspect-oriented dependency tree와 relation head의 영향력을 평가함

• R-GAT를 사용할 때 더 성능이 올라가는 것을 보이고, aspect-oriented로 reshape 했을 때 성능이 더 향상 되는 것이 보임
• 특히 R-GAT에서 n:con의 관계를 빼면 성능이 떨어지는 것을 보아 좋은 영향을 주는 것을 알 수 있음

5.3.5 Error Analysis

• ABAS의 한계를 알기 위해서 실패한 것들 중에서 100개를 랜덤으로 고름
• 실패하는 이유는 여러가지가 있었다.
  • 대부분의 이유로는 중립 리뷰로 인한 것이였다.
  • 다른 요인은 실제로 이해하기 어려운 언어라 분석하기 어려웠었다.
  • 문장에서 뚜렷한 특징이 없거나
  • 이중 부정이 나타나는 경우에 분석이 힘들었다.

문제:

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력:

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

풀이방법:

주어진 조건대로 톱니바퀴가 동작하는 알고리즘을 구현하면 되는 문제다.

 회전하는 것을 구현하기 위해서 collections에 있는 deque의 rotation 함수를 사용한다. 따라서 입력을 받을 때, 각 톱니바퀴들은 deque의 자료형을 가지게 된다.

 입력으로 주어지는 톱니바퀴를 우선적으로 회전시킨 후에 조건에 맞는다면 주변 톱니바퀴도 회전시킨다. 12시 방향이 모든 배열의 시작이기 때문에, 톱니바퀴들이 서로 만나는 인덱스는 '2'번 인덱스와 '-2'번 인덱스다. 따라서 두 인덱스가 다르고, 아직 방문하지 않은 톱니바퀴라면 현재 톱니바퀴의 반대 방향으로 회전시키도록 한다.

문제링크:

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

Lecture 3

Basic

• Overview of CNNs
  • A special case of MLP
  • Commonly apply to visual object or 2D array input
  • Unified feature extractor and classifier in one network
  • Filter kernel = weights in between layers
  • Feature map = filtered outputs

• How can compute Feature Map Size?

  

  • i = input size, k = filter size(kernel), s = stride, o = output feature map size

  • if o<i, can occur some problem

    • then, we can use Zero Padding

      

• At same points, we can apply multiple filters. We call it "channel"

Two Characteristics of CNNs

1. Local Connectivity - image is locally correlated
2. Weight Sharing- overcome enormous weights problem

Local Connectivity

• MLP : Weights are fully connected, ie. MLP use all weights
• CNNs : One neuron will connect to filter size chunk , thus only have 5x5x3 weights

Receptive Field(RF)

How much a convolution window "see" on it's input image or part of the image that is visible to one filter at a time

In upper figure, dark pink square in left light pink square(32x32x3) is Receptive Filed.

It means "Receptive Filed size == filter size"

• How the later feature map "see" the image?

Weight Sharing

• MLP has different weights for every single neuron.
  • Total # of weights = (filter size) x (Input_w x Input_h x # of feature maps) = too many!
• CNN has same weight for every single feature map
  • Total # of weights = (filter size) x # of feature maps = small than MLP

Max Pooling

Pooling does resize the activation map from convolution to get new layer.

• Output size (o)
• Input size (i)
• Pooling window size (k)
• Stride (s)

Fully Connected (FC) layer

• FC layer started right after the last convolution or pooling layer
• Flatten pooling layer = input layer of MLP
• Last FC layer = output layer of ConvNet. It uses several tasks like classification.

Summary

Typical ConvNet process : [CONV layer - ReLU-Pooling] x N - [FC-ReLU] x M - FC - (softmax or sigmoid)

• Parameter in CNN

  • Conv layer
    • Filter window size (Odd number)
    • Number of Filters (Power of 2)
    • Stride
    • # of Conv layers
  • Pooling layer
    • Pooling window size
    • stride
    • # of pooling layer
  • Fc layer
    • # of hidden nodes
    • # of FC layer
  • BP algorithm
    • Learning rate, batch number, momentum coefficient, L2 coefficient

  Feature Normalization in CNN

  Batch Normalization(BN)

  • Using mean and variance of each feature, Normalize each feature in batch
  • normalize feature map of each channel over a batch sample

  Layer Normalization(LN)

  • Using mean and variance of each feature in input, normalize each input in batch
  • applicable to dynamic network and recurrent network(good)
  • normalize entire feature map

  

  Instance Normalization

  • It is similar with LN but not applicable to MLP and RNN. It is best for CNNs.
  • Effective for style transfer and image generation tasks using GAN
  • Compute mean and variance each sample in each channel

  Group Normalization

  • It is similar with Instance Normalization but not applicable to MLP and RNN. It is best for CNNs.
  • Effective for object detection, video classification (It is effective in memory problem)
  • Compute mean and variance each sample in each group that channels are grouped by group size g.
  • In image, The center of image and edge of image do not have equal meaning.
    • Thus, We can get flexibility if we compute differently each channels.
    • Also, Image's channel is not independent. If we use some channels nearby pivot channel, we can apply normalization at large region.

Storage and Computational Complexity

• c_i-1 = previous layer channel number
• c_i = previous layer channel number
• m_i-1 = previous feature map size
• m_i = previous feature map size
• k = filter size

# weights for layer i = (k x k x c_i-1) xc_i

# memory of layer i = m_i x m_i x c_i

# FLOPs = (kxk) x(m_i x m_i) x (c_i-1 x c_i)

CNNs Variants

Legends

LeNet 5 (1998)

• This architecture has become the standard
  • Stacking ConvNet and pooling
  • ending network with one or more fc.

AlexNet(2012)

• Apply RelU, pooling, data augmentation, dropout, Xavier initialization

VGGNet - 16 (2014)

• use only 3x3 sized filter.
• Before VGGNet, they use large filter. But 3x3 sized filter can result same output if use mulitple filter compared with large sized filter.

Effects of 3x3 sized filter

1. Decrease number of weights
   • If we have an input which has size [50x50x3] and 5x5 sized filter, # of weight is 5x5x3 = 75
   • If 3x3 sized filter, # of weight is (3x3x3)+(3x3x1) = 27 + 9 = 36
     • 2 consecutive 3x3 filters are same as 5x5 filter
2. Increase non-linearity
   • Each convolution has ReLU. 3x3 sized filter model has more non-linear function like ReLU than large sized filter model.

GoogleNet Inception-V1 (2014)

• 22 layers and 5 Million weights in total

• GoogleNet contains Inception Module that has parallel towers of convolutions with different filters, followed by concatenation, which captures different features at 1x1, 3x3 and 5x5.

  • In Inception Module, use 1x1 filter before 5x5 filter or 3x3 filter because if we don't use 1x1 sized filter, will get too many weights!

• We call 1x1 filter "bottleneck structure".

  • 1x1 convolutions are used for dimensionality reduction to remove computational bottlenecks
  • 1x1 convolutions add nonlinearity within a convolution

• Auxiliary classifier

  • Deeper network layers, higher likelihood of vanishing gradient.
  • Encourage discrimination in the lower stages
  • It only uses in training time.

ResNet-50 (2015)

• Skip connections/identity mapping can make deep network
• use batch normalization
• Remove FC layer and replace with GAP(Global Average Pooling)

Motivation

• When networks go deeper, a degradation problem has been exposed.
  • 56-layer's result is worse than 20-layer
  • But deep layer model has good results in many times.
    • So, need some techniques to make deep-layer model

Why ResNet works?

• use identity mappings to approximate "shallow network"

  

• Advantages of Skip Connection

  • Reduce optimization difficulty of deeper networks
  • Alleviate gradient vanishing problem
  • Reuse lower level feature

Xception (2016)

• An adaptation from Inception where the Inception modules have been replaced with depthwise separable convolution(DS-convolution layers)
  • Xception has same number of parameters as Inception

Inception - ResNet-V2 (2016)

• Converting Inception modules to Residual Inception blocks

ResNext-50 (2017)

• Adding of parallel towers/branches/paths within each module.

DenseNet (2017)

• Dense blocks where each layer is connected to every other layer in feedforward fashion
  • Alleviates vanishing gradient

Squeeze and Extraction - SENet (2017)

• Squeeze and Extraction can do feature recalibration to feature maps from origin networks.
• It is not a complete network, but a wrapper. Thus, we can use it with ResNet, ResNext, Inception etc.
• Improve channel interdependencies at almost no computational cost.

Squeeze

• Get a global understanding of each channel by squeezing the feature maps to a single numeric value.
  • use GAP(Global Average Pooling)

Extraction

• Feature Recalibration to computer channel-wise dependencies.
  • using Fully connected layer and non-linear function.

문제:

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력:

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이방법:

 nodes라는 이중배열을 사용해서 입력으로 주어지는 연결된 두 정점 사이의 관계를 기록한다. 그리고 항상 트리의 루트는 1이라고 정해졌기 때문에, 1부터 dfs를 사용해서 노드들을 탐색하면서 parent를 기록한다.

문제링크:

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

Does syntax matter? A strong baseline for Aspect-based Sentiment Analysis with RoBERTa

• Aspect-Based Sentiment Analysis (ABSA)는 Aspect의 특성을 예측하는 것이며, Sentiment Anaylsis의 한 분야다.
  • 즉, 주어진 Aspect에 따라 sentiment를 예측하는 것('pos' or 'neg')
• 이전 연구에서는 Dependency Tree와 같은 syntactic information이 ABSA의 성능을 향상시키는 것을 보였음
• 최근에는 Pre-Trained Models(PTMs)도 ABSA에서 성능을 보이고 있다.
  • 그러므로 PTM이 ABSA를 위해 충분한 syntactic 정보를 가지고 있어서, PTMs만을 기반으로 하여 좋은 ABSA 모델을 얻을 수 있는지 자연스러운 의문이 생긴다.
• 그래서 PTM에서 유도된 tree와 dependency parsing tree를 사용한 여러 유명한 모델을 비교해서 FT-RoBERTa로부터의 tree가 성능이 가장 좋음을 알 수 있다.
  • 또한 FT-RoBERTa가 더 sentiment-word-oriented다.
  • 순수한 RoBERTa 기반 모델도 충분한 SOTA 성능을 보인다.

1. Introduction

• Aspect-Based Sentiment Analysis (ABSA)는 Aspect의 특성을 예측하는 것이며, Sentiment Anaylsis의 한 분야다.

  • 한 문장에 여러 Aspect가 존재할 수 있고, 각 Aspect에 대해 sentiment를 예측해야 한다.
  • "great food but the service was dreadful"과 같은 문장이 있다
    • food와 service가 aspect가 되며, food의 sentiment는 'pos' service의 sentiment는 'neg'가 된다.

• ABSA에는 Aspect Extraction(AE)와 Aspect-level sentiment classification(ALSC)가 있는데, 그 중 ALSC에 집중한다.

• ALSC의 예전 연구들은 수동으로 설계된 syntactic feature에 의존했고 이는 굉장히 노동집약적이며 불충분하다

• ALSC model 기반 dependency tree는 3가지 방법으로 적용된다.

  1. Topological structure

  2. Tree-based distance

  3. 1과 2를 동시에 사용

• Dependency tree를 제외하고도 PTM이 좋은 성능을 기록했음

  • PTM의 결과를 보면 dependency tree 정보를 함축적으로 담고 있다.

Q1: Will the tree induced from PTMs achieve better performance than the tree given by a dependency parser when combined with different tree-based ALSC models?

-> 뒷 부분에서 3개의 dependency tree와 파서가 제공하는 의존성 트리 및 PTM 유도 트리와 결합할 때 성능을 비교한다.

Q2: Will the tree induced from PTMs achieve better performance than the tree given by a dependency parser when combined with different tree-based ALSC models?

-> 이 논문에서 PTM으로부터의 tree도 사용하지만 FT-PTM으로부터의 tree도 사용한다. 실험결과를 보았을 때, FT-PTM이 더 좋은 성능을 기록했으며, dependency tree보다도 더 좋았다.

마지막으로 RoBERTa에 MLP만을 더해도 좋은 성능을 보였으며, tree 구조를 더하는 것은 큰 성과를 보이지 못했다.

기여점을 요약하면 다음과 같다.

(1) PTM, FT-PTM으로 유도된 트리를 비교해봄. FT-PTM으로부터의 tree가 가장 좋은 성능을 기록했으며, 다른 트리들보다도 좋았다.

(2) FT-PTM으로부터의 트리는 더 sentiment word oriented하다. 즉 aspect term과 sentiment adjective를 직접적으로 연결한다.

(3) RoBERTa를 사용했을 때 성능이 가장 좋게 나왔다.

2. Related Work

ALSC without Dependencies

LSTM, LSTM with attention, CNN등을 사용함

ALSC with Dependencies

초기에는 Sentiment lexicon과 parsing dependency를 결합해서 사용했음

이후에는 dependency tree와 neural network를 결합해서 사용하려는 시도가 있었음

1. dependency tree를 binary tree로 바꾸는 것, 이후 recursive neural network를 젝용해 context word에서 aspect로 information을 전달하려는 시도를 함
   • 별로 성능이 좋아지진 않음
2. neural network
   • GNN을 적용하려는 시도
   • dependency tree를 aspect-oriented dependency tree
   • Tree-based distance

PTMs-based Dependency Probing

• PTMs는 NLP 분야에서 많이 사용되고 있다
  • 그래서 PTMs으로 linguistic knowledge를 얻으려는 시도를 함
  • 하나 혹은 여러개의 attention head를 사용해보았지만 dependency를 잡아내기 힘들었다
  • 추가적인 파라미터를 사용해서 하려는 시도들이 있었음

3. Method

PTMs으로 부터 tree를 어떻게 유도하는지 알아보고, dependency tree를 통합하는 3가지 대표적인 방법에서 선택한 3개의 tree 기반 ASLC 모델들을 소개한다.

3.1 Inducing Tree Structure from PTMs

Perturbed Masking은 추가적인 parameter 없이 pre-trained model에서 tree를 유도할 수 있다.

base가 되는 모델은 BERT와 RoBERTa를 사용하기 때문에, 이를 먼저 소개하고 Perturbed Masking을 소개한다.

3.1.1 BERT and RoBERTa

생략

3.1.2 Perturbed Masking

Perturbed Masking은 pre-trained model로부터 syntactic 정보를 찾기 위한 것이 목적이다. BERT와 RoBERTa는 x_i를 H(x)_i에 map한다.

Perturbed Masking은 와 x_j가 x_i에 영향을 주는 정도인 f(x_i,x_j)를 유도하는 것이 목적이다.

우선 [MASK]를 사용해서 x_i를 대체하고 H(x\{x_i})_i를 반환한다.

그 다음으론 x_j를 mask를 하고 H(x\{x_i,x_j})_i 를 얻고 f는 다음과 같이 구한다.

이 과정을 문장의 매 두 토큰에 대해 수행하면 f값들로 이루어진 M을 얻을 수 있다.

tree decoding 알고리즘을 통해서 M으로 부터 dependency tree를 얻는다.

3.2 ALSC Models Based on Trees

3개의 representative tree 기반 ALSC model을 소개함 각 모델들은 introduction에서 소개했고, 공정한 비교를 위해 가장 최근에 발전된 ALSC 모델들을 선정함

3.2.1 Aspect-specific Graph Convolutional Networks(ASGCN)

dependency tree를 그래프로 이용함. word를 노드로, dependency를 edge로 사용

3.2.2 Proximity-Weighted Convolution Network(PWCN)

PWCN은 aspect가 contextual word를 찾을수 있도록 도운다. input sentence에서 PWCN은 dependency tree를 얻고, 이 트리를 기반해서 각 단어에 proximity value를 부여한다.

각 단어의 proximity value는 단어와 aspect 사시의 dependency tree의 짧은 path를 계산하여 얻는다.

3.3 Relation Graph Attention Network

dependency tree를 aspect-oriented dependency tree로 변환한다.

aspect-oriented dependency tree는 aspect를 root로 사용하고, 다른 단어들은 leaf가 되는 구조

aspect와 다른 단어사이의 관계는 syntactic tag나 tree 기반 거리를 기반으로 구한다.

4. Experimental Setup

4가지 언어로 구성되어 있는 6개 데이터셋에 대해서 실험을 진행함

4.1 Datasets

pass

4.2 Tree Strucutres

(1) spaCy나 allenNLP에서 얻은 dependency tree parer로부터의 tree -> "Dep"

(2)PTM으로 얻은 tree

(3)Perturbed Masking을 사용한 FT-PTM

(4) Left, Right chain -> 왼쪽이나 오른쪽 단어에 의존하는 방법

4.3 Implementation Details

5. Experimental Results

5.1 ALSC Performance with Different Trees

다른 트리를 가지고 있는 모델 간의 비교는 위와 같다.

• FT-RoBERTa induced Tree를 사용할 때, 가장 좋은 성능을 기록함

• BERT Induced Tree나 RoBERTa Induced Tree를 기반으로 한 모델들은 Left-chain이나 Right chain이나 큰 차이가 없음

  

  • RoBERTa의 연결성을 보면 주위에 강하게 연결되어 있는데, 그 이유는 MLM을 수행하는 과정에서 주변을 많이 봐야하기 때문 그래서 왼쪽 종속이나 오른쪽에 종속하는 것과 큰차이가 없다

• Q1에 대한 답변을 하자면 "Dep"이 BERT Induced Tree나 RoBERTa Induced Tree보다 더 좋음

  • 그 이유는 PTM은 왼쪽이나 오른쪽에 의존하기 때문에
  • PWCN의 경우에만 더 좋은 성능을 보였는데 그건 크게 문제 될 것은 없음
  • 하지만 FT-PTM은 dependency tree보다 더 좋음

5.2 Analysis

• tree간의 차이를 조사하기 위해 quantitaive metrics를 제안함

Proportion of Neighboring Connections

• 위 표는 문장에서 주위 단어와 연결되어 있는 비율을 뜻함

• BERT가 70퍼대의 연결성을 보이는데 이 것이 성능에 영향을 줬을 것

• FT-PTM일땐 충분한 하락을 보임

  • 그림으로 보면 다음과 같음

    

Aspects-sentiment Distance

Aspect와 sentiment word 사이의 평균 거리를 의미

• C는 pre-define sentiment words set
  • Amazon-2
• S는 dataset, S_i는 sentence, S_i는 w들로 구성되어 있음
• |.|은 set의 원소 갯수

• FTM-PTM의 거리가 가장 짧다

첫 표의 "Dep" 결과를 볼 때 Twitter만 결과가 조금 다른데, 이는 Twitter가 문법을 중시하지 않기 때문에 그럼

Q2에 대한 답을 해보자면 PNC가 줄었기 때문에 긴 연결이 생겼지만 AsD를 보면 그 거리가 짧기 때문에 문제가 없다.

따라서 FT-PTM은 ALSC task에 적합하며 성능도 더 좋다.

5.3 Comparision between ALSC models

• MLP와 RoBERTa를 사용했어도 SOTA에 근접한 성능을 나타낸다.
• FT-RoBERTa는 Glove 기반의 모델에 효과적이며, RoBERTa와 결합하는 것은 큰 효과는 없다. 오히려 감소한 케이스가 있을 정도
• RoBERTa 기반 ALSC 모델을 최적화하는 것은 어려움

6. Conclusion

• parser-provided dependency tree와 PTMs 기반 tree를 포함한 여러 트리들을 비교함
• 특히 Perturbed Masking을 사용한 PTM 방법이 가장 성능이 좋았음
• Glove 기반 모델에 더 좋은 성능 향상을 보이며, RoBERTa+MLP로만 사용해도 성능이 좋다.

문제:

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력:

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

풀이방법:

이 문제는 다른 방법을 사용하면 쉽게 풀 수 있겠지만, 트라이 자료구조를 활용해서 풀어보았다. 생각보다 시간제한이 어려웠던 문제라서 최대한 시간을 줄이고자, Node를 정의해서 풀었던 다른 문제들과는 달리 하나의 class만으로 해결해보도록 구성해보았다.

class Trie(object):
    @classmethod
    def __init__(self):
        self.root = {}
        self.terminate = 'eof'
        
    @classmethod
    def insert(self, string):
        currNode = self.root
        for chr_ in string:
            if chr_ not in currNode:
                currNode[chr_] = {}
            currNode = currNode[chr_]
        currNode[self.terminate] = string
        
    @classmethod
    def search(self,string):
        currNode = self.root
        for chr_ in string:
            if chr_ in currNode:
                currNode = currNode[chr_]
            else:
                return False
        if 'eof' in currNode.keys():
            return True
        else:
            return False

n, m = map(int,input().split())
T = Trie()
for _ in range(n):
    T.insert(input())
answer = 0
for _ in range(m):
    if T.search(input()):
        answer+=1
        
print(answer)

문제링크:

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

문제:

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력:

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력:

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

풀이방법:

문자열 알고리즘 중 효율성이 가장 좋은 트라이(Trie) 알고리즘을 사용해서 입력받는 문자열을 정리하고, 별도의 탐색없이 지정된 출력형식으로 출력하면 되기 때문에, 재귀를 사용해서 문제에서 요구하는 방식대로 출력하도록 한다.

class Node(object):
    def __init__(self,name,flag=False):
        self.parent = name
        self.terminate = flag
        self.child = {}
        
    def __str__(self):
        return self.parent
        
class Trie(object):
    @classmethod
    def __init__(self):
        self.root = Node(None)
        
    @classmethod
    def insert(self, food):
        currNode = self.root
        for f in food:
            if f not in currNode.child:
                currNode.child[f] = Node(f)
            currNode.terminate = False
            currNode = currNode.child[f]
        currNode.terminate = True
        
    @staticmethod
    def antPrint(curNode,count):
        currList = sorted(list(curNode.child))
        for curr in currList:
            print("-"*count*2,end='')
            print(curNode.child[curr])
            Trie.antPrint(curNode.child[curr],count+1)

n = int(input())
T = Trie()
for _ in range(n):
    list_ = input().split()
    m, foods = list_[0], list_[1:]
    Trie.insert(foods)
Trie.antPrint(Trie.root,0)

문제링크:

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

High-Dimensional Bayesian Optimization with Multi-Task Learning for RocksDB

• RocksDB는 general-purpose embedded key-value store를 사용
• 본 논문에서는 10개의 파라미터를 다양한 범위로 auto-tuning해서 Throughput을 개선한다.
• 보통 optimizer들은 고차원 문제와 많은 training sample 요구를 한다.
• 이 문제를 해결하기 위해 multi-task modeling과 clustering을 통한 차원 감소를 진행한다.
  • 일반적으로 최적화하는 것은 수렴 속도가 빠른 것과 다른 tuner들이 찾기 못하는 복잡한 세팅을 찾으려는 것이 목적
    • but, 계산량이 많아
    • 그래서 사전지식과 Bayesian Optimization loop를 사용해서 throughput을 최대화 하는 파라미터를 찾는다.

1. Introduction

• RocksDB를 튜닝하는 것의 문제점
  • RocksDB는 30개가 넘는 파라미터를 가지고 있어서 configuration 조합들은 사용자에게 너무 많다
  • 하드웨어는 사용자가 선택한 configuration에 큰 영향을 준다.
  • 각 Application은 독특한 접근 패턴을 가지고 있다.
• Auto-tuning으로 이러한 문제를 해결하려 함
  • 하지만 많은 training sample이 필요한데 이 training sample들은 restart and execution을 해야 함
  • 따라서 굉장히 효율적인 Bayesian Optimization(BO)를 사용. Process는 아래 그림과 같음

• BO의 단점으로는 curse of dimensionality 때문에 고차원에서는 사용하기 어렵고, 계산량이 비싸다는 것이 단점이다.

  • 따라서 전문가의 지식을 추가해서 이 문제를 해소하고자 한다.
  • multiple target을 통한 최적화, sub-task decomposition을 통해 고차원 문제를 줄일 수 있다.

• multiple target 통해 최적화 하는 것은 다양한 내부 component에 성능을 영향을 받기 때문에 이득이 있음

  • 예를 들어 RocksDB에서는 write throughput은 IO stalls에 bottleneck이 있지만 지연시간을 줄여서 향상 가능

• 하지만 target을 늘리는 것은 계산량을 증가시키기 때문에 decomposition을 사용하도록 한다.

  • 모든 파라미터들을 한번에 다 고려하는 것이 아닌 일부 subset으로 decompose하고 target을 최적화함

    

• 기여도는 다음과 같다.

  • BO에 structural knowledge를 주입해서 수렴속도를 낮춤
  • manual task decomposition을 사용해서 차원 문제를 해결함
  • default보다 최대 1.45배 향상시킴

2. Background

2.2 Bayesian optimization

• Black-box function 최적화 문제를 해결하려는 효율적인 최적화 framework
• 미지의 목적 함수(Surrogate Model)을 만들고 평가를 통해 최적의 하이퍼파라미터 조합을 탐색하는 것.
  • 즉 확률적인 추정을 수행하는 모델
  • 이 함수로 GP, Additive Kernel, TPE, RF를 사용하도록 한다.
• Acquisition Function은 확률적 추정 결과를 바탕으로 유용한 다음 입력값 후보를 추천해 주는 함수를 지칭

3. Structured multi-task optimization

3.1 Overview

• 메커니즘을 통해 전문가의 지식을 model에 넣고, 사용하들은 main objective를 최적화할 수 있는 low-level metrics를 확인할 수 있다.
• multi-task learning을 통해 system component 간의 상호작용을 알 수 있고, 샘플에서 더 많을 것을 배워서 수렴에 필요한 관찰을 줄일 수 있다.
• 파라미터의 manual grouping을 통해 최대 차원을 줄였고 수렴 속도를 빠르게 했다.

3.2 Problem space and assumptions

• GP를 사용할 때, multivariate Gaussian distribution이고, 모든 점에서 미분 가능하다.

• modeling space에서 랜덤하게 선택된 500개의 독립된 실험을 수행

• 그 결과는 아래 그래프와 같음

  

3.3 Multi-task learning

3.3.1 Tasks

• RocksDB 구조의 이해를 바탕으로 3개의 추가적인 objective를 선정함.
• 이 objective들은 직접적으로 혹은 간접적으로 IOPS에 영향을 준다.
• 선정한 3개는 다음과 같다.
  • WriteAmplification
  • ReadBlockGetP99
  • Level0Tolevel1P99

3.3.2 Intrinsic coregionalization model

• 이 3가지 task를 더함에 따라 GP의 kernel 함수를 변경해야 한다.

  • Intrinsic Coregionalization Model kernel을 사용한다.

    

    • k_x은 covariance kernel, k_T는 task similarity kernel을 의미한다.
      • 따라서 서로 연관성을 파악하기 좋음
    • 각 output은 BO loop에서 최적화된다.

  • task간의 지식을 공유하는 능력과 각 task 별 충분한 sample이 있으면 수렴 속도를 빠르게 할 수 있다.

• 수행하는 알고리즘은 다음과 같다.

• scaling하고 normalizing 한다.
  • 이 것이 분포를 smooth하게 해서 더 쉽게 할 수 있도록 함

3.3.3 ICM challenges

• ICM이 뭘 제공하긴 하는데 모르겠고, 이는 확장성에 문제가 있다고 함
  • 일반적으로 GP는 O(n³)인데, task가 생기면 O(Tn³)임
  • 그래서 Decomposition이 필요하다.

3.4 Decomposability through clustering

3.4.1 Decomposability in RocksDB

• RocksDB의 large parameter space는 *"차원의 저주"* 와 높은 계산량을 발생시킨다.
  • multi-task 방법을 사용하면 계산량을 증가시켜서 차원의 저주 문제를 일부 해소 시킨다.
• 계산량 문제를 줄이기 위해 RocksDB의 구조를 이용한다.
  • final observed metric = sum of multiple internal components performance. (functional decomposability)
  • 이는 차원을 줄이는 역할도 수행할 수 있다.

3.4.2 Manual clustering

• 복잡도는 차원과 연관있기 때문에 이를 줄이도록 하자.
• 500개의 random configuration trace를 이용하여, IOPS와 517 observable metric간의 correlation과 파라미터간의 correlation을 계산한다.
  • 이를 통해 cluster pool을 30개로 줄였고, 그 중 전문가 지식과 독립된 실험을 통해서 그림의 구조에 도달할 수 있었다.
• parameter space를 decompose했고, 각 parameter cluster에 독립적인 GP를 사용했음
  • ICM Kernel을 사용한 GP로 지식을 공유하도록 했음

3.4.3 Unsupervised clustering

• unsupervised clustering을 적용해서 이러한 cluster를 찾는다.
• pass

4. Evaluation

4.1 Setup

• IOPS를 최대화 하기 위해 10개의 RocksDB 파라미터를 튜닝한다.
• parameter의 범위는 다음 표와 같다.

4.1.1 Experiment goals

• tuner가 수렴 속도가 빠르고, IO throughput을 잘 하는 것이 중요하다.
• Decomposability를 이용하는 cluster 기반의 multi-task의 효율성을 강조할 것이다.

4.1.2 Benchmark

생략

4.1.3 Libraries

생략

4.1.4 Hardware

생략

4.1.5 Baselines

4.2 IOPS performance

• 제한된 계산량으로 IOPS를 최대화 하고 싶기 때문에 100개의 최적화 step만을 부여한다.

• MultiTask를 사용할 때 1.38 ± 0.06 만큼의 성능 향상을 보였다.

4.3 Convergence

• Multi-task와 cluster multi-task가 좀 더 빠르게 찾아냈다.
• clustered MT는 10개의 iteration만에 1.3배의 향상을 보이는 config를 찾았다.(non-cluster-based는 60개의 iter가 걸림)
  • 대신 60 iter 후에는 더 좋은 것들을 찾을 수 있었지만 unstable 함
• 일반 GP보다는 GP(BoTorch)가 더 좋음

5. Related work

pass

6. Conclusion

• 이전에 tuning하는 과정은 고차원이라는 것이 문제였음.
• 따라서 alternative observable metrics와 structural decomposability를 이용해서 수렴 속도를 빠르게 하고, 고차원을 줄임

문제:

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력:

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

풀이방법:

 각 학생들이 작성한 예상 등수를 바탕으로 정렬을 하고, 그와 동일하게 순위를 부여하는 것이 가장 사람들의 불만도를 최소로 하는 방법이다.

문제링크:

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