알고리즘 문제 풀이 디버깅시 주의할점

알고리즘 문제 풀이 디버깅시 주의할점

(오답노트 형식으로 계속 추가되는 게시글 입니다.)

 

분명 컴파일 오류도 없고, 논리적으로도 문제가 없음에도 오답판정이 난다면 다양한 오류를 고려하며 디버깅해야 한다. 그런데 이떤 오류들은 굉장히 찾기 어려운 경우들도 있다. 그래서 문제 풀이시 발생할 수 있는 오류 특히, 직관적으로 찾기 어려운 오류들을 정리하고자 한다. 오답의 원인을 알 수 없는 경우 아래의 사항을 점검해 보자.

1. 오버플로 발생여부

• 계산 결과 뿐만 아니라 계산 중간중간 오버플로가 발생할 수도 있으니 최종 결과값 뿐만 아니라 중간계산 과정의 값들의 최댓값을 반드시 점검하자.

2. INF 값의 크기 문제

• 문제를 풀다보면 INF 값을 설정해야할 때가 있다. INF는 풀이과정에 나오는 수들 중 가장 큰 수보다 더 큰 수로 지정해야 한다. 그런데 INF값에 충분히 큰 값을 설정 하지 않으면 풀이 과정에 나오는 수가 INF를 넘어설 수 있다. 반대로 INF + INF를 계산해야하는 경우도 있다. 그런데 INF + INF에서 오버플로가 발생하여 음수가 될 수도 있다. 그래서 INF값은 적당한 크기로 설정하는 것이 필요하다. (문제마다 다르겠지만 987,654,321 같은 수가 많은경우에서 INF 값으로 적당한 크기이면서 눈으로 자리수를 확인하기도 쉽다.)
  • 사례: BOJ 11404 이 문제에서 이동 할 수 없는 도시간의 거리를 INF로 표현했는데 INF 값이 충분히 크지 않아서 INF 가 갱신되었음.

3. 실수형의 부정확함

• float은 최대 6자리의 정확도를 가지고 있다. 실수를 사용해야한다면 반드시 double을 사용하자. double로도 부족하다면 long double을 사용해야한다.
  • 사례: BOJ 2108 이 문제에서 디버깅만 한 시간 했는데 결국 float의 부정확함으로 인한 오류였음. float을 double로 변경후 문제가 해결됐다.

4. 중복 값에 대한 처리

• 중복값에대한 별다른 언급이 없다면 중복값이 들어올 수 있다. 중복값이 들어올 경우 어떻게 처리할지 로직을 함께 고민해야한다. 영어 문제에서는 distinct로 값이 고유하다고 표현할 수 있다.

5. 경계값 확인

• 주어진 값의 범위의 경계값을 잘 확인한 후 경계값에서 잘 동작하는지 확인이 필요하다. 예를들어  BOJ 10830 문제에서 1,000보다 작거나 같은 값이 입력으로 주어진다고 하였다. 그런데 출력값에 1,000을 나눈 나머지값을 출력해야한다. 그래서 계산 중간에 모든 값들은 1,000보다 작아지지만, 아래와 같은 반례 처럼 중간 계산을 하지 않을 경우 1,000이 그대로 출력되어서 오답처리가 될 수 있다.

input
2 1
1000 1000
1000 1000

answer
0 0
0 0

 

• BFS등 탐색을 해야하는 문제에서 시작값과 탐색목표가 동일할 수 있다. 이럴경우에도 별도의 예외가 필요할 수 있다.

6. 에러가 발생하지 않는 오타

에러가 발생하지 않는 오타의 경우에도 찾기가 어렵다. 다음과 같은 경우를 점검해 보자.

출력단어 오타

• 데이터가 존재하지 않을 경우 "no"를 출력해야하는데 "NO"를 출력했다거나 "February"를 출력해야 하는데 "Febuary"를 출력한 경우 디버깅에서는 알 수 없고, 출력창을 확인해서도 쉽게 찾을 수 없는 오류에 속한다. 가능하다면 예제 출력을 직접 복사해와서 사용하는 방법을 사용하자.

대입 연산자 오타

• 비교연산자들 계속 사용하다보면 실수로 대입연산자를 사용해야할 때 비교연산을 사용하는 경우가 발생할 수 있다. 이 또한 에러가 발생하지 않기 때문에 찾기 어려운 오류에 속한다.

if (graph[i][k] == 1 && graph[k][j] == 1)
{
    graph[i][j] == 1;    // == 이 아니라 = 사용
}

7. 연산자 우선순위 문제

간결한 코드를 작성하기 위해서 여러 연산자들을 연속해서 사용할 때가 있다. 그런데 연산자들의 우선순위를 잘못 생각할 경우 예상치 못할 경우 예상치 못한 결과가 나온다. 아래의 코드를 보자.

int answer{};
while (num /= 2 > 0) 
    answer++;

위 코드의 의도한 바는 num을 2로 나누고, 나눈 값이 0보다 클 경우 반복문을 시행하는 것일테지만, 안타깝게도 무한루프에 빠진다. 왜냐하면 /= 연산보다 >연산이 우선 진행되어서 num /= 1 와 같은 결과가 되기 때문이다. 위 코드는 괄호를 사용하여 아래와 같이 수정해야한다. 연산자 우선순위를 모두 파악하고 있는것이 가장 좋지만 가급적 괄호를 사용해서 명시적으로 기입하자.

int answer{};
while ((num /= 2) > 0) 
    answer++;