February 19, 2021 15:49

개요

이전 글들에서 시간 복잡도를 고려한 코드 설계 전략과 PS에서의 런타임 에러와 디버깅에 대해 각각 다루어 보았습니다. ‘시간 초과’와 ‘런타임 에러’는 모두 오답 판정 중 특수한 경우에 해당하기 때문에 코드의 어떤 부분에 초점을 맞추어 디버깅을 해야 할지가 비교적 명확하고, 문제가 될 수 있는 유형도 어느 정도는 제한적이고 빈번히 발생하는 패턴들이 존재합니다. 특히 ‘런타임 에러’의 경우에는 백준 온라인 저지에서 얼마 전부터 런타임 에러의 종류를 공개하기 시작해서, 문제의 원인을 파악하기가 이전보다 훨씬 용이해졌습니다.

오답 판정 중 가장 막막한 것은 도움이 될 만한 별다른 힌트가 없는 ‘틀렸습니다’ (Wrong answer)입니다. 이 판정은 그야말로 답이 틀렸다는 것 외에는 아무것도 알려주지 않습니다. 출력한 양이 많았는지 / 적었는지, 정답에 비해 얼마나 큰 수였는지 / 작은 수였는지 등의 정보를 일반적으로는 아무것도 알아낼 수가 없습니다.¹

문제 풀이 코드의 가장 주된 목표가 정답을 도출해내는 것이기 때문에 어떠한 이유로든 ‘틀렸습니다’가 나왔다면 그 코드는 효율성과 안정성을 불문하고 목적을 달성하지 못했다고 할 수 있습니다. 이번 글에서는 정답을 도출하지 못하는 코드의 문제점을 디버깅하여 정답을 받는 코드로 바꾸기 위한 팁을 제시하려고 합니다.

‘틀렸습니다’의 원인

입력을 주고 그에 대한 답을 출력하는 방식을 사용하는 온라인 저지에서는 ‘틀렸습니다’는 오로지 정상적으로 종료된 프로그램의 출력 내용에 의해서만 발생할 수 있습니다. 프로그램 실행 도중에 문제가 생겨서 강제 종료가 됐다면 ‘런타임 에러’를, 제한 시간이 모두 지나기 전까지 프로그램이 종료되지 않았다면 ‘시간 초과’를 대신 받게 됩니다. 따라서 ‘틀렸습니다’를 받았다면 그 코드는 오답을 출력한 어떤 케이스에 대해 처음부터 끝까지 걸림돌 없이 모든 제한을 지키면서 매끄럽게 실행이 잘 됐음에도 불구하고 출력한 답이 틀렸다는 것을 의미합니다.

직접적인 원인은 출력한 내용이 오답인 것이지만, 오답을 출력하게 되는 원인은 매우 다양합니다. 크게는 다음과 같이 분류할 수 있습니다.

• 구현의 오류: 생각한 로직과는 다른 의미가 되는 코드를 작성해서 의도한 대로 코드가 동작하지 않아 오답을 출력한 경우입니다.
• 논리의 오류: 코드의 모든 부분이 생각한 그대로 잘 구현되었지만, 그 생각 자체에 결점이 있었기 때문에 오답을 출력한 경우입니다.

가장 좋은 것은 어떤 이유로든 ‘틀렸습니다’를 받지 않도록 처음부터 올바른 코드를 작성하도록 연습하는 것입니다.

전자는 주로 프로그래밍 스킬과 연관되어 있고, 디버깅 시에도 코드를 일부 수정하기만 하면 되는 경우가 많습니다. 하지만 언어 / 라이브러리의 동작 방식에 대한 이해가 없는 상태에서 작성한 코드에는 이러한 오류가 아주 많이 포함되어 있을 가능성이 높습니다. 코드는 한 문장에서 문자 하나라도 잘못 사용하면 의도와 전혀 다른 동작을 할 수 있기 때문에, 확실하지 않은 부분에 대해서는 레퍼런스를 참고하여 온전하게 문법과 사용법을 익히도록 하는 것이 바람직합니다.

