위의 코드는 오류를 발생시켰다. 오류는 아래와 같다.

Could not find method compile() for arguments [org.springframework:spring-context:5.0.2.RELEASE] on object of type org.gradle.api.internal.artifacts.dsl.dependencies.DefaultDependencyHandler.

compile, runtime, testCompile, testRuntime 은 Gradle 4.10 (2018.8.27) 이래로
deprecate 되었다. 그리고 Gradle 7.0 (2021.4.9) 부터 삭제되었다.

필자는 Gradle 7.3.3 을 이용하고 있어서 삭제된 명령을 사용했으므로 오류가 발생했었다. 삭제된 네 명령은 각각 implementation, runtimeOnly, testImplementation, testRuntimeOnly 으로 대체되었다. 따라서 compile 을 implementation 으로 수정하여 오류를 해결했다.

참고한 글

https://stackoverflow.com/questions/23796404/could-not-find-method-compile-for-arguments-gradle

가장 위의 Binary tar.gz 파일을 받는다.

1. 터미널 오픈
2. 다음의 명령어 입력(3.8.4 는 받은 Maven 의 버전) sudo mv Downloads/apache-maven-3.8.4 /usr/local
3. 패스워드 입력
4. 다음의 명령어 입력 vi ~/.zshrc
5. 적당한 위치(가장 아래)에 다음의 문장 입력 export M3_HOME=/usr/local/apache-maven-3.8.4 export PATH=$PATH:$M3_HOME/bin
6. 저장 후 닫기
7. 다음의 명령어 입력 source ~/.zshrc
8. 설치 완료

설치 완료는 mvn -version 을 입력하고, 버전 정보의 출력을 확인하면 된다.

참고한 글이 bash 기준으로 작성되어, zsh 가 기본 쉘로 변경된 현재를 기준으로 다시 작성했다.

참고한 글

https://nobacking.tistory.com/43

변수 목록(static public constant -> static private variable -> private variable) -> public method -> private method(Next to caller)

캡슐화 변수와 유틸리티 함수는 가능한 공개하지 않는 편이 낫지만, 반드시 숨겨야 하는건 아니다. (protected로 테스트 코드에 접근 허용) 하지만 그 전에 비공개 상태를 유지할 온갖 방법을 강구하자.

클래스는 작아야 한다!

함수가 물리적인 행 수로 크기를 측정한다면, 클래스는 맡은 책임을 센다.

클래스 이름은 해당 클래스 책임을 기술해야 하는데,

1. 간결한 이름이 떠오르지 않는다면 클래스 크기가 너무 커서 그렇다.
2. 클래스 이름이 모호하다면 클래스 책임이 너무 많아서다. (Processor, Manager, Super 등...)

단일 책임 원칙 Single Responsibility Principle, SRP 는 클래스나 모듈을 변경할 이유(책임)가 단 하나뿐이어야 한다는 원칙이다.

걱정: 자잘한 단일 책임 클래스가 많아지면 큰 그림을 이해하기 어려워지지 않을까? 반박: 규모가 어느 수준에 이르는 시스템은 논리가 많고도 복잡하다. 이런 복잡성을 다루려면 체계적인 정리가 필수다. 직접 영향이 미치는 컴포넌트만 이해해도 충분하다. 큼직한 다목적 클래스 몇 개로 이뤄진 시스템은 당장 알 필요가 없는 사실까지 들이밀어 독자를 방해한다.

응집도 Cohesion 가 높다는 말은 클래스에 속한 메서드와 변수가 서로 의존하며 논리적인 단위로 묶인다는 의미다.

응집도가 높아지도록 변수와 메섣르르 적절히 분리해 새로운 클래스로 쪼개준다.

응집도를 유지하면 작은 클래스 여럿이 나온다 클래스가 응집력을 잃는다면 쪼개라!

변경하기 쉬운 클래스

어떤 변경이든 클래스에 손대면 다른 코드를 망가뜨릴 잠정적인 위험이 존재한다. => SRP 를 지키자. (파생 클래스를 만들어 책임 분리, OCP도 지킬 수 있다.) 클래스 일부에서만 사용되는 비공개 메서드는 코드를 개선할 잠재적인 여지를 시사한다. => 유틸리티 클래스를 만들자.

변경으로부터 격리 상세한 구현에 의존하는 클라이언트 클래스는 구현이 바뀌면 위험에 빠진다. 인터페이스와 추상 클래스를 사용해 구현이 미치는 영향을 격리한다.

결합도가 낮다는 소리는 각 시스템 요소가 다른 요소로부터 그리고 변경으로부터 잘 격리되어 있다는 의미다.

DIP Dependency Inversion Principle 는 클래스가 상세한 구현이 아니라 추상화에 의존해야 한다는 원칙이다.

외부 코드 사용하기

• 인터페이스 제공자: 적용성을 최대한 넓히려 애쓴다.
• 인터페이스 사용자: 자신의 요구에 집중하는 인터페이스를 바란다.

Map 인터페이스는 사용자에게 필요하지 않은 기능까지 제공한다. (ex. clear 메소드)

Map<String, Sensor> 인스턴스를 여기저기로 넘기면, Map 인터페이스가 변경되었을 때 수정할 코드가 많아진다.

public class Sensors {
    private Map sensors = new Hashmap();

    public Sensor getById(String id) {
        return (Sensor) sensors.get(id);
    }
}

위와 같이 캡슐화해서 사용하면 Map 인터페이스가 변경되더라도 나머지 프로그램에는 영향을 미치지 않는다.

Map과 같은 경계 인터페이스를 항상 캡슐화하라는 의미가 아니고, 이를 이용하는 클래스나 클래스 계열 밖으로 노출되지 않도록 주의하라는 의미다.

인스턴스를 공개 API의 인수로 넘기거나 반환값으로 사용하지 않는다.

경계 살피고 익히기

곧바로 우리쪽 코드를 작성해 외부 코드를 호출하는 대신, 먼저 간단한 테스트 케이스를 작성해 외부 코드를 익히자. => 학습 테스트(테스트 주도 개발, 짐 뉴커크)

log4j 익히기

의의를 모르겠다. 학습 테스트의 예를 보여주는 듯한데, TDD의 개념을 잘 몰라서 그런지 이해가 잘 가지 않는다. => 학습 테스트를 이용하여 외부 패키지를 배우는 방법을 보여주고 있다.

학습 테스트는 공짜 이상이다

패키지 새 버전이 나온다면 학습 테스트를 돌려 차이가 있는지 확인한다. => 새 버전이 우리 코드와 호환되지 않으면 학습 테스트가 이 사실을 곧바로 밝혀낸다.

아직 존재하지 않는 코드를 사용하기

모르는 부분의 구현은 미뤄두고, 인터페이스를 구현하면 우리가 인터페이스를 전적으로 통제할 수 있고, 코드 가독성은 높아지며, 코드 의도도 분명해진다.

ADAPTER 패턴(GOF의 디자인 패턴): API 사용을 캡슐화해 API가 바뀔 때 수정할 코드를 한 곳에 모은다.

깨끗한 경계

• 경계에 위치하는 코드는 분리한다.
• 기대치를 정의하는 테스트 케이스를 작성한다.
• 외부 패키지를 호출하는 코드를 가능한 줄여 경계를 관리하자.
  • 새로운 클래스로 경계를 감싼다.
  • ADAPTER 패턴을 사용해 우리가 원하는 인터페이스를 패키지가 제공하는 인터페이스로 변환한다.

얻는 효과

• 코드 가독성이 높아진다.
• 경계 인터페이스를 사용하는 일관성이 높아진다.
• 외부 패키지가 변했을 때 변경할 코드가 줄어든다.

오류 코드보다 예외를 사용하라

• 디바이스 종료 알고리즘, 오류 처리 알고리즘 분리해서 각 개념을 독립적으로 살펴보고 이해할 수 있음

Try-Catch-Finally 문부터 작성하라

• 이해 안됨

미확인 예외를 사용하라

• OCP 위반(하위 단계에서 코드를 변경하면 상위 단계 메서드 선언부를 전부 고쳐야 함)
• throws 경로에 위치하는 모든 함수가 최하위 함수에서 던지는 예외를 알아야 하므로 캡슐화 깨짐

예외에 의미를 제공하라

• 오류 메시지에 정보(실패한 연산 이름, 실패 유형)를 담아 예외와 함께 던진다.

호출자를 고려해 예외 클래스를 정의하라

• 감싸기 기법이 뭐가 바뀐건지 모르겠음

정상 흐름을 정의하라

• Special case pattern(클래스나 객체가 예외적인 상황을 캡슐화해서 처리함)

null을 반환하지 마라

