ChatGPT와 코드 비교 (greedy)

 

그리디유형의 문제를 풀고 있었다

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

14916번: 거스름돈

간단한 문제여서 첫 시도에 통과후

다른사람의 코드와 ChatGPT의 코드를 살펴보고 있었다

 

카태고리가 그리디유형 이였지만

N을 나눠가거나 곱해가는 문제는 패턴을 알면 O(1)로 시간을 대폭 개선 할수 있을것이라 생각했기 때문에

패턴부터 파악했다

 

패턴 설명

 

 

1~4 까지는 예외처리,

그후부터 일정한 패턴을 가진다

사실 1~4도 일정한 패턴을 준수하지만

5보다 작은수 이기 때문에 동전을 -X개 줄수없다

그래서 예외로 처리 해주어야 한다

N      5원     2원       출력(동전 갯수)

1                               -1

2       5x0 + 2X1      1

3                              -1

4      5x0 + 2X2       2

 

5      5x1 + 2X0       1 

6      5x0 + 2X3       3

7      5x1 + 2X1       2

8      5x0 + 2X4       4

9      5x1 + 2X2       3

 

10      5x2 + 2X0       2

11      5x1 + 2X3       4

12      5x2 + 2X1       3

13      5x1 + 2X4       5

14      5x2 + 2X2       4

 

15      5x3 + 2X0       3

16      5x2 + 2X3       5

17      5x3 + 2X1       4

18      5x2 + 2X4       6

 

일정한 패턴이 보인다

 5원은 N/5 와 N/5-1을 반복하고

2원은 0 > 3 > 1 > 4 > 2 > 다시 0 부터 반복한다 

 

거스름돈 coin N개 를 가장큰 동전 5원으로 모조리 나누는것이 그리디의 전제조건이다

모든동전의 합이 가장 적을수있는 이상적인 상황은

가장 큰단위인 5원의 갯수가 많아야 하기때문이다

 

 

 

나 / ChatGPT

 

 

 

ChatGPT의 코드는 while로 N번 반복한다

나머지값이 없으면서 5원을 가장 많이 사용할수 있을때 까지 반복하기때문에

결과가 큰수에서 -1 인경우 최악의 상황으로 N회 반복한뒤 -1을 출력하기 때문에

chatGPT의 알고리즘 시간복잡도는O(N)이다

//chatGPT가 짠 코드

public class Java14916ChatGpt {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        long startTime = System.currentTimeMillis(); // 시작 시간 체크

        int count = 0;

        while (n > 0) {
            // 5원짜리로 거슬러 줄 수 있을 때
            if (n % 5 == 0) {
                count += n / 5;
                n = 0;
            } else {
                // 5원짜리로 거슬러 줄 수 없을 때 2원짜리를 사용
                n -= 2;
                count++;

                // 거스름돈이 음수가 되면 거슬러 줄 수 없는 경우
                if (n < 0) {
                    count = -1;
                    break;
                }
            }
        }

        System.out.println(count);
        long endTime = System.currentTimeMillis(); // 종료 시간 체크
        long executionTime = endTime - startTime; // 실행 시간 계산
        System.out.println("실행 시간: " + executionTime + "ms");
    }
}

//chatGPT가 짠 코드

 

 

 

하지만 나는 if / swith 를 사용하여 한번에 답을 도출 하기때문에

O(1) 의 시간 복잡도를 가진다

public class Java14916 {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int coin = sc.nextInt();
        sc.close();
        long startTime = System.currentTimeMillis(); // 시작 시간 체크
        int coin2 = coin % 5;
        int coin5 = coin/5;
        int coin5ans=0;//5원 동전의 갯수
        int coin2ans=0;//2원 동전의 갯수

