📌 목차
1. Intro. 코딩의 중요성을 간과하지 말라!!!
2. 좋은 코드작성을 위한 원칙
3. 자주하는 실수
4. Debugging. &. Testing
5. 변수범위의 이해
1. Intro. 코딩의 중요성을 간과하지 말라!!!
코딩테스트 및 대회에서 코드를 빨리 작성하는 것보다 더욱 중요한 것은 뭘까?
바로 "읽기 쉬운 코드"를 작성하는 것이다.
복잡하고 가독성이 떨어지는 코드는 디버깅도 어렵고 한번에 정확히 작성하기도 어렵기 때문이다.
많은 전문가들은 반복적 연습으로 자신의 코드 스타일을 간결하고 일관되고 다듬기 위해 노력한다.
본 글에서는 코딩과 디버깅에 관한 노하우와 코딩테스트에서 자주하는 실수에 대해 다룬다.
2. 좋은 코드작성을 위한 원칙
간결한 코드 작성
짧고 간결한 코드는 오타나 단순버그가 생길 확률을 줄이고 쉬운 디버깅을 가능케한다.
C/C++의 경우, #define을 이용한 매크로 방법으로 반복문처럼 우리가 자주 타이핑 하는 코드를 빠르게 표현하는 경우를 예로 들 수 있다.
#define FOR(i,n) for(int i=0; i < (n); i++) bool hasDuplicate(const vector<int>& array){ FOR(i, array.size()) FOR(j, i) if (array[i] == array[j]) return true; return false; }물론, 위와 같은 방법은 속된말로 "에바"라고 생각할 수도 있다.
하지만, 위와 같은 방법은 아래와 같은 실수를 예방할 수 있다.
다만, 이런 방법은 가끔 사용하면 아주 유용하지만for (int i=0; i < array.size(); i++) for (int j=0; j < i; i++) // j++이어야함
일종의 "대치동의 어둠의 스킬"같은 느낌이기에 신중히 사용할 것이 권장된다.
적극적인 코드 재사용
간결한 코드를 작성하기 위한 가장 직접적인 방법은 코드를 "모듈화"하는 것이다.
같은 코드 반복시(약 3번이상), 이들을 함수나 클래스로 분리해 재사용하는 것이다.
시간이 없다해서 코드를 더 알기 쉽게 고치는 것을 주저하는 것은 아니된다.
계속 눈이 코드의 간결성에 익숙하게 하여 다음 코딩에 좀 더 간결한 코딩을 가능케한다.
표준 라이브러리 공부
C++의 표준라이브러리, STL의 경우 문자열, 동적배열, 스택, 큐, 리스트, 딕셔너리 등의 자료구조와 정렬 등의 표준 알고리즘 구현을 직접하는 것이 아닌, 구현 사용법에 익숙해진다면 이를 활용해 더욱 빠른 코드작성이 가능하다.
항상 같은형태로 작성
while문을 쓰던자리에 do-while문을 사용해본다던지 하는 등을 말한다.
이는 시간이 지나면서 점점 실수의 원인이 될 수 있는만큼 지양하는 편이 좋다.
일관∙명료한 명명법 사용
int a[30][30], i, j, k=0;위와같은 코드는 모호하지 않은 변수명과 함수명의 예시이다.
보통, 사용언어에 맞는 naming convention을 익히는 것을 추천한다.(예를 들어 CamelCase)
모든 자료를 정규화
같은 자료를 2가지 형태로 저장하지 않는 것이다.
예를 들어 유리수 표현클래스 Fraction의 경우, 기약분수로 표현하는 것이 좋다.
(9/6과 3/2로 표현하는 방법이 달라지면 표현하는 변수가 달라질 수 있기 때문.)
코드와 데이터를 분리
날짜를 다루는 프로그램을 작성한다 가정하자.
처음 코딩하는 사람들의 경우, 위와 같이 작성할 것이다.string getMonthName(int month){ if (month == 1) return "Jan"; if (month == 1) return "Feb"; ... if (month == 12) return "Dec"; }
하지만, 이는 연차가 쌓일수록 기피하는 코드가 되는데, 코드의 논리와 상관없는 데이터는 분리하는 쪽이 낫다.
예를들어, 아래처럼 월의 영어이름을 아래처럼 table로 생성할 수 있다.
const string monthName[] = {"Jan", "Feb", ... , "Dec"};
이 기법의 또 다른 좋은 예시로 체스와 같은 보드게임이 존재한다.
const int KnightDx[8] = {2,2,-2,-2,1,1,-1,-1}; const int KnightDy[8] = {1,-1,1,-1,2,2,2,-2};
3. 자주하는 실수
산술 Overflow
계산과정에서 변수의 표현범위를 벗어나는 값을 사용하는 것으로 Section 5에서 좀 더 상세히 다룬다.
배열범위 밖 원소에 접근
C/C++은 배열원소 접근 시, 별도로 확인하지 않기에 범위를 벗어난 위치값에 접근하는 버그는 아주 찾기 힘들다.
다만, 이때 Run-time stack등을 건드려 프로그램이 Run-Time-Error를 내고 종료될 때, 이를 알아챌 수 있다.
하지만, 오류가 나지 않으면서 틀린 답만 내놓는 경우도 종종 있기에 이런 실수를 예방하기 위해서는 배열크기를 정할 때, 계산을 신중하게 하는 것이 가장 중요하다.
일관되지 않은 범위표현방식의 사용
배열의 잘못된 인덱스를 참조하는 오류가 발생하는 큰 원인 중 하나.
2~12를 프로그램내에서 표현해보자.
2 ≤ i ≤ 12도 되고 1 < i < 13도 되며,이 두가지 방법에는 모두 나름의 장단점이 존재한다.
닫힌구간의 문제는 공집합을 우아하게 직관적으로 표현할 수 없다는 점이고
열린구간의 문제는 배열의 첫원소부터 시작하는 법위를 표현시, 첫원소 이전의 가상원소를 사용해야한다.
따라서 프로그래밍언어는 대부분 이 둘 사이의 절충인 반열린구간(half-open-interval)을 사용한다.
0 ≤ i < n
ex)
[C++]: begin()은 첫원소를 가리키지만, end()는 마지막원소 다음의 가상의 원소를 가리킨다.
[Python]: a[4:8]은 a[4]~a[7]의 원소를 의미.
Off-by-One 오류
계산의 큰 줄기는 맞지만, 하나가 모자라거나 하나가 많아서 틀리는 코드로 발생하는 모든 오류들을 가리킨다.
예를들어 <, > 연산자와 ≤, ≥연산자를 혼동해 원소를 하나 더 적게나 많이 순회하는 경우도 이 예시에 포함된다.
ex) 100미터에 10미터 간격으로 기둥을 세운다 가정하자.
이때, 필요한 기둥은 10개가 아닌, 11개이다.
Compiler가 못잡는 상수오타
변수명이나 함수명에서 낸 오타는 컴파일러에서 잡는다.
하지만 각종 상수에 대한 오타로 오답처리될 수 있다.
Stack Overflow
프로그램 실행 중, call stack이 overflow해 프로그램이 강제종료 되는 것.
stackoverflow는 대개 재귀호출의 깊이가 너무 깊어지게될 때 발생한다.
C++의 경우, 지역변수로 선언한 배열이나 클래스인스턴스가 기본적으로 stack memory를 사용하기에 특히나 stackoverflow를 조심해야한다.
따라서, 대부분 heap에 메모리를 할당하는 STL container를 사용하거나 전역변수를 사용한다.
다차원 배열인덱스 순서바꿔쓰기
심심찮게 4, 5차원 이상의 고차원 배열 사용 시, 한두군데 인덱스의 순서를 헷갈려 잘못쓰는 일이 있다.
특히, 이후 다루는 동적 계획법(DP; Dynamic Programming)를 위한 memoization 패턴을 사용 시 이런 일이 잦은데, 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.
잘못된 비교함수의 작성
위의 함수의 경우, 정수의 집합을 저장하는 IntegerSet클래스에 대해 vector<IntegerSet>에 담긴 집합들을 순서대로 처리하기 위한 함수로 operator overloading을 이용해 < 연산자를 오버로딩한다.// a가 b의 진부부분집합이면 true bool isProperSubset(const IntegerSet& a, const IntegerSet& b); // a가 b의 진부분집합일 때, a가 항상 앞에 오도록 집합을 정렬 bool operator < (const IntegerSet& a, const IntegerSet& b){ if (isProperSubset(a,b)) return true; if (isProperSubset(b,a)) return false; return false; ]
위 함수의 경우, 어떤 문제가 있을까?
대부분 사람들은 isProperSubset()의 구현을 찬찬히 살피고 테스트 해볼 것이다.
하지만 아무런 문제가 없다는 것을 알게되면, 어떻게 해결해야할 지 막막해진다.
operator < 의 경우, a<b와 b<a가 모두 거짓이라면, a와 b를 같은 값으로 간주한다.
즉, a,b와 b,c가 같다면 a와 c도 같아야 한다. (상등관계의 전이성)
이 성질을 만족시키지 못하는 것을 알 수 있다.
이를 해결하기 위해 코드를 수정하면 아래와 같다.
위의 코드처럼, 애초에 크기비교 및 사전순 비교만으로 충분한 문제에 복잡한 비교함수사용은 실수를 유발하니 유의하는 것이 좋다.bool operator < (const IntegerSet& a, const IntegerSet& b) { if (isProperSubset(a,b)) return true; if (isProperSubset(b,a)) return false; if (a.size() != b.size()) return a.size() < b.size(); return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); }
최대∙최소 예외 잘못 다루기
예외란, 우리가 예상한 입력규칙에 들어맞지 않는 모든 입력이다.
이때, 가능한 입력 중 최소값과 최대값이 예외가 되는 문제들은 생각외로 많다.
ex) 자연수를 입력받아 소수(prime number)인지 판정하는 함수로 예를 들어보자면,
bool isPrime(int n) { if (n%2==0) return false; // 짝수는 소수가 아님 for (int i = 2; i < n; i++) if (n%i==0) return false; // 2이상, n미만의 약수가 있으면 소수가 아님 return true; // 통과 시 소수 }오류 1) 모든 짝수를 소수가 아니라고 판단한 것. (반례: 2)
따라서 2를 별도로 처리해야한다.
bool isPrime(int n) { if (n == 2) return true; // 2는 소수임 if (n%2==0) return false; // 짝수는 소수가 아님 for (int i = 2; i < n; i++) if (n%i==0) return false; // 2이상, n미만의 약수가 있으면 소수가 아님 return true; // 통과 시 소수 }아직 오류가 있는 곳이 있을까?
따라서 1에 대해서도 별도로 예외처리가 필요하다.
소수인 가장 작은 입력에 대해 확인했으니, 소수가 아닌 가장 작은 입력도 생각해봐야한다.
소수가 아닌 가장 작은 자연수는 1로, for문도 실행되지 않고 건너뛰어 true를 반환해버린다.
이처럼, 예외는 꼼꼼히 처리하기 쉽지 않다는 것을 알 수 있다.
연산자 우선순위의 오사용
사칙연산은 혼동하는 일이 적다.
하지만, 시프트연산자나 비트단위연산자들의 우선순위는 종종 헷갈리게 된다.
예를 들어보자.
이 if문은 얼핏 b의 최하 비트가 0일 때 참으로 보인다.if(b & 1 == 0)
하지만 bit단위 연산자 &의 우선순위는 비교연산자 ==보다 낮다.
따라서 아래처럼 해석된다.
if (b & (1 == 0))
결과적으로 위의 조건문은 항상 거짓이 된다.
(1 == 0)은 항상 False(즉, 0의 값)를 갖는다.
따라서 헷갈리는 경우, 괄호를 적절히 감싸는 것이 중요하다.
너무 느린 입출력방식
cin 의 사용은 고수준 입력방식을 사용할 수 있어 코드가 간단해진다.
하지만 이에 따른 속도저하 또한 클 수 있다.
따라서 아래와 같은 방법으로 입력을 받기 전에 수행하는 것이 좋다.
cin.sync_with_stdio(false);
변수 초기화 문제
대부분의 코딩테스트에서 한번에 여러개의 입력에 대해 답을 처리하라 요구한다.
이때, 이전 입력에서 사용한 전역변수값을 초기화하지 않고 그대로 사용하는 것은 문제가 된다.
4. Debugging. &. Testing
Debugging
프로그램을 작성하고 예제입력에 대해 원하는 결과와 다르게 나왔을 때, 보통 Debugger를 활용한다.
Debugger는 물론 유용한 도구지만, 프로그래밍 대회나 테스트에서는 이런 유용성이 제한된다.
따라서 Debugger없이 프로그램의 버그를 찾아내는 연습이 필요하다.
보통 Debugger사용 대신, 아래 단계가 추천된다.
1. 작은 입력에 대해 제대로 실행되나 확인 2. 단정문(assertion) 사용 3. 프로그램의 계산 중간결과를 출력
Testing
많은 경우, 예제입출력 외에도 몇가지 간단한 입력을 직접 만들어 넣어보면 오답률을 줄일 수 있다.
프로그램 테스트 시, 유용한 기법은 스캐폴딩(scaffolding)이 있다.
스캐폴딩이란, 다른 코드 개발 시, 뼈대를 잡기위해 임시로 사용하는 코드이다.
아래는 정렬함수를 테스트하는 스캐폴딩 코드이다.
void mySort(vector<int>& array); // 주어진 배열을 문자열로 바꾼다. string toString(const vector<int>& array); int main(){ while(true) { // 임의의 입력 생성 int n = rand()%100 + 1; vector<int> input(n); for (int i=0; i<n; i++) input[i] = rand(); // 2개의 복제를 생성 // 하나는 우리의 정렬함수로, 하나는 STL로 정렬 vector<int> mySorted = input; mySort(mySorted); vector<int> ref = input; sort(ref.begin(), ref.end()); // 만약 다르면 오류를 내고 종료 if (mySorted != ref) { cout << "MisMatch!" << endl; cout << "Input: " << toString(input) << endl; cout << "Expected: " << toString(ref) << endl; cout << "Got: " << toString(mySorted) << endl; break; } } }작은 입력을 여러개 수행하며 더 빠른 코드의 문제를 찾아내는데 유용하다.
5. 변수범위의 이해
Arithmetic Overflow
컴퓨터의 가장 대표적 제한은 유한성이다. 컴퓨터의 모든 변수에는 답을 담을 수 있는 크기가 제한되어 있다.
이때, 수학적/논리적으로 완전히 정당한 알고리즘도 예상과 다르게 동작가능한데, 이 문제를 일으키는 흔한 원인이 바로 산술 오버플로(arithmetic overflow)다.
산술오버플로는 어떤 식의 계산값이 반환되는 자료형의 표현가능범위를 벗어나는 경우이다.
상당히 많이 저지르는 실수 중 하나인데, 여기에는 크게 2가지 이유가 있다.
1. 대부분의 프로그래밍언어들은 사칙연산과정 중 overflow가 발생해도 별다른 경고가 없다.
(연산이 일어날 때마다 overflow를 확인하는 것은 너무 비효율적이기 때문)
2. 프로그램의 정당성을 검증할 때, 프로그램 논리의 정확성에만 집중하면 산술오버플로 등장사실을 잊기 쉽다.
다만, STL 등의 제공으로 산술오버플로를 신경 쓸 일이 크게 줄어들었지만 이런 클래스들은 훨씬 많은 Cost를 차지한다.
너무 큰 결과
당연하게도 32bits자료형의 범위를 넘어가면 64bits정수나 더 큰 정수구현을 이용해야한다.
이때, 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 들여야한다.
너무 큰 중간값
산술오버플로가 문제가 되는 또다른 경우는 무엇일까?
프로그램의 출력값의 범위는 작지만 중간과정에서 큰 값을 일시적으로 계산해야하는 경우이다.
ex)
int gcd(int a, int b); // 두 수의 최대공약수 반환 int lcm(int a, int b) { return (a*b) / gcd(a,b); }위의 코드로 lcm(50000, 100000)을 계산해보자.
사실 반환값은 간단하게도 100000이며 이는 32bits보다 작은 수이기에 잘 계산될 것 같다.
하지만 위의 코드는 14100을 출력한다.
위의 경우, a×b의 값은 5×109가 된다. 이 값은 signed_int_32bit의 최대치를 가뿐히 넘긴다.
이때, C++은 아무 경고를 하지도 않기에 이런 버그를 찾기는 힘들다.
너무 큰 '무한대'값
프로그램을 작성시, 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 존재한다. (최단경로 문제.)
무한대 값을 선택 시, 무한대값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 이럴 때도 overflow가 나지 않을 크기의 값을 선택하는 것이 좋다.
Overflow 심화
그렇다면 overflow발생사실을 알았을 때, 어떻게 코드를 고쳐야할까?
가장 간단한 방법은 "더 큰 자료형"을 사용하는 것이다.
int lcm(int a, int b) { return (a * (long long)b) / gcd(a,b); }
'Gain Study > Algorithm문해전' 카테고리의 다른 글
| [Gain_Study_종만북]01. 문제해결 시작하기 (0) | 2023.09.04 |
|---|