• null을 반환하지 말고 예외를 던지거나 특수 사례 객체를 반환
• 외부 API가 null 반환하면 감싸기 메서드 구현하여 예외 던지거나 special case pattern 사용
• 리스트가 null이라면? 이 아니라 빈 리스트를 반환 (Collections.emptyList()

null을 전달하지 마라

• assert 조건문 : 반환문;
• null을 넘기지 못하도록 금지하는 정책을 따르자

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

재귀 호출과의 차이는 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있다.

1. 문제를 더 작은 문제로 분할하는 과정(divide)
2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

분할 정복을 적용하려면 문제에 몇 가지 특성이 성립해야 한다.

• 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

분할 정복은 많은 경우 같은 작업을 더 빠르게 처리해 준다.

예제: 수열의 빠른 합과 행렬의 빠른 제곱

$1+2+…+n$의 합을 재귀 호출을 이용해 계산하는 recursiveSum() 함수를 작성했었는데, 여기서는 분할 정복을 이용해 똑같은 일을 하는 fastSum() 함수를 만들어 보자.

1부터 n 까지의 합을 n개의 조각으로 나눈 뒤, 이들을 반으로 뚝 잘라 $\frac{n}{2}$개의 조각들로 만들어진 부분 문제 두 개를 만든다. (편의상 n은 짝수라고 가정한다.)

$fastSum()=1+2+…+n$ $$= \left(1+2+…+{\frac{n}{2}} \right) + \left(\left(\frac{n}{2}+1 \right) + … + n \right) $$

첫 번째 부분 문제는 $fastSum(\frac{n}{2})$로 나타낼 수 있지만, 두 번째 부분 문제는 그렇지 않다.

문제를 재귀적으로 풀기 위해서는 각 부분 문제를 '1부터 n까지의 합' 꼴로 표현할 수 있어야 하는데, 위의 분할에서 두 번째 조각은 'a부터 b까지의 합' 형태를 가지고 있다. 따라서, 다음과 같이 두 번째 부분 문제를 $fastSum(x)$를 포함하는 형태로 바꿔야 한다.

(아래부터 이해 못함)

$$ \left({\frac{n}{2}}+1 \right) + … + n= \left(\frac{n}{2}+1 \right)+\left(\frac{n}{2}+2 \right)+…+\left(\frac{n}{2}+\frac{n}{2} \right) $$

시간 복잡도 분석

fastSum()이 수행하는 데 걸리는 시간은 내부에 반복문이 없기 때문에, 순전히 함수가 호출되는 횟수에 비례한다. 호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.

$fastSum(1011_2)=fastSum(1010_2)+11$ $fastSum(1010_2)=fastSum(101_2)×2+25$ $fastSum(101_2)=fastSum(100_2)+5$ $fastSum(100_2)=fastSum(10_2)×2+4$ $fastSum(10_2)=fastSum(1_2)×2+1$ $fastSum(1_2)=1$

위는 fastSum(11)을 실행할 때 재귀 호출의 입력이 어떻게 변화하는지를 이진수 표현으로 보여준다. 재귀 호출을 할 때 n의 이진수 표현의 마지막 자리가 1이면 0으로 바뀌고, 마지막 자리가 0이면 끝자리가 없어진다는 것을 알 수 있다. 따라서 fastSum()의 총 호출 횟수는 n의 이진수 표현의 자릿수+첫 자리를 제외하고 나타나는 1의 개수가 된다. 두 값의 상한은 모두 $lgn$이므로 이 알고리즘의 실행 시간은 $O(lgn)$이다.

행렬의 거듭제곱

$n×n$ 크기의 행렬 $A$가 주어질 때, $A$의 거듭제곱 $A^m$은 $A$를 연속해서 m번 곱한 것이다. 해열르이 곱셈에는 $O(n^3)$의 시간이 들기 때문에 곧이곧대로 $m-1$번의 곱셈을 통해 $A^m$을 구하려면 모두 $O(n^3m)$번의 연산이 필요하다.

분할 정복을 이용해 눈깜짝할 새에 이 값을 구해보자.

$A^m=A^{m/2}×A^{m/2}$

위는 $A^m$을 구하는데 필요한 $m$개의 조각을 절반으로 나눈 것이다. 구현해보자.

// 정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(Identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
// A^m을 반환한다.
SquareMatrix pow(const SquareMatrix& A, int m) {
  // 기저 사례: A^0 = 1
  if(m == 0) return identity(A.size());
  if(m % 2 > 0) return pow(A, m-1) * A;
  SquareMatrix half = pow(A, m / 2);
  // A^m = (A^(m/2)) * (A^(m/2))
  return half * half;
}

나누어 떨어지지 않을 때의 분할과 시간 복잡도

$m$이 홀수일 때, $A^m=A×A^{m-1}$로 나누지 않고, 좀더 절반에 가깝게 나누는 게 좋지 않을까라는 생각을 할 수도 있다. 그러나 이 문제에서 이 방식의 분할은 오히려 알고리즘을 더 느리게 만든다. 이런 식으로 문제를 나누면 $A^m$을 찾기 위해 계산해야 할 부분 문제의 수가 늘어난다.

절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문이다. 이런 속성을 부분 문제가 중복된다(overlapping subproblems)고 부르며, 8장에서 다루는 동적 계획법이 고안된 계기다.

예제: 병합 정렬과 퀵 정렬

병합 정렬 알고리즘

주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

시간 복잡도 분석

각 단계마다 반으로 나눈 부분 문제를 재귀 호출을 ㅣㅇ용해 해결한 뒤, 이들의 결과 수열을 합쳐 전체 문제의 답을 계산한다. 정렬된 두 부분 수열을 합치는 데는 두 수열의 길이 합만큼 반복문을 수행해야 하기 때문에, 병합 정렬의 수행 시간은 이 병합 과정에 의해 지배된다.

아래 단계로 내려갈수록 부분 문제의 수는 두 배로 늘고 각 부분 문제의 크기는 반으로 줄어들기 때문에, 한 단계 내에서 모든 병합에 필요한 총 시간은 $O(n)$으로 항상 일정하다.

각 단계를 나타내는 각 가로줄에 있는 원소의 수는 항상 일정하다. 따라서 단계의 수에 n을 곱하면 병합 정렬에 필요한 전체 시간을 얻을 수 있다. 문제의 크기는 항상 거의 절반으로 나누어 지기 때문에, 필요한 단계의 수는 $O(lgn)$이다.

따라서 병합 정렬의 시간 복잡도는 $O(nlgn)$이다.

퀵 정렬 알고리즘

배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 파티션(partition)이라고 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 '기준 수(pivot)'을 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.

시간 복잡도 분석

대부분의 시간을 차지하는 것은 주어진 문제를 두 개의 부분 문제로 나누는 파티션 과정이다. 파티션에는 주어진 수열의 길이에 비례하는 시간이 걸린다.

퀵 정렬의 시간 복잡도를 분석하기 따라로운 것은 결과적으로 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없기 때문이다.

기준으로 택한 원소가 최소 원소나 최대 원소인 경우 부분 문제의 크기가 하나씩만 줄어들 수도 있다.

최악의 경우 시간 복잡도는 $O(n^2)$이 되지만 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 퀵 정렬의 시간 복잡도는 병합 정렬과 같은 $O(nlgn)$이 된다.

예제: 카라츠바의 빠른 곱셈 알고리즘

큰 숫자들을 다룰 때 주로 사용한다. 이렇게 큰 숫자들은 배열을 이용해 저장해야 한다. 두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 초등학교 산수 시간에 배운 방법을 그대로 사용하는 것이다.

나쁜 코드에 주석을 달지 마라. 새로 짜라.

• 브라이언 W. 커니핸, P.J. 플라우거

잘 달린 주석은 그 어떤 정보보다 유용하다. 경솔하고 근거 없는 주석은 코드를 이해하기 어렵게 만든다.

우리에게 프로그래밍 언어를 치밀하게 사용해 의도를 표현할 능력이 있다면, 주석은 전혀 필요하지 않다.

우리는 코드로 의도를 표현하지 못해 주석을 사용한다. 주석 없이는 자신을 표현할 방법을 찾지 못해 할 수 없이 주석을 사용한다.

주석이 필요한 상황에 처하면 상황을 역전해 코드로 의도를 표현할 방법은 없을까 곰곰이 생각하자. 주석을 달 때마다 자신에게 표현력이 없다는 사실을 푸념해야 마땅하다.

주석은 나쁜 코드를 보완하지 못한다

코드에 주석을 추가하는 일반적인 이유는 코드 품질이 나쁘기 때문이다.

표현력이 풍부하고 깔끔하며 주석이 거의 없는 코드가, 복잡하고 어수선하며 주석이 많이 딸린 코드보다 훨씬 좋다.

코드로 의도를 표현하라!

몇 초만 더 생각하면 코드로 대다수 의도를 표현할 수 있다. 많은 경우 주석으로 달려는 설명을 함수로 만들어 표현해도 충분하다.

// 직원에게 복지 혜택을 받을 자격이 있는지 검사한다.
if ((employee.flags & HOURLY_FLAG) &&
  (employee.age > 65))

위 코드보다 아래 코드가 낫다.

if (employee.isEligibleForFullBenefits())

좋은 주석

어떤 주석은 필요하거나 유익하다.

법적인 주석

때로는 회사가 정립한 구현 표준에 맞춰 법적인 이유로 특정 주석을 넣으라고 명시한다. 각 소스 파일 첫머리에 주석으로 들어가는 저작권 정보, 소유권 정보는 필요하고도 타당하다. 가능하다면, 표준 라이선스나 외부 문서를 참조해도 되겠다.

정보를 제공하는 주석

때로는 기본적인 정보를 주석으로 제공하면 편리하다. 예를 들어, 다음 주석은 추상 메서드가 반환할 값을 설명한다.

// 테스트 중인 Responder 인스턴스를 반환한다.
protected abstract Responder responderInstance();

가능하다면, 함수 이름에 정보를 담는 편이 더 좋다. 위 코드는 함수 이름을 responderBeingTested로 바꾸면 주석이 필요 없어진다.

다음은 좀 더 나은 예제다.

// kk:mm:ss EEE, MMM dd, yyyy 형식이다.
Pattern timeMatcher = Pattern.compile(
  "\\d*:\\d*:\\d* \\w*, \\\w* \\d*, \\d*");

위에 제시한 주석은 정규표현식이 시각과 날짜를 뜻한다고 설명한다. 이왕이면 시각과 날짜를 변환하는 클래스를 만들어 코드를 옮겨주면 더 좋고 더 깔끔하겠다. 그러면 주석이 필요 없어진다.

의도를 설명하는 주석

때때로 주석은 구현을 이해하게 도와주는 선ㅇ르 넘어 결정에 깔린 의도까지 설명한다. 다음은 예제다. 두 객체를 비교할 때 저자는 다른 어떤 객체보다 자기 객체 높은 순위를 주기로 결정했다.

public int compareTo(Object o)
{
  if(o instanceof WikiPagePath)
  {
    WikiPagePath p = (WikiPagePath) o;
    String compressedName = StringUtil.join(names, "");
    String compressedArgumentName = StringUtil.join(p.names, "");
    return compressedName.compareTo(compressedArgumentName);
  }
  return 1; // 오른쪽 유형이므로 정렬 순위가 더 높다.
}

다음은 더 나은 예제다.

// 스레드를 대량 생성하는 방법으로 어떻게든 경쟁 조건을 만들려 시도한다.
for (int i = 0; i < 25000; i++) {
  WidgetBuilderThread widgetBuilderThread =
    new WidgetBuilderThread(widgetBuilder, text, parent, failFlag);
  Thread thread = new Thread(widgetBuilderThread);
  thread.start();
}

의미를 명료하게 밝히는 주석

일반적으로는 인수나 반환값 자체를 명확하게 만들면 더 좋겠지만, 인수나 반환값이 표준 라이브러리나 변경하지 못하는 코드에 속한다면 의미를 명료하게 밝히는 주석이 유용하다.

assertTrue(a.compareTo(a) == 0); // a == a
assertTrue(a.compareTo(b) != 0); // a != b

그릇된 주석을 달아놓을 위험은 높다. 예제를 살펴보면 알겠지만 주석이 올바른지 검증하기 쉽지 않다. 그러므로 위와 같은 주석을 달 때는 더 나은 방법이 없는지 고민하고 정확히 달도록 각별히 주의한다.

결과를 경고하는 주석

때로 다른 프로그래머에게 결과를 경고할 목적으로 주석을 사용한다.

// 여유 시간이 충분하지 않다면 실행하지 마십시오.
public void _testWithReallyBigFile()
{
  writeLinesToFile(10000000);
  …
}

물론 요즘에는 @Ignore 속성을 이용해 테스트 케이스를 꺼버린다. 구체적인 설명은 @Ignore("실행이 너무 오래 걸린다.") 와 같이 속성에 문자열로 넣어준다. 하지만 JUnit4가 나오기 전에는 메서드 이름 앞에 _ 기호를 붙이는 방법이 일반적인 관레였다.

public static SimpleDateFormat makeStandardHttpDateFormat()
{
  // SimpleDateFormat은 스레드에 안전하지 못하다.
  // 따라서 각 인스턴스를 독립적으로 생성해야 한다.
  SimpleDateFormat df = new SimpleDateFormat("EEE, dd MMM yyyy HH:mm:ss z");
  df.setTimeZone(TimeZone.getTimeZone("GMT"));
  return df;
}

프로그램 효율을 높이기 위해 정적 초기화 함수를 사용하려던 열성적인 프로그래머가 주석 때문에 실수를 면한다.

TODO 주석

때로는 '앞으로 할 일'을 //TODO 주석으로 남겨두면 편하다.

// TODO-MdM 현재 필요하지 않다.
// 체크아웃 모델을 도입하면 함수가 필요 없다.
protected VersionInfo makeVersion() throws Exception
{
  return null;
}

TODO 주석은 프로그래머가 필요하다 여기지만 당장 구현하기 어려운 업무를 기술한다.

• 더 이상 필요 없는 기능을 삭제하라는 알림
• 누군가에게 문제를 봐달라는 요청
• 더 좋은 이름을 떠올려달라는 부탁
• 앞으로 발생할 이벤트에 맞춰 코드를 고치라는 주의
• …

위와 같은 용도로 유용하다.

하지만 어떤 용도로 사용하든 시스템에 나쁜 코드를 남겨 놓는 핑계가 되어서는 안 된다. 그리고 TODO로 떡칠한 코드는 바람직하지 않다. 주기적으로 TODO 주석을 점검해 없애도 괜찮은 주석은 없애라고 권한다.

중요성을 강조하는 주석

자칫 대수롭지 않다고 여겨질 중요성을 강조하기 위해서도 주석을 사용한다.

String listItemContent = match.group(3).trim();
// 여기서 trim은 정말 중요하다. trim 함수는 문자열에서 시작 공백을 제거한다.
// 문자열에 시작 공백이 있으면 다른 문자열로 인식되기 때문이다.
new ListItemwidget(this, listItemContent, this.level + 1);
return buildList(text.substring(math.end()));

공개 API에서 Javadocs

설명이 잘 된 공개 API는 참으로 유용하고 만족스럽다. Javadocs가 없다면 자바 프로그램을 짜기가 아주 어려울거다. 공개 API를 구현한다면 반드시 훌륭한 Javadocs를 작성한다.

여느 주석과 마찬가지로 Javadocs 역시 독자를 오도하거나, 잘못 위치하거나, 그릇된 정보를 전달할 가능성이 존재함을 명심하자.

나쁜 주석

대다수 주석이 이 범주에 속한다. 허술한 코드를 지탱하거나, 엉성한 코드를 변명하거나, 미숙한 결정을 합리화하는 등 프로그래머가 주절거리는 독백에서 크게 벗어나지 못한다.

주절거리는 주석

주석을 달기로 결정했다면 충분한 시간을 들여 최고의 주석을 달도록 노력한다.

public void loadProperties()
{
  try
  {
    String propertiesPath = propertiesLocation + "/" + PROPERTIES_FILE;
    FileInputStream propertiesStream = new FileInputStream(propertiesPath);
    loadedProperties.load(propertiesStream);
  }
  catch(IOException e)
  {
    // 속성 파일이 없다면 기본값을 모두 메모리로 읽어 들였다는 의미다.
  }
}

누가 모든 기본값을 읽어 들이는가? loadProperties.load를 호출하기 전에 읽어 들이는가? 아니면 loadProperties.load가 파일을 읽어 들이기 전에 모든 기본값부터 읽어 들이는가? 저자가 catch 블록을 비워놓기 뭐해 몇 마디 덧붙였을 뿐인가? 아니면 나중에 돌아와서 기본값을 읽어 들이는 코드를 구현하려 했는가?

답을 알아내려면 다른 코드를 뒤져보는 수밖에 없다. 이해가 안 되어 다른 모듈까지 뒤져야 하는 주석은 독자와 제대로 소통하지 못하는 주석이다.

같은 이야기를 중복하는 주석

헤더에 달린 주석이 같은 코드 내용을 그대로 중복한다. 자칫하면 코드보다 주석 읽는 시간이 더 오래 걸린다.

// this.closed가 true일 때 반환되는 유틸리티 메서드다.
// 타임아웃에 도달하면 예의를 던진다.
public synchronized void waitForClose(final long timeoutMillis)
throws Exception
{
  if(!closed)
  {
    wait(timeoutMillis);
    if(!closed)
      throw new Exception("MockResponseSender could not be closed");
  }
}

주석이 코드보다 더 많은 정보를 제공하지 못한다. 코드를 정당화하는 주석도 아니고, 의도나 근거를 설명하는 주석도 아니다. 코드보다 읽기가 쉽지도 않다.

실제로 코드보다 부정확해 독자가 함수를 대충 이해하고 넘어가게 만든다.

/**
 * 이 컴포넌트를 위한 컨테이너 이벤트 Listener
 */
protected Loader loader = null;

오해할 여지가 있는 주석

// this.closed가 true일 때 반환되는 유틸리티 메서드다.
// 타임아웃에 도달하면 예의를 던진다.
public synchronized void waitForClose(final long timeoutMillis)
throws Exception
{
  if(!closed)
  {
    wait(timeoutMillis);
    if(!closed)
      throw new Exception("MockResponseSender could not be closed");
  }
}

위에서는 다음과 같은 오해의 여지가 있다.

this.closed가 true로 변하는 순간에 메서드는 반환되지 않는다. this.closed가 true여야 메서드는 반환된다. 아니면 무조건 타임아웃을 기다렸다 this.closed가 그래도 true가 아니면 예외를 던진다.

주석에 담긴 '살짝 잘못된 정보'로 인해 this.closed가 true로 변하는 순간에 함수가 반환되리라는 생각으로 함수를 호출하게 될 수 있다.

이력을 기록하는 주석

예전에는 모든 모듈 첫머리에 변경 이력을 기록하고 관리하는 관례가 바람직했다. 지금은 소스 코드 관리 시스템이 있다. 이제는 혼란만 가중할 뿐이니 완전히 제거하자.

있으나 마나 한 주석

새로운 정보를 제공하지 못하는 주석을 제거하자.

/**
 * 기본 생성자
 */
protected AnnualDateRule() {
}

/** 월 중 일자 */
private int dayOfMonth;

/**
 * 월 중 일자를 반환한다.
 * @return 월 중 일자
 */
public int getDayOfMonth() {
  return dayOfMonth;
}

위와 같은 주석은 지나친 참견이라 개발자가 주석을 무시하는 습관에 빠진다.

어떤 프로그램이든 가장 기본적인 단위가 함수다.

FitNesse: 오픈 소스 테스트 도구

이해하기 어려운 코드

• 추상화 수준이 다양하다.
• 코드가 너무 길다.
• 두 겹으로 중첩된 if 문은 이상한 플래그를 확인한다.
• 이상한 문자열을 사용한다.
• 이상한 함수를 호출한다.

public static String renderPageWithSetupsAndTeardowns (
    PageData pageData, boolean isSuite
) throws Exception {
    boolean isTestPage = pageData.hasAttribute("Test");
       if (isTestPage) {
        WikiPage testPage = pageData.getWikiPage();
        StringBuffer newPageContent = new StringBuffer();
        includesteupPages(testPage, newPageContent, isSuite);
        newPageContent.append(pageData.getContent());
        includeTeardownPages(testPage, newPageContent, isSuite);
        pageData.setContent(newPageContent.toString());
    }
    return pageData.getHtml();
}

FitNesse에 익숙하지 않으면 100% 이해하기는 어렵지만, 그래도 함수가 설정(setup) 페이지와 해제(teardown) 페이지를 테스트 페이지에 넣은 후 해당 테스트 페이지를 HTML로 렌더링한다는 사실은 짐작할 수 있다.

JUnit: 오픈 소스 단위 테스트 도구

작게 만들어라!

함수를 만드는 규칙

1. '작게!' 만들어라
2. '더 작게!' 만들어라

함수는 작을 수록 좋다. 위의 코드를 다음과 같이 줄여야 마땅하다.

public static String renderPageWithSetupsAndTeardowns(
    PageData pageData, boolean isSuite) throws Exception {
    if (isTestPage(pageData))
        includeSetupAndTeardownPages(pageData, isSuite);
    return pageData.getHtml();
}

블록과 들여쓰기

if 문/else 문/while 문 등에 들어가는 블록은 한 줄이어야 한다. 대개 거기서 함수를 호출한다.

바깥을 감싸는 함수(enclosing function)가 작아질 뿐 아니라, 블록 안에서 호출하는 함수 이름을 적절히 짓는다면 코드를 이해하기 쉬워진다.

중첩 구조가 생길만큼 함수가 커져서는 안 된다는 뜻이다. 함수에서 들여쓰기 수준은 1단이나 2단을 넘어서면 안 된다.

한 가지만 해라!

함수는 한 가지를 해야 한다. 그 한 가지를 잘 해야 한다. 그 한 가지만을 해야 한다.

TO: LOGO 언어에서 사용하는 키워드 'TO'는 루비나 파이썬에서 사용하는 'def'와 똑같다. LOGO에서 모든 함수는 키워드 'to'로 시작한다. 이는 함수를 설계하는 방식에 흥미로운 영향을 미쳤다.

지정된 함수 이름 아래에서 추상화 수준이 하나인 단계만 수행한다면 그 함수는 한 가지 작업만 한다.

함수가 '한 가지'만 하는지 판단하는 방법이 하나 더 있다. 단순히 다른 표현이 아니라 의미 있는 이름으로 다른 함수를 추출할 수 있다면 그 함수는 여러 작업을 하는 셈이다.

함수 당 추상화 수준은 하나로!

함수가 확실히 '한 가지' 작업만 하려면 함수 내 모든 문장의 추상화 수준이 동일해야 한다.

getHtml()

위와 같은 코드는 추상화 수준이 아주 높다.

String pagePathName = PathParser.render(pagepath);

반면, 위와 같은 코드는 추상화 수준이 중간이다.

.append("\n")

그리고, 위와 같은 코드는 추상화 수준이 아주 낮다.

한 함수 내에 추상화 수준을 섞으면 코드를 읽는 사람이 헷갈린다. 특정 표현이 근본 개념인지 아니면 세부사항인지 구분하기 어려운 탓이다.

위에서 아래로 코드 읽기: 내려가기 규칙

코드는 위에서 아래로 이야기처럼 읽혀야 좋다. 한 함수 다음에는 추상화 수준이 한 단계 낮은 함수가 온다. 이것을 내려가기 규칙이라 부른다.

다르게 표현하면, 일련의 TO 문단을 읽듯이 프로그램이 읽혀야 한다는 의미다.

TO 문단: LOGO 키워드인 TO는 영어로 '~하려면'의 의미도 된다.

TO 설정 페이지와 해제 페이지를 포함하려면, 설정 페이지를 포함하고, 테스트 페이지 내용을 포함하고, 해제 페이지를 포함한다. TO 설정 페이지를 포함하려면, 슈트이면 슈트 설정 페이지를 포함한 후 일반 설정 페이지를 포함한다. TO 슈트 설정 페이지를 포함하려면, 부모 계층에서 "SuiteSetUp" 페이지를 찾아 include 문과 페이지 경로를 추가한다. TO 부모 계층을 검색하려면, …

핵심은 짧으면서도 '한 가지'만 하는 함수다. 위에서 아래로 TO 문단을 읽어내려 가듯이 코드를 구현하면 추상화 수준을 일관되게 유지하기가 쉬워진다.

Switch 문

switch 문은 작게 만들기 어렵다. (if/else가 여럿 이어지는 구문도 포함) 코드가 길어지고, '한 가지' 작업만 하는 switch 문을 만들기 어렵다.

다형성을 이용하여 각 switch 문을 저차원 클래스에 숨기고 절대로 반복하지 말자.

public Money calculatePay(Employee e)
throws InvalidEmployeeType {
  switch (e.type) {
    case COMMISSIONED:
      return calculateCommissionedPay(e);
    case HOURLY:
      return calculateHourlyPay(e);
    case SALARIED:
      return calculateSalariedPay(e);
    default:
      throw new InvalidEmployeeType(e.type);
  }
}

위 함수의 문제

1. 함수가 길다. 새 직원 유형을 추가하면 더 길어진다.
2. '한 가지' 작업만 수행하지 않는다.
3. SRP(Single Responsibility Principle)를 위반한다. 코드를 변경할 이유가 여럿이기 때문이다.
4. OCP(Open Closed Principle)를 위반한다. 새 직원 유형을 추가할 때마다 코드를 변경하기 때문이다.

다음과 같이 위와 구조가 동일한 함수가 무한정 존재할 수 있다.

isPayday(Employee e, Date date);

혹은

deliverPay(Employee e, Money pay);

이 문제를 해결하려면 switch 문을 추상 팩토리(ABSTRACT FACTORY)에 꽁꽁 숨기는 것이다. 팩토리는 switch 문을 사용해 적절한 Employee 파생 클래스의 인스턴스를 생성한다. calculatePay, isPayday, deliverPay 등과 같은 함수는 Employee 인터페이스를 거쳐 호출된다. 그러면 다형성으로 인해 실제 파생 클래스의 함수가 실행된다.

public abstract class Employee {
  public abstract boolean isPayday();
  public abstract Money calculatePay();
  public abstract void deliverPay(Money pay);
}

// 다른 클래스

public interface EmployeeFactory {
  public EMployee makeEmployee(EmployeeRecord r) throws InvalidEmployeeType;
}

// 다른 클래스

public class EmployeeFactoryImpl implements EmployeeFactory {
  public Employee makeEmployee(EmployeeRecord r) throws InvalidEmployeeType {
    switch (r.type) {
      case COMMISIONED:
        return new CommissionedEmployee(r);
      case HOURLY:
        return new HourlyEmployee(r);
      case SALARIED:
        return new SalariedEmployee(r);
      default:
        throw new InvalidEmployeeType(r.type);
    }
  }
}

switch 문을 단 한 번만 참아주자. 다형적 객체를 생성하는 코드 안에서다. 이렇게 상속 관계로 숨긴 후에는 절대로 다른 코드에 노출하지 않는다.

서술적인 이름을 사용하라!

워드가 말했던 원칙

"코드를 읽으면서 짐작했던 기능을 각 루틴이 그대로 수행한다면 깨끗한 코드라 불러도 되겠다."

한 가지만 하는 작은 함수에 좋은 이름을 붙인다면 이런 원칙을 절반은 달성했다고 할 수 있다.

• 길고 서술적인 이름이 짧고 어려운 이름보다 좋다.
• 길고 서술적인 이름이 길고 서술적인 주석보다 좋다.

이름을 정하느라 시간을 들여도 괜찮다! 서술적인 이름을 사용하면 개발자 머릿속에서도 설계가 뚜렷해지므로 코드를 개선하기 쉬워진다.

이름을 붙일 때는 일관성이 있어야 한다. 모듈 내에서 함수 이름은 같은 문구, 명사, 동사를 사용한다. includeSetupAndTeardownPages, includeSetupPages, includeSuiteSetupPage, includeSetupPage 등이 좋은 예다.

문체가 비슷하면 이야기를 순차적으로 풀어가기도 쉬워진다.

함수 인수

함수에서 이상적인 인수 개수는 0개(무항)다. 다음은 1개(단항)고, 다음은 2개(이항)다. 3개(삼항)는 가능한 피하는 편이 좋다. 4개 이상(다항)은 특별한 이유가 필요하다. 특별한 이유가 있어도 사용하면 안 된다.

includeSetupPageInto(new PageContent) 보다 includeSetupPage()가 이해하기 더 쉽다. 전자는 함수 이름과 인수 사이에 추상화 수준이 다르다. 게다가 코드를 읽는 사람이 현 시점에서 별로 중요하지 않은 세부사항, 즉 StringBuffer를 알아야 한다.

테스트 관점에서 보면 인수는 더 어렵다. 갖가지 인수 조합으로 함수를 검ㅁ증하는 테스트 케이스를 작성한다고 하면 인수가 없을 때 간단하다.

출력 인수는 입력 인수보다 이해하기 어렵다.

최선은 입력 인수가 없는 경우이며, 차선은 입력 인수가 1개뿐인 경우다. SetupTeardownIncluder.render(pageData)는 이해하기 아주 쉽다. pageData 객체 내용을 렌더링하겠다는 뜻이다.

많이 쓰는 단항 형식

함수에 인수 1개를 넘기는 이유로 가장 흔한 경우는 두 가지다.

1. 인수에 질문을 던지는 경우 boolean fileExists("MyFile")이 좋은 예다.
2. 인수를 뭔가로 변환해 결과를 반환하는 경우 InputStream fileOpen("MyFile")은 String 형의 파일 이름을 InputStream으로 변환한다.

함수 이름을 지을 때는 두 경우를 분명히 구분한다. 또한 언제나 일관적인 방식으로 두 형식을 사용한다.

다소 드물게 사용하지만 그래도 아주 유용한 단항 함수 형식이 이벤트다. 이벤트 함수는 출력 인수가 없고 입력 인수만 있다. 프로그램은 함수 호출을 이벤트로 해석해 입력 인수로 시스템 상태를 바꾼다. passwordAttemptFailedNtimes(int attempts)가 좋은 예다. 이벤트라는 사실이 코드에 명확히 드러나야 한다.

플래그 인수

플래그 인수는 추하다. 함수로 부울 값을 넘기는 관례는 함수가 한꺼번에 여러 가지를 처리한다고 대놓고 공표하는 셈이다. render(boolean isSuite)보다 renderForSuite()와 renderForSingleTest()라는 함수로 나누는 것이 낫다.

이항 함수

인수가 2개인 함수는 인수가 1개인 함수보다 이해하기 어렵다. 예를 들어, writeField(name)는 writeField(outputStream, name)보다 이해하기 쉽다.

이항 함수가 적절한 경우도 있다. Point p = new Point(0, 0)가 좋은 예다. 직교 좌표계 점은 일반적으로 인수 2개를 취한다. 여기서 인수 2개는 한 값을 표현하는 두 요소다. 두 요소에는 자연적인 순서도 있다.

가능하면 단항 함수로 바꾸도록 애쓰자. 예를 들어, writeField 메서드를 outputStream 클래스 구성원으로 만들어 outputStream.writeField(name)으로 호출한다.

아니면 outputStream을 현재 클래스 구성원 변수로 만들어 인수로 넘기지 않는다.

아니면 FieldWriter라는 새 클래스를 만들어 구성자에서 outputStream을 받고 write 메서드를 구현한다.

삼항 함수

인수가 3개인 함수는 인수가 2개인 함수보다 훨씬 더 이해하기 어렵다. 반면 assertEquals(1.0, amount, .001)은 그리 음험하지 않은 삼항 함수다. 여전히 주춤하게 되지만 그만한 가치가 충분하다. 부동소수점 비교가 상대적이라는 사실은 언제든 주지할 중요한 사항이다.

인수 객체

인수가 2-3개 필요하다면 일부를 독자적인 클래스 변수로 선언할 가능성을 짚어보자.

Circle makeCircle(double x, double y, double radius);
Circle makeCircle(Point center, double radius);

객체를 생성해 인수를 줄이는 방법이 눈속임이라 여겨질 수 있지만 그렇지 않다. 위 예제에서 x와 y를 묶었듯이 변수를 묶어 넘기려면 이름을 붙여야 하므로 결국은 개념을 표현하게 된다.

인수 목록

때로는 인수 개수가 가변적인 함수도 필요하다. String.format 메서드가 좋은 예다.

가변 인수 전부를 동등하게 취급하면 List 형 인수 하나로 취급할 수 있다. 이런 논리로 따져보면 String.format은 사실상 이항 함수다.

동사와 키워드

함수의 의도나 인수의 순서와 의도를 제대로 표현하려면 좋은 함수 이름이 필수다. 단항 함수는 함수와 인수가 동사/명사 쌍을 이뤄야 한다. 예를 들어, write(name)은 누구나 곧바로 이해한다. 좀 더 나은 이름은 writeField(name)이다. 그러면 name이 field라는 사실이 분명히 드러난다.

함수 이름에 키워드를 추가하는 형식도 있다. 함수 이름에 인수 이름을 넣는다. 예를 들어 assertEquals보다 assertExpectedEqualsActual(expected, actual)이 더 좋다. 그러면 인수 순서를 기억할 필요가 없어진다.

부수 효과를 일으키지 마라!

부수 효과는 함수에서 한 가지를 하겠다고 약속하고선 남몰래 다른 짓을 한다. 많은 경우 시간적인 결합(temporal coupling)이나 순서 종속성(order dependency)을 초래한다.

부수 효과는 시간적인 결합을 초래한다. 시간적인 결합은 혼란을 초래한다.

부수적인 효과가 필요하다면 함수 이름에 명시하자.

출력 인수

일반적으로 우리는 인수를 함수 입력으로 해석한다.

appendFooter(s); 이 함수는 무언가에 s를 바닥글로 첨부할까? 아니면 s에 바닥글을 첨부할까? 인수 s는 입력일까 출력일까?

함수 선언부를 찾아보면 분명해진다.

public void appendFooter(StringBuffer report)

함수 선언부를 찾아보는 행위는 코드를 보다가 주춤하는 행위와 동급이다. 인지적으로 거슬린다는 뜻이므로 피해야 한다.

객체 지향 언어에서는 출력 인수를 사용할 필요가 거의 없다. 출력 인수로 사용하라고 설계한 변수가 바로 this이기 때문이다. 다시 말해, appendFooter는 report.appendFooter() 와 같이 호출하는 방식이 좋다.

일반적으로 출력 인수는 피해야 한다. 함수에서 상태를 변경해야 한다면 함수가 속한 객체 상태를 변경하는 방식을 택한다.

명령과 조회를 분리하라!

함수는 뭔가를 수행하거나 뭔가에 답하거나 둘 중 하나만 해야 한다. 객체 상태를 변경하거나 아니면 객체 정보를 반환하거나 둘 중 하나다.

public boolean set(String attribute, String value);

이 함수는 이름이 attribute인 속성을 찾아 값을 value로 설정한 후 성공하면 true를 반환하고 실패하면 false를 반환한다. 그래서 다음과 같이 괴상한 코드가 나온다.

if (set("username", "unclebob"))...

"username"이 "unclebob"으로 설정되어 있는지 확인하는 코드인가? "username"을 "unclebob"으로 설정하는 코드인가? 의미가 모호한다.

setAndCheckIfExists라고 함수 이름을 바꾸는 방법도 있지만 if 문에 넣고 보면 여전히 어색하다. 진짜 해결책은 명령과 조회를 분리해 혼란을 애초에 뿌리뽑는 방법이다.

if (attributeExists("username")) {
  setATtribute("username", "unclebob");
  ...
}

오류 코드보다 예외를 사용하라!

명령 함수에서 오류 코드를 반환하는 방식은 명령/조회 분리 규칙을 미묘하게 위반한다. 자칫하면 if 문에서 명령을 표현식으로 사용하기 쉬운 탓이다.

if (DeletePage(page) == E_OK)

위 코드는 여러 단계로 중첩되는 코드를 야기한다. 오류 코드를 반환하면 호출자는 오류 코드를 곧바로 처리해야 한다는 문제에 부딪힌다.

반면 오류 코드 대신 예외를 사용하면 오류 처리 코드가 원래 코드에서 분리되므로 코드가 깔끔해진다.

try {
  deletePage(page);
  registry.delteReference(page.name);
  configKeys.deleteKey(page.name.makeKey());
}
catch (Exception e) {
  logger.log(e.getMessage());
}

Try/Catch 블록 뽑아내기

try/catch 블록은 원래 추하다. 그러므로 try/catch 블록을 별도 함수로 뽑아내는 편이 좋다.

public void delete(Page page) {
  try {
    deletePageAndAllReferences(page);
  }
  catch (Exception e) {
    logError(e);
  }
}

실제로 페이지를 제거하는 함수는 deletePageAndAllReferences다. 이 함수는 예외를 처리하지 않는다.

이렇게 정상 동작과 오류 처리 동작을 분리하면 코드를 이해하고 수정하기 쉬워진다.

오류 처리도 한 가지 작업이다.

함수는 '한 가지' 작업만 해야 한다. 오류 처리도 '한 가지' 작업이다. 그러므로 오류를 처리하는 함수는 오류만 처리해야 마땅하다.

함수에 키워드 try가 있다면 함수는 try 문으로 시작해 catch/finally 문으로 끝나야 한다는 말이다.

Error.java 의존성 자석

오류 코드를 반환한다는 이야기는, 클래스든 열거형 변수든, 어디선가 오류 코드를 정의한다는 뜻이다.

public enum Error {
  OK,
  LOCKED,
  WAITING_FOR_EVENT
}

위와 같은 클래스는 의존성 자석이다. 다른 클래스에서 Error enum을 import해 사용해야 하므로, Error enum이 변한다면 이를 사용하는 클래스 전부를 재컴파일, 재배치해야 한다. 그래서 Error 클래스 변경이 어려워진다.

오류 코드 대신 예외를 사용하면 새 예외는 Exception 클래스에서 파생된다. 따라서 재컴파일/재배치 없이도 새 예외 클래스를 추가할 수 있다. OCP를 보여주는 예다.

OCP: 기존의 코드를 변경하지 않으면서 기능을 추가할 수 있도록 설계가 되어야 한다.

반복하지 마라!

중복은 문제다. 코드 길이가 늘어날 뿐 아니라 알고리즘이 변하면 네 곳이나 손봐야 한다. 게다가 어느 한곳이라도 빠뜨린다면 오류가 발생할 확률이 네 배나 높다.

include 방법으로 중복을 없앨 수 있다.

AOP(Aspect Oriented Programming): 어떤 로직을 기준으로 핵심적인 관점, 부가적인 관점으로 나누어서 보고 그 관점을 기준으로 각각 모듈화하자. COP(Component Oriented Programming): 기존의 시스템이나 소프트웨어를 구성하는 컴포넌트를 조립해서 하나의 새로운 응용 프로그램을 만드는 소프트웨어 개발방법론

구조적 프로그래밍

에츠허르 데이크스트라Edsger Dijkstra 는 모든 함수와 함수 내 모든 블록에 입구와 출구가 하나만 존재해야 한다고 말했다. 즉, 함수는 return 문이 하나여야 한다는 말이다. 루프 안에서 break나 continue를 사용해선 안 되며 goto는 절대로, 절대로 안 된다.

구조적 프로그래밍의 목표와 규율은 좋지만, 함수가 작다면 위 규칙은 별 이익을 제공하지 못한다.

함수를 작게 만든다면 간혹 return, break, continue를 여러 차례 사용해도 괜찮다. 오히려 때로는 단일 입/출구 규칙single entry-exit rule 보다 의도를 표현하기 쉬워진다. 반면, goto 문은 큰 함수에서만 의미가 있으므로, 작은 함수에서는 피해야만 한다.

함수를 어떻게 짜죠?

처음에는 길고 복잡한다. 들여쓰기 단계도 많고 중복된 루프도 많다. 인수 목록도 아주 길다. 이름은 즉흥적이고 코드는 중복된다. 하지만 서투른 코드를 빠짐없이 테스트하는 단위 테스트 케이스도 만든다.

그런 다음 코드를 다듬고, 함수를 만들고, 이름을 바꾸고, 중복을 제거한다. 메서드를 줄이고 순서를 바꾼다. 때로는 전체 클래스를 쪼개기도 한다. 이 와중에도 코드는 항상 단위 테스트를 통과한다.

최종적으로는 이 장에서 설명한 규칙을 따르는 함수가 얻어진다. 처음부터 탁 짜내지 않는다. 그게 가능한 사람은 없을거다.

결론

모든 시스템은 특정 응용 분야 시스템을 기술할 목적으로 프로그래머가 설계한 도메인 특화 언어 Domain Specific Language, DSL 로 만들어진다.

Master 프로그래머는 시스템을 (구현할) 프로그램이 아니라 (풀어갈) 이야기로 여긴다.

프로그래밍 언어라는 수단을 사용해 좀 더 풍부하고 좀 더 표현력이 강한 언어를 만들어 이야기를 풀어간다. 시스템에서 발생하는 모든 동작을 설명하는 함수 계층이 바로 그 언어에 속한다.

각 동작은 바로 그 도메인에 트고하된 언어를 사용해 자신만의 이야기를 풀어간다.

여기서 설명한 규칙을 따른다면 길이가 짧고, 이름이 좋고, 체계가 잡힌 함수가 나오리라. 하지만 진짜 목표는 시스템이라는 이야기를 풀어가는 데 있다.

내가 작성한 함수가 분명하고 정확한 언어로 깔끔하게 같이 맞아떨어져야 이야기를 풀어가기가 쉬워진다는 사실을 명심하자.

참고 문헌

[KP78]: Kernighan and Plaugher, The Elements of Programming Style, 2d, ed., McGraw-Hill, 1978. [PPP02]: Agile Software Devlopment: Principles, Patterns, and Practices, Robert C. Martin, Prentice Hall, 2002. 『소프트웨어 개발의 지혜: 원칙, 디자인패턴, 실천방법』(2004 야스미디어, 이용원 옮김) [GOF]: Design Patterns: Elements of Reusable Object Oriented Software, Gammaet al.,Addison-Wesley, 1996. 『GOF의 디자인 패턴(개정판)』(2007 피어슨에듀케이션코리아, 김정아 옮김) [PRAG]: The Pragmatic Programmer, Andrew Hunt, Dave Thomas, Addison-Wesley, 2000. 『실용주의 프로그래머』(2006 인사이트, 김창준 정지호 옮김) [SP72]: Structured Programming, O.-J. Dahl, E. W. Eijkstra, C. A. R. Hoare, Academic Press, London, 1972.

알고리즘을 고안하기 위해서는 해결할 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해해야 하며, 적절한 자료 구조를 선택할 줄 알아야 한다.

대부분의 사람들이 쉬운 문제를 어렵게 푸는 실수를 한다. 이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어보자. "무식하게 풀 수 있을까?"

전산학에서 "무식하게 푼다(brute-force)"라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.

가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부른다.

재귀 호출과 완전 탐색

재귀 호출

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function) 혹은 재귀 호출(recursion)이다.

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 한다.

