Exploring the Competency of ChatGPT in Solving Competitive Programming Challanges

논문 링크

International Journal

Received Date : December 20, 2023
Accepted Date: January 21, 2024
Published Date: February 06, 2024

Abstract

ChatGPT의 각 난이도 수준에서의 문제 해결 성능을 확인하였다.
쉬운 문제는 89%, 중간 문제는 68%, 어려운 문제는 41%, 총 66%의 해결률을 보였다.
사람 참가자의 경우 평균 52.95%의 해결률로 인해 ChatGPT가 Competitive programming 능력이 평균적인 인간보다 뛰어남을 확인하였고 본 연구로 Prompt의 효과성을 입증하여 AI의 한계를 강조하고, 추가 개선이 필요한 영역을 식별하였다고 한다.

1. Introduction

다양한 분야에서 ChatGPT는 인간을 지원할 수 있어 AI에 대한 수요가 증가하였다.
하지만 컴퓨터 과학, 소프트웨어 공학, 정보 통신 기술 및 관련 과목의 학생들이 종종 학업 프로젝트와 과제를 해결하기 위해 ChatGPT를 활용하고 있어 학계에서 이 도구의 잠재적 위험에 대한 질문이 제기되고 있다.

ChatGPT의 성능을 이용하기 위해 ChatGPT가 일반적인 학문적 과제에 일관적이고 정확하게 대응하는 지 확인하기 위해 ChatGPT가 Competitive programming 문제를 해결하는 것으로 성능을 평가한다.

2장은 ChatGPT와 그 발전에 대한 개요, 3장에는 기존 문헌의 관련 연구, 4장에선 연구의 방법론, 5장에서 연구 결과, 6장에선 연구의 잠재적인 타당성 위협, 7장에서 연구를 마무리한다.

2. ChatGPT and its Evolution

현재 중요하지 않아 정리하지 않는다.

3. Related Works

Minnesota 대학교의 Law school에서 ChatGPT Model이 인간 개입 없이 법학 시험 질문에 대한 답변을 생성하는 능력을 평가하기 위한 연구가 수행하였고 총 네개의 과목 모두 성공적으로 합격하여 평균 C+를 받았다.

ChatGPT의 다지선다형 질문(Multiple-Choice Question, MCQ) 기반 시험 성능을 평가하였다.
고등 교육의 다양한 과목에 대한 평가를 진행하였는데 ChatGPT의 무료 버전(GPT-3/3.5)에서는 무작위 추측보다 나은 결과이나 시험 결과가 좋지 못하였으나(평균적인 학생들보다 성취가 낮음) GPT-4는 상당한 개선으로 인해 인간과 비교하여 경쟁력있는 결과를 보였다.
연구의 결론으론 ChatGPT는 MCQ-based 평가에 잠재적 위협이 될 수 있고 시험 환경에서는 AI 도구 사용을 제한할 것을 제안하였다.

Pursnani, Sermet, Demir는 공학 기초 시험에 대해 GPT-4의 효과를 탐구하였고 ChatGPT가 성공적으로 시험을 통과하여 정확도를 확보했음을 발견하였다.
Prompt 조정을 통해 더 정확한 응답을 제공함으로 성능 향상이 가능함까지 확인하였다.
이 연구로 고등 교육에서 AI 관련 도전 중요성과 시험 무결성을 위해 AI 저항성 시험 문제를 만드는 필요성을 강조한다.

Qadir는 공학 교육에서 ChatGPT의 잠재적 장단점을 탐구하기 위한 연구를 수행하였다.
학습에 도움이 될 수 있는 잠재적 Application(가상 튜터링 등)을 식별하나 부주의한 사용으로 학생들에게 잘못된 정보를 제공할 수 있음에 대한 의구심을 표현하였다.

한 연구에서 학부 컴퓨터 과학 과정에 대한 ChatGPT의 응답을 평가하였다.
ChatGPT는 Alogrithm과 Data structure의 기말 시험에 대한 응답을 하였다.
평가 편향을 줄이기 위해 AI가 생성한 응답으로 손으로 작성한 답안지를 준비하고 블라인드 채점을 실시하였다.
GPT-3.5는 50%, GPT-4는 60%의 점수를 기록하였다.
시험의 참가한 200명의 학생들의 평균 점수와 거의 유사하여 ChatGPT가 Computer science에 대한 부분적인 이해를 가지고 있다고 판단하였다.

Kashefi와 Mukerji는 Numerical analysis 과정의 코드 생성 및 Debugging을 위한 ChatGPT의 가능성을 조사하였다.
C++, Python, MATLAB에서의 코드 생성, 디버깅, 완성, Language translation 등의 다양한 작업에 대해 탐구하였다.
ChatGPT가 불완전한 코드를 인식할 수 있는 능력을 평가하기 위해 다양한 수학문제(선형 방정식 해 구하기, 함수 근 찾기)를 고려하였다.
특정 한계가 있었으나 ChatGPT가 다양한 Programming language에서 Numeric algorithm을 생성하는 유능한 도구라고 판단하였다.

S. Biswas는 Computer programming에서 ChatGPT의 역할에 초점을 맞춘 연구를 진행하였다.
Code 완성 및 수정, 문서 생성, 예측, 오류 수정, 최적화, Text-code 변환 및 기술적 질문에 대한 답변 등의 다양한 분야에서 유용한 도구로 활용될 수 있다.
요약하여 ChatGPT는 Computer programming 분야에서 상당한 영향을 미칠 수 있는 잠재적 도구라고 발견하였다.

