'맞았습니다'가 뜨지 않는 이유..

최근 백준 온라인 저지(boj.kr)를 활용하여 알고리즘 문제를 중점적으로 풀면서 겪었던 에러를 몇 가지 기록하고자 한다.

 

알고리즘 문제를 풀다 보면 정말 단순한 이유나 오타에서부터 생각지도 못한 에러까지 다양한 원인으로 인해 1시간 넘게 삽질하는 경우가 빈번하게 발생한다.

 

부딪혔던 문제들의 원인을 잘 기억하고 해결 방법을 숙지해서 같은 실수를 반복하지 말자!!

---

1. 런타임 에러(Runtime Error)

 : 프로그램이 비정상적으로 종료된 경우 발생한다.

 

런타임 에러에는 다양한 원인이 존재하지만, 나는 OutOfBounds, Segfault 두 가지의 런타임 에러를 경험해 보았다.

근데 사실 이 두 개가 가장 대표적이고 대중적인 런타임 에러인 것 같다.

 

 A. OutOfBounds

 : 배열, 벡터 등 컨테이너에서 할당한 경계를 넘어가는 경우 발생.

 

- 대표적으로 두 가지의 경우가 있다.

  1 ) 문제의 조건보다 작은 크기로 컨테이너를 선언하여 할당된 범위를 넘어가는 경우.

  2 ) 반복문, 재귀 호출 등을 통해 배열에 인덱스로 접근할 때, 특히 그래프 탐색하며 컨테이너의 다음 칸으로 이동할 때

      할당 범위를 초과하는 경우.

 

※ 문제를 풀면서 컨테이너의 크기나 반복 조건 등을 생각하면서 size를 정하지만 input 값이 커지면 할당 범위를 초과할 수 있는 경우가 발생하기도 한다. 이를 잘 고려하여 변수 값을 설정하여야 한다.

 

 B. Segfault

 : Segmentation fault 줄임말로, 잘못된 메모리를 참조하였을 때 발생

허용되지 않은 방법으로 메모리에 접근하거나, 허용되지 않은 메모리 영역에 접근할 때 발생하여 다른 데이터가 오염되는 것을 방지한다.

 

예시)

scanf("%d",arr[i]);

위와 같이 scanf 함수를 사용하여 배열에 값을 저장할 때 & 를 붙이지 않는 경우, 주소 값을 통해 변수(arr 배열)의 메모리에 제대로 접근하지 못해 Segfault 에러가 발생한다.

---

2. 컴파일 에러

 

test case를 실행해본 후 제출하는 경우, 컴파일 에러는 대부분 간단하게 해결할 수 있다.

내가 겪은 컴파일 에러는 아래의 두 가지 경우밖에 없다.

 

 a. 백준 온라인 저지의 컴파일러(g++ (GCC) 11.1.0)와 다른 컴파일러를 사용하여 푼 경우.

 b. 전역에서 지역변수를 사용하거나 이미 정의되어 있는 변수(size, max 등)나 메소드를 호출하는 등 사실상 오타가 발생한 경우.

error: reference to ‘size’ is ambiguous   // 이미 정의되어 있는 이름을 사용한 경우 뜨는 에러 메시지.

 

경고 메시지(Warning)가 떠도 컴파일만 성공하면 제대로 잘 채점된다. 

에러 메시지를 잘 읽어보면 쉽게 해결할 수 있을 것이다!

---

3. 메모리 초과

말 그대로 문제에서 주어진 메모리를 초과한 경우 발생한다.

 

A. 최악의 경우 사용해야 하는 메모리를 계산해보고 문제의 조건과 비교해본다.

B. 만약, 조건을 넘어가게 된다면 동적 할당을 활용하거나 동적 할당을 기반의 컨테이너(vector,queue 등)를 사용한다.

C. 동적 할당을 활용하더라도 반복 호출, 재귀 등으로 인해 메모리를 초과할 수 있기 때문에 조건 값을 잘 설정해야 한다.

---

4. 시간 초과

알고리즘 문제를 풀 때, 연산 시간은 1억 번의 연산 = 1초 정도로 어림짐작한다. (feat. 휴리스틱)

 

c++에서 cin, cout을 사용하는 경우, 웬만하면 다음과 같은 방법을 사용하여 시간을 단축하는 것이 좋다.

 

가장 중요한 것은 문제의 의도와 조건에 알맞게 STL에서 제공하는 탐색 속도가 높은 컨테이너를 사용하거나 이분 탐색, DP 등 다양한 알고리즘을 십분 활용하여 로직을 설계하고 구현하는 것이다.

 

---

5. 틀렸습니다.

'틀렸습니다'는 프로그램 자체는 정상적으로 종료되었지만 틀린 결과(오답)를 출력하는 경우 발생한다.

 

나의 경우 문제에서 발생할 수 있는 특별한 경우, 예외 상황 등을 인지하지 못한 상태에서 코드를 구현하여 '틀렸습니다'를 자주 받았다.

 

문제에서 제공하는 test case 외의 다양한 예외 상황, 내 코드의 반례를 찾아보고 구현해야 한다.

 

문제를 분석하고 어떻게 풀어나갈지 고민하는 초기에 최대한 예외 상황이 없는 코드를 작성하는 것이 베스트이며

 

중간중간에 간단한 print test 등을 하며 코드를 완성해나가는 것이 이상적인 problem solving 이 될 것이다!

 

※ int형의 범위를 초과하는 값을 int형 변수에 넣은 경우와 같이 자료형을 잘못 지정한 경우에 뜨기도 한다. 

---

 

출력 형식, 출력 초과 등 다른 종류의 에러도 있지만 이는 대부분 오타에서 비롯되기 때문에 생략하였다. 최근 한 달여간 바짝 알고리즘 공부를 하며 부딪혔던 문제들을 간단하게 정리해보았다

화이팅!!