October 22, 2021 23:33

개요

저는 백준 온라인 저지의 질문 게시판에서 풀라는 문제는 안 풀고 오랜 기간 많은 답변을 해왔습니다. 그러면서 느꼈던 것 중 하나는 문제 풀이 실력과는 별도로 처음 보는 코드를 분석하는 실력이 많이 늘었다는 점입니다. 예전에는 타인의 코드를 읽는 것이 마냥 어렵기만 했다면, 지금은 그 코드가 제 코딩 스타일과 크게 다르더라도 작성자의 의도를 파악하며 보다 객관적으로 코드를 읽는 능력이 향상되어 더 빠르게 답변을 해줄 수 있게 되었습니다. 부분적으로는 제 코드를 돌아보고 디버깅을 하는 데에도 도움이 됐다고 생각합니다.

그래서 이번 글에서는 제 경험을 바탕으로 질문글에 답변을 할 때 어떤 과정을 거쳐 문제점을 찾아야 할지를 서술해보려고 합니다. 이 글이 여러분의 디버깅 실력 향상뿐만 아니라, 늘 부족한 질문 게시판 레귤러를 양성해내는 데에도 한 몫 하기를 바라는 마음입니다.

상세

개인적으로는 풀지 않은 문제에 대한 질문은 보지 않는 편입니다. 문제에 대한 스포일러를 당할 수도 있고, 문제를 정확하게 알고 있지 않으면 잘못된 답변을 하게 될 수도 있기 때문입니다. 문제가 재미있어 보이면 우선 먼저 스스로 풀어본 뒤에 다시 질문을 보기도 합니다.

또한 질문 게시판의 다른 질문들의 답변을 보거나 아무 입력이나 랜덤으로 만들다 보면 반례가 나오는 일도 많지만 그렇다 하더라도 가능하면 코드의 문제점을 직접 찾아내는 편을 선호합니다. 랜덤으로 만들어진 반례에는 코드의 결함과는 무관한 요소가 많이 포함되어 있을 수 있기에, 반례만을 제시하더라도 우선 직접 코드의 문제점을 알아낸 뒤에 그 문제점만을 최소한으로 꼬집는 반례를 만드는 것이 더 유용하다고 생각합니다.

언어

질문을 읽기로 했다면 가장 먼저 언어를 확인해야 합니다. 모르는 언어는 코드를 제대로 읽기도 어렵고, 알고 있던 언어와 동작 방식이 크게 달라 엉뚱한 답변을 하게 될 수도 있기 때문입니다. 언어의 버전(C++11 / 14 / 17, Python / PyPy, Java 8 / 11)과 컴파일러(gcc / clang¹)까지 채점 현황을 확인하여 먼저 봐두는 것도 좋습니다. 또한 C 문법만으로 작성한 코드이지만 제출은 C++로 하지 않았는지 등도 확인을 해두면 유용합니다.

다만 그 언어를 공부해볼 생각이 있다면 꼼꼼히 읽어보는 것도 좋은 생각입니다. 실제로 저는 Python 3를 처음에는 질문 게시판의 코드들과 그 답변들을 보면서 어깨너머로 익혔고, 그 후 공부하고 사용해보면서 이제는 어느 정도 답변도 하고 문제 풀이에 쓸 수 있는 정도가 되었습니다.

판정

그 다음으로는 질문의 코드가 받았던 판정을 확인해야 합니다. 코드가 받은 판정에 따라 먼저 / 중점적으로 봐야 할 부분이 다르기 때문입니다. 익숙한 문제 번호 + 판정만으로 상황이 파악되는 경우도 있습니다. 예를 들어 스택 수열 문제에서 출력 초과를 받았다는 질문이 보인다면 매우 높은 확률로 NO만 출력해야 하는데 +와 -들이 $2n$ 줄 출력되거나, 출력되던 중 NO가 출력되고 종료된 경우입니다. 8진수 2진수 문제에서 시간 초과가 났다고 하면 어딘가에 이중 루프나 for (int i = 0; i < strlen(str); i++)가 있을 것이라고 예상하고 바로 루프들부터 확인할 수 있습니다.

