알고리즘 문제 해결 전략 03 - 코딩과 디버깅

빨리 코드를 작성하는 것보다 읽기 쉬운 코드를 작성하는 것이 중요

좋은 코드를 짜기 위한 원칙

간결한 코드 작성하기

• 코드가 짧을 수록 오타, 단순한 버그가 생길 우려가 줄고 디버깅도 쉬워진다.

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

• 코드를 모듈화하기
• 같은 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본 원칙을 만들자.
• 엄격하겐 하지 말자. 시간 제한도 있고 대부분의 용도는 문제 풀이용이기 때문에 재사용에 한계가 있음

표준 라이브러리 공부하기

• 큐나 스택 같은 자료구조, 정렬 등 기초적인 알고리즘을 직접 작성할 필요 없음 → 표준 라이브러리를 참고하기
  • 메모리 관리나 정당성 증명에 신경 쓸 필요 없이 편하게 사용 가능
• 언어의 문자열, 동적 배열, 스택, 큐, 리스트, 사전 등의 자료구조, 정렬 등 표준적인 알고리즘 구현 사용법을 반드시 잘 알아두기!

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

• 코드를 검증하는 것이 쉬운 일이 아니기 때문에 시간에 쫓기지 않도록 한 번 검증된 같은 코드를 작성하고 꾸준히 사용하는 것이 좋다.
• 그래야 도구가 아닌 문제에 집중할 수 있기 때문

일관적으고 명료한 명명법 사용하기

• 모호하지 않은 변수명과 함수명을 사용하는 버릇을 들이고, 사용하는 언어의 표준 라이브러리에서 사용하는 명명 규약을 익히기

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

• 같은 자료를 두 가지 형태로 저장하지 않는 것
  • 미묘한 버그들이 생기기 쉽다.
• 이상적으로는 자료를 표현하는 클래스의 생성자에서 정규화를 수행하거나, 외부에서 자료를 입력받자마자 정규화를 수행하는 것이 좋다.

코드와 데이터 분리

• 코드의 논리와 상관 없는 데이터는 가능한 한 분리
• 날짜를 다루는 프로그램 작성시, 날짜 출력의 월을 숫자가 아니라 영문 이름으로 출력한다 하면 12줄 짜리 함수를 짜곤 한다. -> 배열에 넣으면 됨

자주 하는 실수

같은 실수를 반복하기보다 실수에서 배우고, 남의 실수를 배워 유사한 실수를 저지르지 않기

산술 오버플로

• 계산 과정에서 변수의 표현 범위를 벗어나는 값을 사용하는 것

배열 범위 밖 원소에 접근

• 배열 크기를 정할 때 계산을 신중히 하자

일관되지 않은 범위 표현 방식 사용

• 닫힌 구간(closed interval)
  • [2, 12] → 2 ≦ i ≦ 12
• 열린 구간(open interval)
  • (1, 13) → 2 ≦ i ≦ 12
  • (2, 12) → [3, 4, ..., 11]
• 대부분의 프로그래밍 언어는 반 열린 구간(half-open interval)을 사용
  • 첫 번째 값은 집합 안에 포함하고, 다른 하나는 집합 안에 포함하지 않는다.
    • n개의 원소를 갖는 배열 a의 첫 번째 원소는 a[0]이고 마지막 원소는 a[n-1]이다.

Off-by-one 오류

• 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리키는 말
  • 100미터 담장에 10미터 간격으로 울타리 기둥을 세우면 몇 개의 기둥이 필요한가? → 10개가 아닌 11개
  • 배열 a가 주어질 때 a[i] 부터 a[j] 까지의 평균을 구하려면 합을 얼마로 나누어야 하나? → j-i가 아니라 j-i+1
• 방지하려면, 최소 입력이 주어졌을 때 이 코드가 어떻게 동작하는지 되새겨 보면서 프로그램을 짜는 것
  • 담장의 길이가 0미터라도 기둥은 하나 박아야 한다.
  • a[1]부터 a[2]까지 평균을 구할 땐 1이 아니라 2로 나눠야 한다.

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

• 오타 주의

스택 오버플로

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

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

• 고차원 배열(4, 5차원 이상)을 사용할 때 인덱스의 순서를 헷갈려 잘못 쓰는 경우가 있음

잘못된 비교 함수 작성

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

• 가능한 입력 중 최소 값과 최대 값이 예외가 되는 문제들이 생각보다 많으므로 코드를 짤 때 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해보면 오류를 잡을 수 있는 경우가 꽤 있다.

연산자 우선순위 잘못 쓰기

• 비트 단위 AND 연산자인 &&은 비교 연산자인 == 보다 낮다.
• 연산자 우선순위가 헷갈릴 경우 괄호로 적절히 감싸자

너무 느린 입출력 방식 선택

변수 초기화 문제

• 새 테스트 케이스를 처리할 때마다 변수들을 적절히 초기화하도록 신경 써서 코딩

디버깅과 테스팅

디버깅에 관해

• 프로그램을 작성하고 예제 입력을 실행해보니 원하는 결과와 다르다. → 디버깅을 한다.
• 눈으로 디버깅하는 쪽이 빠를 수 있다. 소스코드가 길지 않다면
• 재귀 호출이나 중복 반복문을 많이 사용하는 복잡한 코드는 디버거로 디버깅하기에는 적당하지 않다.
• 디버거 없이 버그를 찾아낼 연습이 필요하다.
  • 코드가 복잡하면 디버거 없이 눈으로 프로그램을 검증하기 어렵긴 하지만, 애초에 코드를 복잡하게 짰다는 것이 문제
  • 잘 분리된 기능적 코드는 디버거 없이 눈으로도 검증하기 비교적 쉽다.
• 디버거 사용 대신에 밟으면 좋은 단계
  • 작은 입력에 대해 제대로 실행되나 확인하기
  • 단정문 쓰기
    • 단정문: 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문을 의미
  • 프로그램의 계산 중간 결과 출력하기
    • 범위를 좁힐 수 있다.

테스트에 관해

• 답안 작성 후 제출 전 예제 입력을 만들어 가능한 많이 프로그램을 테스트하는 것이 좋다.
• 예제 입출력 외에도 몇 가지 간단한 입력을 직접 만들어 넣어 보면 오답률을 줄일 수 있다.
  • 주어진 예제 입력을 약간 바꿔서 넣어 보거나 , 있을 수 있는 가장 작은 입력과 가장 큰 입력을 만들어서 넣어보고 시간 안에 실행되는지 확인
• 스캐폴딩(scaffolding) 기법
  • 원래 건물을 짓거나 보수할 때 공사하는 사람들이 걸어다니기 위해 설치하는 임시 구조물
  • 다른 코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드라는 뜻

변수 범위의 이해

산술 오버플로

• 수학에선 어떤 변수 n이 있다면 담을 수 있는 숫자에 제한이 없다. 그러나 컴퓨터는 크기가 제한되어 있다.
• 산술 오버플로가 발생하는 이유
  • 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 일어나도 경고를 주지 않는다. 연산이 일어날 때마다 오버플로 확인하는 것은 너무 비효율적이기 때문
  • 프로그램의 정당성을 검증할 때 논리 정확성에만 집중하다보면 산술 오버플로가 등장할 수 있다는 사실을 간과하기 쉽다.

오버플로 피해가기

• 더 큰 자료형 사용하기