요즘 프롬프트에 관심이 생겼고 이 논문이 관심이 가게 되어서 리뷰를 하게 되었다.

ProQA: Structural Prompt-based Pre-training for Unified Question Answering
https://aclanthology.org/2022.naacl-main.313/

Introduction

질의응답(QA, Question Answering)은 NLP 연구에서 오랫동안 영감을 주는 도전과제로 여겨져 왔다. 최근 연구에서 모델은 특정 질문 유형(Extractive QA, Abstractive QA, Multiple-Choice QA)이나 특정 분야(NewsQA, NaturalQA)에 초점에 맞춰져 있다. 

최근 LLM에 대한 연구는 다양한 Task에 대해 연결성이 있을 수 있음을 시사하며 이 논문에서는 Task 간의 연결성을 모델링하기 위해 다양한 QA Task를 하나의 모델에서 해결할 수 있는 통합 패러다임인 ProQA를 제시한다.

ProQA : 두 가지를 모델링할 수 있다.

• 일반적으로 요구되는 QA 능력
• 동일한 패러다임에서 여러 QA Task 간 공통성과 차이점 모델링

2가지 모델링을 위해 2가지 문제를 직면한다.

• 다양한 Domain/Format 에서 QA task 간 공통점을 모델링하고 전이성을 강화하며 충돌을 피하는 방법
• Pre-training을 위한 High-Quality QA Data의 부족에 대해 Large-scale QA Corpus 생성 방법

→ 두 가지 문제를 해결하기 위해 Structural prompt, Structural prompt-based pre-training와 대규모 합성 QA 코퍼스 구축을 통해 ProQA : 통합 QA 패러다임을 구상한다.

AboutQA