        if (coin==1 || coin ==3) { //예외처리
            System.out.println(-1);
            return;
        }else if (coin ==2 ) {
            System.out.println(1);
            return;
        }else if (coin ==4) {
            System.out.println(2);
            return;
        }
        switch (coin2){
            case 0:
                coin2ans=0;
                coin5ans=coin5;
                break;
            case 1:
                coin2ans=3;
                coin5ans=coin5-1;
                break;
            case 2:
                coin2ans=1;
                coin5ans=coin5;
                break;
            case 3:
                coin2ans=4;
                coin5ans=coin5-1;
                break;
            case 4:
                coin2ans=2;
                coin5ans=coin5;
                break;
        }
        System.out.println(coin5ans+coin2ans);
        long endTime = System.currentTimeMillis(); // 종료 시간 체크
        long executionTime = endTime - startTime; // 실행 시간 계산
        System.out.println("실행 시간: " + executionTime + "ms");
    }
}

//내가 짠 코드

 

chatGPT보다 좋은 답을 생각해낸것이 기분좋은 일이지만

시간 차이가 그렇게 크지않았다

 

10ms 미만으로 내코드가 더 빨랐다

시간복잡도 유형중 가장빠른 O(1)인데

 

4ms의 차이가 어떤지 감을 잡을수없고

인터넷에 물어보더라도 다양한 환경과 문제와 테스트케이스 때문에 변별력이 없다고 생각해서

직접 시간을 측정 해봤다

 

컴퓨터 연산 속도가 너무 빨라서 나노초 단위로 카운트 해야 됬다

 

long startTime = System.nanoTime();

// 코드 실행

long endTime = System.nanoTime();
long executionTime = endTime - startTime;
System.out.println("실행 시간: " + executionTime + "ms");

 

아쉽게도 두 코드가 큰 차이가 나지않았다

서로에게 최적의 연산수행 시간과 최악의 연산시간

테스트케이스를 적용 시켜봐도 별 차이가 없었다

 

코드, 입력값의 영향을 받지않고

297833 ~ 855208 나노초 까지 랜덤하게 나왔다

모두 오차값안에서의 변동 사항 이였다

 

왜 그럴까 유추해 봤는데

 

ChatGPT가 작성한 코드에 while에 n이 0까지 반복 된다고 해도
최대 4번 반복될수 있다

왜냐하면

while (n > 0) {
            // 5원짜리로 거슬러 줄 수 있을 때
            if (n % 5 == 0) {
                count += n / 5;
                n = 0;
            } else {
                // 5원짜리로 거슬러 줄 수 없을 때 2원짜리를 사용
                n -= 2;
                count++;

                // 거스름돈이 음수가 되면 거슬러 줄 수 없는 경우
                if (n < 0) {
                    count = -1;
                    break;
                }
            }
        }

오직 else의 2원을 연산할때 반복하게 되는대

문제 자체에서 2원이 가장 많이 사용 되는경우가 고작 4개 뿐이기 때문에

최악의 조건에서도 반복문은 4회 반복될뿐이다

 

그래서 시간을 쟀을때 순수 코드 연산 시간의 범위보다

컴푸터의 연산시간 오차가 더 크기 때문에

속도를 채감 할수 없는것이다

 

 

시간복잡도는 대략적인 시간을 유추하는것으로 사용하는것이 맞다고 생각한다

 

chatGPT의 코드가 더 좋다고 생각하게된이유는 chatGPT코드의 유연함에 있다

 

내 코드의 경우

결과의 패턴을 찾아 알고리즘으로 만들었기 때문에

문제의 요소가 하나라도 변경되면

다시 패턴을 찾고 코드를 일괄 수정 해야 한다

 

하지만 

chatGPT의 코드는

문제를 그리디로 푸는 정석적인 방법으로 풀었기 때문에

약간의 수정으로 대응이 가능하다

코드를 읽었을때 그대로 해석이 가능한 chatGPT의 코드가 가독성도 좋다고 생각한다

 

때에 따라 간결하고 직선적인 해결법이 더 좋을수도 있다고 생각했다

특별한 패턴을 파악해 새롭게 문제를 푸는것은 문제를 통과하고 난뒤 시도해본다면

문제풀이 실력이 더 빨리 좋아질것이라고 생각한다