728x90
3. 자주하는 실수
1. 산술 오버플로
계산 과정에서 변수의 표현범위를 벗어나는 것
2. 배열 범위 밖 원소에 접근
C/C++는 배열의 원소에 접근할 때 해당 인덱스가 배열 범위 안에 있는지를 별도로 확인해 주지 않는다.
int array[10], t;
이때 변수 array[10] 위치에 값을 대입하면 엉뚱하게도 t에 있던 값이 덮어씌워집니다.
(C/C++ 컴파일러들은 스택에 선언된 지역 변수의 순서를 바꿀 수 있기 때문에 항상 그런 것은 아니다.)
가장 좋은 방법은 배열의 크기를 정할때 계산을 신중히 하는것이다.
3. 일관되지 않은 범위 표현 방식 사용하기
닫힌 구간과 열린 구간
닫힌 구간 : 범위 내의 첫 번째 값과 마지막 값으로 해당 범위를 표현하는 것입니다.
열린 구간 : 양 끝의 경계를 포함하지 않는 집합입니다.
장단점
닫힌 구간 단점 : 공집합을 우아하게 표현할 수 있는 방법이 없다는 것.
열린 구간 단점 : 배열의 첫 번째 원소부터 시작하는 범위를표현하고 싶을 경우 첫 번째 원소 이전에 존재하는 가상의 원소를 사용해야 한다.
대부분의 프로그래밍 언어는 첫 번째 값을 집합 안에 포함하고 다른 하나는 집합 안에 포함하지 않는 반 열린 구간을 사용합니다.
- C++ STL에서는 반복 자로 범위를 표현할 때 첫 원소를 가르키는 반복자와 마지막 원소 다음 위치를 가르키는 반복자를 사용합니다. STL 자료 구조에서 모든 원소를 갖는 범위는 첫 번째 원소를 가르키는 begin(), 마지막 원소 다음에 있는 가상의 위치를 가르키는 end() 로 표현한다.
- 자바의 SortedSet 인터페이스는 범위를 fromElement와 toElement로 전달 받는데 fromElement는 포함되지만 toElement는 포함되지 않는다.
- 파이썬에서는 a[4:8]과 같은 문법으로 잘라낼 수 있는데 이렇게 잘라내면 a[4]~a[7]까지 포함하는 부분을 얻을 수 있다.
장점
- 첫번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간을 쉽게 표현 할 수 있습니다.
- 두 구간이 연속 해 있는지를 쉽게 알 수 있습니다. [a,b),[c,d)가 연속해 잇는지를 보려면 b=c and a=d로 확인할 수 있다.
- 구간의 크기를 쉽게 알수 있다. [a,b)의 구간에 포함된 자연수의 수는 b-a가 됩니다.
4. Off-by-one 오류
계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리킵니다.
최소 입력이 주어졌을 때 이 코드가 어떻게 동작할지를 되새겨 보면서 프로그램을 짜는 것입니다. 담장의 길이가 0미터라도 기둥을 하나는 박아야 하듯이
5. 컴파일러가 잡아주지 못하는 상수 오타
변수명이나 함수명에서 낸 오타는 컴파일러가 잡아 주기 때문에 프로그램을 짤 때 오타에 대해서는 걱정하지 않는 경우가 많습니다. 하지만 각종 상수를 잘못 입력해서 문제가 오답 처리되는 경우가 있다.
6. 스택 오버플로
프로그램의 실행 중 콜 스택이 오버플로해서 프로그램이 강제종료되는 것 또한 흔히 하는 실수입니다.
프로그래밍 대회를 공부하면서 재귀 호출을 사용할 일이 굉장히 많기 때문에 늘 유의하는 것이 좋습니다.
c++의 경우에는 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본적으로 스택 메모리를 사용하기 때문에 스택 오버플로를 조심해야 합니다.
배열 등의 큰 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽다.
때문에 대부분의 참가자들은 자동으로 힙에 메모를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 사용하곤 합니다.
7. 다차원 배열 인덱스 순서 바꿔 쓰기
프로그래밍 대회에서는 심심찮게 4,5차원 이상의 고차원 배열을 쓰게 됩니다. 배열을 이곳저곳에서 접근하다 보면 인덱스의 순서를 헷갈려서 잘못쓰는 일이 흔히있습니다. 특히 동적 계획법을 위한 메모이제이션 패턴을 사용할 떄 이런 일이 잦은데, 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋습니다.
8. 잘못된 비교 함수 작성
사용자가 작성한 클래스를 정렬할 때는 정렬 함수에 비교 함수를 전달하거나, 연산자 오버로딩을 이용해 < 연산을 오버로딩해야 한다.
1. a<a는 항상 거짓입니다. 이 성질을 비반사성이라고 합니다 .
2. a<b가 참이면 b<a는 거짓입니다. 이 성질을 비대칭성이라 합니다.
3. a<b가 참이고 b<c가 참이면 a<c입니다. 이 성질을 전이성이라고 합니다.
4. a<b, b<a가 모두 거짓이면 a,b는 값은 값으로 간주합니다. 이 성질을 상등 관계의 전이성이라고 합니다.
또 하나 실수하기 쉬운 부분은 자바의 표준 라이브러리가 <연산 대신에 <= 연산을 비교 함수의 모델로 쓴다는 것입니다.
9. 최소, 최대 예외 잘못 다루기
최소 / 최대 예외는 코드를 짤 떄 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해 보면 오류를 잡을 수 있는 경우가 꽤 있습니다.
10. 연산자 우선순위 잘못 쓰기
사칙연산의 우선순위는 잘알지만 시프트 연산자나 비트 단위 연산자들의 우선순위는 종종 헷갈리게 마련입니다.
연산자의 우선순위들을 잘 기억해 두거나, 헷갈릴 경우에는 괄호로 적절히 감싸는 것입니다.
11. 너무 느린 입출력 방식 선택
C++에서는 gets()를 이용해 모든 입력을 문자열 히나로 읽어들인 뒤 파싱할 수도 있고, cin 등의 고수준 입력 방식을 사용할 수도 있다.
해결방안 : 자신이 사용하는 언어에서 어떤 입출력 방식이 지원되는지를 확인하고, 어느 쪽이 빠른지를 미리 점검해세요.
12. 변수 초기화 문제
흔한 실수는 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 그대로 사용하는 것입니다.
해결방안 : 완전하지는 않지만 이런 실수를 예방하기 위한 팁은 예제 입력 파일을 두 번 반복해 쓰시는 것입니다.
728x90