[Algorithm Strategies] 1-3. 코딩과 디버깅

Loopy·2023년 7월 5일

알고리즘 해결 전략

목록 보기

2/7

[목차]
3.1. 코딩의 중요성을 간과하지 말라
3.2. 좋은 코드를 짜기 위한 원칙
3.3. 자주 하는 실수
3.4. 디버깅과 테스팅
3.5. 변수 범위의 이해
3.6. 실수 자료형의 이해
3.7. 더 읽을 거리

3.1. 코딩의 중요성을 간과하지 말라

반복적인 연습을 거쳐 자신의 코드 스타일을 간결하고 일관되게 다듬으려고 노력해야 한다.

3.2. 좋은 코드를 짜기 위한 원칙

간결한 코드를 작성하기
가장 간결한 코드를 작성하라.
예) 전역변수를 잘 사용하기
적극적으로 코드 재사용하기
코드를 모듈화하자.
같은 코드가 반복된다면 함수나 ㅡㄹ래스로 분리하여 재사용하는 것이 좋다.
같은 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본원칙을 만들면 좋다.
항상 코드를 깔끔하게 작성하고 유지하는 데 신경을 써야, 간결한 코드에 익숙해질 수 있다.
표준 라이브러리 공부하기
표준 라이브러리를 사용하자.
언어의 문자열, 동적 배열, 스택, 큐, 리스트, 사전 등의 자료구조, 그리고 정렬 ㄷㅇ의 표준적인 알고리즘 구현 사용법을 잘 알아두어야 한다.
항상 같은 형태로 프로그램을 작성하기
보통 while문으 쓰던 자리에 do-while무늘 사용해보기도 하고, 2차원 배열의 크기를 세로크기, 가로 크기 순으로 전달하다가 가로 크기, 세로 크기 순으로 전달하기도 한다.
하지만, 이것은 매번 다른 코드를 작성하는 것과 마찬가지이므로 한 번 검증된 코드를 작성하고 이것만을 꾸준히 사용할 필요가 있다.
일관적이고 명료한 명명법 사용하기
모호하지 않은 변수명, 함수명을 사용하는 버릇을 들이고, 사용하는 언어의 표준 라이브러리에서 사용하는 명명 규역을 익혀라. 명명 규약이란 네이밍 컨벤션이라고도 부르는데, 함수나 변수명을 정하는 규칙을 말한다. 언어에 따라 같은 함수명도 addCircle,AddCircle,add_circle등으로 쓰는 방식이 달라질 수 있다.
모든 자료를 정규화해서 저장하기
같은 자료를 두 가지 형태로 저장하지 않는 것이 좋다
예) x축보다 30도 적은 각도를 보고, -30도, 330도, 690등의 여러 방법으로 표현할 수 있으므로 한 가지로 정의해 두지 않으면 각도를 다루는 함수들을 작성하기 힘들다.
또한, 문자열을 다루는 프로그램에서 문자열들의 인코딩이 이것저것 섞여 있는 경우, 외부에서 문자열을 읽어들이자마자 가능한 한 utf-16이나 utf-8인코딩으로 변환해야만 문자열을 다루기 훨씬 편해진다.
정규화는 프로그램이 자료를 입력받거나 계산하자마자 곧장 이루어져야 한다. 이상적으로는 자료를 표현하는 클래스의 생성자에서 정규화를 수행하거나. 외부에서 자료를 입력받자마자 정규화를 수행하는 것이 좋다.
코드와 데이터를 분리하기
코드의 논리와 상관 없는 데이터는 가능한 한 분리하는 것이 좋다.

분리하지 않고 짠 코드
String getMonthName(int month){
 if(month == 1) return "January";
 if(month == 2) return "February";
  ...
  return "December";
}

정수 배열을 선언하여 분리하자.

const string monthName[] = { 'January','February', ... ,"December"
}

3.3. 자주 하는 실수
1. 산술 오버플로
계산 고정에서 변수의 표현 범위를 벗어나는 값을 사용하는 실수
3.5에서 별도로 다루겠다.

배열 범위 밖 원소에 접근

int array[10], t;

이때 array[10]의 위치에 값을 대입하면 즉, 자바에서 배열의 유효한 인덱스 범위를 벗어나는 위치에 값을 대입하려고 한다면, ArrayIndexOutOfBoundsException이 발생한다.
이런 실수를 예방하는 가장 좋은 방법은 배열 크기를 정할 때 계산을 신중히 하는 것이다.