Anagnostopoulos는 Programming 교육에서 ChatGPT의 영향을 연구하였다.
ChatGPT의 구현, 장점, 제한 사항, 윤리적 문제, 미래 전망에 대한 긍정 및 부정적 리뷰를 요약하였다.
결과론 Programmer가 ChatGPT의 응답에만 의존하지 않고 Programmer의 지식과 전문성을 결합하는 것이 유익하다고 결론내었다.

Ma et al.은 Software engineering에서 ChatGPT의 능력과 한계를 조사하였다.
ChatGPT의 Code 구문 이해 능력, 정적 의미 구조 및 동적 행동 분석에 초점을 맞춰 2327개의 Code sample을 분석하였다.
ChatGPT는 Code 구문 규칙을 이해하고 Code의 정적 행동에 대한 일부 이해를 보여주나 동적 행동을 이해하는 능력이 부족함을 드러냈다.
결론적으로 Software engineering에서 ChatGPT의 응답의 신뢰성을 검증할 필요성을 강조하였다.

4. Study Setup

Dataset 수집은 Online judge에서 Problem set을 수집하였다.

1. Array
2. Backtracking
3. Binary Search
4. Bit Manipulation
5. Dynamic Programming
6. Greedy Approach
7. Graph
8. Heap
9. Math
10. Sorting

관련 문제를 똑같이 쉬움, 중간, 어려움으로 10문제씩 총 300문제로 진행하였다.

답변 생성을 위해 초기 접근법으로는 문제의 URL을 제공하는 것이다.

Give the solution in Java for the problem state in
https://leetcode.com/problems/sort-the-people

URL 제공의 경우 ChatGPT의 버전에 따라(이 연구의 경우 21년 9월 이후 생성 문제에 대한 진술 검색 실패) 제한이 존재하여 문제의 설명과 예시를 들어 제공하여 접근하였다.

You are given an array of string names, and an array heights that consists of distinct positive integers.
Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the ith person.

return names sorted in descending order bv people's heights.

Example 1:
Input: names = ["Mary", "John", "Emma"}, heights =[180, 165, 170]
Output: ["Mary", "Emma", "John"]
Explanation: Mary is the tallest, followed by Emma and John.

...

Constraints:
n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Give the solution in Java for the problem stated above.
Use the class given as follows.
class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
    }
}

하지만 연구에 사용한 Online judge인 LeetCode에서 문제를 제출하기 위한 특정 명세를 충족하지 못할 경우 Solution 자체를 Compile error로 처리하며 제출에 부합하지 않는 Solution을 생성하는 확률이 절반 정도여서 이 접근 방식 또한 한계가 존재했다.

앞 접근 방식의 한계를 해결하기 위해 Solution 명세에 대한 상세한 정보를 제공하는 Prompt engineering을 통하여 작성하였다.(앞 접근 방식과 Prompt에 제공하는 정보는 동일)

아래에서는ChatGPT의 Response pattern을 세 부분으로 구분하여 논의한다.

• 첫 번째부분 : 제공한 정보에 대한 소개
  "Certainly! Here's a solution for the problem."
• 두 번째 부분 : 코드 제공
• 세 번째 부분 : 생성된 Solution 설명

LeetCode의 제출 상태는 아래와 같다.

• Accepted
• Wrong Answer
• Runtime Error
• Time Limit Exceeded
• Complie Error

5. Result Discussion

요약하여 사람의 정답률은 52.95%, ChatGPT의 정답률은 66%이다.
전체적으로 사람보다 뛰어난 성능이 나왔다.
난이도 수준을 고려한 전체 성능 분석에서 쉬움, 중간 어려움에 해당하는 사람의 정답률이 62.72%, 54.04%, 36.87%인데 비해 ChatGPT의 정답률은 89%, 68%, 41%로 나왔다.
ChatGPT 역시 더 복잡하고 어려운 문제를 다룰 때 정답률이 떨어지는 것을 확인할 수 있었다.

.png)

위 Table을 요약하여 ChatGPT는 Binary Search에 강세를 보이고 Math, Greedy Approach, Bit Manipulation에서 약세를 보였다.

6. Threats to Validity

더 다양한 문제와 Data set으로 향상된 일반화가 가능하다.
LeetCode에서 생성했기에 해당 Platform의 제출 통계로 고려하였으나 다른 Online judge를 활용한다면 결과가 다를 수 있다.
ChatGTP는 지속적으로 발전하기에 똑같은 연구를 했을 때 똑같은 결과가 나오지 않을 수 있다.

7. Conclusion

ChatGPT는 쉽거나 보통 수준의 문제에서 인간 참여자보다 우수한 성능을 보였으나 난이도가 높은 문제에 대해서는 성능이 크게 저하되는 것을 확인할 수 있었다.
ChatGPT는 Programming 문제를 해결하는 데 유용한 도구이나 개선이 필요해 보인다.
이후 이 논문의 저자는 AI 저항성 문제 Set를 준비하기 위한 가이드라인을 제공하는 쪽으로 초점을 맞춰 진행할 예정이다.