base case를 선택할 때는 존재하는 모든 입력이 항상 base case의 답을 이용해 계산될 수 있도록 신경써야 한다.

int recursiveSum(int n) {
    if(n == 1) return 1; // 더이상 쪼개지지 않을 때
    return n + recursiveSum(n-1);

위 코드에서 만약 n이 1인 경우를 확인하는 것이 아니라 n이 2인지 확인하고, 2라면 3을 반환한다고 가정해 보자.

이렇게 구현하더라도 입력이 2 이상이라면 아무 문제 없이 답을 모두 계산할 수 있지만 1이 입력으로 들어오면 문제가 생긴다.

예제: 중첩 반복문 대체하기

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘을 구현하자. 중첩 반복문으로 구현하면 다음과 같다.

for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
    for (int k = j + 1; k < n; ++k)
        for (int l = k + 1; l < n; ++l)
        cout << i << " " << j << " " << k << " " << l << '\n';

위와 같은 중첩 for문은 골라야 할 원소의 수가 늘어날수록 코드가 길고 복잡해지는데다, 골라야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다.

각 조각에서 하나의 원소를 고르자. 이렇게 원소를 고른 뒤, 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성하자.

남은 원소들을 고르는 '작업'을 다음과 같은 입력들의 집합으로 정의할 수 있다.

• 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

#include <iostream>
#include <vector>

using namespace std;

void printElements(vector<int>& elementsToPrint) {
    const int ELEMENT_SIZE = elementsToPrint.size();
    for (int i = 0; i < ELEMENT_SIZE; ++i)
        cout << elementsToPrint[i] << ' ';
    cout << '\n';
}

void printCombination(const int TOTAL_ELEMENT_AMOUNT, vector<int>& elementsToPrint, int remainedElement) {
    if (remainedElement == 0) {
        printElements(elementsToPrint);
        return;
    }

    int starting = elementsToPrint.size() == 0 ? 0 : elementsToPrint.back() + 1;

    for (int i = starting; i < TOTAL_ELEMENT_AMOUNT; ++i) {
        elementsToPrint.push_back(i);
        printCombination(TOTAL_ELEMENT_AMOUNT, elementsToPrint, remainedElement - 1);
        elementsToPrint.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> elementsToPrint;
    printCombination(n, elementsToPrint, m);
    return 0;
}

이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생성한다.

이 코드는 중첩 for문과 달리 우리가 n개의 원소 중에서 몇 개를 고르든지 사용할 수 있다.

예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)

게임판에서의 현재 위치 (x, y) 그리고 단어 word가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?

hasWord(x, y, word) = 보글 게임판의 (x, y)에서 시작하는 단어 word의 존재 여부를 반환한다.

이 문제를 풀 때 가장 까다로운 점은 다음 글자가 될 수 있는 칸이 여러 개 있을 때 이 중 어느 글자를 선택해야 할지 미리 알 수 없다는 점이다.

간단한 방법은 완전 탐색을 이용해, 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 보면 된다.

문제의 분할

hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르다면 곧장 false를 반환하고 종료한다. 그러고 나면 원래 단어 word에서 첫 글자를 뗀 단어 word[1..]을 격자에서 찾으면 된다.

기저 사례의 선택

1. 위치 (x, y)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
2. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

간결한 코드를 작성하는 유용한 팁으로, 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하는 것이다. 그러면 함수를 호출하는 시점에서 이런 오류를 검사할 필요가 없다.

나의 구현

#include <iostream>
#include <vector>

#define BOARD_SIZE    5

using namespace std;

typedef vector<vector<char>> GameBoard;

bool isStartFrom(GameBoard& gameBoard, int x, int y, string& word) {
    return gameBoard[x][y] == word[0];
}

string getRidofFirstCharacter(string& word) {
    return word.substr(1);
}

bool hasWord(GameBoard& gameBoard, int x, int y, string& word) {
    if (word.size() == 0) return true;
    if (x < 0 || y < 0) return false;
    if (!isStartFrom(gameBoard, x, y, word)) return false;
    string seperatedWord = getRidofFirstCharacter(word);
    for (int newX = x - 1; newX <= x + 1 && newX < BOARD_SIZE; ++newX) {
        for (int newY = y - 1; newY <= y + 1 && newY < BOARD_SIZE; ++newY) {
            if (newX == x && newY == y) continue;
            if (hasWord(gameBoard, newX, newY, seperatedWord))
                return true;
        }
    }
    return false;
}

bool findWord(GameBoard& gameBoard, string& word) {
    for (int x = 0; x < BOARD_SIZE; ++x) {
        for (int y = 0; y < BOARD_SIZE; ++y) {
            if (hasWord(gameBoard, x, y, word))
                return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int C;
    cin >> C;
    while (C--) {
        GameBoard gameBoard(BOARD_SIZE, vector<char>(BOARD_SIZE));
        for (int i = 0; i < BOARD_SIZE; ++i)
            for (int j = 0; j < BOARD_SIZE; ++j)
                cin >> gameBoard[i][j];
        int N;
        cin >> N;
        while (N--) {
            string word;
            cin >> word;
            cout << word << " " << (findWord(gameBoard, word) ? "YES" : "NO");
            cout << '\n';
        }
    }
    return 0;
}

책의 구현

const int dx[8] = { -1, -1, -1, 1, 1, 1, 0, 0 };
const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1 };
// 5x5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, int x, const string& word) {
  // 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
  if(!inRange(y, x)) return false;
  // 기저 사례 2: 첫 글자가 일치하지 않으면 실패
  if(board[y][x] != word[0]) return flase;
  // 기저 사례 3: 단어 길이가 1이면 성공
  if(word.size() == 1) return true;
  // 인접한 여덟 칸을 검사한다.
  for(int direction = 0; direction < 8; ++direction) {
    int nextY = y + dy[direction], nextX = x + dx[direction];
    // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
    if(hasWord(nextY, nextX, word.substr(1)))
      return true;
  }
  return false;
}

1. 함수의 처음에서 시작 위치의 범위와 첫 글자 일치 여부를 확인하고 있기 때문에 for문 안에서 별도로 확인을 하지 않아도 된다.
2. 다음 칸의 상대 좌표 목록을 함수 내에 직접 코딩해 넣은 것이 아니라 별도의 변수로 분리했다.

시간 복잡도 분석

최악인 경우는 답이 아예 존재하지 않는 경우인 때가 많다. 예를 들어 A로 가득찬 격자에서, 단어 AAAAAH를 찾는다고 하면, 찾을 가능성이 없지만, 완전 탐색은 그걸 모른다.

마지막 글자에 도달하기 전에는 주변의 모든 칸에 대해 재귀 호출을 하게 된다. 각 칸에는 최대 여덟 개의 이웃이 있고, 탐색은 단어의 길이 $N$에 대해 $N-1$단계 진행된다. 따라서 우리가 검사하는 후보의 수는 최대 $8^{N-1}=O(8^N)$이 되고, 이것이 이 알고리즘의 시간 복잡도가 된다.

완전 탐색 레시피

문제를 처음 접근하는 대략적인 지침

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 완전히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지 가늠한다. 만약 시간 안에 계산할 수 없다면 다른 장에서 소개하는 설계 패러다임을 적용하자.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나 밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.

이론적 배경: 재귀 호출과 부분 문제

재귀 호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다. {1, 2, 3}을 정렬하는 문제와 {3, 2, 1}을 정렬하는 문제는 서로 다른 문제다.

보글 게임에서는 아홉 가지 정보를 알아야 한다.

1. 현재 위치 (x, y)에 단어의 첫 글자가 있는가?
2. 윗 칸 (y-1, x)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
3. …

2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과다. 문제를 구성하는 조각들 중 하나를 뺏기 때문에, 이 문제들은 원래 문제의 일부라고 할 수 있다. 이런 문제들을 원래 문제의 부분 문제라고 한다.

문제: 소풍 (문제 ID: PICNIC, 난이도: 하)

문제 보기 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 계산하는 프로그램을 작성하자.

완전 탐색

가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 조합을 모두 만들어 보는 것이다. 재귀 호출을 이용해 문제를 해결하려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나누어야 한다. 전체 문제를 $\frac{n}{2}$개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 주는 것으로 하자. 이때 문제의 형태는 '아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라'가 된다.

중복으로 세는 문제

다음과 같은 경우가 있다.

• 같은 학생 쌍을 두 번 짝지어 준다. 예를 들어 (0, 1)과 (1, 0)을 따로 센다.
• 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다. 예를 들어 (0, 1) 후에 (2, 3)을 짝지어 주는 것과 (2, 3) 후에 (0, 1)을 짝지어주는 것을 다른 경우로 센다.

실질적으로 같은 답을 중복으로 세는 이런 상황은 경우의 수를 다룰 때 굉장히 흔하게 마주치게 된다.

좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다. 흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있다. 예를 들어 (2, 3), (0, 1) 말고 (0, 1), (2, 3)만 세는 것이다.

이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.

1. 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일 수밖에 없기 때문에 (1, 0)과 같은 짝은 나올 수 없다.
2. 항상 번호가 가장 빠른 학생부터 짝을 짓기 때문에 (2, 3), (0, 1)의 순서로 짝을 지어줄 일도 없다.

답의 수의 상한

모든 답을 생성해 가며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸린다. 실제로 프로그램을 짜기 전에 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는 데 시간이 얼마나 오래 걸릴지를 확인해야 된다.

이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 서로 친구인 경우다. 이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 아홉 명이고, 그 다음 학생이 선택할 수 있는 짝은 일곱 명이다.

이와 같이 나가면 최종 답의 개수는 $9×7×5×3×1=945$ 가 된다.

구현

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<bool>> Graph;
typedef vector<bool> Paired;

int n = 0;

int countPairCase(const Graph& graph, Paired paired) {
    int toPair = -1;
        // 가장 빠른 순서의 학생을 구합니다.
    for (int i = 0; i < n; ++i)
        if (!paired[i]) {
            toPair = i;
            break;
        }
        // 더 이상 짝을 지어줄 학생이 없다면 종료합니다.
    if (toPair == -1) return 1;
    int caseCount = 0;
    for (int i = toPair + 1; i < n; ++i) {
            // 두 학생이 친구인지, 이미 짝이 지어진 학생이 아닌지 검사합니다.
                // 조건에 부합하면 짝을 지어주고 재귀 호출합니다.
        if (graph[toPair][i] && !paired[i]) {
            paired[toPair] = paired[i] = true;
            caseCount += countPairCase(graph, paired);
            paired[toPair] = paired[i] = false;
        }
    }
    return caseCount;
}

void linkNodeByKeyboard(Graph& graph) {
    int from, to;
    cin >> from >> to;
    graph[from][to] = 1;
    graph[to][from] = 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int C;
    cin >> C;
    while (C--) {
        int m;
        cin >> n >> m;
        Graph graph(n, vector<bool>(n));
        Paired paired = vector<bool>(n);
        for (int i = 0; i < m; ++i)
            linkNodeByKeyboard(graph);
        cout << countPairCase(graph, paired) << '\n';
    }
    return 0;
}

문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

문제 보기 게임판이 주어질 때 이를 L자 모양의 3칸짜리 블록으로 덮는 방법의 수를 계산하는 프로그램을 작성하자.

완전 탐색

이 문제도 경우의 수를 세는 것이니만큼, 게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 해결할 수 있다.

• 입력으로 주어진 게임판에서 흰 칸의 수가 3의 배수가 아닐 경우 무조건 답이 없으므로 따로 처리한다.
• 이 외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 하자. 재귀 함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하자.

중복으로 세는 문제

같은 배치도 블록을 놓는 순서에 따라서 여러 번 셀 수 있다. 특정한 순서대로 답을 생성하도록 강제해야 한다.

재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하자. 한 답을 한 가지 방법으로밖에 생성할 수 없으므로 중복으로 세지 않는다.

각 칸을 채우는 방법은 다음과 같다. 순서대로 (a), (b), (c), (d), (e)

재귀 호출 알고리즘은 첫 번째 빈 칸을 찾은 후 덮을 방법을 하나하나 시도한다. 이 방법이 달라질 때마다 서로 다른 배치가 되므로, 우리가 원하는 답은 남은 게임판을 재귀 호출에 넘겨서 얻은 경우의 수를 모두 더한 수가 된다.

답의 수의 상한

한 블록을 놓을 때마다 모두 네 가지의 선택지가 있다. 우리는 최대 $\lfloor\frac{50}{3}\rfloor=16$개의 블록을 놓기 때문에 가능한 답의 상한은 $4^{16}=2^{32}$개가 된다. 이론 상으로는 굉장히 큰 수지만, 실제 작성해보면 시간 안에 답을 구할 수 있다는 확신을 얻을 수 있다.

구현

• 한 칸을 덮는 네 가지 방법을 배열에 저장한다. 이 배열은 네 가지 방법에서 새로 채워질 칸들의 상대 좌표의 목록을 저장한다.
• coverBoardWithCenterAndType()은 해당 위치에 블록을 놓을 수 있는지 여부도 같이 판단한다. 단, 이때 곧장 함수를 종료하면 안 된다. 만약 블록을 구성하는 세 칸 중에 기존의 블록과 겹치는 칸이 있다면, 함수를 곧장 종료하면 나중에 덮었던 블록을 치울 때, 두 번째 칸에 이미 있던 블록마저 치워 버리게 된다. 따라서 그 자리에 1을 더함으로써 두 개의 블록이 겹쳐서 놓여 있다고 표시한다.

#include <iostream>
#include <vector>

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)