특수한 경우로 언어가 Python 3인데 시간 초과를 받았다고 하는 경우가 있는데, 이럴 때에는 바로 PyPy3로 바꾸어 내보는 것도 하나의 방법입니다. 상당히 많은 경우 이것이 실제로 해결 방법이 됩니다.

자주 하는 실수 확인하기

쉽고 코드가 짧은 문제들의 경우 대개는 눈으로 디버깅이 가능합니다. 질문 본문에 요약된 정보를 바탕으로, 자주 실수할 만한 부분들을 빠르게 체크하여 대다수의 코드에 대한 문제점을 찾아낼 수 있습니다.

초보자의 코드에는 공통적으로 많이 실수하는 부분들이 있습니다. 따라서 다음과 같은 것들을 먼저 체크해보면 좋습니다.

• 배열의 크기: 초보자의 경우 문제의 제한보다는 예제에 맞추어 코드를 작성하는 경우가 많기 때문에 제한과 전혀 상관없는 크기로 배열 크기를 설정할 때가 많습니다. 문제의 제한을 먼저 보고 비교해보면 좋습니다.
• Off-by-one: 배열 크기가 0으로 끝난 것이 보이면 일단 의심해보는 것이 좋습니다. 많은 코드에서 1을 시작 인덱스로 사용하기 때문에 이런 경우 매우 높은 확률로 마지막 인덱스를 하나 벗어난 곳에 접근하게 됩니다. 특히 char 배열의 크기가 0으로 끝나게 선언되어 있다면 십중팔구 이 문제가 생깁니다. 널 문자가 들어갈 위치가 고려되지 않았기 때문입니다.
• 변수의 초기화: 초기화를 하지 않고 증가만 시키는 변수가 있는지², 지역 배열의 일부에만 값을 대입하고 나머지에는 원하는 값이 들어있을 거라고 가정했는지³, 다중 케이스 문제인데 루프의 시작이나 끝에서 초기화하지 않고 쓰는 변수가 있는지 등을 체크하면 됩니다.
• 자료형: 답이 int 범위를 벗어나는 문제인데 답을 저장하는 변수가 int형이거나, 최대 100만까지 수를 세야 하는데 char로 수를 세거나, long long 이하의 정수로 입력받을 수 있는 범위가 아닌데 정수형으로 입력받는 것을 시도하거나 하는 경우 등이 대표적입니다. 또한 float형이 보이면 일단 바로 실수 오차를 의심해봐도 좋습니다.
• 시간 복잡도: 초보자는 아직 시간 복잡도의 개념을 배우지 않아 입력 크기를 신경쓰지 않고 코드를 작성하는 경우가 많기 때문에 $N$이 $10^6$ 이하인데 이중 루프를 돌거나, $N \le 10^{18}$인 제한에서 $N$까지 루프를 돌리는 등 눈에 바로 보이는 실수들이 자주 있습니다.

눈으로 디버깅하기

위의 사항들은 거의 30초 내외로 전부 확인이 가능한 것들입니다. 질문의 반 이상은 이 중에서 문제점을 찾아낼 수 있지만, 조금 더 풀이의 로직과 직결되는 부분까지 살펴보아야 할 수도 있습니다. 아직은 코드를 직접 돌려볼 단계는 아니며, 눈으로 찾아보아도 충분합니다.

여기서부터는 이 코드가 받은 판정에 따라 중점적으로 살펴보아야 할 곳을 정하는 것이 좋습니다. 각 판정마다 자주 보이는 시나리오들로는 다음과 같은 것들이 있습니다.

틀렸습니다

디버깅에 도움이 가장 안 되는 판정이라고 할 수 있습니다. 모든 가능성을 열어두어고 꼼꼼히 살펴보아야 합니다. 특히 C/C++에서는 undefined behavior에 의해서도 이 판정이 나올 수 있기 때문에 단순히 로직상의 문제만 볼 것이 아니라 런타임 에러를 발생시킬 수 있는 요소들에 대해서까지도 모두 확인해야 합니다.⁴

