백준 C# 속도 개선

최근 백준 C#과 관련해서 시간초과 이슈가 있는 것 같습니다.

이전에 통과했던 코드도 최근에는 시간초과로 통과가 안된다는 사례도 있었습니다.

이러한 상황에서 속도 개선하는 방법을 공유하고자 합니다.

 

Console.WriteLine

백준 알고리즘 문제를 풀다 보면 많은 양의 출력이 필요한 경우가 있습니다.

Console.WriteLine()은 호출될 때마다 실제로 콘솔에 출력하는 I/O 작업을 수행합니다. I/O 작업은 메모리 접근에 비해 매우 느린 작업이며, 이를 반복적으로 수행하면 프로그램의 성능이 크게 저하되며 시간 초과의 이유가 됩니다.

 

이 때, 사용할 수 있는 방법이 StringBuilder입니다.

 

StringBuilder

문자열을 바로 출력 하는 것이 아니라 StringBuilder를 통해 문자열을 저장해놓습니다.

이후 모든 로직이 종료되면 해당 stringBuilder를 출력하는 방식입니다.

static StringBuilder sb = new StringBuilder();

public static void Hanoi(int n,  int from, int by, int to)
{
    if (n == 0)
        return;

    Hanoi(n - 1, from, to, by);
    sb.AppendLine($"{from} {to}");
    Hanoi(n - 1, by, from, to);
} 

static void Main(string[] args)
{
    int N = int.Parse(Console.ReadLine());
    Console.WriteLine(Math.Pow(2, N) - 1);

    Hanoi(N, 1, 2, 3);
    Console.Write(sb.ToString());
}

 

계속해서 콘솔에 접근하는 작업을 1번으로 줄임으로서 속도의 확실한 개선을 볼 수 있습니다.

 

 

성능 비교

예를 들어 하노이 탑 문제에서 N=20인 경우:

• 이동 횟수: 2^20 - 1 = 1,048,575번
• Console.WriteLine 사용 시: 1,048,575번의 I/O 작업
• StringBuilder 사용 시: 1번의 I/O 작업

시간 복잡도 관점

• Console.WriteLine: O(n) 번의 I/O 작업
• StringBuilder: O(1) 번의 I/O 작업

 

 

결론

알고리즘 문제 풀이에서 많은 양의 출력이 필요한 경우, StringBuilder를 사용하는 것이 성능상 큰 이점을 가져옵니다. 특히 백준과 같은 온라인 저지 사이트에서는 시간 제한이 있기 때문에, 이러한 최적화가 문제 해결의 핵심 요소가 될 수 있습니다.

참고사항

• 출력량이 적은 경우에는 차이가 미미할 수 있습니다.
• 실시간 출력이 필요한 경우에는 Console.WriteLine이 더 적합할 수 있습니다.
• StringBuilder의 초기 용량 설정을 통해 더 나은 성능을 얻을 수 있습니다.