#define BLOCK_SPACE    3
#define NONE        -1
#define TYPE_AMOUNT    4
#define COVER        1
#define ERASE        -1
#define OVERLAP        1

using namespace std;

typedef vector<vector<int>> GameBoard;

typedef struct Point { int x, y; } Point;

const int COVER_TYPE[TYPE_AMOUNT][BLOCK_SPACE][2] = {
    {{0,0},{1,0},{0,1}},    // (b)
    {{0,0},{0,1},{1,1}},    // (c)
    {{0,0},{1,0},{1,1}},    // (d)
    {{0,0},{1,0},{1,-1}},    // (e)
};

Point findFirstWhite(GameBoard& gameBoard) {
    FOR(y, 0, gameBoard.size()) {
        FOR(x, 0, gameBoard[0].size()) {
            if (!gameBoard[y][x])
                return { x, y };
        }
    }
    return { NONE, NONE };
}

bool hasNoWhite(Point& whitePoint) {
    return whitePoint.x == NONE || whitePoint.y == NONE;
}

bool coverBoardWithCenterAndType(GameBoard& gameBoard, Point center, int type) {
    bool canCoverBoard = true;
    FOR(i, 0, BLOCK_SPACE) {
        const int COVERED_Y = center.y + COVER_TYPE[type][i][0];
        const int COVERED_X = center.x + COVER_TYPE[type][i][1];
        if (COVERED_Y < 0 || COVERED_X < 0 ||
            COVERED_Y >= gameBoard.size() || COVERED_X >= gameBoard[0].size())
            canCoverBoard = false;
        else if ((gameBoard[COVERED_Y][COVERED_X] += COVER) > OVERLAP)
            canCoverBoard = false;
    }
    return canCoverBoard;
}

bool eraseBoardWithCenterAndType(GameBoard& gameBoard, Point center, int type) {
    bool canCoverBoard = false;
    FOR(i, 0, 3) {
        const int COVERED_Y = center.y + COVER_TYPE[type][i][0];
        const int COVERED_X = center.x + COVER_TYPE[type][i][1];
        if (COVERED_Y < 0 || COVERED_X < 0 ||
            COVERED_Y >= gameBoard.size() || COVERED_X >= gameBoard[0].size())
            canCoverBoard = false;
        else if ((gameBoard[COVERED_Y][COVERED_X] += ERASE) > OVERLAP)
            canCoverBoard = false;
    }
    return canCoverBoard;
}