다만 로직 이외에도 ‘틀렸습니다’에 대해서만 몇 가지 확인해볼만한 것들은 있습니다. 예를 들면 대소문자를 올바르게 구분하지 않는 입력⁵이나 출력⁶, 출력 형식을 정확하게 지키지 않는 경우⁷ 등이 대상이 됩니다.

몇 %에서 틀렸습니다

‘몇 %에서’라는 표현이 있다면 도움이 될 수도 있습니다. 특히 100%에 가까운 곳에서 틀렸다면 그 코드는 $N=1$ 등의 매우 작고 극단적인 케이스에서 틀렸을 가능성이 높습니다. 다중 케이스 문제의 경우 예제를 제외한 데이터가 하나뿐인 경우가 많고, 이때 주로 50%에서 틀렸다는 글을 보게 되는데 이는 그냥 ‘틀렸습니다’와 똑같다고 생각할 수 있습니다.⁸ 시작하자마자 틀렸다고 한다면 자잘한 실수가 아닌 로직 자체의 결함일 가능성이 조금 더 높다고 볼 수 있습니다.

런타임 에러

최근 BOJ에서는 런타임 에러의 종류를 분류하여 알려주고 있습니다. 이를 활용하면 어떤 부분에서 문제가 생겼을지 대략적인 짐작이 가능합니다. 특히 Java나 Python에서는 각 예외가 발생할 수 있는 위치가 딱 정해져 있기 때문에 런타임 에러의 종류를 보는 것만으로도 90%의 실마리는 잡았다고 할 수 있습니다. 해당 예외가 발생할 수 있는 후보지를 모두 찾은 후, 거기서부터 거꾸로 되짚어가며 그런 상황을 만들어낼 수 있는 입력이 있을 수 있는지 생각해보면 됩니다.

C나 C++의 경우는 undefined behavior 때문에 이것만으로는 명확한 원인을 알기 어려운 경우가 많습니다. 앞에서 살펴본 배열 크기 등의 문제에 덧붙여서, 반환형이 있는 함수가 반환을 하지 않는 분기가 존재한다든지, 라이브러리를 올바르지 않은 방법으로 사용했다든지, 또는 라이브러리의 동작이 정의되지 않도록 만들 수 있는 케이스가 존재할 수 있는지 등등을 꼼꼼하게 확인해야 합니다.

시간 초과

크게 네 가지로 후보를 좁힐 수 있습니다.

1. 로직의 시간 복잡도가 너무 큰 경우: 자주 하는 실수를 확인할 때는 바로 보이지 않더라도, 문제에서 사용한 알고리즘에 따라 발생할 수 있는 여러 전형적인 케이스들도 있습니다. 대표적으로 BFS를 하는데 방문 체크를 하지 않는 것이나, 초소형이 아닌 그래프를 완전탐색 하는 것 등이 있습니다. 또는 정렬을 위해 퀵소트를 구현했거나, 병합 정렬을 구현하는데 end-start+1이 아닌 그냥 end만큼 배열을 매번 할당하거나 복사할 때 start가 아닌 0부터 end까지 복사하는 것도 아주 아주 흔한 실수의 예시입니다. 잘못 구현한 다익스트라 알고리즘 저격하기에 해당하는 코드 등도 기억해두면 쓸모가 있습니다.
2. 무한 루프를 도는 경우: 입력 제한이 작은데 시간 초과가 났다고 한다면 거의 대부분 너무 오래 걸리는 것이 아니라 무한 루프를 도는 경우입니다. 대표적으로 더하기 사이클 문제가 있는데, 이 문제에서 식을 잘못 구현하면 매우 높은 확률로 처음 시작한 수로 돌아오지 못하게 되어 무한 루프에 빠지게 됩니다.
3. Undefined behavior가 있는 경우: 이 경우는 어쩔 수 없이 코드 전문을 꼼꼼하게 확인해야 합니다.
4. 사용한 언어가 너무 느리거나 (Python 3 vs. PyPy3) 느린 입출력 등을 사용한 경우: 입력 제한이 큰 문제라면 그저 입출력이 너무 느리기 때문에 적절한 시간 복잡도임에도 불구하고 시간 초과가 나는 경우가 있습니다. Python 3의 경우 PyPy3로 바꾸어 내보거나, 빠른 A+B 문제에서 제시한 입출력으로만 바꾸어도 해결되는 경우가 많습니다. 특히 C++에서는 출력이 많은 문제에서 endl을 쓰고 있거나, 입출력이 번갈아 나타나는데 cin.tie(0)을 하지 않아서 시간 초과를 받는 경우가 대단히 많습니다.