후자는 문제를 읽는 순간부터 마지막까지 항상 주의를 기울여야 하는 부분입니다. 프로그램의 전체적인 동작을 설계하는 것뿐만 아니라, 문장 하나 하나를 작성할 때 이 자리에 어떤 코드가 들어가는 것이 옳은지를 끊임없이 생각하여 프로그램 전체의 로직이 정답을 도출해내는 데에 결함이 없음에 확신을 가질 수 있도록 해야 합니다. 논리적인 오류가 있었다면 코드의 상당 부분이나 전체를 처음부터 다시 작성해야 할 수도 있기 때문에, 코드를 작성하기 전에 머릿속으로 논리에 대한 대략적인 검증을 마친 뒤에 코딩에 돌입하는 것이 좋습니다.

논리의 오류는 생각에 관련된 부분이기 때문에 글로 설명하기는 어렵고, 많은 연습을 통해 경험을 쌓는 수밖에 없습니다. 그래서 이 글에서는 주로 구현의 오류를 잡아내기 위한 방법에 대해서 설명합니다.

컴파일 경고

모든 종류의 프로그래밍에 있어 가장 기본이 되는 것 중 하나는 바로 컴파일 경고를 무시하지 않는 것입니다. 정상적으로 실행될 여지가 있는 경우 컴파일러는 웬만해서는 경고를 발생시키지 않으며, 컴파일러가 경고를 내보냈다는 것은 충분히 문제가 될 소지가 있음을 실행도 해보기 전에 감지할 수 있었다는 뜻입니다. 물론 문제 풀이를 하는 단계에서는 무시해도 좋을 수준의 경고들도 일부 있으나, 그러한 경우에도 왜 그 경고가 발생했는지, 그 영향이 어떤지를 정확히 알고 내 코드에서는 문제가 될 여지가 없음을 확신할 수 있을 때에만 이를 무시해야 합니다.

기본으로 설정된 컴파일 경고 단계가 너무 낮은 경우 높여서 경고가 더 나오게끔 해주는 것도 좋습니다. 컴파일 경고를 분석하는 것만으로도 초기화되지 않은 변수의 사용, 반환형이 있는 함수가 반환을 하지 않는 경우 등 자주 하기 쉬운 실수들을 대다수 찾아낼 수 있다는 점을 기억해야 합니다.

예제의 함정

대부분의 문제에서는 어떤 제한 내에서의 입력을 프로그램에 넣어주고 그에 대한 답을 출력하게 하고, 하나 이상의 예제를 같이 보여줍니다. 하지만, 예제를 믿으면 곤란합니다. 예제는 일반적으로 ‘예제를 맞을 수 있으면 거의 맞는 코드임을 확신할 수 있는 수준’으로 만들어주지 않기 때문입니다. 그보다는 오히려 ‘입력과 출력 양식에 대한 힌트’를 주기 위한 것에 가깝습니다. 예제만을 유일한 케이스로 생각하고 코드를 작성하다 보면 자신도 모르게 그 예제의 특수한 상황을 코드 전체에서 가정한 채로 작성하는 실수를 하게 될 수 있습니다.

예를 들어 정수 $N$ ($1 \le N \le 10^6$)에 대한 소수 판정을 하는 프로그램을 작성해야 하는 경우 예제에서는 $N=5$, $N=18$ 정도만 보여줄 수도 있습니다. 이것을 보고 $N$이 매우 작다고 착각하여 $2$, $3$, $5$, $7$으로만 나누어 떨어지는지 보는 실수를 하면 $N \ge 121$이면서 소인수로 $2$, $3$, $5$, $7$를 가지지 않는 합성수의 경우에는 항상 오답을 출력하게 됩니다.² 게다가 예제에 $1$이 포함되어 있지 않다면 높은 확률로 $1$을 소수로 잘못 판정하는 코드를 작성하게 됩니다. 이 문제에서 염두에 두어야 하는 것은 $1 \le N \le 10^6$이라는 전체 범위이지, 예제에 나온 $N=5$, $N=18$이 아닙니다.