int countCoverCapacity(GameBoard& gameBoard) {
    Point firstWhite = findFirstWhite(gameBoard);
    if (hasNoWhite(firstWhite)) return 1;

    int capacity = 0;
    FOR(type, 0, TYPE_AMOUNT) {
        if (coverBoardWithCenterAndType(gameBoard, firstWhite, type))
            capacity += countCoverCapacity(gameBoard);
        eraseBoardWithCenterAndType(gameBoard, firstWhite, type);
    }
    return capacity;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int C;
    cin >> C;
    while (C--) {
        int H, W;
        cin >> H >> W;
        GameBoard gameBoard = vector<vector<int>>(H, vector<int>(W));
        int whiteAmount = 0;
        FOR(y, 0, H) {
            FOR(x, 0, W) {
                char temp;
                cin >> temp;
                whiteAmount += temp == '.' ? 1 : 0;
                gameBoard[y][x] = temp == '#' ? 1 : 0;
            }
        }
        if (whiteAmount % BLOCK_SPACE == 0)
            cout << countCoverCapacity(gameBoard) << '\n';
        else
            cout << "0\n";
    }
    return 0;
}

최적화 문제

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제(Optimization problem)라고 부른다.

최적화 문제의 예

• n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
• 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제

최적화 문제를 해결하는 방법

• 동적 계획법
• 조합 탐색
• 최적화 문제를 결정 문제로 바꿔 해결하는 기법

가장 기초적인 것이 완전 탐색이다. 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 된다.

예제: 여행하는 외판원 문제

문제 보기 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾자.

책과의 차이점

1. 시작 지점으로 돌아가는 경로는 제외한다. (사이클이 아닌 단순 경로를 구해야 한다.)
2. 시작 지점은 0뿐만 아니라 모든 점이 될 수 있다.

무식하게 풀 수 있을까?

완전 탐색으로 문제를 풀기 위해서는 첫번째로 시간 안에 답을 구할 수 있을지 확인해야 한다. 우리가 시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 신경 쓰지 않고 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다. 그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 된다.

n-1개의 도시를 나열하는 방법은 모두 $(n-1)!$가지가 있다. 도시가 열 개라면 경로의 수는 $9!=362,880$개가 된다. 따라서 안전하게 완전 탐색을 사용해 문제를 해결할 수 있음을 알 수 있다.

알고스팟의 문제에서는 최대 8개의 도시가 있고, 시작한 도시로 돌아오지 않기 때문에 경로의 수는 $8!=40320$개가 된다.

재귀 호출을 통한 답안 생성

n개의 도시로 구성된 경로를 n개의 조각으로 나눠, 앞에서부터 도시를 하나씩 추가해 경로를 만들어 가기로 하자.

shortestPath(path)=path가 지금까지 만든 경로일 때, 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.

책의 구현

int n;    // 도시의 수
double dist[MAX][MAX];    // 두 도시 간의 거리를 저장하는 배열
// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited,
        double currentLength) {
  // 기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
  if(path.size() == n)
    return currentLength + dist[path[0]][path.back()];
  double ret = INF; // 매우 큰 값으로 초기화
  // 다음 방문할 도시를 전부 시도해 본다.
  for(int next = 0; next < n; ++next) {
    if(visited[next]) continue;
    int here = path.back();
    path.push_back(next);
    visited[next] = true;
    // 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
    double cand = shortestPath(path, visited, currentLength + dist[here][next]);
    ret = min(ret, cand);
    visited[next] = false;
    path.pop_back();
  }
  return ret;
}

나의 구현

#include <iostream>
#include <vector>

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)
#define min(first, second) first <= second ? first : second;

using namespace std;

typedef vector<vector<double>> Distance;
typedef vector<bool> Visit;

Visit visited;

// 책과의 차이점
// 방문할 정점과 남은 정점의 수를 인수로 받습니다
// (방문한 정점에서 인접한 정점으로 가는 길이 + 그 정점으로 가는 경로 중에서 가장 짧은 길이)를 더해서 그중 최소값을 구합니다.
double findFastestRouteDistance(Distance & distance, int toTraverse, int remains) {
    if (remains == 0)
        return 0.0;
    visited[toTraverse] = true;
    double minDistance = 1e20;
    FOR(i, 0, distance.size()) {
        if (visited[i]) continue;
        double temp = distance[toTraverse][i] + findFastestRouteDistance(distance, i, remains - 1);
        minDistance = min(minDistance, temp);
    }
    visited[toTraverse] = false;
    return minDistance;
}

void setDistanceForNByKeyboard(Distance & distance, int n) {
    FOR(i, 0, n)
        FOR(j, 0, n)
            cin >> distance[i][j];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int C;
    cin >> C;
    while (C--) {
        int N;
        cin >> N;
        Distance distance = vector<vector<double>>(N, vector<double>(N));
        visited = vector<bool>(N);
        setDistanceForNByKeyboard(distance, N);

        double fastestDistance = 1e20;
        for (int startNode = 0; startNode < N; ++startNode)
            fastestDistance = min(fastestDistance, findFastestRouteDistance(distance, startNode, N - 1));

        cout << fixed;
        cout.precision(10);
        cout << fastestDistance << '\n';
    }
    return 0;
}

문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

문제 보기 스위치를 눌러서 모든 시계를 12시로 맞출 수 있는 최소 회수를 구하자.

문제 변형하기

문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결할 수 있다.

예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다. 두 스위치를 누르는 순서를 바꾼다고 해서 결과가 바뀌지는 않기 때문이다. 따라서 각 스위치를 몇 번 눌렀는지를 계산하면 된다.

완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나 하나 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없고 따라서 그 조합의 수는 무한하다.

시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용하면 유한하게 바꿀 수 있다. 어떤 스위치를 네 번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하니 하나도 누르지 않는 것과 다름없다. 따라서 어떤 스위치건 최대 세 번 이상 누르지 않아도 된다. 따라서 각 스위치를 누르는 횟수는 0에서 3 사이의 정수다.

열 개의 스위치가 있으니 전체 경우의 수는 $4^{10}=1,048,576$이다. 따라서 완전 탐색으로 무난하게 풀 수 있다.

완전 탐색 구현하기

• 만약 답을 구할 수 없을 경우 재귀 함수의 반환 값은 문제의 출력 값인 -1이 아니라 매우 큰 값이 된다. solve()는 재귀 호출하면서 가장 작은 출력 값을 찾게 되는데,
• 1 대신에 매우 큰 값을 반환하면 답이 없는 경우를 따로 확인하지 않아도 된다. 마지막에 답을 출력할 때 답이 매우 크다면 -1을 대신 출력하면 된다.
• 어떤 스위치가 어떤 시계에 연결되어 있는지 2차원 배열에 저장했다. i번째 스위치가 j번째 시계에 연결되어 있는 것은 linked[i][j]로 확인할 수 있다. 문제에 적혀 있는 표현과 다르기 때문에 눈으로 확인하기 까다롭다는 단점이 있다.

책의 구현

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS+1] = {
   //0123456789012345
   "xxx.............", 
   "...x...x.x.x....", 
   "....x.....x...xx", 
   "x...xxxx........", 
   "......xxx.x.x...",
   "x.x...........xx",
   "...x..........xx",
   "....xx.x......xx",
   ".xxxxx..........",
   "...xxx...x...x.."
};

//모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);

//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) 
{
   for(int i = 0; i< CLOCKS; i++)
      if(linked[swtch][i] == 'x')
      {
         clocks[i] += 3;
         if(clocks[i] == 15) clocks[i] = 3;
      }
}

//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch)
{
   //이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
   if(swtch == SWITCHES)
      return areAligned(clocks) ? 0 : INF;

   int ret = INF;

   for(int cnt = 0; cnt < 4; cnt++)
   {
      ret = min(ret, cnt + solve(clocks, swtch+1)); 
      push(clocks, swtch);
   }
   //push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
   return ret;
}

나의 구현

#include <iostream>
#include <vector>

#define CLOCK_AMOUNT        16
#define SWITCH_AMOUNT        10
#define TWELVE_CLOCK        3
#define TIME_TYPE_AMOUNT    4
#define INF                    99999

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)
#define min(first, second) first <= second ? first : second;

using namespace std;

typedef int Time[CLOCK_AMOUNT];
typedef const vector<vector<int>> Switch;

Switch SWITCH_WITH_LINKED_CLOCK = {
    {0, 1, 2},
    {3, 7, 9, 11},
    {4, 10, 14, 15},
    {0, 4, 5, 6, 7},
    {6, 7, 8, 10, 12},
    {0, 2, 14, 15},
    {3, 14, 15},
    {4, 5, 7, 14, 15},
    {1, 2, 3, 4, 5},
    {3, 4, 5, 9, 13}
};

void setTimeByKeyboard(Time& time) {
    FOR(i, 0, CLOCK_AMOUNT) {
        int temp;
        cin >> temp;
        time[i] = temp / 3 - 1;
    }
}

void clickSwitch(Time& clockTime, int switchIndex) {
    FOR(i, 0, SWITCH_WITH_LINKED_CLOCK[switchIndex].size()) {
        int clockIndex = SWITCH_WITH_LINKED_CLOCK[switchIndex][i];
        clockTime[clockIndex] += 1;
        clockTime[clockIndex] %= TIME_TYPE_AMOUNT;
    }
}

bool checkAllTwelveClock(Time& time) {
    FOR(clock, 0, CLOCK_AMOUNT)
        if (time[clock] != TWELVE_CLOCK) {
            return false;
        }
    return true;
}

int getMinCount(Time& clockTime, int switchIndex) {
    if (switchIndex == SWITCH_AMOUNT)
        return checkAllTwelveClock(clockTime) ? 0 : INF;

    int minCount = INF;
    FOR(clickCount, 0, TIME_TYPE_AMOUNT) {
        minCount = min(minCount, clickCount + getMinCount(clockTime, switchIndex + 1));
        clickSwitch(clockTime, switchIndex);
    }
    return minCount;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int C;
    cin >> C;
    while (C--) {
        Time time;
        setTimeByKeyboard(time);
        int minCount = getMinCount(time, 0);
        cout << (minCount == INF ? -1 : minCount) << '\n';
    }
    return 0;
}

구현하면서 실수를 했었다. 마지막에 답을 출력하는 구문의 삼항 연산자를 괄호로 감싸지 않아 계속해서 답이 0으로 출력됐다.

연산자 우선순위를 제대로 숙지하지 못 하면 괄호를 사용하는 편이 좋겠다.

많이 등장하는 완전 탐색 유형

주어진 원소로 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등은 다른 문제의 부분 문제로도 빈번히 출제된다.

그러니 입력의 크기에 따라 답의 개수가 어떻게 변하는지를 알고 구현하는 방법을 연습해 두면 좋다.

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열(permutation)이라고 부른다. 가능한 순열의 수는 $N!$이 되는데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려우므로 완전 탐색 말고 다른 방법을 생각해야 한다. 다른 방법으로는 9.11절(정수 이외의 입력에 대한 메모이제이션)의 기법들이 유용하다.

C++ 사용자는 표준 라이브러리인 STL에 포함된 next_permutation() 함수에서 모든 순열을 순서대로 생성하는 작업을 대신하게 할 수 있다.

모든 조합 만들기

서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다. 이때 경우의 수는 이항 계수 $\begin{pmatrix} N \ R \end{pmatrix}$로 정의된다. $\begin{pmatrix} N \ R \end{pmatrix}=\frac{N!}{(N-R)!}$

$2^n$가지 경우의 수 만들기

n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 $2^n$가지다.

각 조합을 하나의 n비트 정수로 표현한다고 생각하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다. 비트 마스크

의도를 분명히 밝혀라

의도가 분명한 이름은 정말로 중요하다. 변수나 함수 그리고 클래스 이름은 다음과 같은 굵직한 질문에 모두 답해야 한다.

변수(혹은 함수나 클래스)의 존재 이유는? 수행 기능은? 사용 방법은?

따로 주석이 필요하다면 의도를 분명히 드러내지 못했다는 말이다.

public List<int[]> getThem() {
    List<int[]> list1 = new ArrayList<int[]>();

    for (int[] x : theList)
        if (x[0] == 4)
            list1.add(x);
    return list1;
}

코드가 하는 일을 짐작하기 어렵다. 문제는 코드의 함축성이다. 코드 맥락이 코드 자체에 명시적으로 드러나지 않는다.

1. theList에 무엇이 들었는가?
2. theList에서 0번째 값이 어째서 중요한가?
3. 값 4는 무슨 의미인가?
4. 함수가 반환하는 리스트 list1을 어떻게 사용하는가?

public List<int[]> getFlaggedCells() {
    List<int[]> flaggedCells = new ArrayList<int[]>();

    for (int[] cell : gameBoard)
        if (cell[STATUS_VALUE == FLAGGED)
            flaggedCells.add(x);
    return flaggedCells;
}

한 걸음 더 나아가, 칸을 간단한 클래스로 만들어도 되겟다. isFlagged라는 좀 더 명시적인 함수를 사용해 FLAGGED라는 상수를 감춰도 좋겠다.

public List<int[]> getFlaggedCells() {
    List<Cell> flaggedCells = new ArrayList<Cell>();

    for (Cell cell : gameBoard)
        if (cell.isFlagged())
            flaggedCells.add(cell);
    return flaggedCells;
}

이름만 고쳤는데도 함수가 하는 일을 이해하기 쉬워졌다. 이것이 좋은 이름이 주는 위력이다.

그릇된 정보를 피하라

그릇된 단서는 코드 의미를 흐린다. 나름대로 널리 쓰이는 의미가 있는 단어를 다른 의미로 사용해도 안 된다.

예를 들어 hp, aix, sco는 유닉스 플랫폼이나 유닉스 변종을 가리키는 이름이라 변수 이름으로 적합하지 않다.

여러 계정을 그룹으로 묶을 때 실제 List가 아니라면 accountList라 명명하지 않는다. accountGroup, bunchOfAccoounts, Accounts 등이 대안이다.

서로 흡사한 이름을 사용하지 않도록 주의한다. 한 모듈에서 XYZControllerForEfficientHandlingOfStrings 라는 이름을 사용하고, 조금 떨어진 모듈에서 XYZControllerForEfficientStorageOfStrings 라는 이름을 사용한다면 두 단어는 너무 비슷하다.

유사한 개념은 유사한 표기법을 사용한다. 일관성이 떨어지는 표기법은 그릇된 정보다.

의미 있게 구분하라

동일한 범위 안에서는 다른 두 개념에 같은 이름을 사용하지 못한다. 컴파일러를 통과시키기 위해 연속된 숫자를 덧붙이거나 불용어(의미가 불분명한 용어)를 추가하는 방식은 적절하지 못하다. 이름이 달라야 한다면 의미도 달라져야 한다.

public static void copyCharas(char a1[], char a2[]) {
    for (int i = 0; i < a1.length; i++) {
        a2[i] = a1[i];
    }
}

함수 인수 이름으로 source와 destination을 사용한다면 코드 읽기가 훨씬 더 쉬워진다.

Customer라는 클래스와 CustomerObject라는 클래스를 발견했다면 차이를 알기 힘들다.

발음하기 쉬운 이름을 사용하라

발음하기 어려운 이름은 토론하기 어렵다. 예) genymdhms

검색하기 쉬운 이름을 사용하라

간단한 메서드에서 로컬 변수만 한 문자를 사용한다. 이름 길이는 범위 크기에 비례해야 한다. 변수나 상수를 코드 여러 곳에서 사용한다면 검색하기 쉬운 이름이 바람직하다. 긴 이름이 검색하기 쉽다. 검색하기 쉬운 이름이 상수보다 좋다.

인코딩을 피하라

유형이나 범위 정보까지 인코딩에 넣으면 그만큼 이름을 해독하기 어려워진다. 대개 새로운 개발자가 익힐 코드 양은 상당히 많다. 인코딩 언어까지 익히라는 요구는 비합리적이다.

헝가리식 표기법

요즘은 컴파일러가 타입을 기억하고 강제한다. 변수를 선언한 위치와 사용하는 위치가 멀지 않다. 자바 프로그래머는 변수 이름에 타입을 인코딩할 필요가 없다. 변수, 함수, 클래스 이름이나 타입을 바꾸기가 어려워지며 읽기도 어려워진다.

멤버 변수 접두어

멤버 변수에 m_ 이라는 접두어를 붙일 필요가 없다. 클래스와 함수는 접두어가 필요없을 정도로 작아야 마땅하다.

인터페이스 클래스와 구현 클래스

인터페이스 이름은 접두어를 붙이지 않는 편이 좋다. IShapeFactory 의 접두어 I는 주의를 흐트리고 과도한 정보를 제공한다. 클래스 사용자가 인터페이스라는 사실을 모르도록 ShapeFactory 로 하고, 구현 클래스 이름을 ShapeFactoryImp, CShapeFactory 등으로 한다.

자신의 기억력을 자랑하지 마라

