(C#) AI와의 대결 : 백준 알고리즘 2231번 Chat-GPT와 코드 비교

이 문제는 내가 알고리즘에 취약하다는 걸 알려준 문제이다. 지금까지의 알고리즘 문제는 알고리즘이라고 하기보단 논리적인 수학접근법으로 코드를 작성하면 잘 풀렸다. 그래서 이 문제를 시도할때도 분명 규칙이 있을 것이라 생각했다. 2~3시간 고민해도 쉽게 답이 나오지 않았고 이 문제가 브루트 포스 알고리즘이라는 것을 알게되면서 바로 풀렸던 문제다.

---

백준 2231번 문제

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

문제 풀이

위에서 말했듯이 브루트 포스 알고리즘을 기반으로 코드를 작성했다. 브루트 포스 알고리즘이 궁금하다면 아래 정리를 한번 보는 것을 추천한다.

 

브루트 포스 알고리즘 정의

 

나의 코드는 아래와 같다.

string input = Console.ReadLine();
int real_num = int.Parse(input);

int result = 0;

// for문 끝내는 조건은 while(true)와 같이 계속 반복을 하는데 의의를 두었다.
// 원하는 값을 얻었을때 break;로 빠져나오게 했다.

for (int count = 0; count <= real_num; count++)
{
    int i = count;
    int sum = 0;
    sum += i;
	
    
    while (i != 0)
    {
        sum += i % 10;
        i /= 10;
    }

    if (sum == real_num)
    {
        result = count;
        break;
    }
}
Console.WriteLine(result);

내가 지금봐도 복잡하긴하다. 이번에는 Chat-GPT한테 코드를 작성하라고 하지 않고 최적화 해보라고 시켜보았다.

---

Chat-GPT에게 물어본 문장

시간제한이 2초이고 메모리제한이 192MB일때 아래 문제에 대한 코드를 작성해보았는데 최적화 해줘 프로그래밍 언어는 C#으로 해줘
위에서 설명한 [문제,입력,출력]
추가적으로 아래 코드는 내가 작성한 코드야.
(나의 코드)

---

 

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        for (int i = Math.Max(1, n - 54); i < n; i++)
        {
            int sum = i;

            for (int j = i; j > 0; j /= 10)
            {
                sum += j % 10;
            }

            if (sum == n)
            {
                Console.WriteLine(i);
                return;
            }
        }

        Console.WriteLine(0);
    }
}

이 최적화된 코드에서는 먼저 입력 숫자의 자릿수를 고려하는 수학 공식을 사용하여 가장 작은 생성기의 상한을 계산합니다. 이 상한선은 가장 작은 생성기를 찾기 위해 확인해야 하는 가장 높은 숫자입니다.

그런 다음 하한값 1과 방금 계산한 상한값 사이의 숫자 범위를 반복합니다. 각 숫자에 대해 각 숫자를 숫자 자체에 더하여 분해 합계를 계산합니다.

현재 숫자의 분해 합이 입력 숫자와 같으면 입력 숫자의 가장 작은 생성기를 찾아 출력하고 프로그램을 종료합니다.

가장 작은 생성기를 찾지 않고 루프를 종료하면 0이 출력됩니다.

---

for문에서 i값을 초기화 할때 입력에서 주어질 수 있는 최대값을 감안 해서 최적화 된게 놀라웠다. 사실 생각지도 못한 방법이였고 이해하는데 꽤나 걸렸다. 이해함과 동시에 이 코드는 좋은 코드인가 라는 의문이 생겼다. 물론 수학적 논리로는 좋은 방법이지만 이런 코드를 추구한다면 다른 개발자들이 내 코드를 이해하는데 시간이 걸릴 것이고 협업을 하는데 문제가 생길것이다. 이 코드가 최적화가 되었냐 라고 물어보면 아니라고 대답을 할 것 이다.