다른 예시로 길이가 $N$ ($1 \le N \le 10^5$)인 수열을 입력으로 주고, 예시로 $N=5$인 예제를 10개 보여주는 문제를 하나 생각해 보겠습니다. 만일 여기에 정밀한 검증 과정을 거치지 않고 ‘웬만하면 맞을 것 같은’ 그럴듯한 코드를 작성했는데, 실제로는 길이 1당 99.99%의 확률로만 맞는 코드였다고 가정하면 예제 하나가 맞을 확률은 약 99.95%에 달하고, 10개의 예제가 모두 맞을 확률도 99.5%나 됩니다. 하지만 문제의 최대 제한인 $N=100000$의 입력이 들어오게 되면 맞을 확률은 약 0.0045%밖에 되지 않기 때문에, 아무리 많은 예제를 넣어봐도 맞는 코드를 단 한 개의 테스트 케이스만으로도 틀리게 만들기에 충분합니다.

케이스의 분류와 코너 케이스

이와 같이 문제를 풀 때에는 예제를 중심으로 코드를 작성해서는 안 되고 입력 전체 범위를 생각해야 합니다. 생각한 로직에 다양한 케이스를 대입해보는 것은 검증에 아주 좋은 방법입니다. 하지만 가능한 모든 종류의 입력을 시험해보는 것은 대부분의 문제에서 가능하지 않고, 문제 푸는 속도를 고려한다면 너무 많은 케이스를 고려할 수도 없을 것입니다.

그래서 테스트를 할 때에는 어떤 특징을 가진 케이스들을 일부 대표로 뽑아야 합니다. 입력 범위가 아주 넓더라도 대다수의 케이스들은 서로 비슷한 특징을 가지고 있어 그룹화하는 것이 가능하고, 각각에 대해 몇 가지의 케이스만 테스트해보는 것이 효율적입니다. 어떤 특징이 중요하게 작용할지는 문제에 따라 다르지만, 전체 범위에서 아무 값이나 랜덤으로 해보는 것은 대체로 비슷한 특징의 케이스들만 반복적으로 테스트하게 될 가능성이 높습니다.

케이스를 분류할 때 가장 중점적으로 고려해야 하는 것은 코너 케이스입니다. 코너 케이스란 입력값을 최대한 극단적으로 만든 것을 의미하는데, 대표적으로는 입력 범위 내에서의 최소와 최대가 있습니다. 수열에서는 모든 수가 같은 수열, 오름차순, 내림차순, 또는 최소와 최대가 반복되는 수열 등이 코너 케이스가 될 수 있고, 행렬이 주어질 때에는 $n \times 1$ 행렬이나 $1 \times m$ 행렬 등이 극단적인 예시가 될 수 있습니다.

특히 문제를 풀 때에는 주로 큰 입력을 시간 내에 처리할 수 있는지를 중점으로 생각하기 때문에 극단적으로 작은 입력에 대한 고려를 소홀히 하는 경우가 많은데, 그 때문에 실제로는 그러한 입력들이 유일한 반례가 되는 코드가 매우 많습니다. 대표적인 것이 위에서도 살펴본 소수 판정에서의 1과 같은 예시로, 다음과 같이 코드를 작성하여 1을 소수로 잘못 판정하는 경우가 매우 많습니다.

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int flag = 1;
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	cout << flag << '\n';
}

다른 예시로는 1로 만들기와 같은 DP 문제에서 dp 배열을 n+1만큼 동적할당을 했는데 dp[1], dp[2], dp[3]에 무조건 값을 대입하고 시작하는 것도 있습니다. 만약 n이 1이라면 dp의 크기는 2가 되기 때문에 dp[2]와 dp[3]이 존재하지 않고, 이는 C나 C++에서는 추후 설명할 undefined behavior, Java나 Python 등에서는 런타임 에러로 이어지게 됩니다.