독자가 코드를 읽으면서 변수 이름을 자신이 아는 이름으로 변환해야 한다면 그 변수 이름은 바람직하지 못하다. 일반적으로 문제 영역이나 해법 영역에서 사용하지 않는 이름을 선택했기 때문에 생기는 문제다.

명료함이 최고다. 남들이 이해하는 코드를 내놓자.

클래스 이름

클래스 이름과 객체 이름은 명사나 명사구가 적합하다. Customer, WikiPage, Account, AddressParser 등이 좋은 예다. Manager, Processor, Data, Info 등과 같은 단어는 피하고, 동사는 사용하지 않는다. 앞에서 불용어를 사용하지 말라고 해서 그런 것 같다.

메서드 이름

메서드 일므은 동사나 동사구가 적합하다. postPayment, deletePage, save 등이 좋은 예다. 접근자(Accessor), 변경자(Mutator), 조건자(Predicate)는 javabean 표준에 따라 값 앞에 get, set, is를 붙인다.

string name = blogger.getName();
blogger.setName("Jun");
if (paycheck.isPosted())
    …

생성자를 중복정의(overload)할 때는 정적 팩토리 메서드를 사용한다. 메서드는 인수를 설명하는 이름을 사용한다.

정적 팩토리 메서드: 객체를 생성하는 메서드를 static 으로 선언하는 기법

정적 팩토리 메서드

Complex fulcrumPoint = Complex.FromRealNumber(23.0);

일반적인 메서드 선언

Complex fulcrumPoint = new Complex(23.0);

생성자 사용을 제한하려면 해당 생성자를 private로 선언한다.

기발한 이름은 피하라

이름이 너무 기발하면 저자와 유머 감각이 비슷한 사람만, 그리고 농담을 기억하는 동안만 이름을 기억한다. 특정 문화에서만 사용하는 농담은 피하는 편이 좋다. 의도를 분명하고 솔직하게 표현하라.

한 개념에 한 단어를 사용하라

추상적인 개념 하나에 단어 하나를 선택해 이를 고수한다. 예를 들어 똑같은 메서드를 클래스마다 fetch, retrieve, get 으로 제각각 부르면 혼란스럽다. 메서드 이름은 독자적이고 일관적이어야 한다. 마찬가지로 동일 코드 기반에 controller, manager, driver를 섞어 써도 혼란스럽다. 일관성 있는 어휘는 코드를 사용할 프로그래머가 반갑게 여길 선물이다.

말장난을 하지 마라

한 단어를 두 가지 목적으로 사용하지 마라. 여러 클래스에 add라는 메서드가 생겼을 때 모든 add 메서드의 매개변수와 반환값이 의미적으로 똑같다면 문제가 없다. 하지만 지금까지 구현한 add 메서드는 모두가 기존 값 두 개를 더하거나 이어서 새로운 값을 만들었는데, 새로 작성하는 메서드는 집합에 값 하나를 추가한다면 기존 add 메서드와 맥락이 다르므로 insert나 append라는 이름이 적당하다. 프로그래머는 코드를 최대한 이해하기 쉽게 짜야 한다. 대충 훑어봐도 이해할 코드 작성이 목표다.

해법 영역에서 가져온 이름을 사용하라

독자가 프로그래머이므로 기술 용어를 사용해도 된다. 전산 용어, 알고리즘 이름, 패턴 이름, 수학 용어 등을 사용해도 괜찮다.

문제 영역에서 가져온 이름을 사용하라

적절한 프로그래머 용어가 없다면 문제 영역에서 이름을 가져온다. 해법 영역과 문제 영역(domain)을 구분할 줄 알아야 한다. 문제 영역 개념과 관련이 깊은 코드라면 문제 영역에서 이름을 가져와야 한다.

의미 있는 맥락을 추가하라

스스로 의미가 분명한 이름이 있다. 하지만 대다수 이름은 그렇지 못하다. 그래서 클래스, 함수, namespace에 넣어 맥락을 부여한다. 모든 방법이 실패하면 마지막 수단으로 접두어를 붙인다.

state 라는 변수 하나만 있으면 주소를 나타내는건지 모른다. 이럴 때는 addrState라 쓰면 맥락이 좀 더 분명해진다. 물론 Address라는 클래스를 생성하면 더 좋다.

private void printGuessStatistics(char candidate, int count) {
    String number;
    String verb;
    String pluralModifier;
    if (count == 0) {
        number = "no";
        verb = "are";
        pluralModifier = "s";
    } else if (count == 1) {
        number = "1";
        verb = "is";
        pluralModifier = "";
    } else {
        number = Integer.toString(count);
        verb = "are";
        pluralModifier = "s";
    }
    String guessMessage = String.format(
        "There %s %s %s%s", verb, number, candidate, pluralModifier
    );
    print(guessMessage);
}

• 함수가 좀 길다.
• 세 변수를 함수 전반에서 사용한다.

함수를 작은 조각으로 쪼개고자 클래스를 만든 후 세 변수를 클래스에 넣자. 그러면 세 변수는 맥락이 분명해진다.

public class GuessStatisticsMessage {
    private String number;
    private String verb;
    private String pluralModifier;

    public String make(char candidate, int count) {
        createPluralDependentMessageParts(count);
        return String.format(
            "There %s %s %s%s",
            verb, number, candidate, pluralModifier );
    }

    private void createPluralDependentMessageParts(int count) {
        if (count == 0) {
        thereAreNoLetters();
        } else if (count == 1) {
        thereIsOneLetter();
        } else {
        thereAreManyLetters(count);
        }
    }

    private void thereAreManyLetters(int count) {
        number = Integer.toString(count);
        verb = "are";
        pluralModifier = "s";
       }

    private void thereIsOneLetter() {
        number = "1";
        verb = "is";
        pluralModifier = "";
    }

    private void thereAreNoLetters() {
          number = "no";
        verb = "are";
        pluralModifier = "s";
    }
}

불필요한 맥락을 없애라

일반적으로는 짧은 이름이 긴 이름보다 좋다. 단, 의미가 분명한 경우에 한해서다. 이름에 불필요한 맥락을 추가하지 않도록 주의한다.

accountAddress와 customerAddress는 Address 클래스 인스턴스로는 좋은 이름이나 클래스 이름으로는 적합하지 못한다.

마치면서

좋은 이름을 선택하려면 설명 능력이 뛰어나야 하고 문화적인 배경이 같아야 한다. 우리들 대다수는 자신이 짠 클래스 이름과 메서드 이름을 모두 암기하지 못한다. 우리는 문장이나 문단처럼 읽히는 코드 아니면 (정보를 표시하는 최선의 방법이 항상 문장만은 아니므로) 적어도 표나 자료 구조처럼 읽히는 코드를 짜는 데만 집중해야 마땅하다.

다른 사람이 짠 코드를 손본다면 리팩터링 도구를 사용해 문제 해결 목적으로 이름을 개선하라. 이 장에서 소개한 규칙을 적용해 코드 가독성이 높아지는지 살펴보라.

코드를 개선하려는 노력을 중단해서는 안 된다.

모르는 용어 정리

인수 테스트 케이스(Acceptance Testing): 정보 시스템의 검사 중 하나로서, 해당 시스템이 실제 운영 환경에서 사용될 준비가 되었는지 최종적으로 확인하는 테스팅 단계이다.

메서드 추출 리팩터링(Extract Method): 한 메서드안에 이런저런 세세한 처리가 많다면 그런 처리를 묶어서 나누고 독립된 메서드로 추출하고 추출한 메서드에는 적절한 이름을 붙임.

grep: 유닉스를 위해 만들어진 텍스트 검색 기능을 가진 명령어다. global / regular expression / print 의 앞 글자를 따왔다.

get, fetch, retrieve 의 차이: 미묘한 차이가 있다. 저자가 말하는 대로 한 개념에 한 단어를 사용하자.

작업 큐(JobQueue): 시스템 소프트웨어에서 작업 큐는 실행할 작업을 포함하는 작업 스케줄러 소프트웨어가 유지 보수하는 데이터 구조입니다. (큐에 작업들을 담아뒀다가 빈 스레드에 스케줄링해서 처리하는 방식)

VISITOR 패턴: 방문자와 방문 공간을 분리하여, 방문 공간이 방문자를 맞이할 때, 이후에 대한 행동을 방문자에게 위임하는 패턴이다. 즉, 방문한 '나'가 주체가 되지 않고 방문 공간이 주체가 되는 패턴.

코드를 하나하나 짚어가며 저자가 코드를 고쳐간 방식을 이해하고 납득해야 가치를 발휘하는 책이다.

5S 철학

1. 정리seiri : 적절한 명명법
2. 정돈seiton : 코드는 누구나 예상하는 위치에 있어야 한다.
3. 청소seiso : 필요없는 주석을 제거하라.
4. 청결seiketsu : 일관적인 구현 스타일과 기법의 필요성, 표준
5. 생활화shutsuke : 관례를 따르고, 자기 작품을 자주 돌아보고, 기꺼이 변경하는 규율

책의 구성

1. 깨끗한 코드를 작성하는 원칙, 패턴, 실기
2. 사례 연구. 코드를 깨끗하게 고치는, 즉 문제가 있는 코드를 문제가 더 적은 코드로 바꾸는 연습
3. 사례 연구를 만들며 수집한 냄새와 휴리스틱

휴리스틱: 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법

휴리스틱 함수: 가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수

깨끗한 코드

요구사항을 명시하는 작업이 프로그래밍, 이렇게 명시한 결과가 바로 코드.

시간 압박은 나쁜 코드를 생산하게 하고 나쁜 코드는 개발 속도를 크게 떨어트린다.

나쁜 코드를 양산하면 기한을 맞추지 못한다. 기한을 맞추는 유일한 방법은 언제나 코드를 깨끗하게 유지하는 습관이다.

깨끗한 코드를 작성하려면 '청결'이라는 힙겹게 습득한 감각을 활용해 자잘한 기법들을 적용하는 절제와 규율이 필요하다. 열쇠는 '코드 감각'이다. '코드 감각'이 있는 프로그래머는 나쁜 모듈을 보면 좋은 모듈로 개선한 방안을 떠올린다.

나쁜 코드를 고치면서 오히려 더 나쁜 코드를 만든다. 깨진 창문이 더 깨져도 사람들은 상관하지 않는다.

깨끗한 코드는 세세한 사항(메모리 누수, 경쟁 상태, 일관성 없는 명명법 같은 오류 처리)까지 꼼꼼하게 처리하는 코드다.

깨끗한 코드는 한 가지에 '집중'한다. 각 함수와 클래스와 모듈을 주변 상황에 현혹되거나 오염되지 않은 채 한길만 걷는다.

깨끗한 코드는 결코 설계자의 의도를 숨기지 않는다. 오히려 명쾌한 추상화와 단순한 제어문으로 가득하다. 반드시 필요한 내용만 담자.

깨끗한 코드는 작성자가 아닌 사람도 읽기 쉽고 고치기 쉽다. 테스트 케이스가 존재한다. 의미 잇는 이름이 붙는다. 특정 목적을 달성하는 방법은 하나만 제공한다. 의존성은 최소이며 각 의존성을 명확히 정의한다. API는 명확하며 최소로 줄였다.

깨끗한 코드는 세세한 사항까지 꼼꼼하게 신경쓴 코드다.

단순한 코드

• 모든 테스트를 통과한다.
• 중복이 없다.
• 시스템 내 모든 설계 아이디어를 표현한다.
• 클래스, 메서드, 함수 등을 최대한 줄인다.

깨끗한 코드를 만드는 비결

1. 중복 줄이기: 객체가 여러 기능을 수행한다면 여러 객체로 나눈다. 메서드 추출 리팩터링 기법을 적용해 기능을 명확히 기술하는 메서드 하나와 기능을 실제로 수행하는 메서드 여러 개로 나눈다.
2. 표현력 높이기: 의미 있는 이름을 사용한다.
3. 초반부터 간단한 추상화 고려하기: 어떤 집합에서 특정 항목을 찾아낼 필요가 생길 때 추상 메서드나 추상 클래스를 만들어 실제 구현을 감싼다. 이렇게 하면 실제 구현은 언제든지 바꿔도 괜찮다.

읽으면서 짐작한 대로 돌아가는 코드가 깨끗한 코드다.

코드가 그 문제를 풀기 위한 언어처럼 보인다면 아름다운 코드다.

우리는 저자다. 저자에게는 독자와 잘 소통할 책임도 있다. 코드를 짤 때는 자신이 저자라는 사실을, 저자의 노력을 보고 판단을 내릴 독자가 있다는 사실을 기억하자.

보이스카우트 규칙: 체크아웃할 때보다 좀 더 깨끗한 코드를 체크인한다면 코드는 절대 나빠지지 않는다.

알고리즘의 시간 복잡도 분석

알고리즘: 주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것

알고리즘 평가 기준

• 시간: 더 빠르게 동작해야 한다. 이를 위해서는 알고리즘의 수행 속도와 특성을 분석하는 능력이 필요하다.
• 공간: 더 적은 용량의 메모리를 사용해야 한다.

수행 속도가 중요하다. 더 많은 메모리를 사용해 수행 속도를 높이는 알고리즘(동적 계획법 등)이 있고 수행 속도를 희생해서 메모리 사용량을 줄인 알고리즘이 있다.

도입

프로그램의 실행 시간은 직관적이지만 알고리즘의 속도를 이야기하는 기준이 되기에는 부적합하다.

• 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 뿐만 아니라 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 최종 수행 시간이 크게 달라질 수 있다.
• 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못한다.

반복문(수행 횟수)이 알고리즘의 수행 시간을 지배한다.

선형 시간 알고리즘

수행 시간이 N에 정비례할 때 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 된다. 이런 알고리즘을 선형 시간(linear time) 알고리즘이라 부른다.

선형 이하 시간 알고리즘

이진 탐색 알고리즘으로 N개의 자료 중 하나를 찾는다고 하면 최대 $log_2N$ 번 만에 찾을 수 있다. 이와 같이 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time) 알고리즘이라 부른다.

이진 탐색

binarySearch(A[], x) : 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때 A[i-1]<x≤A[i]인 i를 반환한다. 이때 A[-1] = -∞, A[N] = ∞ 로 가정한다.

C++ STL 에는 x를 삽입할 수 있는 위치 중 가장 이른 것을 반환하는 lower_bound, upper_bound 가 있다.

지수 시간 알고리즘

다항 시간 알고리즘

반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘 $N$, $N^2$ , $N^{100}$ 모두 다항 시간 알고리즘

지수 시간 알고리즘

N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작한다고 말한다. 지수 시간은 가장 큰 수행 시간 중 하나다.

다항 시간 알고리즘이 있는 문제는 계산적으로 쉬운 문제, 아직 없는 문제를 계산적으로 어려운 문제라고 이야기한다.

지수 시간이 걸리는 문제들을 효율적으로 해결할 수 있는 방법으로 조합 탐색이 있다.

소인수 분해의 수행 시간

입력으로 주어지는 숫자의 개수가 아니라 그 크기에 따라 수행 시간이 달라지는 알고리즘도 지수 수행 시간을 가질 수 있다. 자연수 N이 주어질 때 N의 소인수 분해 결과를 구할 때 최악의 경우인 반복문이 가장 많이 실행되는 경우는 주어진 수 N이 소수인 경우다. 입력의 값이 커질수록 숫자를 저장하는데 필요한 메모리의 공간이 증가한다.

이때 입력이 차지하는 비트의 수에 따라 수행 시간이 증가한다고 생각하면 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간이 두 배로 증가하므로 입력의 크기를 입력이 차지하는 비트 수로 정의했을 때 입력의 크기에 대해 지수 시간이 걸린다고 말할 수 있다.

시간 복잡도

가장 널리 사용되는 알고리즘의 수행 시간 기준 알고리즘이 실행되는 동안 수행하는 깆본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것

시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다.

입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다. 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다. (탐색 문제에서 입력받은 배열에 찾는 원소의 위치에 따라 반복문이 실행되는 횟수가 달라짐)

최선의 수행 시간, 최악의 수행 시간, 평균적인 경우의 수행 시간 최악의 수행 시간이나 수행 시간의 기대치를 대개 사용한다.

점근적 시간 표기: O 표기

전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

O 표기법의 의미

함수의 상한을 나타낸다. N에 대한 함수 $f(N)$이 주어질 때, $f(N)=O(g(N))$이라고 쓰는 것은 다음과 같은 의미다.

아주 큰 $N_0$와 $C(N_{0}, C>0)$를 적절히 선택하면 $N_{0}≤N$인 모든 $N$에 대해 $|f(N)|≤C×|g(N)|$이 참이 되도록 할 수 있다.

O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있지는 않다.

시간 복잡도의 분할 상환 분석

$N$개의 작은 작업들을 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다.

동적 배열을 다루는 18.2절, 10장의 연습 문제인 미나스 아노르에서 다룬다.

수행 시간 어림짐작하기

주먹구구 법칙

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다.

