[Algorithmic Problem Solving Strategies] 3. 코딩과 디버깅에 관하여

알고리즘 문제 해결 전략 세트 국내도서 저자 : 구종만 출판 : 인사이트 2012.11.23 상세보기

알고리즘 문제 해결 전략 세트구종만 상세보기

 

3.1 코딩의 중요성을 간과하지 말라

============

3.2 좋은 코드를 짜기 위한 원칙

============
간결한 코드를 작성하기
————————
적극적으로 코드 재사용하기

• 코드를 모듈화
  ————————
• 표준 라이브러리 공부하기*
• 언어의 문자열
• 동적배열
• 스택, 큐, 리스트, 사전...(자료구조)
• 정렬
  ————————
• 항상 같은 형태로 프로그램을 작성하기*
  ————————
• 일관적이고 명료한 명명법 사용하기*
• 모호하지 않은 변수명&함수명
• 사용하는 언어의 표준 라이브러리에서 사용하는 명명규약(naming convention)
  ————————
• 모든 자료를 정규화해서 저장하기*
• 예)
  기약분수로 표현: 9/6, 3/2 미묘한 버그를 만들 수 있음(각각의 문자열 표현이 달라지고, 해시 값이 달라짐)
  각도 표현: -30도, 330도, 690도
• 시간: UTC(협정세계시간, Coordinated Universal Time)
• 문자열: UTF-16, UTF-8
• 자료를 입력받거나 계산하자마자

  자료를 표현하는 클래스의 생성자
  외부에서 자료를 입력받자마자 수행

———————

코드와 데이터를 분리하기

• 코드의 논리와 상관없는 데이터는 가능한 한 분리
  ————————

3.3 자주하는 실수

===========
산술오버플로
————————
배열 범위 밖 원소에 접근
————————
일관되지 않은 범위 표현 방식 사용하기

• 프로그램 내에서 여러 가지의 범위 표현 방식을 섞어쓰는 경우가 있음
• 닫힌 구간(closed interval): [2,12]

  단점) 공집합표현X

• 열린 구간(open interval): (2,12)

  단점) 배열의 첫번째 원소부터 사용하고 싶을 때, 첫번째 원소 이전에 존재하는 가상의 원소 사용

• 반열린구간(half-open interval): [2, 12)

————————
Off-by-one 오류
————————
컴파일러가 잡아주지 못하는 상수 오타
————————
스택 오버플로

• 대개 재귀 호출의 깊이가 너무 깊어져 옴
• 스택의 최대 크기

  컴파일이나 실행시 설정가능
  언어나 아키텍처 등에 따라 매우 다름 - 대회에서 사용하는 환경의 스택 허용량에 대해 알아두어야 함

————————

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

• 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋음
  ————————

잘못된 비교 함수 작성

• 연산자의 성질strict weak ordering

  비반사성irreflexvity
  a<a는 항상 거짓
  비대칭성asymmetry
  a<b 참 -> b<a는 거짓
  전이성transitivity
  a<b 참 && b<c 참 -> a<c

• 상등 관계의 전이성transitivity of equivalence
  a<b 거짓 && b<a 거짓 -> a==b
a==b && b==c -> a==c
  ————————

최소, 최대 예외 잘못 다루기

• 코드를 짤 때 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할 지 생각
  ————————

연산자 우선순위 잘못쓰기

• 시프트 연산자, 비트 단위 연산자
  ————————
• 너무 느린 입출력 방식 선택*
  ————————
• 변수 초기화 문제*
  ————————

3.4 디버깅과 테스팅

==========
잘 분리된 기능적인 코드 - 눈으로 디버깅 하기 쉬움
————————
디버거를 사용해도 좋은 경우)

• 프로그램이 런타임 오류를 내고 종료하는 경우
  ————————
• 눈으로 디버깅 방법)*
• 작은 입력에 대해 제대로 실행되나 확인
• 단정문(assertion) 쓰기: 주어진 조건이 거짓일 때 오류를 내고, 프로그램을 강제 종료시키는 함수 or 구문
• 프로그램의 계산 중간 결과를 출력
  ————————
• 테스트*
• 주어진 예제 입력을 바꾸기
• 있을 수 있는 가장 작은/큰 입력 넣어서 시간 안에 실행되는지, 답은 잘 나오는 지
• 스캐폴딩Scaffolding

  코드의 정당성을 확인 || 반례 찾음
  다른 코드를 개발 할 때 뼈대를 잡기 위해 임시로 사용하는 코드
  웹) 실제 자료를 추가하는 부분을 작성하지 않고도 다른 부분을 개밠할 수 있도록 DB를 쉽게 조작할 수 있게 해주는 프로그램

3.5 변수 범위의 이해

==========

산술 오버플로

• 어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어난 경우(값이 너무 작을 때도 포함됨)
  ————————
• 너무 큰 결과*
• 32비트 자료형의 범위를 넘어 갔을 때, 그대로 32비트를 사용하는 경우(64비트, 큰 정수 구현 이용하기)
  ————————
• 너무 큰 중간 값*
• 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우
  ————————
• 너무 큰 ‘무한대’ 값*
  ————————
• 오버플로 피해가기*
• 더 큰 자료형 쓰기
  ————————
• 자료형의 프로모션*
• 피연사자의 자료형이 다르거나 범위가 너무 작은 경우, 컴파일러들이 대개 이들을 같은 자료형으로 변환해서 계산
• java) 부호 없는 정수 지원 X
• c#) size(): 부호 있는 정수로 반환
  ————————

3.6 실수 자료형의 이해

==========

실수 연산의 어려움
————————
실수와 근사값

• 컴퓨터의 모든 실수 변수는 정확도가 제한된 근사값을 저장
• 어떤 순서로 / 컴파일러 최적화 여부 등
  ————————
• IEEE 754 표준: 실수 연산에 관한 규정, 오버플로와 언더플로의 처리, 반올림에 관한 규정 등을 포함*
• 이진수로 실수를 표기
• 부동 소수점(floating-point) 표기
• 무한대, 비정규 수(subnormal number), NaN(Not a Numer) 등 특수한 값이 존재
  ————————
• 실수의 이진법 표기*
  ————————
• 부동 소수점(소수점을 움직이는 실수 표기법) 표기*
• 소수점을 옮긴 후, 1을 제외 한 나머지를 저장하는 방식으로
• 실수 변수에 저장되는 정보

  부호비트sign bit: 양수인지 음수인지 여부(1bit)
  지수exponent: 소수점을 몇 칸 옮겼나()
  가수mantissa: 소수점을 옮긴 실수의 최상위 X비트
  ————————

• 실수 비교하기*
• 1) 비교할 실수의 크기들에 비례한 오차 한도를 정한다.
• 2) 상대 오차를 이용한다.
  ————————
• 대소비교*
  ————————
• 정확한 사칙연산*
• 항상 십진수로 정확히 표현할 수 있다면 큰 정수 변수에서 소숫점위치를 옮길 수 있는 십진수 클래스(java의 BigDecimal) 사용
  ————————
• 코드의 수치적 안정성(numerically) 파악하기*
  ————————
• 실수 연산 아예 하지 않기*
• 곱셈과 나눗셈의 순서를 바꾸기

  결과가 항상 정수라는 것을 알고 있을 때

• 양변 제곱하기
• 실수 좌표를 써야 하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리기

+) 더 읽을 거리: Clean Code