논문에서는 UnifiedQA와 T5(Text-to-Text Transfer-Transformer의 영감을 받아, Downstream QA Task에서 통합 Text-to-Text 모델을 사용합니다. 이 작업에서는 T5 모델을 백본으로 사용합니다.

위의 그림을 보게되면, 다양한 QA 작업을 위해 통합된 Structural prompt로 구성됩니다. 또한, QA 능력과 Structural prompt의 의미와 Task 간의 공통점과 차이점을 학습하기 위해 Structural prompt-based pre-training을 진행합니다.

Structural Prompt

위의 Structural Prompt는 여러 개의 { Key : Value }로 구성됩니다. 

• KEY
  • Key indicator : [ ]
    • 구성 요소간의 기능적 차이를 구별하여 모델을 강화하기 위해, 각 키를 학습 가능한 표현을 가진 특별한 Key indicator을 사용합니다.
    • e.g., $Task, Format, Question,\space etc.$
• Value : 두 가지로 표현합니다.
  • textual content of the data instance (데이터 인스턴스의 텍스트 내용)
    • e.g., $question,\space passage,\space options$
  • the combination of a discrete $hard\space prompt$ and $soft\space prompts$
    • Hard prompt (< >) : 미리 정의된 이산적인 설명 (특수 토큰을 사용)
      • e.g,. Extrative QA, Abstractive QA와 같이 첫 번째 그림의 여러 요소들 
    • Soft prompt (Grey squares) : 학습 가능하고 플러그 앤 플레이가 가능한 연속 임베딩
      • 여러 Task/Domain/Format의 차이를 모델링하기 위해, Customized characteristics를 나타내는 학습 가능하고 저장 가능한 Soft prompt를 사용

Structural Prompt = { (Key indicator : Hard Prompt or Soft Prompt) * $k$ } 

Key Indicator : 구성 요소 간의 기능적 차이를 구별하는 데 사용

Hard Prompt : Task를 구별하는 역할

Soft Prompt : 여러 Task/Domain/Format간 차이와 공통점등을 모델링할 때 사용하며 이 Soft prompt는 학습가능하며 저장 가능하다.

입력 표현

구조적 프롬프트 형식의 인스턴스가 주어지면, 모델 입력으로 변환한다.

$k$번째 키를 $key\space indicator\space D_k$로 변환하고, 특정 값의 토큰 $V_k$에 의해 토큰 시퀀스를 형성하며, $E_k\space = \space Embedding([D_k;V_k])$로 표현한다. $D_k$의 표현은 훈련 중에 초기화되고 업데이트됩니다.

소프트 프롬프트인 Task/Format/Domain를 값으로 $P_{task}/P_{format}/P_{domain}$를 사용하고 편의를 위해 먼저 추가하고 모든 $E_k$를 연결하여 입력 $X$를 만든다.

$X = [P_{domain};P_{format};P_{task};E_1;...;E_k]$

Key indicator D와 Soft prompt P는 Pre-training 중에 공동으로 훈련되며, Structrual prompt의 의미를 학습한다. 다양한 작업에 조정된 후, Soft prompt P는 customized 작업별 특성을 기록하기 위해 저장될 수 있다.

Structural Prompt-based pre-training

Task Formulation

이 부분에서는 모델이 Pre-training 중에 요구되는 QA 능력과 Structrual prompt의 의미를 학습하는데 도움이 되는 Structural prompt-based pre-training이 수행되는 방법에 대해 소개합니다.

Pre-training을 위한 다양한 QA 유형(i.e., $Extractive\space QA,\space Abstractive\space QA,\space Multiple-choice QA$)을 제시하며, QA 능력을 주입한다. Multi-format QA corpus가 주어지면, 제안된 Structural prompt에 따라 QA 형식으로 변환하여, 형식 간의 차이를 유지하면서 공동으로 Pre-training을 가능하게 합니다.

→ Structural prompt로 Instance를 형식화해 입력으로 바꾼 뒤, 자유 형식의 답변을 출력하여 작업은 QA 작업으로 더 맞춤화됩니다.

Pre-training Corpus Construction

Pre-training을 위한 QA Corpus는 2가지 이유로 데이터 부족이 심각합니다.

1. Pre-training을 위한 고품질 주석이 달린 데이터는 비현실적이며 번거롭습니다.
2. 규칙 기반(token masking or sentence reordering)을 사용해 QA 중심 self-supervised 데이터 생성은 어렵습니다.

이 작업에서 Generation-filtering based corpus construction method를 채택하여 600M개의 본문을 포함한 Large-scale unlabeled Wikipedia corpus를 기반으로 Corpus를 합성합니다.

과정은 다음과 같다.

1. QA 쌍 생성 모델 $g_{qa}(q,a|c)$ : 본문 $c$ 를 입력으로 사용할 때, $g_{qa}(q, a|c)$는 질문 q와 그 답변 $a$를 포함하는 출력 시퀀스 $q$ [SEP] $a$를 생성한다.
2. 생성된 QA 쌍을 필터링하여 질문과 답변의 품질과 일관성을 보장하기 위한 필터링 QA 언어 모델 f(a|q, c)는 조건부 확률 기반 접근 방식을 사용하여 QA 쌍을 부드럽게 필터링합니다. 이는 본문 c c와 질문 q에 대한 답변 a의 가능성으로 QA 쌍 (q, a)을 평가합니다. 점수가 임계값보다 높은 QA 쌍은 사전 훈련을 위해 보존됩니다.

Experimental Setup

실험에서는 세 가지 형태의 QA Dataset을 고려합니다. Extractive QA, Abstractive QA, MultiChoice QA

11개의 Dataset은 3가지 형식과 다양한 언어 이해 능력을 갖고 있습니다.

Results and Analyses

Main Results

• QA 중심 사전 훈련 모델인 UnifiedQA와 ProQA는 시드 데이터셋과 비시드 데이터셋 모두에서 T5를 큰 차이로 능가한다. 다양한 QA 작업 간 전이 가능한 지식이 있기 때문입니다.
• ProQA는 UnifiedQA보다 Few-Shot 및 Zero-Shot에서 UnifiedQA를 큰 차이로 이깁니다.
  1. Structural prompt 내의 hard prompt와 soft prompt가 QA 작업에 대해 지시 Customization을 가능하게 하며 특히 “Task”의 key-value쌍이 중요합니다.
  2. Structural prompt-based pre-training은 비시드 데이터에 더 빠르고 잘 적응할 수 있도록 도와줍니다.
• proQA(qapair)과 ProQA(paq)에서 paq가 우수한 성능을 보인다. 이 방식으로 데이터 생성을 하려면 네 개의 BERT 모델이 준비되어야 하지만, 논문에서의 qapair은 단순하며 모델을 하나를 사용하며 3개의 QA Corpus 추출에 적용할 수 있습니다.

Ablation Study

각 구성 요소의 효과를 밝히기 위한 소거 연구가 수행되었습니다. 총 3가지 변형을 고려했습니다.

1. Soft prompt를 제거한 ProQA
2. 추가적으로 pre-training을 제거한 ProQA
3. UnifiedQA + Pre-trained Corpus는 논문에서 준비한 합성 QA 코퍼스로 Pre-trained 모델

3가지를 통해 모델에서 Soft prompt를 제거하면 Pre-training도중에 학습된 작업별 지식이 비활성화된다는 것입니다. Prompt-based pre-training을 제거하면, 성능이 크게 떨어지며 동등한 모델인 (T5 + hard structural prompt)에는 어떠한 QA 지식도 없기 때문입니다.

→ UnifiedQA + Pre-train Corpus는 ProQA보다 낮은 성능을 나타내며, 논문에서 제시한 Structral prompt가 지식 Generation와 지식 Customization 사이의 더 나은 균형을 보여줍니다.

출처

ProQA : https://aclanthology.org/2022.naacl-main.313/

UnifiedQA : https://arxiv.org/abs/2005.00700

T5 : https://arxiv.org/abs/1910.10683

결론부터 말하자면 Python의 round함수는 오사오입을 사용한다.

사사오입과 오사오입은 숫자를 반올림하는 두 가지 방법이다. 이들은 소수점 이하의 숫자를 처리할 때 사용되며, 각각의 방식은 두 가지이다.

사사오입(Round Half Up)이란?

5 이상에서 올리고, 5 미만은 버리는 것이 우리가 알고 있는 반올림 방식인 사사오입이며 Round Half Up이라고 한다.

일반적으로 알고 있는 반올림이다. 소수점 0부터 5까지는 파이썬의 floor 함수를 사용하는 것과 같고, 소수점이 5를 초과할 때부터는 파이썬의 ceil 함수와 동일하다.

그림으로 표현하면 다음과 같으며, 프로그램 실행 시 다음과 같이 결과가 나온다.

혹시 코드가 필요한 사람이 있을 수 있으므로 코드도 첨부하겠다.

from math import floor, ceil

def custom_round(num):
    if num % 1 >= 0.5:
        return int(ceil(num))
    else:
        return int(floor(num))

for i in range(-4,4):
    print(f"{i+0.5} 반올림 : {custom_round(i+0.5)}")

오사오입(Round Half to Even / Banker's Rounding) 이란?

그렇다면 사사오입이 아닌 오사오입은 무엇일까? 

이 방법은 반올림할 숫자가 정확히 반 (즉,.5) 일 때 가장 가까운 짝수로 반올림하는 방식이다. 예를 들어 2.5는 2, 3.5는 4로 반올림된다.

숫자의 소수점이 .5 일 때 반올림을 하게 되면 가장 가까운 짝수로 출력되는 것을 볼 수 있다.

그래서 왜 사용하는데?

사용하는 이유

주된 목적은 반올림 과정에서 발생하는 오류를 최소화하기 위해서 사용한다. 

사사오입 방식

• 3.5는 4로 반올림 
• 4.5는 5로 반올림 
• 5.5는 6으로 반올림 
• 6.5는 7로 반올림 
• 평균 반올림 값 = (4 + 5 + 6 + 7) / 4 = 5.5
• 실제 평균 = 5.0

실제 평균과 사사오입 평균이 0.5가 차이 나는 것을 볼 수 있다.

오사오입 방식

• 3.5는 4로 반올림 (4는 짝수) 
• 4.5는 4로 반올림 (4는 짝수) 
• 5.5는 6으로 반올림 (6은 짝수) 
• 6.5는 6로 반올림 (6은 짝수) 
• 평균 반올림 값 = (4 + 4 + 6 + 6) / 4 = 5.0
• 실제 평균 = 5.0

실제 평균과 오사오입의 평균의 오차가 줄어든 것을 볼 수 있다.

위의 예시를 통해 반올림으로 발생하는 총합의 증가나 감소가 장기적으로 상쇄되어, 데이터 셋의 평균값이 실제 값에 더 가깝게 유지되기 때문에 파이썬의 round 함수는 오사오입 방식을 사용한다.

이 방식을 알게 된 이유는 백준문제이다.

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

그리고 이 문제와 관련된 해설은 다음 글에서 확인할 수 있다.

https://giliit.tistory.com/79

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

문제

solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다.

ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.

• 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
• 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.

절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.

제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.

마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 입력을 모두 배열에 추가한다.

2. 배열을 정렬한다.

3. 범위를 지정하여 합을 구한다.

4. 합을 범위의 길이만큼으로 나눈다.

5.값을 정수형으로 출력한다.

* 여기서 파이썬의 round 함수의 오사오입과 사사오입 문제를 이해하고 따로 함수를 만들어 해결해야 한다. 그 방식에 대해서는 밑의 글에서 설명했다.

https://giliit.tistory.com/80

코드

# silver
# solved.ac
# 절사평균 30 : 위 15%, 아래 15%

import sys
from math import ceil, floor

# 파이썬의 사사오입, 오사오입 해결위한 방법
def custom_round(num):
    if num % 1 >= 0.5:
        return int(ceil(num))
    else:
        return int(floor(num))

def main():
    n = int(input())
    lst = []
    # 배열 입력
    for _ in range(n):
        tmp = int(input())
        lst.append(tmp)

	# 상위 15%와 하위 15% 수치를 구한다.
    k = int(custom_round(n * 0.15))
    
    # 배열을 정렬한다.
    lst.sort()
	
    # 0인 경우, 0 출력, 0이 아닌 경우, 값을 출력한다.
    if n == 0:
        print(0)
    else:
        print(int(custom_round(sum(lst[k:n-k])/(n-2*k))))



if __name__ == "__main__":
    input = sys.stdin.readline
    main()

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

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

출력

풀이방법

C++언에서 Substr을 이용해서 문자열을 slicing 한다. 이후에 set 자료구조를 이용해 중복을 제거하고 출련한다.

코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main()
{
  fastio;
  string str; cin>>str;

  set<string> sstr;

  for(int i=0;i<str.size();i++)
  {
    for(int j=1;j+i<=str.size();j++)
      sstr.insert(str.substr(i,j));
  }
  cout<<sstr.size();
}

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

문제

친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다.

바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. 힌트는 “확장자”야.

화가 났던 스브러스는 보물 이야기에 금세 화가 풀렸고 보물의 정보를 알아내려고 애썼다. 하지만 파일이 너무 많은 탓에 이내 포기했고 보물의 절반을 보상으로 파일의 정리를 요청해왔다. 스브러스의 요청은 다음과 같다.

• 파일을 확장자 별로 정리해서 몇 개씩 있는지 알려줘
• 보기 편하게 확장자들을 사전 순으로 정렬해 줘

그럼 보물의 절반을 얻어내기 위해 얼른 스브러스의 노트북 파일 정리를 해줄 프로그램을 만들자!

입력

출력

풀이방법

1. 파일을 파일이름과 파일 확장자로 나눈다.

2. 파일 확장자를 dictionary를 사용해 처음 나오는 확장자라면 value = 1을, 이전에 나온 확장자라면 value = value + 1

ex) 

3. 확장자(key)의 값들을 정렬한다.

4. 정렬된 확장자들을 차례대로 출력하면서 value값도 출력한다.

코드

# silver
# 파일 정리

import sys

def main():
    n = int(input())
    file = dict()
    
    # 파일이름과 파일 확장자로 나누는 코드
    for _ in range(n):
        file_name, file_extension = input().rstrip().split('.')
        
        # 처음나오는 확장자라면 dict에 추가
        if file_extension not in file:
            file[file_extension] = 1
        # 이전에 나온 확장자라면 dict에서 + 1을 한다.
        else:
            file[file_extension] += 1
    
    # key들을 정렬한다.
    file_extension_lst = sorted(file.keys())
    
    # key와 value들을 차례대로 출력한다.
    for i in file_extension_lst:
        print(f'{i} {file[i]}\n')

if __name__ == '__main__':
    input = sys.stdin.readline
    print = sys.stdout.write
    main()

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

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 듣도 못한 사람을 set에 추가한다.

2. 보도 못한 사람이 set에 있다면 KK 에 추가한다.

3. KK라는 요소들을 출력한다.

코드

#include<bits/stdc++.h>
using namespace std;


int main()
{
  int a,b;
  cin>>a>>b;
  set <string> K;
  
  // 듣도 못한 사람을 추가한다.
  while(a--)
  {
    string temp;  cin>>temp;
    K.insert(temp);
  }
  set<string> KK;
  // 보도 못한 사람이 듣도 못한 사람에 있다면 KK에 추가한다.
  while(b--)
  {
    string temp; cin>>temp;
    if(K.count(temp)) KK.insert(temp);
  }

  // 듣도 보도 못한 사람을 출력한다.
  cout<<KK.size()<<"\n";
  for(auto k : KK)
  {
    cout<<k<<"\n";
  }

}

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

문제

79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다.

문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다.

입력

출력

풀이방법

1. N to M의 숫자를 문자로 변환하여 arr에 추가한다.

2. arr의 문자들을 알파벳 숫서대로 정렬한다.

3. 정렬한 arr의 문자들을 숫자로 변환한다.

4. 양식에 맞게 10개 출력 후 줄바꿈을 한다.

코드

# silver
# 숫자놀이

import sys

def main():
    num = ['zero ', 'one ', 'two ', 'three ', 'four ', 'five ', 'six ', 'seven ', 'eight ', 'nine ']
    num_dict = {'zero': '0','one':'1', 'two':'2','three':'3' , 'four':'4', 'five' : '5', 'six' : '6', 'seven': '7', 'eight' : '8', 'nine' : '9'}
    arr = []
    n, m = map(int, input().rstrip().split())
    
    # 숫자 -> 문자 변환
    for i in range(n,m+1):
        i_lst = list(str(i))
        i_str = ""
        for j in range(len(i_lst)):
            i_str += num[int(i_lst[j])]
        arr.append(i_str)
    
    # 문자 정렬
    arr.sort()

	# 문자 -> 숫자 변환 및 출력
    for i in range(len(arr)):
        a = arr[i].split()
        tmp = ''
        for k in a:
            tmp += num_dict[k]
        print(tmp+" ",end='')
        
        # 10개 출력 후 줄 바꿈
        if i % 10 == 9:
            print()


if __name__ == '__main__':
    main()

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

문제

두 단어 A와 B가 주어졌을 때, A에 속하는 알파벳의 순서를 바꾸어서 B를 만들 수 있다면, A와 B를 애너그램이라고 한다.

두 단어가 애너그램인지 아닌지 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

2개의 문장을 정렬한다.

2개의 문장이 동일하다면 애너그램이며, 동일하지 않으면 애너그램이 아니다.

코드

# bronze
# 애너그램

import sys

def main():

    n = int(input())
    for _ in range(n):
        a, b = map(list,input().rstrip().split())
        a_sorted = sorted(a)
        b_sorted = sorted(b)
		
        # 정렬한 문장이 동일하다면
        if a_sorted == b_sorted:
            print(f"{''.join(a)} & {''.join(b)} are anagrams.")
		
        # 정렬한 문장이 동일하지 않다면
        else:
            print(f"{''.join(a)} & {''.join(b)} are NOT anagrams.")

if __name__ == '__main__':
    input = sys.stdin.readline
    main()

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

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다.

$4^2+3^2+1^2$ 으로 표현할 수도 있다.

역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가

$15663=125^2+6^2+1^2+1^2$

라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다.

$11339=105^2+15^2+8^2+5^2$

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

출력

풀이방법

총 4가지 경우로 나뉜다.

1번째의 경우, 제곱수인 경우이다.

2번째인 경우, n = 제곱수 + 제곱수

3번째인 경우, n = 제곱수 + 제곱수 + 제곱수

4번째인 경우는 1, 2, 3번째 경우를 제외하고 이다. 

코드

import math

def main():
    n = int(input())
    squares = [i*i for i in range(1,224)]

    # 제곱 수가 있는 경우
    if n in squares:
        return 1

    for square in squares:
        if n-square  < 0:
            break
        if n-square in squares:
            return 2

    for square_1 in squares:
        if n-square_1 < 0:
            break
        for square_2 in squares:
            if n - (square_1 + square_2) < 0:
                break
            if n - (square_1 + square_2) in squares:
                return 3

    return 4

if __name__ == '__main__':
    print(main())