입력 자체의 극단성을 이용하는 것 외에도 문제에서 요구하는 답과 연관지어 코너 케이스를 만들 수도 있습니다. 예를 들어 최소, 최대 문제에서 다음과 같이 틀린 코드를 작성할 수 있습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1000005];

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int mn = 9999999, mx = -9999999;
	for (int i = 1; i < n; i++)
	{
		mn = min(mn, arr[i]);
		mx = max(mx, arr[i]);
	}

	cout << mn << ' ' << mx << '\n';
}

이 코드는 입력을 arr[0]부터 받았지만 실제 최소, 최대를 찾을 때에는 arr[1]부터 찾기 때문에 첫 번째 원소가 최소 또는 최대인 경우 틀리게 됩니다. 이런 실수를 했을 경우를 고려하여 원소가 1 9 9 9 9와 같은 형태로 나타나게끔 입력을 만들어 보면 반례를 찾을 수 있습니다. 정답이 나타나는 위치를 수열의 가장 끝에 배치시켜 극단적인 입력을 만든 예시입니다.

코드의 분기 테스트

프로그램 테스트에서 반드시 수행되어야 할 것 중 하나는 코드의 모든 분기가 의도한 대로 동작하는지를 검사하는 것입니다. 예외를 처리하기 위해 분기를 넣어놓았는데 실제로는 잘못된 방식으로 처리했거나, 오히려 분기를 없애야 맞는 코드가 되는 경우도 있을 수 있습니다. 이런 분야로 질문이 많은 알람 시계 문제에 대한 틀린 코드를 하나 보겠습니다.

#include <iostream>
using namespace std;

int main()
{
	int h, m;
	cin >> h >> m;
	if (h == 0)
	{
		if (m < 45)
		{
			h = 23;
			m += 15;
		}
		else
		{
			h = 23;
			m -= 45;
		}
	}
	else
	{
		m -= 45;
		if (m < 0)
		{
			h--;
			m += 60;
		}
	}
	cout << h << ' ' << m << '\n';
}

h가 0인 경우 처리가 까다롭기 때문에 분기로 따로 나눈 모습입니다. 이 코드로 문제에 있는 3개의 예제를 돌려보면 모두 답이 잘 나오는 것을 확인할 수 있습니다. 하지만 이 코드를 제출하면 그래도 틀립니다. 문제는 처음으로 나오는 else 부분에 있는데, 이 부분이 실행되는 케이스를 한 개도 넣어보지 않았기 때문에 이 문제를 잡아내지 못한 것입니다. 예제에 해당 코드가 실행되게 하는 케이스가 하나도 없음을 인지한 다음, 입력으로 0 45와 같은 것을 넣어보면 답이 이상하게 출력되는 것을 찾아낼 수 있었을 것입니다.

각각의 분기에 대해서도 분기가 나뉘는 경계에서의 입력도 넣어볼 가치가 있습니다. 예를 들어, 위 코드에서 if (m < 45) 부분을 if (m <= 45)로 쓰는 실수를 하기 쉬운데 그러면 m이 45인 케이스가 반례가 될 것이고 역시 예제에 없기 때문에 그대로 제출한 뒤 ‘틀렸습니다’를 받게 될 수 있습니다. m이 45인 경우를 기준으로 분기를 나누었기 때문에 이 경계에서의 분기 처리가 올바르게 되어있는지에 대한 테스트를 해보는 것은 아주 중요합니다.

자동화된 랜덤 테스트

도저히 어떻게 해도 손으로 반례를 찾을 수 없을 때 사용할 수 있는 최후의 수단입니다. 무작위로 랜덤 테스트를 생성한 뒤 정답이 나오는지를 확인하는 것을 자동으로 반례가 나올 때까지 반복해주는 프로그램을 작성하는 것입니다.

이 작업에는 다음과 같은 것들이 필요합니다.

• 테스트하고자 하는 코드
• 정답 코드 또는 효율이 떨어지지만 답은 맞다고 확신하는 코드
• 데이터 생성 프로그램 (generator)
• (스페셜 저지가 필요한 경우) 정답 비교 프로그램 (checker)
• (optional) 데이터 검증기 (validator)

