대학원생이 쉽게 설명해보기

Abstract

The dominant sequence transduction models are based on complex recurrent or convolutional neural networks that include an encoder and a decoder. The best performing models also connect the encoder and decoder through an attention mechanism. We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train. Our model achieves 28.4 BLEU on the WMT 2014 Englishto-German translation task, improving over the existing best results, including ensembles, by over 2 BLEU. On the WMT 2014 English-to-French translation task, our model establishes a new single-model state-of-the-art BLEU score of 41.0 after training for 3.5 days on eight GPUs, a small fraction of the training costs of the best models from the literature.

대표적인 문장 번역 모델들은 인코더와 디코더를 포함한 순환 또는 컨볼루션 신경망으로 구성된다.

가장 우수한 모델은 어텐션 메커니즘을 통해 인코더와 디코더를 연결한다.

우리는 순환 및 컨볼루션 신경망을 완전히 배제하고 어텐션 메커니즘을 사용하는 새로운 모델 아키텍쳐 Transformer를 제안한다.

두 가지 기계번역의 실험에서 제안한 모델은 우수한 성능과 병렬화가 가능하고, 학습 시간을 감소시킨다.

영어 -> 독일 28.4 2 BLEU는 앙상블을 포함하여 현존 최고의 성능이다.

영어 -> 프랑스어 작업에서는 8개의 GPU로 3.5일동안 학습시킨 결과 최고의 성능을 얻었다. 학습 비용 측면에서도 우수하다. 

요약

• self-attention은 연산량이 O(1)로 낮으며, 시퀀스의 모든 값들을 비교분석해볼 수 있다. 예를 들어, CNN 같은 경우는 필터의 크기만큼에 해당하는 값만 비교할 수 있었다.

• 논문에서는 CNN과 RNN을 사용하지 않고 오로지 어텐션만 사용하여 모델을 구성하였다. 위의 그림에서 N = 6이다.
• 어텐션은 대표적으로 Additive와 dot--product attention이 사용된다.

• dot-product 어텐션은 sparsity에 강하다. self-attention은 컨볼루션과 다르게 위치에 관한 정보를 가지지 않게 되는데, 이를 Multi-head 어텐션을 통해 보완해준다.

Reference

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., ... & Polosukhin, I. (2017). Attention is all you need. In Advances in neural information processing systems (pp. 5998-6008).

https://www.youtube.com/watch?v=6zGgVIlStXs&list=PLWKf9beHi3Tg50UoyTe6rIm20sVQOH1br&index=50

expression = input().split('-')
for_minimum_list = []

for exp in expression:
    splited = list(map(int, exp.split('+')))
    for_minimum_list.append(sum(splited))
    
sum_value = for_minimum_list[0]
for value in for_minimum_list[1:]:
    sum_value = sum_value - value
    
print(sum_value)

N = int(input())
time_list = list(map(int, input().split()))
time_list = sorted(time_list)
sum_value = time_list[0]

for i in range(1, N):
    sum_value = sum_value + sum(time_list[:i+1])
    
print(sum_value)

N = int(input())

meeting_list = [list(map(int, input().split())) for _ in range(N)]
# 파이썬에서 여러 조건으로 정렬하는 방법
meeting_list = sorted(meeting_list, key = lambda x:(x[1], x[0]))

max_meeting = 0
start = 0

for time in meeting_list:
    if(time[0] >= start):
        start = time[1]
        max_meeting += 1
        
print(max_meeting)

N, K = list(map(int, input().split()))
m_list = []
for _ in range(N):
    m_list.append(int(input()))
    
min_value = 0

for i in m_list[::-1]:
    if(i > K):
        continue
    else:     
        if((K % i) < K):
            min_value = min_value + (K // i)
            K = K % i
        
print(min_value)

N, K = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

weights = [ele[0] for ele in wv]
values = [ele[1] for ele in wv]

dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, K+1):
        w = weights[i-1]
        v = values[i-1]
        
        # 먼저, 가질 수 있는 무게보다 물건의 무게가 클 경우는
        # 가져갈 수 없으므로 이전에 구했던 최댓값을 선택한다.
        # 여기서 i-1이 이전에 구했던 것이고, j가 가질 수 있는 무게를 의미한다.
        if(j < w):
            dp[i][j] = dp[i-1][j]
        # 물건의 무게보다 가질 수 있는 무게가 더 작을 경우는
        # 해당 물건을 가져갈 수 있음을 의미한다.
        # 따라서 v + dp[i-1][j-w]
        # --> 현재 물건을 가져감(v)과 동시에
        # 이전에 미리 구해둔 해당 물건의 무게만큼을 제외했을 때의 최댓값과(dp[i-1][j-w])
        # 이전에 구했던 무게를 비교하여 선택한다.(안가져가는게 이득일 수도 있으니까)
        else:
            dp[i][j] = max(v + dp[i-1][j - w], dp[i-1][j])
print(dp[N][K])

from itertools import combinations

N = int(input())
ability_board = []
for _ in range(N):
    ability_board.append(list(map(int, input().split())))

num_list = [i for i in range(N)]
res = float('inf')

