2022.07.13

p51~100

 

자주 하는 실수 

1. 산술 오버플로

2. 배열 범위 밖 원소에 접근 

3. 일관되지 않은 범위 표현 방식 사용하기 (반열린구간으로 통일하기 [a,b))

4. Off by one 오류 (계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 오류)

5. 컴파일러가 잡아주지 못하는 상수 오타 

6. 스택 오버플로 (재귀 호출의 깊이가 너무 깊어져서 옴. 대회에서 사용하는 환경의 스택 허용량 알아둘 필요 있음. C++의 경우 자동으로 힙에 메모리를 할당하는 STL 컨테이너 사용하거나 전역 변수 사용하기)

7. 다차원 배열 인덱스 순서 바꿔 쓰기

8. 잘못된 비교 함수 작성 -> 크기 비교, 사전순 비교만을 사용하더라도 충분한 문제에 복잡한 비교 함수를 작성하지 말자. 

+연산자의 성질(strict weak ordering)

1.  a < a 는 항상 거짓이다. 비반사성

2. a < b  가 참이면 b < a 는 거짓이다. 비대칭성

3. a< b 가 참이고 b < c 가 참이면 a < c 이다. 전이성

4. a < b 와 b < a 가 모두 거짓이면 a 와 b는 같은 값으로 간주한다. a 와 b 가 같고 b와 c가 같다면 a와 c도 같아야 한다. 상등 관계의 전이성

9. 최소 최대 예외 잘못 다루기 (최소 값과 최대 값이 예외가 되는 문제들이 생각 외로 많으니 최소 최대에 대해 제대로 동작할지를 생각해 보면 오류를 잡는 경우가 꽤 있음)

10. 연산자 우선순위 잘못 쓰기 (괄호 적극 활용)

11. 너무 느린 입출력 방식 선택 (cin 등의 고수준 입력 방식을 사용할 경우 코드가 간단해지지만 속도 저하 큼. 입출력 양이 많을 때는 어떤 입출력 방식을 선택하는지가 프로그램의 정답 여부 바꿈)

12. 변수 초기화 문제 (이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 그대로 사용하는 경우) 예방 팁: 예제 입력 파일 두 번 반복해서 쓰기

 

디버깅 

프로그래밍 대회에서는 디버거 없이 디버깅하는 연습이 필요함. 

디버거 쓰기 전 거치면 좋은 단계들 

1. 작은 입력에 대해 제대로 실행되나 확인하기

2. 단정문 쓰기

3. 프로그램의 계산 중간 결과 출력하기

단 프로그램이 런타임 에러를 내고 종류하는 경우, 언어에서 스택 기록을 출력해 주는 경우가 아니라면 디버거 사용해 간단히 알아낼 수 있음.

테스팅 

예제 입출력 외 몇 개 간단히 테스트 해 보기. 이때 사용 가능한 기법 = 스캐폴딩. 임의의 입력값을 자동으로 생성해 프로그램을 돌려 보고 답안을 검증하는 프로그램 짜보기. 단 꼭 필요한 경우에만 쓸 것. 

 

산술 오버플로

어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우 

1. 너무 큰 결과 (64비트 정수를 32비트에 담는다는 등)

2. 너무 큰 중간값 (출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우)

3. 너무 큰 '무한대' 값

 

오버플로 피해가는 법

1. 더 큰 자료형을 쓴다.

2. 문제에 따라 계산 방법을 다르게 한다. (ex. 이항 계수 계산 시 점화 식 이용해 팩토리얼 계산 피하기) 

 

자료형의 프로모션

피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러가 같은 자료형으로 변환해서 계산하는 것. 

 

실수와 근사 값

컴퓨터의 모든 실수 변수는 정확도가 제한된 근사 값을 저장한다. 

 

IEEE 754 표준 <- 실수 표기 방식

1. 이진수로 실수 표기

 소수점 및 i 번째 자리의 크기는 1/2^i 이 된다. 