메모리 초과

대개는 로직상 너무 많은 메모리를 할당받은 경우입니다. 1차원이나 2차원 배열의 생성 부분을 잘 보면 됩니다. 드물게 시간 초과가 나는 로직 속에서 그에 비례하는 횟수만큼 동적 할당을 시도하는 경우도 있습니다.

Java의 경우 조금 더 까다로운 경우들이 있는데, 수천만 정도의 연산량이 나오는 로직에 동시에 사용하는 객체의 수가 얼마 되지 않더라도 단순히 객체의 총 생성 횟수가 그만큼 많다면 소멸 시점을 알 수 없는 Java 특성상 객체들이 누적되어 그대로 메모리 초과로 이어지기도 합니다.

출력 형식이 잘못되었습니다

주로 별 찍기를 비롯한 출력 위주의 문제에서 많이 보이며, 빈 줄이나 공백 / 개행 사용이 잘 되었는지만 확인하면 됩니다.

출력 초과

출력해야 할 답의 길이가 고정되어 있지 않은 문제들에서 종종 보이는데, 사실 스택 수열 문제를 제외하고는 대부분 무한 루프 내에서 출력을 하면서 발생합니다. 이 무한 루프 자체가 undefined behavior에 의한 경우가 많습니다.⁹

로직상의 문제 찾기

여기까지 둘러보았는데도 문제점이 보이지 않는다면 이제 진짜로 로직을 확인해야 합니다. 경험상 질문글의 약 20% 정도가 여기까지 오게 됩니다. 로직을 체크할 때에는 다음과 같은 점들을 주의하면서 보면 좋습니다.

• 변수의 의미 파악하기: 선언된 변수들이 각각 어떤 역할을 위해 존재하는지를 이해해야 합니다. 예를 들어 x, y라는 변수는 어떤 코드에서는 (행, 열)을 의미하고 어떤 코드에서는 (열, 행)을 의미하기도 하는데, 어느 쪽으로 쓰인 것인지를 우선 확실하게 이해해야 코드 어딘가에서 실수로 둘을 뒤바꾸어 쓴 곳이 있는지 확인해볼 수 있게 됩니다.
• 코드를 여러 부분으로 나누어 이해하기: 일반적으로 코드는 입력을 받는 부분, 하나 이상의 계산 부분, 그리고 출력을 하는 부분으로 나눌 수 있습니다. 나누어진 부분들이 각각 올바르게 동작하는지 파악하는 것이 처음부터 끝까지를 연속적으로 이해하려고 하는 것보다 더 수월하게 분석하는 데에 도움을 줍니다. 또한 각 부분이 하려는 일이 무엇인지를 명확하게 정리한 뒤 그 역할을 충실히 해내는지 확인하는 것이 좋습니다.
• 의도에 어긋나게 하는 케이스를 생각하기: 불완전해 보이는 로직이 보인다면 그 로직이 의도한 것과 다르게 동작하도록 만드는 케이스를 생각하면서 머릿속으로 시뮬레이션을 해보는 것이 좋습니다. 최대한 극단적으로 코드의 각 부분을 공격하다 보면 프로그램의 흐름이 질문자가 생각한 것과 다르게 흘러가도록 만드는 케이스를 찾아낼 수 있습니다.

실제로 코드를 실행해보기