일관되지 않은 범위 표현 방식 사용하기
자바의 SortedSet 인터페이스는 범위를 fromElement와 toElement로 전달받는데, fromElement는 범위에 포함되지만 toElement는 포함되지 않는다.
이러한 선택의 장점은 두 구간이 연속해 있는지를 쉽게 알 수 있다. 두 구간 [a,b)와 [c,d)가 연속해 있는지를 보려면 b=c 혹은 a=d인지만 확인하면 된다.
배열 a[]의 부분 구간의 평균을 구하는 함수 average(A[],i,j)를 만든다고 하면, average()가 반 열린 구간을 입력받는 다면 average(a,0,n-1)을 호출해야 할 것이고, 닫힌 구간을 입력받는다면 average(a,0,n-1)을 호출해야 할 것이다.만약 함수 내에서 사용하는 표현 방법과 함수 밖에서 사용하는 표현 방법이 다르다면 혼동이 발생하므로, 프로그램 내에서는 한 가지 방법으로만 범위를 표현할 필요가 있다.
off-by-one 오류
off-by-one오류는 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리킨다.
예) 길이가 100미터인 담장에 10미터 간격으로 울타리 기둥을 세운다고 하자. 기둥은 10개가 아닌 11개가 필요하다. 정수 배열 A[]가 주어질 때 A[i]부터 A[j]까지의 평균을 구한다고 할 때, 합은 얼마로 나누어야 할까? j-i가 아니라 j-i+1로 나누어야 한다. 또한, 담장의 길이가 0미터라도 기둥은 하나 박아야하고, A[1]부터 A[1]까지의 평균을 구할 땐 0이 아니라 1로 나누어야 한다.
컴파일러가 잡아주지 못하는 상수 오타
각종 상수를 잘못 입력해서 문제를 잘 풀어 놓고도 오답 처리되는 경우가 있다.
흔히 실수하는 것들 아래를 보자.
3.2절에서 설명한 바와 같이, 코드와 데이터를 분리하기 위해 데이터를 별도의 상수 배열에 저장하는 것은 좋으나, 여기에 오타가 발생하여 멀쩡한 코드만 한잠 디버깅할 수도 있다.
출력한 문자열 상수를 잘못 쓸 수도 있다. 예를 들어 전부 대문자로 써야하는데, 첫 글자만 대문자로 쓰는 경우
계산해야 할 값이 아주 큰 경우 큰 수 M으로 나눈 나머지를 대신 계산하는 문제들이 있는데, 이때 M은 10000007같이 큰 상수들로 지저오디는데, 0의 개수를 틀리게 쓰거나 할 수도 있다.
64비트 정수형에 들어갈 상수를 쓰면서 해당 상수가 64비트라고 지정하지 않는 실수 또한 종종 볼 수 있다.
스택 오버플로
콜 스택 (call stack)이 오버플로해서 프로그램이 강제종료되는 것 또한 흔히 하는 실수이다. 스택 오버플로는 대개 재귀호출의 깊이가 너무 깊어져서 온다. 스택 초대 크기는 컴파일이나 실행시에 설정할 수 있고 기본 값이 언어나 아키텍처 등에 따라 매우 다르기 때문에 대회에서 사용하는 환경의 스택 허용량에 대해 알아 둘 필요가 있다.
다차원 배열 인덱스 순서 바꿔 쓰기
4,5 이상의 고차원 배열을 쓰게 될 때, 이런 경우 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.
잘못된 비교 함수 작성
'<' 연산자의 성질

비반사성 : a<a는 항상 거짓이다.
비대칭성 : a<b가 참이면 b<a는 거짓이다.
전이성 : a<b가 참이고 b<c가 참이면 a<c이다.
상등 관계의 전이성 : a<b와 b<a가 모두 거짓이면 a와 b는 같은 값으로 간주한다. 또한, a와 b가 같고, b와 c가 같다면 a와 c도 같아야 한다.

최소, 최대 예외 잘못 다루기

입력 중 최소 값과 최대 값이 예외가 되는 문제들이 많으므로, 코드를 짤 때 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해보자.

연산자 우선순위 잘못 쓰기

시프트 연산자나 비트 단위 연산자를 섞어쓰는 경우 혼란을 야기한다.
헷갈리면 괄호를 적절히 감싸버리자.

너무 느린 입출력 방식 선택

입출력 양이 많은 경우 프로그래밍 언어에 맞게 빠른 방식을 찾아야 한다.

12.변수 초기화 문제

테스트 케이스가 여러개인 경우, 이전 입력의 전역 변수 값을 초기화하지 않아서 문제가 발생할 수 있다.
가끔 테스트 케이스에서 검증하지 못하는 경우가 있는데, 예제 입력 파일을 두 번 반복해서 실행하면, 예제 간의 의존 관계 때문에 우연히 답이 나오는 경우를 방지할 수 있다.

3.4. 디버깅과 테스팅

1.디버거에 관하여

대회에서 작성하는 소스 코드는 길지 않으므로, 눈으로 디버깅하는 쪽이 훨씬 빠른 경우가 많다.
재귀 호출이나 중복 반복문을 많이 사용하는 복잡한 코드는 디버거로 디버깅하기에 적당하지 않다.
디버거 없이 아래와 같은 단계를 밟으면 좋다.
- 작은 입력에 대해 제대로 실행되나 확인하기 : 오작동하는 가장 작은 입력을 먼저 찾아내자.
- 단정문을 쓰기 : 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문을 쓰자.
- 프로그램의 게산 중간 결과를 출력하기
디버기를 사용해도 좋은 에는 프로그램이 런타임 오류를 내고 종료하는 경우이다.

테스트에 관하여

제출 전에 에제 입력을 만들어 가능한 한 많이 프로그램을 테스트하는 것이 좋다.
예제 입력을 통과하고, 소스코드에서도 오류를 발견하기 어려울 때는 임의의 작은 입력을 자동으로 생성해 프로그램을 돌려보고, 그 답안을 검증하는 프로그램을 짜는 것이 좋다. 이런 프로그램을 스캐폴딩(scaffolding)이라고 한다.

3.5. 변수 범위의 이해
1. 산술 오버플로
어떤 식의 게산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우를 말한다.