[알고리즘 문제 해결 전략] 코딩과 디버깅에 관하여
알고리즘 문제 해결 전략
알고리즘을 공부하면서 문제에 대한 암기보다, 알고리즘 자체에 대한 개념을 학습하기 위해 읽기 시작한 책이다.
3장 코딩과 디버깅에 관하여
도입: 코딩의 중요성을 간과하지 말라
알고리즘 능력도 중요하지만 기초가 되는 코딩능력도 매우 중요하다.
실상 프로그래밍 대회에서 빠르게 짜기 위한 스파게티 코드를 짠다고 생각할 수 있지만, 좋은 성적을 올리기 가장 좋은 방법은 읽기 쉬운 코드를 작성하는 것이다.
복잡하고 읽기 어려운 코드는 디버깅도 어렵고, 한 번에 정확하게 작성하기도 어렵기 때문이다.
실제 입상자들의 코드는 반복적인 연습을 거쳐 일관된 코드 스타일을 갖추고 있다.
좋은 코드를 짜기 위한 원칙
대회에서 작성하는 코드나 실무에서 작성하는 코드나 좋은 코드의 조건은 크게 다르지 않다.
이 내용은 차라리 다른 좋은 코드관련 책을 참고하는 게 더 좋다. (너무 방대함 클린 코드같은)
간결한 코드를 작성하기
프로그래밍 대회에서 코드를 작성할 때의 첫 번째 원칙은 가장 간결한 코드를 작성하라는 것이다.
코드가 짧으면 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅 시간도 줄어든다.
그렇다고 닌자코드는 x
하지만 대회에 따라 일반적인 경우보다 한발짝 더 나아간 방법들을 사용할 수 있다.
대표적으로 광법위한 변수의 사용이 있다. (전역)
다른 예로는 C++의 매크로를 사용하는 것이다.
적극적으로 코드 재사용하기
간결한 코드를 작성하기 위한 가장 직접적인 방법은 코드를 모듈화하는 것이다.
코드가 반복된다면 이를 함수나 클래스로 분리하여 재사용한다.
대회의 급박한 상황이라도 코드를 더 알기 쉽게 만들어주는 모듈화를 주저해서는 안된다.
물론 그렇다고 실무에서 작성하듯이 코드를 작성할 수는 없다.
표준 라이브러리 공부하기
간결한 코드를 작성하기 위해 또 다른 원칙은 표준 라이브러리를 사용하는 것이다.
항상 같은 형태로 프로그램을 작성하기
대회에 참가하다 보면 여러 종류의 코드를 반복적으로 짜게 된다. (이분법, 그래프 너비 등등)
코드를 검증한다는 것은 그렇게 쉬운일이 아니기에 항상 같은 형태로 프로그램을 작성하는 것이 좋다.
일관적이고 명료한 명명법 사용하기
int a, i, j;
이런 선언문은 실무에서라면 낙제감이고, 프로그래밍 대회라고 다르지 않다.
모호하지 않은 변수명과 함수명을 사용하는 버릇을 들이고, 사용하는 언어의 표준 명명법을 따르는 것이 좋다.
모든 자료를 정규화해서 저장하기
쉽게 말해 사용자가 오용할 수 있는 자료형은 만들지 않는 것이 좋다.
이런 이유로 자료를 정규화하는 것이 좋다.
코드와 데이터를 분리하기
코드의 논리와 상관 없는 데이터는 가능한 한 분리하는 것이 좋다.
예로 영어 달에 맞는 테이블, enum을 만들어 사용하거나 체스말의 경우 움직일 수 있는 방향을 미리 저장해두는 것이다.
자주 하는 실수
같은 실수를 반복하기보다는 실수에서 배우는 것이 좋고, 그보다 더 좋은 것은 남의 실수로부터 배워 유사한 실수를 저지르지 않는 것이다.
산술 오버플로
가장 자주 등장하는 실수는 계산 과정에서 변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로이다.
배열 범위 밖 원소에 접근하기
다음으로 흔하게 등장하는 실수는 배열 범위 밖 원소에 접근하는 것이다.
0, 1의 혼동으로 인한..
일관되지 않은 범위 표현 방식 사용하기
배열의 잘못된 위치를 참조하는 오류가 발생하는 원인 중 하나로, 프로그램 내에서 여러 가지의 범위 표현 방식을 섞어 쓰는 경우가 있다.
열린 구간과 닫힌 구간의 각기 다른 이점 때문에 이런 실수가 발생한다.
off-by-one 오류
off-by-one오류는 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류를 가리킨다.
길이가 100미터인 담장에 10미터 간격으로 울타리 기둥을 세운다고 한다면 몇개가 필요할까?
정답은 11개다.
이 처럼 더 적게, 더 많이 순회하거나 반 열린 구간과 닫힌 구간을 혼동하여 사용하는 경우가 그렇다.
컴파일러가 잡아주지 못하는 상수 오타
변수명이나 함수명에서 낸 오타는 컴파일러가 잡아 주기 때문에 프로그램을 짤 때 오타에 대해서는 걱정하지 않는 경우가 많다.
스택 오버플로
프로그램의 실행 중 콜 스택이 오버플로해서 프로그램이 강제로 종료되는 경우가 있다.
대개 재귀 호출의 깊이가 너무 깊어져서 오는데, 프로그래밍 대회에서는 매우 많기 때문에 이런 점은 늘 유의하는 것이 좋다.
다차원 배열 인덱스 순서 바꿔 쓰기
평소에는 2차원 이상의 배열을 사용할 일이 없지만, 알고리즘 풀이에선 자주 고차원 배열을 필요로 한다.
잘못된 비교 함수 작성
정렬이나 우선순위 큐를 사용할 때는 비교 함수를 작성해야 한다.
최소, 최대 예외 잘못 다루기
예외란 말 그대로 예상한 입력 규칙에 들어맞지 않는 모든 입력이다.
이러한 문제는 생각보다 많이 발생함으로 가장 작은 입력과 큰 입력에 대해서 생각해보면 도움이 될 수 있다.
연산자 우선순위 잘못 쓰기
사칙연산의 경우는 잘 알고 있어서 드물지만, 시프트 연산자나 비트 단위 연산자들의 우선순위는 종종 헷갈리기 마련이다.
if (b & 1 == 0)
if (b & (1 == 0))
실제로는 위와 아래가 같은 코드이다. (즉 모르면 괄호를 쳐라)
너무 느린 입출려 방식 선택
c++의 cin같은 고수준입력 방식
자신이 사용하는 언어에 따라 다르지만 입력이 1만개가 넘어간다면 저수준의 입출력을 알아두는 것이 좋다.
변수 초기화 문제
프로그램을 한 번만 실행하고, 한 번에 여러 개의 입력에 대해 답을 처리하라고 요구한다.
이 때 값을 초기화하지 않고 사용하기 때문에 문제가 된다.
디버깅과 테스팅
디버깅에 관하여
프로그램을 작성하고 예제 입력을 실행해 보니 원하는 결과가 다르게 나왔다.
이 때 대부분의 사람들은 IDE에 맞게 디버거를 키고 실행과정을 따라간다.
- 알고리즘 문제의 경우 길이가 길지 않기에 한줄 씩 읽어 내려가며 검증이 가능하다. (눈이 더 빠른 경우가 있음)
- 재귀나 중복 반복문의 경우 디버깅이 적합하지 않다.
따라서 디버거 없이 버그를 찾아내는 연습이 필요하다.
- 작은 입력에 제대로 실행되나 확인하기
- 단정문을 쓴다.
- 프로그램의 계산 중간 결과를 출력한다.
위 방법으로도 버그를 찾을 수 없을 때 디버거를 사용해도 좋다.
테스트에 관하여
대회에서 답안을 작성 후 예제 입력을 만들어 가능한 한 많이 프로그램을 테스트하는 것이 좋다.
있을 수 있는 가장 큰 값과 작은 값을 넣어 보고 시간안에 실행되는지, 답은 잘 나오는지 보는 것
유용한 기법으로는 스캐폴딩이라는 기법으로 정당성을 확인하거나 반례를 찾는데 특히 유용하다.
수백개의 입력으로 자동으로 테스트할 수 있도록 하는 것
변수 범위의 이해
산술 오버플로
컴퓨터는 실세계와 다르게 변수의 제한이 있다.
따라서 수학적/논리적으로 완전히 정당한 알고리즘이라도 예상과 다르게 동작하는 경우도 있다.
이 원인이 바로 산술 오버플로로 어떤 식의 계산 값이 반환되는 자료형의 표현 가능 범위를 벗어나는 경우를 말한다.
- 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 별다른 경고를 해주지 않는다. (연산마다 확인하는 것이 매우 비효율적)
- 프로그램의 정당성을 검증할 때 프로그램의 논리의 정확성에만 집중하다 보면 산술 오버플로를 간과하기 쉽다.
너무 큰 결과
프로그램이 출력해야 할 결과가 흔히 사용하는 32비트보다 큰 경우가 종종 있다.
그럴 땐 64비트로 교체를 해줘야 하지만, 실수가 꽤 발생한다.
너무 큰 중간 값
산술 오버플로가 문제가 되는 또 다른 대표적인 경우는 프로그램의 출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우다.
너무 큰 ‘무한대’깂
프로그램을 짜다 보면 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 있다.
오버플로 피해가기
가장 간단한 방법은 더 큰 자료형을 사용하는 것이다.
두 번째 방법으로 오버플로가 나지 않도록 연산의 순서를 바꾸는 것이다. (중간 값의 경우 약수이니 먼저 나눠서)
자료형의 프로모션
사칙연산이나 대소 비교 등의 이항 연산자들은 두 개의 피연산자를 받는다.
만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산하는데, 이를 프로모션이라고 한다.
C#의 경우엔 컨테이너의 크기가 부호 있는 정수로 반환되기에 고려하지 않아도 된다.
실수 자료형의 이해
실수 연산의 어려움
실수의 연산의 위험성은 다들 경험해봤으리라 생각된다.
실수와 근사 값
정수는 컴퓨터가 모두 정확하게 표현할 수 있지만, 실수는 조금 다르다.
컴퓨터의 모든 실수 변수는 정확도가 제한된 근사값을 저장한다.
값이 다양한 요인에 따라 매번 변화하기 때문에 이를 명확하게 이해하는 것이 중요하다.
IEEE 754 표준
가장 많은 컴퓨터/컴파일러들에서 사용되는 실수 표기 방식은 IEEE 754 표준이다.
- 이진수로 실수를 표기
- 부동 소수점 방식으로 표기
- 무한대, 비정규 수, NaN(Not a Number) 등의 특수한 값들이 존재
실수의 이진법 표기
이 부분은 검색하여 표기법을 참고하는 게 좋다.
부동 소수점 표기
실수 비교하기
위 사실을 이해한다면 처음 나온 예제가 매번 다른 값이 나오는 것을 이해할 수 있다.
실수는 정확한 값이 아니라 근사 값으로 저장되는데, 이 때 생기는 작은 오차가 다른 결과를 가져오는 것
하나. 비교할 실수의 크기들에 비례한 오차 한도를 정한다
많은 경우 우리는 코드가 다루는 값의 범위를 예측할 수 있다.
그렇다고 해도 오차 한도 값은 신중하게 결정해야 한다.
둘, 상대 오차를 이용한다
문제의 입력으로 한 자리가 주어질지 서른 자리가 주어질지 알 수 없을 때는 오차 한도를 미리 정할 수 없다.
이런 경우는 비교하는 숫자들의 크기에 비례하여 오차를 정하는 방식을 사용해야 한다.
대소 비교
두 수가 같은지를 판단하는 것이 아니라 대소를 판단할 때도 연산 오차가 발목을 잡을 수 있다.
이런 문제를 피하려면 비교할 때 항상 두 값이 같은 경우, 다시 말해 두 값이 아주 가까운 경우를 먼저 확인하고 처리해야 한다.
정확한 사칙연산
실수 변수라고 해서 그 값이 항상 정확하지 않은 것은 아니다.
IEEE 표준에 의해 실수 변수들은, 정확하게 표현할 수 있는 값이 항상 정확하게 저장하도록 구현되어 있다.
코드의 수치적 안정성 파악하기
실수 문제가 이처럼 복잡하지만 수치적으로 안정적인 코드에서는 실수의 정확도 문제를 고려하지 않아도 된다.
경고
책에서 다룬 내용 말고도 컴퓨터에서 실수의 표현은 매우 방대하고 복잡한 내용이다.
매우 한정적인 이야기만 다루었으니 다 안다고 생각하고 접근하면 안된다.
실수 연산 아예 하지 않기
실수 연산을 가장 제대로 하는 방법은 하지 않는 것이다.
마무리
2장과 마찬가지로 필요할 때 찾아서 읽어야 하는 부분이다.
지금은 대략적으로 머리속에 들어가 있지만, 실제로 문제를 만나야 경험이 쌓이기 때문이다.
댓글남기기