눈으로 문제를 찾을 수 없었다면 실행을 해볼 수밖에 없습니다. 의외로 여기까지 오더라도 랜덤 케이스나 작고 극단적인 예시에서 반례가 나오는 경우가 많습니다. 다만 개인적으로는 이렇게 해서 반례가 찾아지더라도 그 즉시 그 반례를 첨부하지 않고, 해당 반례를 이용하여 직접 디버깅을 해서 문제가 되는 부분을 다시 찾아내고는 합니다. 틀린 부분을 찾았다면 그 부분 하나만을 저격하는 최소 크기의 데이터를 만들어서 올리는 것이 보통입니다.

그런데도 반례가 찾아지지 않는다면 최후의 수단으로 스트레스를 돌려볼 수 있지만, 스트레서를 구현하는 시간도 오래 걸릴 뿐더러 이렇게 찾아낸 반례가 과연 서로에게 도움이 될지도 의문이라 포기하곤 합니다.

예시 질문

지금까지의 과정을 적용해볼 수 있는 예시 질문들을 몇 가지 만들어 보았습니다. 초보자들이 자주 하는 실수들이 포함된 코드들의 문제를 찾아보겠습니다.

1. 문자열 반복

아래 코드는 50%에서 ‘틀렸습니다’를 받은 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t >= 0)
	{
		int r;
		char s[20];
		cin >> r >> s;
		for (int i = 0; i < sizeof(s); i++)
			for (int j = 0; j < r; j++)
				cout << s[i];
		t--;
	}
}

먼저 ‘50%에서 틀렸다’는 표현과 이 문제가 다중 테스트 케이스 문제라는 점을 통해 특별히 극단적인 케이스가 아닌 그냥 일반적인 논리 오류일 가능성이 크다고 생각할 수 있습니다. 많은 케이스가 들어있는 첫 번째 파일 어딘가에서 그냥 틀린 것이기 때문입니다.

전체적으로 빠르게 훑었을 때 바로 눈에 보여야 하는 것은 char형인 s 배열의 크기가 0으로 끝나고 있다는 점입니다. 대부분의 문제에서 문자열의 최대 길이는 0으로 끝나게 되어있으므로 널 문자를 위한 한 칸이 더 필요한 상황이 아닌지 바로 의심해보아야 합니다. 아니나다를까, 이 문제에서의 문자열의 최대 길이는 20입니다. 따라서 s 배열의 크기가 잘못되었음을 찾아낼 수 있습니다.

다음으로는 for문에 특이한 것이 하나 보이는데, 문자열의 길이만큼을 돌아야 하는 루프임에도 불구하고 strlen이 아닌 sizeof를 쓰고 있는 것을 볼 수 있습니다. 이 또한 초보자들이 자주 하는 실수에 속합니다.

또한 다중 테스트 케이스 문제인데도 불구하고 개행 문자를 출력하는 곳이 없다는 것 역시 확인할 수 있습니다.

마지막으로 바깥의 while 루프가 도는 횟수를 점검해보면 t번이 아닌 t+1번 돌게 된다는 것 역시 볼 수 있는데, 초보자는 입력이 끝난 뒤 프로그램이 곧바로 종료되어야 한다는 것을 인지하지 못해 예제를 넣어보고도 잘못된 것을 모르는 경우가 많기 때문에 질문에 자주 올라오는 케이스입니다.

2. 소수 구하기

다음 코드는 시작하자마자 틀린 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, i, j;
	bool p[1000000];

	cin >> m >> n;

	for (i = 2; i <= n; i++)
		if (!p[i])
			for (j = i * i; j <= n; j += i)
				p[j] = true;
	for (i = m; i < n; i++)
		if (!p[i])
			cout << i << '\n';
}

이 코드 역시도 p 배열의 크기가 0으로 끝나는 데에서 의심을 해보아야 하고, 실제로 루프들에서 n번째까지 접근하여 배열의 범위를 넘어서는 것을 볼 수 있습니다.

그 다음으로 코드를 쭉 훑다 보면 일관성이 없는 부분이 하나 보이는데, 앞쪽에서는 <= n으로 n 이하까지 보고 있는 반면에 아래에서는 < n으로 n 미만까지 보는 것을 볼 수 있습니다. 문제를 확인해 보면 항상 이하로 하는 것이 맞습니다.

