[Algorithmic Problem Solving Strategies] 코딩과 디버깅에 관하여 독후감

Algorithmic Problem Solving Strategies

해당 책을 읽고 쓰는 독후감 또는 요약 정리본입니다.
주관적인 내용이 아주 많이 들어가 있습니다.

-
(독후감)

  이번 파트는 알고리즘 대회영역에서의 알고리즘 코딩과 디버깅에 대해 이므로 최대한 제 입장에 맞춰서 요약 정리 하였습니다.

코딩 과정에서 지켜야 할 점이나, 이 과정에서의 자주 하는 실수들을 다룹니다.

 

---

 

간결한 코드를 작성하기.

  가장 간결한 코드를 작성하라, 코드가 짧으면 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅도 쉬워지기 때문.
같은 일을 하는 100줄짜리 코드 대신 1000줄짜리 코드를 보고 싶어 하는 사람은 아무도 없을 것이다.

---

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

  간결한 코드를 작성하기 위한 가장 직접적인 방법은 코드를 모듈화 하는 것. 같은 코드가 반복된다면 이들을 함수나 클래스로 분리해 재사용하는 것이 좋다. 같은 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본 원칙을 만들면 좋다. 

  하지만 실무에서는 한 함수가 두 가지 이상의 일을 해서는 안된다.
입력을 읽어 들이는 함수, 입력을 처리하기 쉬운 형태로 바꾸는 함수, 실제 문제를 푸는 함수가 각각 분리되어 있어야 한다.

---

표준 라이브러리 공부하기

  문자열, 동적 배열, 스택, 큐, 리스트, Dictionary 등의 자료 구조, 그리고 정렬 등의 표준적인 알고리즘 구현 사용법을 알아두어야 한다.
아래는 Swift standard library / swift github

Swift.org

GitHub - apple/swift: The Swift Programming Language

---

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

  알고리즘을 풀다 보면 여러 종류의 코드를 반복적으로 짜게 된다. 이분법, 그래프의 너비 우선 탐색 등 유명한 알고리즘부터, 2차원 평면의 점을 표현하는 자료 구조, 두 개의 구간이 서로 겹치는지를 확인하는 함수 등이 좋은 예. 

  같은 코드를 작성하는 더 좋은 방법에 대해 꾸준히 고민할 필요는 있지만, 자주 작성하는 알고리즘이나 코드 등에 대해서는 한 번 검증된 코드를 작성하고 이것만을 꾸준히 사용할 필요가 있다. 그래야 도구가 아니라 문제에 집중할 수 있기 때문.

 

---

일관적이고 명료한 명명법 찾기

 

 

var a = [Int](), i = 0, j :Int?

  실무에서 이런 코드로 선언한다면 완전히 낙제감이고, 프로그래밍 대회에서도 다를 이유가 없다.
모호하지 않은 변수명과 함수명을 사용하는 버릇을 들이고, 사용하는 언어의 표준 라이브러리에서 사용하는 명명 규약을 익혀야 한다.
Swift 명명규약 Link : Swift NamingConvention

모호한 명명법은 가끔 잡아내기 힘든 오류를 만든다. 함수 이름으로 무슨 역할을 하는지 알아낼 수 있도록 잘 작성할 것

---

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

  좋은 코드의 또 다른 원칙으로 같은 자료를 두 가지 형태로 저장하지 않는 것이 있다.
예를 들어 유리수를 표현하는 클래스 Fraction를 작성한다면, 이때 입력받는 유리수를 항상 약분해 기약 분수로 표현하는 것이 좋다.
9/6 == 3/2 가 같은 경우 항상 기약분수 형태로 저장하는 것, 이렇게 쓰지 않으면 같은 자료가 두 개 이상의 표현을 갖게 되고 이로 인해 미묘한 버그들을 만들기 쉽다. 각각의 문자열 표현이 달라지고 해시 값이 달라지는 등의 문제가 있기 때문.

  정규화가 꼭 필요한 다른 예로는, 2차원 평면상에서 x축의 양의 방향과 주어진 점 (x, y) 사이의 각도를 계산하는 것.
예를 들어 x축의 양의 방향과 점 (√3, -1) 사이의 각도는 -30°, 330°, 690°라고도 쓸 수 있다. 이럴 때 각도 표현 방법을 한 가지로 정의해 두지 않으면 각도를 다루는 함수들을 작성하기 아주 힘들어진다.

  실무에서는 오해를 불러일으킬만한 사항들을 정규화해야 한다. 대표적인 정규화로는 Summertime을 UTC로 기재하는 것.