2. 부동 소수점 표기법

 32비트 중 첫 16비트는 정수부, 뒤 16비트는 소수부로 쓰는 식으로 실수 표현 가능. 이해하기 쉽지만 저수부에 많은 비트를 사용하면 소수부의 정확도가 떨어지는 등의 문제 발생. 64비트 쓰는 것 추천. 

실수 변수는 부호 비트, 지수, 가수를 저장함. 

부호 비트: 양수인지 음수인지 여부

지수: 소수점을 몇 칸 옮겼나

가수: 소수점을 옮긴 실수의 최상위 x 비트 

<->고정 소수점 실수 표기법

3. 무한대, 비정규 수 등의 특수한 값 존재 

 

실수 근사값 저장으로 인한 오류 해결 법 두 가지

1. 비교할 실수의 크기들에 비례한 오차 한도를 정한다. 

입력의 최대치와 최소치를 예측할 수 있고 여기에서 오차 한도의 상한과 하한을 이끌어낼 수 있는 경우에는 이 안에서 적절한 값을 사용하면 됨. 만약 이런 계산을 하기 힘든 경우라면

2. 상대 오차를 이용한다.

문제의 입력으로 몇 자리 수가 주어질지 모르는 상황 -> 비교하는 숫자들의 크기에 비례하여 오차를 정하는 방식 사용해야 함. 두 숫자의 크기에 비해 그 차이가 작다면 두 수가 같다고 판정하는 식.  but 매우 작은 식 비교에서는 문제가 나타날 수 있음. 

 

대소 비교 문제

비교할 때 항상 두 값이 같은 경우, 아주 가까운 경우를 먼저 확인하고 처리해 주어야 함. 

 

정확한 사칙연산 일정 범위 크기를 갖는 숫자를 다룰 경우에는 실수도 사칙 연산 정확히 이루어짐. 추가적인 자료구조 도입해서 정하ㅗㄱ한 사칙연사 구현할 수도 있음. 

 

수치적으로 안정적인 코드에서는 실수의 정확도 문제 고려하지 않아도 됨. 프로그램이 수치적으로 안정적이다 = 프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다.

 

결론: 실수 연산은 아예 하지 않는 편이 좋다. 제대로 하기 어려우니까. 

우회 방법

1. 곱셈과 나눗셈 순서 바꾸기

2. 양변 제곱하기

3. 실수 좌표를 써야 하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리기 

 

알고리즘 = 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법

소스 코드가 알고리즘을 정의하는 것이 아니다. 알고리즘은 문제를 해결하는 방법 그 자체를 가리키므로 완전히 달라보이거나 다른 언어로 쓰인 프로그램이라고 해도 같은 원리에 따라 동작한다면 같은 알고리즘을 사용한다고 할 수 있다. 알고리즘은 컴퓨터가 따라할 수 있도록 자세히 설명한 과정을 나타내므로 모호하고 주관적인 것은 알고리즘이라 할 수 없다. 

 

알고리즘을 평가하는 두 가지 기준 

1. 시간

더 빠르게 동작하는가

2. 공간 

더 적은 용량의 메모리를 사용하는가

 

이 둘은 서로 상충하는 경우가 많다. 단 프로그래밍 대회에서 더 중요한 것은 시간이다. 

 

프로그램의 실행 시간과 알고리즘의 속도는 다르다. 

 

알고리즘의 수행 시간은 반복문이 지배한다. 

지배한다 = 한 가지 항목이 전체의 대소를 좌지우지한다.

 

알고리즘의 수행 시간은 종류가 매우 다양함! 

선형 시간 알고리즘 

중복된 계산 없애기. 수행 시간이 입력값에 정비례하면 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 된다. 따라서 이런 알고리즘을 선형 시간 알고리즘이라고 한다. 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.

선형 이하 시간 알고리즘 

입력으로 주어진 자료에 대해 우리가 미리 알고 있는 지식을 활용할 수 있을 때 가능. 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘

이진 탐색 

오름차순으로 정렬된 배열 A[] 와 찾고 싶은 값 x 가 주어질 때 A[i-1]<x<A[i] 인 i 를 반환한다. 이때 A[-1] = -무한대, A[N] = 무한대로 가정한다.