다음으로는 p 배열이 초기화되지 않았고, 입력을 받기 위한 배열이 아니라는 점에서 또 의심을 해보아야 합니다. 역시나, p[j] = true라는 부분은 있지만 나머지 인덱스에 false를 대입한다거나 하는 부분은 없습니다. 나머지 부분에 false가 자연스럽게 들어있을 것이라고 예측하고 있는 코드인 것입니다.¹⁰

또한 에라토스테네스의 체를 구현하는 문제에 특화된 실수가 하나 나오는데, 바로 j = i * i에서 i가 커지면 오버플로우가 발생한다는 점입니다. 이렇게 특정 문제에서 자주 발생하는 실수 등도 기억해두면 좋습니다.

거기에 하나가 더 있는데, 1에 대한 소수 판정을 잘못 내리고 있습니다. 이 역시 에라토스테네스의 체에서만 발생하는 전형적인 실수 중 하나라고 할 수 있습니다.

3. 수 찾기

아래는 8%에서 시간 초과를 받는 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int a[100005];

int f(int n, int x)
{
	int lo = 0, hi = n - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (a[mid] == x)
			return 1;
		if (hi - lo == 1)
		{
			if (a[lo + 1] == x)
				return 1;
			else
				break;
		}
		else if (a[mid] > x)
			hi = mid - 1;
		else
			lo = mid;
	}
}

int main()
{
	int n, m, i, j;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - i - 1; j++)
			if (a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
	cin >> m;
	for (i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		cout << f(n, x) << '\n';
	}
}

시간 초과이니 먼저 시간 복잡도부터 살펴보겠습니다. 눈에 확 띄는 것은 main 함수에서 이중 반복문을 통해 버블 정렬을 하고 있다는 점입니다. 그리고 가장 아래쪽을 보면 cin과 cout이 번갈아서 나타나고 있음에도 cin.tie(0)을 하지 않은 것도 하나의 문제입니다. 또한 f 함수를 보면 return 1을 하는 부분은 있지만 0을 반환하는 부분은 없습니다. 즉, 루프를 그냥 빠져나가면 int를 반환해야 하는 함수가 아무것도 반환하지 않는 undefined behavior가 발생하고, 이 역시 시간 초과의 원인이 될 수 있습니다.¹¹

질문자가 여기까지 고쳐서 아래와 같이 코드를 수정했는데, 여전히 시간 초과가 난다고 합니다.

#include <bits/stdc++.h>
using namespace std;

int a[100005];

int f(int n, int x)
{
	int lo = 0, hi = n - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (a[mid] == x)
			return 1;
		if (hi - lo == 1)
		{
			if (a[lo + 1] == x)
				return 1;
			else
				break;
		}
		else if (a[mid] > x)
			hi = mid - 1;
		else
			lo = mid;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, i, j;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	cin >> m;
	for (i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		cout << f(n, x) << '\n';
	}
}

그렇다면 남은 부분은 하나뿐입니다. 이분 탐색에서 무한 루프를 돌지 않는지를 확인해보아야 합니다. 언뜻 보기에 조금 불필요하게 복잡하게 생긴 면도 있고, hi를 내리는 부분과 lo를 올리는 부분이 비대칭적인 것도 눈에 띕니다. 그런데 hi - lo == 1인 경우까지 걸러냈는데도 무한 루프에 걸릴 수 있을까요? 이 모든 것을 피해가는 케이스가 있는지 생각해봅시다. 만일 lo == mid인데 lo = mid가 실행된다면 이전과 동일한 상태일 테고, 그러면서 hi - lo == 1이 아닌 경우가 있다면 무한 루프에 빠지게 될 것입니다. 이 문제점만을 정확하게 꼬집는 최소 케이스를 만들어봅시다.

1
1
1
2

이런 케이스라면 질문자도 쉽게 문제점을 깨닫고 수정할 수 있을 것입니다.