[알고리즘 문제해결전략] 3.코딩과 디버깅에 관하여 - 2

[알고리즘 문제해결전략] 3.코딩과 디버깅에 관하여 - 2

1. 변수 범위의 이해

1. 산술 오버 플로우

• 수학적/논리적으로는 완전히 정당한 알고리즘도 프로그램으로 구현했을 때는 예상과 다르게 동작하는 경우가 있다. 흔한 원인이 산술 오버 플로우

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

• 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 별다른 경고를 해주지 않는다.

• 프로그램의 정당성을 검증할 때 프로그램의 논리의 정확성에만 집중하다 보면 산술 오버플로가 등장할 수 있다는 사실을 잊기 쉽다.

2. 너무 큰 결과

• 프로그램이 출력해야할 결과가 우리가 흔히 사용하는 32비트 자료형의 범위를 넘어가면, 64비트 정수를 이용하거나 큰 정수 구현을 이용해야 한다.

• 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 들이도록 해야한다.

3. 너무 큰 중간 값

• 프로그램의 출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우.

• 코드의 논리를 보는 것만으로는 중간에 산술 오버플로가 일어난 것을 알 수 없다.

4. 너무 큰 무한대 값

• 예를 들어, 두 위치를 잇는 가장 짧은 길의 길이를 구하는 코드에서, 어떤 구간도 잇는 경로가 없을 때 특수한 값으로 예외 처리를 한다. 해당 테크닉을 쓸 때 하기 쉬운 실수는 해당 자료형이 처리할 수 있는 가장 큰 값을 무한대 값으로 쓰는 것.

• 이 때, 무한대 값을 선택할 때, 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 이럴때도 오버플로가 나지 않을 크기의 값을 선택하는 것이 좋다.

5. 오버플로 피해가기

• 제일 간단한 방법은 더 큰 자료형을 사용하는 것.

• 계산 방법을 달리하기. 예를 들어, nCr을 정의대로 풀지 않고, 점화식으로 풀면, 중간에 오버플로 값이 나오지 않게 처리할 수 있다.

6. 자료형의 프로모션

• 사칙연산이나 대소 비교 등의 이항 연산자들은 두 개의 피 연산자를 받는다. 만약 피 연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산하는데, 이를 프로모션이라고 한다.

• 가끔 알기 어려운 버그를 만드는 주역이 된다.

• C++ 프로모션 규칙

  1. 한쪽은 정수형이고 한쪽은 실수형일 경우: 정수형이 실수형으로 변환됨.
  2. 양쪽 다 정수형이거나 양쪽 다 실수형일 경우, 보다 넓은 범위를 갖는 자료형으로 변환됨.
  3. 양쪽 다 int형보다 작은 정수형인 경우 양쪽 다 int형으로 변환됨.
  4. 부호 없는 정수형와 부호 있는 정수형이 섞여있을 경우, 부호 없는 정수형으로 변환됨.

2. 실수 자료형의 이해

1. 실수와 근사값

• 컴퓨터의 메모리는 유한하고, 모든 값들을 정확하게 담을 수는 없으니 어쩔 수 없이 비슷한 값을 사용하는 것으로 만족해야 한다.

• 근사 값으로 연산한 결과는 수학적으로 정확하지 않을 수 있기 때문에, 실수는 훨씬 다루기 까다롭다.

2. IEEE 754 표준

• 이진수로 실수를 표기
• 부동 소수점 표기법
• 무한대, 비정규 수 , NaN(Not a Number) 등의 특수한 값이 존재
• 실제로 IEEE 754는 실수 연산에 관한 규정, 오버플로와 언더플로의 처리, 반올림에 관한 규정 등을 모두 포함하는 방대한 표준.

3. 실수의 이진법 표기

• 실수의 이진법 표기는 조금만 검색해보면 알 수 있으므로 생략
• 대부분의 기본서에 다 나와있다.
• 부동 소수점 표기에 대해서도 기본적인 자료구조기초 책에 충분히 나와있으니 공부하면 됨.

4. 실수 비교하기

• 이진법으로 표현할 수 없는 형태의 실수는 정확한 값이 아니라 근사 값으로 저장되는데, 이때 생기는 작은 오차가 계산 과정에서 다른 결과를 가져온다.

• 비교할 실수의 크기들에 비례한 오차한도를 정함으로써 문제를 해결할 수 있다.

• 상대오차를 이용하는 방법도 있다. 비교하는 숫자들의 크기에 비례하여 오차를 정하는 방식인데, 두 숫자에 비해 차이가 작다면 두 수가 같다고 판정하는 것.

5. 대소비교

• 두 수의 대소를 비교할 때도 연산 오차가 발목을 잡을 수 있다.
• 이런 경우는 항상 두 값이 같은 경우, 즉 두 값이 아주 가까운 경우를 먼저 확인하고 처리해주어야 한다.

6. 코드의 수치적 안정성 파악하기

• 수치적으로 안정적인 코드에서는 실수의 정확도 문제를 고려하지 않아도 된다.
• 어떤 프로그램이 수치적으로 안정적이라는 말은 프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다는 말.
• 어떤 프로그램의 실행 중 한 연산 결과와 정확한 값이 0.0000001 만큼 차이 났는데, 프로그램이 모두 실행된 후 18000만큼 차이가 난다면, 수치적으로 불안정하다고 말한다.

7. 실수 연산 아예 하지 않기

• 가장 좋은 방법은 아예 실수 연산을 하지 않는 것이다.
• 의외로 많은 경우, 얼핏 봐서는 실수 연산을 써야만 할 것 같은 문제들에 적절한 변형을 가해 실수 연산을 없앨 수 있다.

---

[출처] 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(인사이트), 구종만