이 작업은 곧 문제를 출제할 때 데이터를 만드는 과정과 같습니다. 문제 출제를 위한 플랫폼 - Polygon 사용하기 글에서 자세한 내용을 볼 수 있습니다. 하지만 문제를 하나 풀 때마다 이 모든 것을 온전하게 갖추는 것은 다소 번거로울 수 있고, 대회나 코딩 테스트 중이라면 폴리곤도 사용할 수 없습니다. 그래서 이 작업을 간소화시켜 다음과 같이 하나의 코드 내에서 테스트를 할 수 있습니다.

우선 정답 코드를 하나 구합니다. 코드를 구할 수 없거나 스포일러를 당하고 싶지 않다면 대신 정답 코드를 직접 구현해야 하는데, 코드의 효율성을 포기하고 문제에 있는 그대로를 구현하거나 브루트포스를 수행하는 경우 실수를 하기가 어려울 정도로 코드가 매우 간단해지는 경우가 많습니다. 단, 이 때에는 규모가 큰 테스트 케이스는 사용하기 어렵다는 점을 감안해야 합니다.

그 다음은 정답 코드와 테스트를 할 코드를 복사 / 붙여넣기 하여 하나로 합칩니다. 겹치는 변수/함수 이름은 적절히 변경해주고, 각각의 main 함수가 시작할 때 모든 전역변수를 수동으로 초기화하는 구문을 추가해 줍니다. 입력을 받는 부분은 모두 main 함수의 인자로 받아오는 것으로 변경합니다. 출력하는 구문은 main 함수의 리턴값으로 대체합니다.

각 main 함수의 이름을 다르게 변경하고, 새로운 main 함수를 만듭니다. 새로운 main 함수에서는 무한루프를 돌면서 입력에 해당하는 데이터를 생성하고, 각 코드의 main이었던 함수에 보내준 뒤 리턴값을 받아온 뒤 둘을 비교합니다. 둘이 같다면 루프를 계속 돌고, 그렇지 않으면 해당 케이스를 출력하면 됩니다.

이 방법은 매우 높은 확률로 반례를 찾아줄 수 있다는 점에서 매우 강력한 수단이지만, 반례가 될 만한 경우를 스스로 생각해보는 것 또한 좋은 연습이기 때문에 최후로 미루는 것을 권장합니다.

반례를 찾은 뒤

일단 반례를 찾았다면 이제 어디에서 문제가 발생했는지를 알아내야 합니다. 그런데 그 작업 또한 항상 간단한 것은 아닙니다. 코드가 너무 길 수도 있고, 변수들이 서로 복잡한 관계로 얽혀있을 수도 있습니다.

문제가 발생한 지점을 찾는 가장 기초적이면서도 가장 유용한 방법은 변수들의 값을 출력해보는 것입니다. 코드가 실행되면서 각 변수가 각 시점에 가져야 할 값을 생각한 뒤, 정말로 그 위치에 모든 변수의 값이 의도한 대로 나타나는지를 확인하여 처음으로 달라지는 위치를 찾는 것이 주요 과정입니다. 별도의 디버깅 도구가 없더라도 단순히 화면에 출력해보는 것으로도 충분히 가능하고, 디버깅 도구가 있다면 중단점을 걸고 각 중단점에서 변수의 값들을 조사해보는 식으로 더 체계적인 디버깅을 할 수도 있습니다.

처음으로 의도와 다른 변수 값이 발견되었다면 그 근처에 잘못된 문장이 있을 가능성이 높으므로, 근처의 코드를 다시 하나 하나 잘 관찰해보면 찾아낼 수 있을 것입니다.

코드의 재검토