def solve():
    global res
    
    # 조합을 이용하여 각 후보자를 생성함
    for cand in combinations(num_list, N // 2):
        # 선택된 후보와 나머지
        start_member = list(cand)
        link_member = list(set(num_list) - set(cand))
        
        # 점수 비교는 2명씩 이루어진다.
        start_comb = list(combinations(start_member, 2))
        link_comb = list(combinations(link_member, 2))
        
        # 점수 구하기
        start_sum = 0
        for x, y in start_comb:
            start_sum += (ability_board[x][y] + ability_board[y][x])
            
        link_sum = 0
        for x, y in link_comb:
            link_sum += (ability_board[x][y] + ability_board[y][x])
        
        # 차이를 구하는 것이므로 abs 사용
        if(res > abs(start_sum - link_sum)):
            res = abs(start_sum - link_sum)
            
solve()
print(res)

1, 2 번째 예제가 맞았는데 3번째 예제가 틀리다면 나눗셈 부분을 잘 처리해주었는지 확인해보세요.

c = int(input())
num_list = list(map(int, input().split()))
calc_list = list(map(int, input().split()))

def make_calc_dict(calc_list):
    calc_dict = dict()
    for i, c in enumerate(calc_list):
        calc_dict[i] = c
        
    return calc_dict

def calc(init_num, num, calc_num):
    if(calc_num == 0):
        return init_num + num
    elif(calc_num == 1):
        return init_num - num
    elif(calc_num == 2):
        return init_num * num
    elif(calc_num == 3):
        if(init_num < 0):
            return -(-init_num // num)
        else:
            return init_num // num
    
calc_dict = make_calc_dict(calc_list)

result_list = []
def solve(num_list, calc_dict):
    print(num_list, calc_dict)
    if(len(num_list) == 1):
        print('end')
        result_list.append(num_list[0])
        return 0
    else:
        # 계산에 사용 될 수
        init_num = num_list.pop(0)
        temp_num = num_list[0]
        
        # 백트래킹
        for key, value in calc_dict.items():
            # 0이면 다음 경우로
            if(value == 0):
                continue
            else:
                # 해당 계산을 수행
                num = calc(init_num, temp_num, key)
                calc_dict[key] = calc_dict[key] - 1
                
                if(len(num_list) == 0):
                    deliver_list = [num]
                else:
                    deliver_list = [num] + num_list[1:]
                solve(deliver_list, calc_dict)
                calc_dict[key] = calc_dict[key] + 1

solve(num_list, calc_dict)
print(max(result_list))
print(min(result_list))

python3 불통과, pypy3 통과

# sdk = [[0, 3, 5, 4, 6, 9, 2, 7, 8],
#             [7, 8, 2, 1, 0, 5, 6, 0, 9],
#             [0, 6, 0, 2, 7, 8, 1, 3, 5],
#             [3, 2, 1, 0, 4, 6, 8, 9, 7],
#             [8, 0, 4, 9, 1, 3, 5, 0, 6],
#             [5, 9, 6, 8, 2, 0, 4, 1, 3],
#             [9, 1, 7, 6, 5, 2, 0, 8, 0],
#             [6, 0, 3, 7, 0, 1, 9, 5, 2],
#             [2, 5, 8, 3, 9, 4, 7, 6, 0]]

import sys

sdk = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sdk[i][j] == 0]

def sdoku(index):
    
    # 한 바퀴에서 모든 경우를 다 보았으면 출력
    if index == len(zeros):
        for row in sdk:
            print(*row)
        sys.exit(0)
    else:
        x = zeros[index][0]
        y = zeros[index][1]
        dx = (x//3) * 3
        dy = (y//3) * 3

        # 사용할 수 있는 숫자 9개
        num_list = [False] + [True for _ in range(9)]

        for j in range(9):
            # 가로 검사
            # 세로 검사
            if(sdk[x][j]):
                num_list[sdk[x][j]] = False       
            if(sdk[j][y]):
                num_list[sdk[j][y]] = False

        # 3*3 box 검사
        for i in range(dx, dx + 3):
            for j in range(dy, dy + 3):
                check_num = sdk[i][j]
                if(check_num):
                    num_list[check_num] = False

        # 현재 가능한 수만 가져옴
        # 가능한 수를 가져왔으면, 이전에 다뤄왔던 백트래킹을 사용하면 됨
        candidate_list = [i for i, k in enumerate(num_list) if k]
        
        # 경우의 수 고려
        for num in candidate_list:
            sdk[x][y] = num
            sdoku(index + 1)
            sdk[x][y] = 0
sdoku(0)

파이썬을 통한 모든 코드 시간 초과. 해당 코드를 자바로 바꿔서 제출했음. 확실히 타언어에 비해 수십배 느리단걸 다시 한번 느낌.

밑 코드 말고도 다른 유형으로 해보았지만 안됨. 파이썬 코드로 하지말고 애초부터 java나 C로 하는걸 추천. 빨리 풀고 다음 문제로 넘어가세요....

N = int(input())

res = 0
chess = [0] * N

def nqueen(cnt):
    global res
    
    if(cnt == N):
        res += 1
        return 0
    else:
        for i in range(N):
            chess[cnt] = i
            check = True
            for j in range(cnt):
                # 같은 열에 있는가
                if(chess[cnt] == chess[j]):
                    check = False
                # 대각의 관계에 있을 경우, 
                # 행의 거리와 열의 거리가 같다.
                if(abs(chess[cnt] - chess[j]) == cnt - j):
                    check = False
            
            if(check):
                nqueen(cnt + 1)
nqueen(0)
print(res)

단순히 위 코드를 변경한 자바 코드도 첨부합니다.

import java.util.Scanner;
 
public class Main {
    public static int N;
    public static int res;
    public static int[] chess;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        chess = new int[N];
        
        nqueen(0);
        
        System.out.println(res);
    }
    
    public static void nqueen(int cnt){
        if(cnt == N){
            res++;
        } else{
            for(int i = 0; i < N; i++){
                chess[cnt] = i;
                boolean check = true;
                
                for(int j = 0; j < cnt; j++){
                    if(chess[cnt] == chess[j]){
                        check = false;
                    }
                    if(Math.abs(chess[cnt] - chess[j]) == cnt - j){
                        check = false;
                    }
                }
                if(check){
                nqueen(cnt + 1);
                }
            }
        }
    }
}