algorithm

3. 코딩과 디버깅에 관하여

알고리즘 문제 해결 전략을 읽고 요약했습니다.

3. 코딩과 디버깅에 관하여

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

좋은 성적을 올리기 위한 비결은 당장 빨리 코드를 작성하기 보다 읽기 쉬운 코드를 작성하는 것

  • 복잡하고 읽기 어려운 코드
    • 디버깅이 어렵다.
    • 한 번에 정확하게 작성하기 어렵다.

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

1) 간결한 코드를 작성하기

  • 코드가 짧으면 짧을 수록
    • 오타나 단순한 버그가 사라질 우려가 줄어든다.
    • 디버깅이 쉬워진다.
  • 프로그래밍과 다른 환경을 이용한 Trick
    • 전역 변수 사용하기

2) 적극적으로 코드 재사용하기

  • 간결한 코드를 작성하기 위한 가장 직접적인 방법이다.
  • 같은 코드가 3번 이상 등장한다면 해당 코드를 함수로 분리해 재사용
  • 실무에서는 1 함수 1 기능의 원칙이 있지만 대회에서는…
    • 시간안에 문제를 풀 수가 없다.
    • 대회에서 작성한 코드는 재사용되지 않는다.

3) 표준 라이브러리 공부하기

  • 기본적으로 제공하는 알고리즘, 자료 구조는 직접 구현하지 않는다.
    • 큐, 스택과 같은 자료구조
    • 정렬등의 기초 알고리즘

4) 항상 같은 형태로 프로그램을 작성하기

  • 자주 작성하는 알고리즘이나 코드에 대해서는 한 번 검증된 코드를 작성, 이것만 꾸준히 사용한다.
  • 도구가 아닌 문제에 집중할 수 있다.

5) 일관적이고 명료한 명명법 사용하기

  • 네이밍 컨벤션 잘 지키기
  • 함수의 반환값이 들어나게 이름 짓기
    • judge(...) -> isInsideCircle(...)

6) 모든 자료를 정규화해서 저장하기

  • 같은 자료를 두 가지 형태로 저장하지 않는다.
    • eg 1) 기약 분수
      • $\frac{9}{6}$ -> $\frac{3}{2}$
    • eg 2) 두 점사이의 각도
      • $-30$, $330$, $690$
  • 정규화는 프로그램이 자료를 입력 받거나 계산하자 마자 곧바로 이루어져야 한다.
    1. 자료를 표현하는 클래스의 생성자에서 수행
    2. 외부에서 자료를 입력 받자마자 수행

7) 코드와 데이터를 분리하기

  • 코드의 논리와 상관없는 코드는 부리하기
    • eg) 월을 출력하는 함수
      1
2
3
4
5
6
7
8

      def get_month_name(month: int):
    if month == 1:
        return "January"
    elif month == 3:
        return "Feburary"
    ...
    else:
        return "December"
      => 다음과 같이 수정하기
      1

      month_name = ["January", "Feburary", ... , "Decebmer"]
    • 체스 게임에서 말들이 움직일 수 있는 상대적인 위치를 저장
      1
2

      knight_dx = [2, 2, -2, -2, 1, 1, -1, -1]
knight_dx = [1, -1, 1, -1, 2, -2, 2, -2]

3.3 자주 하는 실수

1) 산술 오버플로

계산 과정에서 변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로

2) 배열 범위 밖 원소 접근

0을 시작으로하는 범위와 1로 시작하는 범위를 혼동하는 것

eg) 1년에 포함된 달의 날짜 수를 저장하는 상수 배열

  • 1년 12달 -> 배열의 크기: 12
  • 입력 받은 값을 곧장 배열 인덱스로 사용할 경우

3) 일관되지 않은 범위 표현 방식 사용하기

  • 프로그램 내에서 여러 가지의 범위 표현 방식을 섞어서 사용할 경우
    • eg) $[2, 3, 4, … , 12]$
    • 닫힌 구간: $[2, 12]$
    • 열린 구간: $(1, 13)$
    • 반 열린 구간: $[2, 13)$
  • 반 열린 구간의 장점
    1. 첫 번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간을 쉽게 표현할 수 있다.
      • eg) $[2, 2)$ -> $2 \leq i < 2$ -> 공집합
    2. 두 구간이 연속해 있는지 쉽게 알 수 있다.
      • eg) $[a, b)$ , $[c, d)$가 연속인지 보려면?
        -> $b = c$, $a = d$ 인지만 확인하면 된다.
    3. 구간의 크기를 알기 쉽다.
      • eg) $[a, b)$ -> 자연수의 수는 $b-a$
  • 자연어에서 사용하는 범위와 다르기 때문에 문제가 생길 수 도 있다.
    • average(A[], i, j): 배열 A[]의 부분 구간의 평균을 구하는 함수
      • 반 열린 구간: average(a, 0, n)
      • 닫힌 구간: average(a, 0, n-1)
        -> 함수 내에서 사용하는 표현 방법과 함수 밖에서 사용하는 표현 방법이 다르면 혼란이 발생.