반례를 통해 문제점을 찾아나서는 것 외에도 코드 그 자체만을 보고 문제점을 찾는 과정도 필요합니다. 여기서 중요한 것은 코드는 항상 전체를 꼼꼼히 확인해야 한다는 점입니다. 풀이의 핵심이 되는 부분만을 보는 것이 아니라 프로그램이 실행된 후 마지막으로 종료되기까지의 모든 문장 하나하나에 결점이 없는지를 빠짐없이 체크해야 합니다. 프로그램은 단 하나의 문장이라도 잘못되면 의도와 전혀 다른 동작을 할 수 있다는 점을 명심해야 합니다.

특히 C와 C++의 경우에는 약간의 배열 범위를 넘어서는 것만으로는 별 문제 없이 실행되는 경우가 많기 때문에 인덱싱에 문제가 없는지 반드시 눈으로 확실히 해야 하며, 입력의 크기가 큰 경우는 직접 테스트해보기 어렵기 때문에 정적 배열의 크기가 충분한지 문제에 쓰인 제한과 다시 한 번 더 비교해가며 확실하게 체크해야 합니다.

이와 같은 undefined behavior (UB)는 많은 C / C++ 프로그래머들의 골치를 아프게 합니다. UB의 문제점은 UB가 하나라도 발생하는 순간 채점 결과는 그 무엇이 나와도 이상하지 않게 된다는 점입니다. 운 좋게 프로그램이 마지막까지 잘 실행돼서 정답을 받을 수도 있고, 답을 틀리게 만들 수도 있고, 루프 변수를 잘못 건드려 무한루프를 돌거나 메모리 할당을 받는 문장이 계속 실행되어 메모리 초과가 될 수도 있습니다. 게다가 같은 케이스에 대해서도 채점 서버에서는 틀렸다고 판정하는데 내 컴퓨터에서는 결과가 잘 나올 수도 있어 아무리 많은 테스트를 거쳐도 문제점을 찾지 못하는 경우도 있을 수 있습니다. UB와 관련한 자세한 정보는 C/C++의 undefined behavior 글을 참조하면 좋습니다.

만일 아무리 많은 테스트를 돌려도 문제점을 찾을 수 없다면 코드의 어디선가 UB가 발생했을 가능성이 높습니다. 일반적으로는 좋은 컴파일러들은 디버깅 모드로 컴파일하고 디버거를 실행할 경우 이러한 UB들을 상당수 잡아내주지만, 결국에는 프로그래머가 언어의 스펙과 라이브러리의 사용법을 정확하게 인지하고 코드를 작성할 수 있어야 이러한 문제를 처음부터 예방할 수 있습니다. 불확실한 것이 있다면 레퍼런스를 찾는 것을 주저하지 않는 습관을 들여야 합니다.

레퍼런스를 참고하지 않고 그냥 어디서 들은 것만으로 코드를 작성해서 많은 사람들이 겪게 되는 문제 중 하나가 바로 sync_with_stdio의 동작과 관련한 실수입니다. 이 함수의 동작 원리를 알아보지 않고 그냥 ‘쓰면 입출력이 빨라진다’는 불완전한 정보만 듣고 사용하면 C와 C++의 입출력 함수를 섞어서 사용하고 무수히 많은 ‘틀렸습니다’를 받게 될 수 있습니다.³

또한 이 문제는 수행 시간과 관련해서도 자주 발생하는데, 라이브러리 함수들에도 각자의 시간 복잡도가 있으며 그 정보 역시 레퍼런스에 대체로 기술되어 있다는 점을 명심하면 좋을 것 같습니다.

마치며

프로그래밍을 통해 문제를 푸는 것은 코드 전체에서의 무결성을 요구하기 때문에 단 한 군데에서의 실수도 용납되지 않습니다. 그래서 오랜 시간을 연습하고 경험을 쌓더라도 항상 ‘틀렸습니다’를 받지 않고 넘어가는 것은 매우 어려운 일이며, 이 빈도를 줄이지 못하면 디버깅의 늪에 빠져 시간만 보내는 일을 계속 반복하게 됩니다. 코드를 작성하기 이전의 시점부터 제출할 때까지 전 과정에서의 논리를 반복적으로 검증하고 코드를 구석 구석 테스트하는 기법들을 알아두어야 하겠습니다.