문자열을 UTF-16 / UTF-8 인코딩으로 변환하는 것. 

  정규화는 프로그램이 자료를 입력받거나 계산하자마자 곧장 이루어져야 한다. 이상적으로는 자료를 표현하는 클래스의 생성자에서 정규화를 수행하거나, 외부에서 자료를 입력받자마자 정규화를 수행하는 것이 좋다.

---

코드와 데이터를 분리하기

날짜를 출력할 때 월을 숫자가 아니라 영문 이름으로 출력해야 하는 프로그램을 작성할 때

func getMonthName(month :Int) -> String {
	if(month == 1) {return "January"}
	if(month == 2) {return "February"}
	    ...
	return "December"
}

이런 식으로 작성하는 것을 나중에는 피하게 된다. 코드의 논리와 상관없는 데이터는 가능한 한 분리하는 것이 좋기 때문.

let monthName = ["January", "February", ... , "December"]

이런 식으로 작성하여 각 월의 영어 이름을 다음과 같은 테이블로 만들 수 있다. 이런 방식은 항상 코드의 양을 줄여서 실수하지 않게 도와준다. 이 기법의 또 다른 좋은 예로는 체스 같은 보드 게임에서 말들의 움직임을 다룰 때 움직임의 상대 좌표를 배열에 저장해 두는 것이다.

let knightMove = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]

 

위와 같이 knight가 움직일 수 있는 상대 좌표는 총 여덟 가지인데, 이를 직접 코드에 저장하기보다 다음과 같이 배열로 선언하고 배열을 순회하면서 각 위치를 검사하는 쪽이 훨씬 쉽다.

---

자주 하는 실수

같은 실수를 반복하기보다는 실수에서 배우는 것이 좋고, 그보다 더 좋은 것은 남의 실수로부터 배워 유사한 실수를 저지르지 않는 것. 

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

 

• 배열 범위 밖 원소 접근
  • Runtime Error Segment Fault
  • 배열 범위 밖의 원소에 접근하는 오류

 

• 일관되지 않은 범위 표현 방식 사용하기
  • 어떤 자연수의 범위 [2, 3, 4, ..., 12]를 표현할 때 자연스러운 방법은 [2, 12]는 2 ≤ i ≤ 12 이는 닫힌 구간이라고 부름.
  • (2, 12)는 열린 구간이라고 부르며 [3, 4, ..., 11]을 나타낸다. 열린 구간으로 원래 구간을 표현하려면 (1, 13)라고 해야 함.
  • 두 가지 모두 장단점이 존재하며 많은 프로그래밍 언어에서는 배열의 인덱스가 0부터 시작하므로, 반 열린 구간을 사용하는 게 일반적. 이 선택에 관해 유명한 글로는 데이크스트라의 《Why numbering should start at zeor》가 있다.
  • [lo, hi)로 표현하며 [lo, lo + 1, ..., hi - 2, hi - 1]를 나타낸다.
  • 대부분의 프로그래밍 언어에서 n개의 원소를 갖는 배열 a의 첫 번째 원소는 a[0]이고 마지막 원소는 a[n-1] 따라서 인덱스의 범위는 0 ≤ i < n
  • 해당 표현 방식의 장점
    • 첫 번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간을 쉽게 표현할 수 있다. [2, 2) 2 ≤ i < 2인 모든 i를 포함하므로 공집합
    • 두 구간이 연속해 있는지 쉽게 알 수 있다. [a, b) [c, d)가 연속해 있는지 보려면 b = c 혹은 a = d인지만 확인하면 된다.
    • 구간의 크기를 쉽게 알 수 있다. [a, b)로 표현된 구간에 포함된 자연수의 수는 b - a가 된다.
  • 쟁점은 [a, b]로 표현하던 [a, b)로 표현하던 프로그램 내에서 한 가지 방법으로만 범위를 표현할 필요가 있다. 
  • Swift에서는 [a, b] == a...b 이고, [a, b) == a..<b이다. 

 