4) Off-by-one 오류

  • 계산의 큰 줄기는 맞지만 하나가 모자르거나 하나가 많아서 틀리는 오류들
    • eg 1) 100미터 길이의 담장에 10미터 간격으로 울타리 기둥을 세운다. 기둥이 몇 개 필요할까? -> 정답은 10개가 아니라 11개
    • eg 2) 정수 배열 A[]가 주어질 때 A[i] 부터 A[j] 까지의 평균을 계산한다. 이 때 합을 얼마로 나누어야 할까? -> $j-i$가 아니라 $j-i+1$
  • 언제 일어날까?
    • 반복문에서 $<, >$ 연산자와 $\leq, \geq$ 연산자를 혼동하여 원서를 하나 더 적게, 혹은 하나 더 많이 분리하는 경우
    • 반 열린 구간과 닫힌 구간을 서로 혼용해 쓸 경우
  • 오류를 방지하는 방법
    • 최소 입력이 주어졌을 때 코드가 어떻게 동작할지 되새겨 보기
      • eg 1) 담장의 길이가 0m 여도 기둥은 하나 박아야 한다.
      • eg 2) A[1] 부터 A[1] 까지의 평균을 구할 때 0이 아니라 1로 나누어야 한다.

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

6) 스택 오버 플로

프로그램 실행 중 콜 스택이 오버플로해서 프로그램이 강제 종료되는 경우

  • 재귀 호출의 깊이가 너무 깊어져서 온다.

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

8) 잘못된 비교 함수 작성

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

가능한 입력 중 최솟 값과 최대 값이 예외가 되는 문제는 생각보다 많다.

eg) 소수 판정 함수

1
2
3
4
5
6
7

def is_prime(n: int):
    if n % 2 == 0: # 짝수면 소수다.
        return False
    for i in range(2, n): # 다른 수로 나눠지면 소수다.
        if n % i == 0:
            return False
    return True

-> 2는 짝수이면서 소수

1
2
3
4
5
6
7
8
9

def is_prime(n: int):
    if n == 2:
        return True
    if n % 2 == 0: # 짝수면 소수다.
        return False
    for i in range(2, n): # 다른 수로 나눠지면 소수다.
        if n % i == 0:
            return False
    return True

-> n=1은 두 조건문을 통과해 소수로 판정됨

10) 연산자 우선 순위 잘못 쓰기

  • 연산자의 우선순위 잘 기억하기
  • 헷갈릴 경우 괄호로 적절히 감싸기

11) 너무 느린 입출력 방식 선택

12) 변수 초기화 문제

  • 이전 입력에서 사용한 전역 변수 값을 초기화 하지 않고 그대로 사용하는 경우
  • Tip) 예제 입력 파일을 두 번 반복해서 쓰기
    • eg)
      1
2
3

      2
1234
321
      ->
      1
2
3
4
5

      4
1234
321
1234
321
  • 예제간의 의존 관계 때문에 우연히 답이 나오는 경우를 방지할 수 있다.

3.4 디버깅과 테스팅

1) 디버깅에 관하여

  • 작은 입력에 대해 제대로 실행되나 확인하기
  • 단정문(assertion)을 쓴다.
  • 프로그램의 계산 중간 결과를 출력한다.

2) 테스팅에 관하여

스캐폴딩 (Scaffolding)

  • 코드의 정당성을 확인하거나 반례를 찾을 때 유용하다.
  • 임의의 작은 입력을 자동으로 생성하는 프로그램 -> 검증하는 프로그램
    • eg) 직접 짠 정렬 알고리즘
      • 난수 생성
      • 라이브러리 결과 == 직접 짠 결과
  • 라이브러리가 없는 경우
    • 작은 입력에서만 동작하는 더 느리지만 단순한 알고리즘을 사용해 검증

3.5 변수 범위의 이해

1) 산술 오버플로

2) 너무 큰 결과

3) 너무 큰 중간값

4) 너무 큰 ‘무한대’ 값

무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 있다.

eg) 두 위치를 잇는 가장 짧은 길의 길이를 구하기
$s$ 에서 $t$ 까지 가는데 세 중간 지점 $a, b, c$ 중 항상 한 군데를 거쳐서 가야 한다.

  • $(s,t)$ 구간의 최단 경로 길이 $dist(s,t)$ 계산 방법
    \( dist(s,t)=min \begin{cases} dist(s,a) + dist(a,t) \\ dist(s,b) + dist(b,t) \\ dist(s,c) + dist(c,t) \\ \end{cases} \)

만약 두 구간을 잇는 경우가 없을 경우에는?

  1. 길이 존재하지 않음을 나타내는 특수한 값을 사용
    • 이 값에 대한 예외 처리를 또 해주어야 함
  2. 실제로 나타날 리 없는 아주 큰 값을 반환
    • $min$ 에서 자동으로 필터링
    • Tip) 987,654,321 같이 디버깅이 쉬운 큰 값을 추천
      • $2^30$에 가까운 매우 큰 값

5) 오버플로 피해가기

  1. 더 큰 자료형 사용하기
  2. 오버플로가 일어나지 않도록 연산의 순서 바꾸기
  3. 계산 방법을 다르게 해 오버플로 피해가기

6) 자료형의 프로모션

© 2020 - 2022 Aiden's Camp
Built with Hugo
Theme Stack designed by Jimmy