문제 해결 과정
1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
체계적인 접근을 위한 질문들
1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까? == 무식하게 풀 수 있을까?
3. 내가 문제를 푸는 과정을 수식화할 수 있을까?
4. 문제를 단순화할 수 없을까? == 문제를 좀 더 쉽게 만들어 볼 순 없을까?
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
8. 뒤에서부터 생각해서 문제를 풀 수 있을까?
9. 순서를 강제할 수 있을까?
10. 특정 형태의 답만을 고려할 수 있을까? == 답 후보의 유한한 갯수만을 고려
코딩과 디버깅에 관하여
1. 간결한 코드를 작성하기
2. 적극적으로 코드 재사용하기 == 코드 모듈화
3. 표준 라이브러리 공부하기
4. 항상 같은 형태로 프로그램을 작성하기 == 반복문의 일관된 사용, 배열의 전달 방법
5. 일관적이고 명료한 명명법 사용하기
6. 모든 자료를 정규화해서 저장하기 == 모든 분수는 기약분수로, 각도를 양수로만 표현
7. 코드와 데이터를 분리하기 == 데이터는 배열로 만들어서 정리
자주 하는 실수
1. 산술 오버플로
2. 배열 범위 밖 원소에 접근 == array[n]이면 0~n-1
3. 일관되지 않은 범위 표현 방식 사용하기
4. 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로
7. 다차원 배열 인덱스 순서 바꿔 쓰기
8. 잘못된 비교 함수 작성 == <, >
9. 최소, 최대 예외 잘못 다루기
10. 연산자 우선순위 잘못 쓰기
11. 너무 느린 입출력 방식 선택
12. 변수 초기화 문제 == 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 사용
스캐폴딩 코드
//우리가 테스트하고 싶은 정렬 함수
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();
//두 개의 복제를 만들어서 하나는 우리의 정렬 함수로, 하나의 표준 라이브러리로
//정렬한다.
vector<int> mySorted = input;
mySort(mySorted);
vector<int> reference = input;
sort(reference.begin(), reference.end());
if(mySorted != reference) {
cout << "Mismatch!" << endl;
cout << "Input: " << toString(input) << endl;
cout << "Expected: " << toString(reference) << endl;
cout << "Got: " << toString(mySorted) << endl;
break;
}
}
}
산술 오버플로
어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우
너무 큰 결과
프로그램이 출력해야 할 결과가 우리가 흔히 사용하는 32비트 자료형의 범위를 넘어가면 64비트 정수를 사용하거나 큰 정수 구현을 이용해야 한다.
너무 큰 중간 값
프로그램의 출력값의 범위는 작지만 중간과정에서 큰 값을 일시적으로 계산해야 하는 경우
너무 큰 '무한대' 값
무한대의 값을 어떤 큰 유한한 값으로 대체할 때 너무 큰 값으로 잡으면 안 됨
오버플로 피해가기
1. 캐스팅을 이용
2. 연산의 순서를 바꾼다. - 먼저 빼거나 나눈다.
3. 계산의 순서를 바꾼다.
실수 자료형의 이해
실수 == 근사값
=> 두 개의 실수값을 비교할 때에는 어느 정도의 오차는 염두해두어야 한다.
1. 오차의 한도를 상황에 맞게 설정한다.
2. 상대 오차를 이용한다.
relativeError(a, b) = |a-b| / max( |a|, |b| ) <= 큰 수를 비교할 때 유용
//절대 오차와 상대 오차를 모두 이용해서 두 수가 같은지 판정한다.
bool doubleEqual(double a , double b) {
double diff = fabs(a - b);
//절대 오차가 허용 범위 안일 경우 무조건 true를 반환한다.
if(diff < 1e-10) return true;
//이 외의 경우레는 상대 오차를 사용한다.
return diff <= 1e-8 * max(fabs(a), fabs(b));
}
대소 비교
연산 오차에 의해서 거짓이 될 값이 참이 될 수 있다.
코드의 수치적 안정성 파악하기
프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다.