고려해야 하는 요소

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: 어디까지나 예측 값
• 반복문의 내부가 복잡한 경우
• 메모리 사용 패턴이 복잡한 경우
• 언어와 컴파일러의 차이
• 구형 컴퓨터를 사용하는 경우

계산 복잡도 클래스: P, NP, NP-완비

계산 복잡도 이론: 각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문

P 문제: 다항 시간 알고리즘이 존재하는 문제들의 집합 NP 문제: 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제

계산 복잡도 클래스: P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합

어려운 문제의 기준

• 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼는다.
• 그리고 앞으로는 기준 문제만큼 어렵거나 그보다 어려운 문제들, 다시 말해 '기준 이상으로 어려운 문제들'만을 어렵다고 부른다.

난이도의 비교

환산: 한 문제를 다른 문제로 바꿔서 푸는 기법

A를 푸는 가장 빠른 알고리즘을 환산 알고리즘과 결합해 B를 푸는 알고리즘을 만들었다. 환산 알고리즘이 무시할 수 있는 정도로 빠르다고 가정하면 결합된 알고리즘은 B를 푸는 가장 빠른 알고리즘이 같거나 더 빠를 테니, 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수밖에 없다. A가 B 이상으로 어렵다는 의미

NP 문제, NP 난해 문제

어려운 문제의 기준은 SAT 문제 SAT 문제는 모든 NP 문제 이상으로 어렵다. SAT 문제란 N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제

((a||b||!c)&&(!c||!a)&&((!a&&b)||(b&&!c)))&&(!b||(!a&&!c))

SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다. 이런 속성을 갖는 문제들의 집합을 NP-난해 문제라고 부른다.

NP-난해 문제이면서 NP인 문제들을 NP-완비 문제라 한다.

P=NP?

1. NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있다.
2. NP 문제 중 하나를 골라 P에 포함되어 있지 않음을, 다시 말해 다항 시간에 푸는 방법이 없음을 증명하면 P≠NP 임을 보일 수 있다.

더 읽을거리

재귀적인 알고리즘의 시간 복잡도를 계산하는 쉬운 방법으로 마스터 정리(Master Theorem)가 있다. O 표기법을 쉽게 계산할 수 있도록 도와준다.

알고리즘의 정당성 증명

단위 테스트는 알고리즘에 문제가 있음을 증명할 수는 있어도 문제가 없음을 증명할 수는 없다. 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다.

수학적 귀납법과 반복문 불변식

수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법이다. 크게 세 단계로 나뉜다.

1. 단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다.
2. 첫 단계 증명: 그중 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.
3. 귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

반복문 불변식은 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 반복문이 마지막에 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 한다. 불변식을 이용하여 다음과 같이 반복문의 정당성을 증명한다.

1. 반복문 진입시에 불변식이 성립함을 보인다.
2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
3. 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

단정문을 이용해 반복문 불변식 강제하기

불변식을 단정문으로 강제해 버리면 해당 불변식이 깨졌을 때 프로그램이 강제 종료되기 때문에 불변식의 유지에 문제가 있다는 사실을 아주 쉽게 알 수 있다.

귀류법

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법을 귀류법이라 한다.

귀류법을 이용한 증명들

알고리즘의 결과가 최선(최단 경로 탐색, 가장 높은 탑 쌓기)임을 보이기 위해 각 단계에서 최선을 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선을 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명한다

다른 기술들

비둘기집의 원리

10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.

동전 뒤집기

100개의 동전이 바닥에 깔려 잇는데 이 중 F개는 앞면, 100-F개는 뒷면이 위로 놓여 있다. 우리는 이 동전들이 모두 앞면을 위로 하게 뒤집고 싶은데, 한 번 뒤집을 때 반드시 X개의 동전을 한꺼번에 뒤집어야 한다. 같은 동전을 두 번 이상 뒤집는 것도 상관없다. 이때 뒤집는 횟수를 최소화하고 싶다면 답의 상한을 얼마일까?

정답은 100. (이해 못함)

순환 소수 찾기

분수 $\frac{a}{b}$가 주어질 때 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력하려 한다.

// a >= 0, b > 0 이라 가정
void printDecimal(int a, int b) {
    int iter = 0;
    while(a > 0) {
        // 첫 번째와 두 번째 사이에 소수점을 찍는다.
        if(iter++ == 1) cout << '.';
        cout << a / b;
        a = (a % b) * 10;
    }
}

무한 소수를 인식해서 별도로 처리해줘야 한다.

a=(a%b)*10을 취하는 부분을 보자. a%b의 결과는 언제나 [0, b-1] 범위의 값을 가진다.

while문이 b+1번 반복될 때까지 함수가 종료되지 않았다고 하자. a%b의 결과는 b가지의 결과만 가질 수 있으니 결과가 중복될 것이다.

그러면 같은 결과가 첫 번째로 등장했을 때부터 두 번재 등장할 때까지가 무한히 순환되는 순환 소수임을 알 수 있다.

구성적 증명

구성적 증명은 흔히 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해서 사용된다. 답이 존재한다는 사실을 논증하는 것이 우리가 지금까지 다룬 방식이라면, 구성적 증명은 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이다.

하늘을 나는 교통 수단을 만들 수 있다는 주장을 증명하려 한다면 구성적 증명이 하는 일은 비행기를 만들어서 보여 주거나, 비행기 만드는 법이 적힌 설명서를 건네 주는 것이다.

안정적 결혼 문제

n명의 남성과 여성이 단체 미팅에서 만났다. 모든 사람은 자신이 원하는 상대방의 우선순위를 맘 속에 정했고, 각각 짝이 되었다. 다른 짝이 서로를 더 선호한다는 사실을 알게 되었는데, 이런 일이 일어나지 않도록 짝을 지어줄 수 있는 방법이 항상 있을까?

1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 한다. 남성이 그중 제일 마음에 드는 여성을 고르면 나머지는 제자리로 돌아간다.
2. 남은 여성들은 다음으로 짝의 여부에 상관없이 마음에 드는 남성에게 다가가 프로포즈한다. 남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가왔다면, 지금의 파트너를 놓아주고 새 여성에게 넘어간다.
3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복한다.

종료 증명

각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈한다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 종료한다.

모든 사람들이 짝을 찾는지 증명

프로포즈를 받은 남성은 그중 한 사람을 반드시 선택하므로 항상 짝이 있다. 귀류법을 적용하여 남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정하자. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에, 이 남성에게도 한 번은 프로포즈 했을 것이다. 이 남성은 프로포즈를 받아들였어야 하므로, 따라서 짝을 찾지 못하는 사람은 있을 수 없다.

짝들의 안정성

역시 귀류법으로 증명한다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정하자. 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 한다. 그런데도 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이다. 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없다. 따라서 우리가 가정했던 상황은 존재할 수 없다.

더 읽을거리

『생각하는 프로그래밍』(인사이트): 쉽게 읽을 수 있으면서 훌륭한 통찰을 여럿 담고있다. 반복문 불변식을 도입하여 이진 탐색 코드의 정당성을 한 줄 한 줄 엄밀하게 증명하는데, 프로그램 정당성 증명에 관한 가장 모범적인 예로 추천한다.

문제 해결 능력을 기르기 위한 방법 중 효과적인 것이 프로그래밍 대회 참가 프로그래밍 대회들은 주로 짧은 요구사항을 제시하고, 이에 맞는 프로그램을 시간 안에 빠르게 작성하는 능력을 겨루는 대회 문제 형식은 '어떤 값을 읽어들여 어떤 값을 계산하는 프로그램을 작성하시오'

배울 수 있는 것

1. 텍스트 출력만 있기 때문에 문제 해결에만 집중 가능
2. 명시적인 시간 제한과 메모리 제한. 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되기 때문에 이런 주제들을 깊이 이해하는 데 큰 도움이 됨
3. 정답과 오답의 여부가 훨씬 명확하여 예외 없고 정확한 프로그램을 짜는 아주 좋은 훈련이 됨
4. 논리적 구조가 복잡한 프로그램의 수행 성능을 예측하는 데 익숙해짐
5. 작은 규모의 코드를 작성하는 경우가 많아 간결하면서 우아한 프로그램을 짜는 데 시간 투자 가능
6. 경쟁이 좋은 동기가 되고 고수 프로그래머들의 코드들과 비교할 수 있음

책의 포인트

1. 책의 문제는 직접 풀어볼 것
2. 알고리즘을 어떻게 구현했는지 비교
3. 더 좋은 알고리즘을 찾아내려 노력

대회 종류

1. 한국 정보 올림피아드: 초, 중 고등학생 대상, 4시간 동안 3개의 문제
2. ACM-ICPC (ACM 대학생 프로그래밍 경시대회): 3인1팀, 한 대의 컴퓨터, 5시간 8~10문제
3. TopCoder: 1시간 15분 3문제. 한 달에 대략 3번. 1년에 한 번 탑코더 오픈 토너먼트 개최
4. 구글 코드 잼: 모든 언어 가능
5. 기타 온라인 대회, 모의고사(탑코더, 코드포스, 바야돌리드 대학교 온라인 채점 사이트)

대회 준비 조언

1. 가능한 한 많은 문제 풀기(개념 이해 후 문제를 풀어 경험 쌓을 것)
2. 온라인 채점 사이트 이용

온라인 채점 사이트

1. 알고스팟(초·중급자용, algospot.com)
2. 백준(초·중급자용,acmicpc.net)
3. USACO Training Program(초·중급자용,train.usaco.org/usacogate)
4. TopCoder(중급자용, topcoder.com/tc)
5. ACM-ICPC Live Archive(중급자용, livearchive.onlinejudge.org)
6. Project Euler(중급자용, projecteuler.net)
7. SPOJ Online Judge(상급자용, spoj.pl)

팀 단위 연습 조언

1. 종이 위에 답안 스케치(자료구조, 함수 역할, 의사 코드)
2. 치밀한 역할 분담(코딩 2명, 문제풀이 1명)
3. 페어 프로그래밍 연습(작성하면서 생각을 입으로 설명하는 연습, 배열 크기 등 실수하기 쉬운 지점 검토)
4. 디버거 없이 디버깅
5. 인쇄 대기 감소를 위한 화면 분할

팀 노트북 준비

ACM-ICPC 에서는 참고 자료로써 20여 장 출력물 지참 가능

1. 미리 준비(문제 풀 때 유용한 것 정리)
2. 간단한 형태의 문서화(역할, 실행 전·후 조건)
3. 클래스 형태 준비
4. 적절한 글꼴

읽을거리

• 『Introduction to Algorithms』(한빛미디어)
• 『Programming Challenges』(한빛미디어)
• 『The Art of Computer Programming』(한빛미디어)

문제 해결 과정

문제를 읽고 이해하기

사소한 제약 조건을 잘못 이해해서 풀 수 없게 되는 문제들이 흔하므로 문제가 원하는 바를 완전히 이해하자.

재정의와 추상화

문제를 자신의 언어로 풀어 쓰자. 복잡한 현실 세계의 개념을 본질만 남겨두고 축약하여 다루기 쉽게 표현하자.

계획 세우기

어떤 방식으로 해결할지, 사용할 알고리즘과 자료구조를 선택하자.

계획 검증하기

설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간, 사용하는 메모리가 문제의 제한 내에 들어가는지 확인하자.

계획 수행하기

설계한 알고리즘을 정확하고 효율적으로 구현하자.

회고하기

문제를 해결한 과정을 돌이켜 보고 개선하자. 더 효율적인 알고리즘을 찾거나 간결한 코드를 작성하고, 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾자.

• 코드와 함께 자신의 경험(간단한 해법, 접근 방식, 결정적인 깨달음)을 기록으로 남기자
• 한번에 맞추지 못한 경우 오답 원인을 적자
• 다른 사람의 코드를 보며 생각하지 못했던 통찰을 얻자

문제를 풀지 못할 때는 일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조한다는 원칙을 세우고 이를 지키자. 단 참조를 했을 경우 반드시 복기를 동반하자.

문제 해결 전략

직관과 체계적인 접근

해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 하자.

체계적인 접근을 위한 질문들

비슷한 문제를 풀어본 적이 있던가?

알고리즘 유형을 분류하는 방법을 익히고 그 동작 과정과 원리를 완전히 이해하자. 어느 경우에 사용될 수 있는지 체계적으로 공부해야 한다.

단순한 방법에서 시작할 수 있을까?

시간, 공간 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보자. 좀더 효율적인 자료 구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선할 수 있다. 점진적인 개선을 통해 문제를 풀 수 없더라도 단순한 방법은 알고리즘 효율성의 기준선을 정해준다.

내가 문제를 푸는 과정을 수식화할 수 있을까?

손으로 여러 간단한 입력을 직접 해결해보자. 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지 알게 된다. 어떻게 문제를 풀어야 할지 감을 잡기에도 유용하다.

문제를 단순화할 수 없을까?

주어진 문제의 좀더 쉬운 변형판을 먼저 풀어보자. 문제의 제약 조건 제거, 계산해야 하는 변수의 수 감소, 다차원의 문제를 1차원으로 감소하는 방식이 있다.

그림으로 그려볼 수 있을까?

두 개의 정수 쌍들을 다루는 문제가 있다면, 이 정수 쌍을 2차원 평면 상의 좌표로 그려 볼 수 있고, 직선 상의 구간들로 그려 볼 수 있다.

수식으로 표현할 수 있을까?

평문으로 쓰여 있는 문제를 수식으로 표현하자. 수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는 데 도움을 줄 수 있다.

문제를 분해할 수 있을까?

복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하자.

뒤에서부터 생각해서 문제를 풀 수 있을까?

문제에 내재된 순서를 바꿔보자. A에서 B로 가는 것보다 B에서 A로 가는 것이 빠를 수 있다. (사다리 게임)

순서를 강제할 수 있을까?

순서가 없는 문제에 순서를 강제해서 문제를 풀어보자. 경우의 수를 셀 때 유용하다. 특정 조건을 만족하는 답들의 수를 세는 문제에서 한 가지 답을 두 가지 이상의 방법으로 만들 수 있을 때 답이 중복해서 세어지는데 할 수 있는 일들의 순서를 강제하는 것이 좋은 해법이 된다. (오름차순으로만 본다던지?)

특정 형태의 답만을 고려할 수 잇을까?

정규화(canonicalization)란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다. 정규화 기법을 사용하기 위해서는 어떤 답이 주어지더라도 이것을 특정 형태의 답으로 바꿀 수 잇는 변형 과정을 찾아야 한다.

더 읽을거리

• 『어떻게 문제를 풀 것인가(How to Solve It)』(교우사)

코딩의 중요성

간결하고 일관되게 코드를 작성하여 읽기 쉽고 디버깅이 쉽게 하자.

좋은 코드를 짜기 위한 원칙

간결한 코드를 작성하기

• 코드가 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅이 쉬워진다
• 작성하는 프로그램이 짧다면 융통성 있게 가려 사용하면 유용하다(전역 변수의 광범위한 사용)
• 반복문처럼 자주 타이핑하게 되는 코드의 일부를 매크로로 표현하자

  #define FOR(i,n) for(int i=0; i<(n); ++i)
  FOR(i, array.size())
  FOR(j, i)
  // 이런 식으로 하면 증감문 오타같은 경우를 대비할 수 있음

  실수를 피해 가는 올바른 방법은 foreach 구문 이용! C++11 부터 구간 기반 for문 지원

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

코드를 모듈화하자. 같은 코드가 세 번 이상 등장한다면 함수로 분리해 재사용한다는 기본 원칙을 만들면 좋다. 한 함수가 두 가지 이상의 일을 해서는 안 된다는 것이 이상적인 코드

표준 라이브러리 공부하기

모든 코드를 직접 작성하는 것은 시간 낭비. 팀원의 이해를 돕기 위해서라도 표준 라이브러리의 사용은 필수. 문자열, 동적 배열, 스택, 큐, 리스트, 딕셔너리 등의 자료 구조, 정렬 등의 표준적인 알고리즘 구현 사용법을 알아두자.

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

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

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

사용하는 언어의 표준 라이브러리에서 사용하는 명명 규악(naming convention)을 익히자. 모호하지 않은 변수명과 함수명을 사용하자.

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

같은 자료를 두 가지 형태로 저장하지 않는 것이 좋다. 유리수를 예로 들면 항상 약분해서 기약 분수로 표현하는 것이 좋다.

자료를 표현하는 클래스의 생성장에서 정규화를 수행하거나, 외부에서 자료를 입력받자마자 정규화를 수행하는 것이 이상적이다.

코드와 데이터를 분리하기

날짜를 영문 이름으로 출력할 때

if(month == 1) return "January";
...

이와 같은 형식으로 작성하면 안 좋다. 코드의 논리와 상관 없는 데이터는 가능한 한 분리하는 것이 좋다. 영문 이름을 별도의 배열에 저장하는 방식이 있다.

자주하는 실수

산술 오버플로

변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로.

배열 범위 밖 원소에 접근

배열 크기를 정할 때 계산을 신중히 하자. 인덱스를 0에서 시작하는지 1에서 시작하는지 주의하자.

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