• Off-by-one Error
  • 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리킨다.
  • 예를 들어 길이가 100미터인 담장에 10미터 간격으로 울타리 기둥을 세울 때 필요한 기둥은 10개가 아닌 11개다.
  • 정수 배열 A가 주어질 때 A[i]부터 A[j]까지의 평균을 구할 때 합은 j-i가 아닌 j-i+1로 나누어야 한다.
  • 반복문에서 < 혹은 > 연산자와 ≤ 혹은 ≥ 연산자를 혼동하여 원소를 하나 더 적게, 혹은 많이 순회하는 경우 반 열린 구간과 닫힌 구간을 서로 혼용해 쓴 경우 흔하게 발생한다. 
  • 이런 오류를 방지할 수 있는 좋은 방법은 최소 입력이 주어졌을 때 이 코드가 어떻게 동작할지를 되새겨 보면서 프로그램을 짜는 것.
  • 담장의 길이가 0미터라도 기둥은 하나 박아야 하고, A[1]부터 A[1]까지의 평균을 구할 땐 0이 아니라 1로 나눠야 한다.

 

• 컴파일러가 잡아주지 못하는 상수 오타
  • 변수명이나 함수명에서 낸 오타는 컴파일러가 잡아주기 때문에 프로그램을 짤 때 오타에 대해서는 걱정하지 않는 경우가 있다.
  • 코드와 데이터를 분리하기 위해 데이터를 별도의 상수 배열에 저장하는 것은 좋은 버릇.(이전의 월 이름 찾기) 그러나 여기에 오타가 발생한다면 찾아내기가 어려울 수 있다. ex) "Feburary"
  • 출력 문자열 상수를 잘못 쓰는 것도 종종 있는 실수
  • 계산해야 할 값이 아주 큰 경우 큰 수 M으로 나눈 나머지를 대신 계산하는 문제들이 있는데 이때 10000007 같이 큰 상수로 지정될 때 0의 개수를 틀리는 것도 종종 있는 실수
  • 자신이 사용하는 언어에서 상수타입을 어떻게 지정하는지, 지정하지 않은 경우 어느 형태로 강제되는지 미리 알아두는 것이 좋다.

 

• 스택 오버플로
  • 프로그램 실행 중 콜 스택(call Stack)이 오버플로해서 프로그램이 강제 종료되는 것 또한 흔히 하는 실수. 
  • 보통 재귀 호출의 깊이가 너무 깊어져서 생기는 경우가 있다. 스택 최대 크기는 컴파일이나 실행 시에 설정할 수 있고 기본 값이 언어나 아키텍처등에 따라 매우 다르기 때문에 사용하는 환경의 스택 허용량에 대해 알아 둘 필요가 있다.
  •  

  • C++의 경우에는 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본 적은 로 스택 메모리를 사용하기 때문에 특히나 스택 오버플로를 조심해야 한다. 배열 등의 큰 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽다. 때문에 대부분의 참가자들은 자동으로 힙에 메모리를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 사용하곤 한다.

 

• 다차원 배열 인덱스 순서 바꿔 쓰기
  • 평소에는 2차원 이상의 다차원 배열을 사용할 일이 많지 않지만, 프로그래밍 대회에서는 심심찮게 4, 5차원 이상의 고차원 배열을 쓰게 되는데, 이 배열을 이곳저곳에서 접근하다 보면 한군데쯤에서 인덱스의 순서를 헷갈려서 잘못 쓰는 일이 흔하다.
  • 동적 계획법을 위한 메모이제이 션 패턴을 사용할 때 이런 일이 잦은데, 이런 경우에는 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다

 

• 잘못된 비교 함수 작성
  • 크기 비교, 사전순 비교. 한 문제에 복잡한 비교 함수를 작성하는 것도 종종 하는 실수.

 

• 최소, 최대 예외 잘못 다루기
  • 코드를 짤 때 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지 생각해봐야 한다.

 

• 연산자 우선순위 잘못 쓰기
  
  • swift에서는 if문에 bool값만 들어올 수 있기 때문에 알아서 컴파일러가 잘 처리해 준다.. 그래도 연산자 우선순위 꼭 한번 보기.
  • 괄호로 잘 감싸주기

if b & 1 == 0 에서 bool 타입으로 추론하기 때문에 b & 1 이 먼저 실행된다.
if b & (1 == 0) < 불가능 >
if (b & 1) == 0 < 가능 >

 

• 너무 느린 입출력 방식 선택 (Swift)
  
  • 빠른 입출력 FileIO 가져다 쓰거나, readLine의 Int형변환 단계에서 Int(String())을 사용해서 속도를 향상한다.

---

테스트 코드의 작성

스캐폴딩(scaffolding) 기법을 사용해서 임의의 작은 입력을 자동으로 생성해 프로그램을 돌려보고, 그 답안을 검증하는 프로그램을 짜면 큰 도움이 된다. 

---

 

알고리즘 문제 해결 전략