자연수 범위 [2, 3, 4, …, 12] 를 표현하고 싶을 때 닫힌 구간: [2, 12] 열린 구간: (1, 13) 반 열린 구간: [2, 13)

C++ STL에서는 반복자(Iterator)로 범위를 표현할 때 첫 원소를 가리키는 반복자와 마지막 원소 다음 위치를 가리키는 반복자를 사용한다. begin() 과 end()

장점

• 첫 번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간 쉽게 표현 가능
• 두 구간이 연속해 있는지 쉽게 알 수 있음. 두 구간 [a, b)와 [c, d) 가 b = c 혹은 a = d 라면 연속함
• 구간 크기를 쉽게 알 수 있음. [a, b) 는 b-a 로 알 수 있음

한 가지 방법으로만 범위를 표현해야 혼란을 초래하지 않음

Off-by-one 오류

반복문에서 < 혹은 > 연산자와 ≤ 와 ≥ 연산자를 혼용할 경우 흔하게 발생한다. 최소 입력이 주여졌을 때 이 코드가 어떻게 동작할지를 되새겨 보면서 프로그램을 짜면 좋다.

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

• 모두 대문자로 출력해야 되는데 첫 문자만 대문자로 출력한 경우
• 100000007 로 나눈 나머지를 구해야 하는데 0을 하나 빼트리는 경우
• 64비트 정수형에 상수를 담으면서 64비트라고 지정하지 않는 경우(C++의 경우 정수형 상수 뒤에 LL을 붙이지 않으면 32비트로 가정)

스택 오버플로

콜 스택이 오버플로해서 프로그램이 강제종료 될 수 있다. 재귀 호출이 깊이가 너무 깊어지면 오는데, 스택 허용량에 대해 알아둘 필요가 있다. 스택 메모리를 절약하기 위해 자동으로 힙에 메모리를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 사용하곤 한다.

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

동적 계획법을 위한 메모이제이션 패턴을 사용할 때 잦다. 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다. C++의 참조 변수를 사용해 해결하자.

잘못된 비교 함수 작성

정렬할 때 비교 함수를 잘못 작성해서 원하는 순서를 얻지 못할 수 있다.

< 연산자의 성질

• 비반사성: a<a는 항상 거짓
• 비대칭성: a<b가 참이면 b<a는 거짓
• 전이성: a<b가 참이고 b<c가 참이면 a<c
• 상등 관계의 전이성: a<b와 b<a가 모두 거짓이면 a=b. a=b 이고 b=c 라면 a=c

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

가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해 보자.

연산자 우선순위 잘못 쓰기

if(b & 1 == 0)
// 위 코드는 다음과 같은 의미
if(b & (1 == 0))

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

너무 느린 입출력 방식 선택

gets() 를 이용해 모든 입력을 문자열 하나로 읽어들여 파싱할 수 있고, cin 등의 고수준 입력 방식을 사용할 수 있지만 cin 은 속도가 느리다. cin.sync_with_stdio(false) 를 사용하자. (cstdio 의 표준 입출력 함수들과의 동기화 해제)

변수 초기화 문제

초기화를 하지 않고 변수를 그대로 사용하면 두 번째 입력부터는 답이 잘못 나올 수 있다. 예제 입력 파일을 두 번 반복해 쓰는 것이 방법이다. 변수를 적절히 초기화하도록 신경 써서 코딩하는 것이 가장 좋은 방법이다.

디버깅에 관하여

• 프로그래밍 대회에서 작성하는 소스 코드를 대개 길지 않기 때문에, 눈으로 디버깅하는 쪽이 훨신 빠를 수 있다.
• 재귀 호출, 중복 반복문을 많이 사용하는 복잡한 코드는 디버거로 디버깅하기에 적당하지 않다.
• ACM-ICPC의 경우 세 명이 한 대의 컴퓨터를 나누어 써야 하기 때문에, 한 사람이 디버깅으로 컴퓨터를 점유하면 다른 두 사람은 아무 것도 할 수 없다.

디버거를 사용하는 대신 디버깅하는 팁

• 작은 입력에 대해 제대로 실행되나 확인하기
• 단정문(assertion)을 쓴다: 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문
• 프로그램의 계산 중간 결과를 출력한다.

테스트에 관하여

주어진 예제 입력을 약간 바꿔서 넣어 보거나, 있을 수 있는 가장 작은 입력과 가장 큰 입력을 만들어서 넣어 보고 시간 안에 실행되는지, 답은 잘 나오는지 테스트하자. 스캐폴딩: 다른 코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드 스캐폴딩으로 코드의 정당성을 확인하거나 반례를 찾는 데 유용하게 쓰자. 임의의 작은 입력을 자동으로 생성해 프로그램을 돌려 보고, 그 답안을 검증하는 프로그램을 짜면 쉽게 테스트할 수 있다.

변수 범위의 이해

산술 오버플로

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

1. 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 경고를 하지 않는다.
2. 프로그램의 정당성을 검증할 때 프로그램 논리의 정확성에만 집중하다 보면 산술 오버플로를 고려하지 못할 수 있음.

너무 큰 결과

큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 가지자. 64비트의 정수를 이용하면서 중간 계산 값을 32비트 정수로 전달할 수 있으니 주의하자.

너무 큰 중간 값

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

너무 큰 '무한대' 값

최단 경로를 구할 때 길이 없는 경우는 굉장히 큰 값을 더해줘서 min 함수에서 걸러지게 할 수 있다. 무한대 값을 선택할 때는 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 오버플로가 나지 않을 크기의 값을 선택하는 것이 좋다. 987,654,321 은 2의 30제곱에 가까운 매우 큰 값이면서 서로 더해지더라도 32비트 부호 있는 정수에 오버플로를 내지 않고, 오타가 났는지 확인하기 용이하다.

오버플로 피해가기

가장 간단한 방법은 더 큰 자료형 쓰는 것.

자료형의 프로모션

이항 연산자에서 만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산한다. 이를 프로모션이라 한다. C++ 의 프로모션 규칙

1. 한쪽은 정수형이고 한쪽은 실수형이면 정수형이 실수형으로 변환
2. 양쪽 다 정수형이거나 양쪽 다 실수형이면 보다 넓은 범위를 갖는 자료형으로 변환
3. 양쪽 다 int형보다 작은 정수형이면 양쪽 다 int형으로 변환
4. 부호 없는 정수형과 부호 있는 정수형이 섞여 있으면 부호 없는 정수형으로 변환

C++ STL 에서 모든 컨테이너의 size() 는 부호 없는 정수형을 반환한다. 이 때 크기가 0인데 -1 을 한다면 가장 큰 수가 되어버린다.

실수 자료형의 이해

실수 연산의 어려움

1/x * x = 1인 x의 수를 세는 코드를 작성하면 원하는 결과를 얻을 수 없음

실수와 근사 값

컴퓨터의 모든 실수 변수는 정확도가 제한된 근사 값을 저장한다.

IEEE 754 표준

• 이진수로 실수를 표기
• 부동 소수점 표기법
• 무한대, 비정규 수, NaN(Not a Number) 등의 특수한 값이 존재

실수의 이진법 표기

소수점 밑 i번째 자리의 크기는 1/(2^i)

부동 소수점 표기

• 부호 비트: 양수인지 음수인지 여부
• 지수: 소수점을 몇 칸 옮겼나?
• 가수: 소수점을 옮긴 실수의 최상위 X 비트

최상위 비트 1은 생략하므로 가수부가 52비트면 총 53비트 표현할 수 있다.

64비트 실수형: 부호 비트(1), 지수 비트(11), 가수 비트(52), 유효자릿수(15(10))

실수 비교하기

하나. 비교할 실수의 크기들에 비례한 오차 한도를 정한다.

둘. 상대 오차를 이용한다.

대소 비교

비교할 때 항상 두 값이 같은 경우, 즉 두 값이 아주 가까운 경우를 먼저 확인하고 처리해주어야 한다.

정확한 사칙연산

IEEE 표준에 의해 실수 변순들은, 정확하게 표현할 수 있는 값은 항상 정확하게 저장하도록 구현되어 있다. 64비트 실수형의 가수부는 52비트이므로 그 범위까지는 정확하게 표현할 수 있다. 추가적인 자료 구조를 도입해서 정확한 사칙연산을 구현할 수도 있다.

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

프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않으면 수치적으로 안정적이라고 한다.

실수 연산 아예 하지 않기.

• 곱셉과 나눗셈의 순서를 바꾸기
• 양변 제곱하기
• 실수 좌표를 써야 하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘려 정수만을 이용하여 문제 풀기

더 읽을거리

『Clean Code』(인사이트): 변수, 함수의 명명법, 함수의 구성, 주석을 쓰는 법까지 깨끗하고 잘 구성된 코드의 여러 원칙과 적용 예를 보여준다.

실수 비교에 관한 심도있는 내용

• http://links.algospot.com/comparingfloats
• http://links.algospot.com/fp-arithmetic
• http://floating-point-gui.de/

알고리즘 분류에 '투 포인터' 라고 나와있어 인터넷을 찾아 봤다. 간단하게 설명하면 부분 배열의 시작과 끝을 나타내는 두 점을 이용해서 원하는 값을 얻는 알고리즘이다. 참고: https://blog.naver.com/kks227/220795165570

투 포인터의 개념을 이용해서 풀었다.

1. 처음으로 시작하는 점의 위치를 찾아 start 에 삽입
2. 두 번째로 시작하는 점의 위치를 end 에 삽입
3. 두 점 사이의 거리의 최소값을 answer 에 삽입
4. start 와 end 사이에는 점이 없으므로 start 를 end 의 위치로 jump
5. 다음 점을 찾아 end 에 삽입
6. 반복

구현

#include <iostream>
#define    MAX    1000001
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    char* s = new char[n];
    for (int i = 0; i < n; ++i) cin >> s[i];

    int answer = MAX;

    int start, end;
    for (start = 0; start < n; ++start)
        if (s[start] == '.') break;
    for (end = start + 1; end < n; ++end)
        if (s[end] == '.') break;

    do {
        int distance = end - start - 1;
        if (distance < answer) answer = distance;
        start = end;
        for (end += 1; end < n; ++end)
            if (s[end] == '.') break;
    } while (end + 1 < n);

    cout << answer << '\n';
    return 0;
}

느낀점

알고리즘 스터디에서 풀 쉬운 투 포인터 문제를 찾다 보니 스페인어로 된 문제를 풀게 됐다. 물론 구글 번역기의 도움을 받았고, 언어 때문인지 작성일 기준 맞춘 사람이 12명 뿐이다.

정답을 맞춘 뒤 채점 현황에서 맞춘 사람들을 확인하니 고스펙 분들 밖에 없어서 배우고자 하는 마음으로 소스를 봤다. 그리고 새로 알게 된 사실이 있다.

1. MAX 를 따로 전처리기로 처리하지 않고 1e9 와 같은 형식으로 초기화
2. cin.tie(0)->sync_with_stdio(0);
3. 반복문 하나로 정답(내 풀이와 원리 자체는 같음)

2번에 대해서만 설명을 덧붙이자면 std::cin 은 istream 의 객체로 표준 입력 스트림 cin.tie(0) 호출 시 cout 과 cin 를 untie 후 ostream* 반환 ostream 은 ios 에 상속되고 ios 는 ios_base 에 상속됨 ios_base 의 멤버 함수 sync_with_stdio 를 멤버 연산자로 호출할 수 있음

자식 노드에 접근하는 식의 변경이 있다. 구현을 단순화하기 위해 1부터 센다고 책에는 나오는데, 그렇게 복잡해지는지는 모르겠다.

삭제 연산할 때 리프 노드를 가져오는 이유

리프 노드는 삭제 되어도 대소 관계나 Heap 의 모양 규칙에 영향을 주지 않는다.

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

삽입과 삭제 모두, 처음에는 모양 규칙을 지키고 그 다음에 대소 관계 규칙에 따라 순서를 바꾼다.

Heap 의 생성을 O(N) 으로 하는 법

상향식 힙 생성은 Heap 에 삽입해야 되는 키가 모두 미리 주어졌을 때 O(N) 으로 가능하다고 한다. 참고: https://youngminieo1005.tistory.com/31

Heap 정렬의 효율

병합 정렬은 배열이 하나 더 필요하다. Heap 정렬은 최대 원소를 배열의 마지막 칸에 삽입하면서 정렬되도록 구현하면 따로 공간이 필요없다. 시간 복잡도는 O(NlgN) 이다.

Heap 의 임의 원소 변경

Heap 에서 임의 원소를 변경하거나 삭제할 수 있다고 한다. 참고: http://www.secmem.org/blog/2020/08/16/heap/

마치며

[알고리즘 문제 해결 전략, 구종만 저] 를 읽다가 갑자기 의문이 든 부분을 정리해봤다. Heap 생성을 O(N) 으로 할 수 있고, 임의 원소를 변경하는 방법이 있다는 점은 새로웠다.

백준 단계별 풀기

위 사진은 백준 저지 사이트의 [문제] -> [단계별로 풀어보기] 의 분할 정복 단계의 문제들이다. 기존에 10단계(재귀)까지는 풀어두어서 스터디는 11단계(브루트 포스)부터 하게 되었는데 단계가 올라갈 수록 solved.ac 티어가 급격히 올라가는걸 볼 수 있다.

개인적으로 내가 현재 풀 수 있는 문제의 수준은 실버3이 최대라고 생각한다. 실버2 이상의 문제부터는 스택, 큐 구현 등 기존에 자료구조만 공부했다면 풀 수 있는 문제를 제외하고서는 거의 인터넷에 나와있는 솔루션을 참고했다.

그렇게 약 6달 정도 알고리즘 스터디를 진행하고 있었는데 플래티넘 문제를 풀어보고 낙담을 하게 되었다. 동적 계획법 문제를 풀면서부터 서서히 느끼던 감정이었는데 나에게는 너무 어려웠다. 결국 솔루션을 참고했지만 '가장 가까운 두 점' 문제는 아직도 완전히 이해하지 못 했다.

실력자의 조언

단계별 풀기에서 어떤 유형을 배우게 되더라도 복습을 하지 않으니 수 개월이 지나 다시 보게 되면 기억이 나지 않았다. 그래서 단계별 풀기만을 고집하지 않고 한 유형의 문제를 계속해서 풀어보는 방법도 괜찮겠다고 생각하는 찰나에 실력자의 조언을 보게 됐다. 코드포스 2400 이상 여러 커뮤니티의 의견을 종합해보고 내린 결론은 다음과 같다.

1. 모르는 개념에 대한 공부를 먼저 한다. (세그먼트 트리, 비트 마스크 등)
2. 그와 관련된 문제를 내 수준에 맞게 검색하여 많이 풀어본다.
3. 언제나 중요하게 생각해야 되는 것은 '이 알고리즘이 어떤 상황에 사용될 때 가장 효율적인가?'

스터디원과 의논

백준 단계별 풀기에서 하루 한 문제씩 푸는 스터디를 진행하고 있는데 매주 토요일마다 모여서 어려웠던 문제에 대해 의견을 나누는 시간을 가진다. 나를 포함하여 3명이 진행하는데 한 명도 플래티넘 문제를 완전히 이해하지는 못 했다. 그래서 최근 생각하고 있던 것을 말했고 앞으로의 공부 방식에 대해 의논을 해봤다.

1. 백준 단계별 풀기를 따라가되 시야를 넓히자는 의미에서 각 단계를 개념 공부 후 1~2문제만 풀어보고 바로 다음 단계로 넘어가며 전체를 빠르게 훑어보고, 그 다음 어려웠던 개념 위주로 문제 검색을 이용해 많은 문제를 풀어보자.
2. 훑어보지 않고 지금까지 풀었던 문제 중 어려운 개념 위주로 많은 문제를 풀어보자.

이렇게 두 가지 의견이 종합되었다. 결론은 1안을 택하게 되었다. 6달 동안 스터디를 진행하며 이전에는 몰랐던 알고리즘을 많이 알게 되었지만 지금도 가끔 솔루션을 참고하면서 모르는 용어를 접하게 되는데 그래서 빠르게 시야를 넓히고 시작하자는 의견이 나오게 됐다.

다짐

단계별로 풀어보기 문제만 156문제를 풀었지만 아직 많이 부족하다고 느낀다. 각 알고리즘의 효율을 생각하며 지금 방법대로 잘 공부해서 좋은 방향으로 나아갔으면 좋겠다!

잡담

GitHub에 팔로우 되어있는 학교 사람들이 velog 를 많이 사용하길래 첫 글을 써봤다. 마크다운을 익힌 뒤로 가끔 Notion 이나 GitHub 에 글을 작성했었는데 velog 도 같은 방식이라 글이 깔끔하게 써져 마음에 든다. 알고리즘 문제를 풀다가 기억에 잘 안 남을 법한 내용을 정리하는 용도로 쓸 것 같다. 내 의지가 계속되도록 간절히 바란다!!