정오표

『코딩 인터뷰 완전 정복』정오표입니다.

 

33쪽 소제목

3. 특별한 상황 – 스타트업

5. 특별한 상황 – 스타트업

58쪽

2^20 값을 1,048,576로 수정

64쪽

7번째 줄: 간단한 계산을 통해, 답이 (30h – 5.5m) % 360 이 됨을 구할 수 있다.

68쪽 두 번째 문단

큰 수 무더기는 최소 힙에 두, 큰 수 무더기 가운데 가장 작은 수가 루트에 오게 한다. 작은 수 무더기는 최대 힙에 두, 그중 가장 큰수가 루트에 오게 한다.

큰 수 무더기는 최소 힙에 두, 큰 수 무더기 가운데 가장 작은 수가 루트에 오게 한다. 작은 수 무더기는 최대 힙에 두, 그중 가장 큰수가 루트에 오게 한다.
(최소 힙은 원래 루트에 가장 작은 수가 오는 것이고, 최대 힙은 원래 루트에 가장 큰 수가 오는 것이니, 대립되는 문장을 연결할 때 사용하는 ‘-되’는 적절하지 않습니다)

93쪽

문제 번호 오류: 객체 지향 설계(#7.10) 정렬과 탐색 (#9.6)

99-100쪽

class Stack 4행

Node pop() { --> Object pop() {

19행

Node peek() { --> Object peek() {

20행

return top.data;
100쪽

class Queue

5행

if (!first) { --> if (first == null) {

14행

Node dequeue(Node n) { --> Object dequeue(Node n) {
102쪽

오름차순 –> 오름차순(보다 큰 값이 스택 상단에 위치)

104쪽

두 번째 단락 2^n –> 2^n – 1

106쪽

첫 번째 가상코드 2행

if (root != null) return; --> if (root == null) return;

6행(열린 괄호 {가 빠짐)

if (n.visited == false) {
107쪽

문제 4.3에 ‘배열 내 모든 원소는 배열 내에서 유일한 값을 갖는다’는 조건 추가

110쪽

표 아래에 있는 답 가운데 네 번째 줄 마지막 답은 0011이 아니라 1000임

111쪽

4번 항목의 처음에 등장하는 수식 x && (~0 << n)은 x & (~0 << n)로 바뀌어야 함

113쪽

페이지 아래에서 두 번째 줄 “v를 i번 시프트한다”는 “v를 왼쪽으로 i번 시프트한다”로 변경.

113쪽

from clearBitsIthrough0() 정의 앞부분의 쓸데없는 public static 제거

113쪽

clearBitsMSBthroughI()의 2행을 다음과 같이 수정

int mask = (1 << (i+1)) - 1;

–>

int mask = (1 << i) - 1;
114쪽

문제 5.2에서 “해당 값이 32개 이하의 비트들을 사용해 이진수 형태로 올바르게 출력될 수 없는 경우에는”을 “해당 값이 길이가 32 이하의 문자열로 출력될 수 없는 경우에는”으로 변경.

115쪽

문제 5.7의 첫 문장 변경: “배열 A에 0부터 n까지의 정수가 저장되어 있다.”

122쪽

“아마 알고 있겠지만, 모든 수는 소수의 곱 형태로 쪼갤 수 있다”
–>
“아마 알고 있겠지만, 모든 양의 정수는 소수의 곱 형태로 쪼갤 수 있다”

134쪽

페이지 맨 위쪽의 클래스 Restaurant의 코드에서 2행을 다음과 같이 변경

private static Restaurant _instance = null;이 되어야 함.
149쪽

10.3 문제에 주석 추가: 배열 내 모든 원소가 해당 배열 내에서 유일한 값을 갖는 경우에 이 문제에 대한 답은 O(log n) 시간에 동작한다. 하지만 중복된 값을 갖는 원소가 많을 경우 실행 시간은 O(n)이 되는데, 배열(또는 부분 배열)의 왼쪽과 오른쪽을 탐색해야 하는 일이 빈번하게 발생하기 때문이다.

157쪽

페이지 상단 그림의 마지막 solution = doc을 다음과 같이 수정함

solution = doc5
171쪽

코드 16행과 17행 사이에 public: 삽입

172쪽

생성자와 소멸자” 첫번째 단락의 “…자동으로 하나 만든다.”뒤에 다음 문장 추가. “그 생성자 대신, 임의의 생성자를 정의해 사용할 수도 있다.

173쪽

페이지 상단의 소멸자 코드를 아래와 같이 변경.

~Person() {
    delete obj; // free any memory allocated within class
}
178쪽

맨 아랫줄 “p++와 같이 하면 p는 4바이트 전진한다”를 “p++와 같이 하면 p는 sizeof(int) 바이트 만큼 전진한다”로 변경.

190쪽

“질의 #1: 학생 등록” 절에서, “bookStudents”와 “bookStudentCourses”로 표시된 모든 테이블 명은 “Students”와 “StudentCourses”로 바뀌어야 한다.

193쪽

“질의 #2: 수강생 수 구하기” 절에서, 첫 번째 단락을 “모든 교사 목록과 각 교사가 가르치는 학생 수를 구하는 질의를 작성해 보자. 동일한 학생이 동일한 교사의 여러 강의를 수강하는 경우, 그 각각을 다른 학생으로 쳐서 가르치는 학생 수에 합산한다. 교사 리스트는 각 교사가 가르치는 학생 수를 기준으로 내림차순 정렬되어야 한다.”

208쪽

메서드 C라고 표시한 부분을 전부 메서드 B로 바꾸어야 한다.

214쪽

문제 18.5를 다음과 같이 변경:

“단어들이 적혀 있는 아주 큰 텍스트 파일이 있다. 단어 두 개가 입력으로 주어졌을 때, 해당 파일 안에서 그 두 단어 사이의 최단거리(단어 수를 기준으로 측정한)를 구하는 코드를 작성하라. 같은 파일에 대해 단어 간 최단거리를 구하는 연산을 여러번 반복하게 된다고 했을 때 (단어 쌍은 서로 다른 것을 사용한다) 어떤 최적화 기법을 사용할 수 있겠는가?”

227쪽

코드 42행 count = 0을 다음과 같이 수정

count = 1
228쪽

17, 24, 28행에서 setChar에 전달되는 인자 str 제거

232쪽

18행에서 쓸데없는 괄호 쌍을 제거. 즉, 다음과 같이 변경

if (row[i] || column[j]) {
235쪽

235페이지 마지막 단락 앞에 다음과 같이 k에 대한 설명을 부가한다. “본 풀이에서는 k = 1이 마지막 원소를 가리킨다고 가정하였다.”

238쪽

페이지 상단의 코드 중 10행에서 nthToLastR2를 호출하는 부분은 다음과 같이 변경

nthToLastR2(head.next, k, i)
238쪽

페이지 아래쪽 코드 1행과 2행 사이에 다음을 추가

if (k
256쪽

256-257 페이지에 걸쳐있는 코드에서 2행, 5행, 7행에 있는 Question.Result를 다음으로 변경

Result
259쪽

259페이지에 실린 코드 3행을 다음으로 변경

static int [] stackPointer = {-1, -1, -1};
260쪽

코드 16행을 다음으로 변경

if (start
260쪽

isWithinStack 함수의 정의를 다음과 같이 변경함.

public boolean isWithinStack(int index, int total_size) {
    // Note: if stack wraps, the head (right side) wraps around to the left.
    if (start total_size && index < (start + capacity) % total_size) {
        // tail (left side) of wrapping case
        return true;
    }
    return false;
}
261쪽

QuestionB 클래스에 numberOfElements()의 정의 추가.

public static int numberOfElements() {
    return stacks[0].size + stacks[1].size + stacks[2].size;
}
264쪽

페이지 맨 윗줄의 push(6)을 push(5)로, 그 다음 줄의 push(5)를 push(6)으로 변경.

276쪽

페이지 첫 번째 단락에 등장하는 “최댓값”은 전부 “최솟값”으로 변경.

276쪽

“네 번째 단락부터 내용과 그림을 다음과 같이 변경. 소스코드 바로 앞까지.
——–
다음과 같은 스택이 주어졌다고 해 보자. S2는 정렬되어 있으나 s1은 아니다.
s1 = [5, 10, 7]
s2 = [12, 8, 3, 1]

s1에서 pop한 5를 넣을 적절한 위치를 s2에서 찾아야 한다. 위의 예제의 경우, s2의 3 위에 넣으면 된다. 그런데 그 자리에 넣으려면 어떻게 해야 하는가? 우선 s1에서 pop한 5를 임시 변수에 보관한 다음, s2의 12와 8으로 차례로 이동시킨다(s2에서 pop한 다음 s1에 push하면 된다). 그런 다음 5를 s2에 push한다.

Step 1
s1 = [10, 7]
s2 = [12, 8, 3, 1]
tmp = 5

Step 2
s1 = [8, 12, 10, 7]
s2 = [3, 1]
tmp = 5

Step 3
s1 = [8, 12, 10, 7]
s2 = [5, 3, 1]
tmp = —

8과 12가 아직도 s1에 남아있다는 것에 유의하자. 그래도 상관없다. 이 두 원소에 대해서도, 원소 5에 시행했던 절차를 그대로 반복한다. s1의 모든 원소를 s2에 적절한 위치를 찾아 삽입하는 것이다. (물론, 8과 12는 s2에서 s1으로 이동시킨 원소이고 5보다 큰 값을 갖기 때문에 이 두 원소의 “”적절한”” 위치는 5 위쪽일 것이다. s2의 다른 원소들을 헤집고 다니느라 시간 낭비할 필요가 없다. 따라서 다음 코드의 while 루프 안쪽에 있는 코드는 tmp의 값이 8이거나 12일때는 실행되지 않는다.)”

279쪽

279페이지의 코드 Line 54와 58이 getFirst() 대신 poll()을 호출하도록 변경한다.
Line 48과 50은 각각 return dequeueDogs();와 return dequeueCats(); 로 변경한다.

283쪽

line 16의 주석문 내의 i.e. pop()을 i.e.dequeue()로 변경.

285쪽

페이지 맨 아래쪽 단락 첫번째 문장 시작부분 “정순회(in-order traversal)”를 “전순회(pre-order traversal)”로 변경.

291쪽

첫 번째 단락의 마지막 부분에 있는 (min = 10, max = INT_MAX)를 다음으로 변경

(min = 20, max = INT_MAX)
295쪽

CommonAncestorHelper 메서드의 시작 부분에 다음의 두 줄을 추가.

if (root == null) return null;
if (root == p || root == q) return root;
306쪽

첫 번째 단락의 첫 문장 “이 알고리즘의 시간 복잡도는 얼마인가?”를 “(균형잡힌 이진 트리를 가정하였을 때) 이 알고리즘의 시간 복잡도는 얼마인가?”로 변경.

306쪽

페이지의 제일 마지막 문장을 다음과 같이 변경. “공간 복잡도는 O(log n)이다. 이 알고리즘은 O(log n) 번의 재귀적 호출을 실행하는데, 인자 path는 재귀 호출이 이루어지는 동안 단 한번 할당되기 때문이다. Path에는 O(log n) 만큼의 공간이 필요하다.

310쪽

소스코드의 10행을 다음으로 변경

if (binary.length() >= 32) {
314쪽

5행 a = a << pos을 다음으로 변경

a = a << p

그 아래 5행 n &= ~((1 << pos) -1)는 다음으로 변경

n &= ~((1 << p) -1) 로 변경.

아래에서 5행을 다음과 같이 변경.

a = 1 << (c1 - 1); // c1 - 1 번 비트는 1, 나머지는 0.
317쪽

getPrev(int n) 메서드의 5행을 다음과 같이 변경.

while ((temp & 1) == 1) {
325쪽

페이지 중간의 두 번째 테이블 바로 앞에 있는 수식을 다음과 같이 변경.

count_2(0s)=count_2(1s) 또는 count_2(0s)=1+count_2(1s) .

(이 수식에서 _2는 2를 아래첨자로 표기하여야 한다는 뜻이다.)

325쪽

페이지 하단 수식 2 줄에 전부 LBS2가 LBS_2로 바뀌어야 함. (2를 아래첨자로 표기)

326쪽

페이지 상단에 있는 LBSi들은 전부 LBS_i들로 바뀌어야 함. (i를 아래첨자로 표기)

328쪽

소스 코드 아래 첫 번째 단락 첫 번째 줄에서 “23번과 25번 줄”은 “24번과 27번 줄”로 변경되어야 함.

329쪽

소스코드의 Line 26을 다음과 같이 변경함.

screen[(width / 8) * y + (x1 / 8)] |= mask;
342쪽

아래에서 두 번째 단락에 있는 “두 직선의 기울기가 다른지 보기만 하면 된다”를 “두 직선의 기울기가 다른지 (아니면 동일한 직선인지) 살펴보기만 하면 된다”로 변경.

346쪽

두 번째 단락의 “더해야 하는 횟수는 a와 같을 것이다”를 “더해야 하는 횟수는 x와 같다”로 수정.

347쪽

소스 코드 앞에 “아래의 풀이에서 원점 (0, 0)은 이차원 평면의 좌상단 꼭지점이라고 가정할 것이다.”로 수정.

347쪽

14-19행을 다음과 같이 변경.

/* 직선 mid2->mid1이 어느 방향으로 가는지 찾는다 */

36-44행을 다음과 같이 변경.

/* (y1 - y2) / (x1 - x2) 식을 사용해 기울기 계산. Note: 기울기가 너무 가파르면 (>1) 선의 끝 부분이
* y축 가운데 지점에서 size / 2 만큼 떨어진 부분을 때리게 된다. 반대로 너무 완만하면 ( * x축의 가운데에서 size / 2 만큼 떨어진 지점을 지나게 된다. */

57-71행의 cut 함수를 다음과 같이 변경.

public Line cut(Square other) {
/* 각 중간점을 잇는 직선이 사각형 가장자리의 어디를 지나는지 계산 */
    Point point_1 = extend(this.middle(), other.middle(), this.size);
    Point point_2 = extend(this.middle(), other.middle(), -1 * this.size);
    Point point_3 = extend(other.middle(), this.middle(), other.size);
    Point point_4 = extend(other.middle(), this.middle(), -1 * other.size);

    /* 계산된 점들 중에 직선들의 시작와 끝 점을 찾는다.
    시작점은 가장 왼쪽점 (같은 점이 있을 때는 맨 윗점), 끝점은 가장 우측점
    (같은 점이 있을 때에는 맨 아랫점) */
    Point start = point_1;
    Point end = point_1;
    Point[] points = {point_2, point_3, point_4};
    for (int i = 0; i < points.length; i++) {
        if (points[i].x < start.x || (points[i].x == start.x && points[i].y < start.y)) {             start = points[i];         } else if (points[i].x > end.x || (points[i].x == end.x && points[i].y > end.y)) {
            end = points[i];
        }
    }
    return new Line(start, end);
}
349쪽

7.6의 해법을 통째로 다음과 같이 바꿉니다.

언뜻 보기에는 꽤 직관적으로 풀 수 있을 것 같은 문제이다. 그리고 어느 정도는 그렇다. 모든 두 점을 통과하는 무한 길이의 직선을 (선분이 아니라) “”그린”” 다음에 해시테이블을 사용해서 어떤 직선이 가장 빈번히 나타나는지 추적하면 된다. 이 알고리즘의 수행 시간은 O(N^2)일 것인데, N^2 개의 직선을 만들 수 있기 때문.

그리고 기울기와 y-절편으로 직선을 표현하면, (x1, y1)과 (x2, y2)를 통과하는 직선이 (x3, y3)와 (X4, y4)를 통과하는 직선과 동일한지를 쉽게 검사할 수 있다. 다시 말해서 가장 많은 점을 통과하는 직선을 찾으려면, 모든 직선을 검사해 나가면서 같은 직선이 몇 번이나 등장했는지를 해시 테이블을 사용해 세면 된다는 것이다. 간단하다!

하지만 문제가 있다. 같은 기울기와 y-절편을 갖는 직선을 동일한 직선이라고 정의하고, 이 두 값을 사용해서 해시 테이블을 뒤지게 되면 (특히, 기울기를 사용하면) 문제가 발생한다. 부동 소수점 수를 이진수로 ‘항상’ 정확하게 표현할 방법이 없기 때문에, 두 부동 소수점 수가 같은지를 올바르게 판별하기가 어렵다는 것. 이 문제를 해결하기 위해, 두 부동 소수점 수가 입실론(epsilon) 편차 안에 있으면 같은 수 인 것으로 보도록 했다. 그런데 이렇게 하면 “”같은”” 두 직선이 “”같은”” 해시 값을 갖지 않는 문제가 발생하게 된다. 이 문제를 해결하기 위해, 기울기를 입실론 값에 따라 내림한 flooredSlope를 계산하여 해시 키로 사용하도록 했다. 그렇게 한 다음, 같을 가능성이 있는 모든 직선을 추출하기 위해 해시 테이블의 세 지점을 탐색하도록 했다. (flooredSlope, flooredSlope – epsilon, 그리고 flooedSlope + epsilon) 그렇게 하면 동일한 직선일 가능성이 있는 모든 직선을 검사할 수 있다.

Line findBestLine(GraphPoint[] points) {
    Line bestLine = null;
    int bestCount = 0;
    HashMap> linesBySlope = new HashMap>();

    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {             Line line = new Line(points[i], points[j]);             insertLine(linesBySlope, line);             int count = countEquivalentLines(linesBySlope, line);             if (count > bestCount) {
                bestLine = line;
                bestCount = count;
            }
        }
    }
    return bestLine;
}

int countEquivalentLines(ArrayListlines, Line line) {
    if (lines == null) return 0;
    int count = 0;
    for (Line parallelLine : lines) {
        if (parallelLine.isEquivalent(line) count++;
    }
    return count;
}

int countEquivLines(HashMap> linesBySlope, Line line) {
    double key = Line.floorToNearestEpsilon(line.slope);
    double eps = Line.epsilon;
    int count = countEquivalentLines(linesBySlope.get(key), line) +
        countEquivalentLines(linesBySlope.get(key - eps), line) +
        countEquivalentLines(linesBySlope.get(key + eps), line);
    return count;
}

void insertLine(HashMap> linesBySlope, Line line) {
    ArrayList lines = null;
    double key = Line.floorToNearestEpsilon(line.slope);
    if (!linesBySlope.containsKey(key)) {
        lines = new ArrayList();
        linesBySlope.put(key, lines);
    } else {
        lines = linesBySlope.get(key);
    }
    lines.add(line);
}

public class Line {
    public static double epsilon = .0001;
    public double slope, intercept;
    private boolean infinite_slope = false;

    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) {    // x가 다르면
            slope = (p.y - q.y) / (p.x - q.x);  // 기울기 계산
            intercept = p.y - slope * p.x;      // y 절편
        } else {
            infinite_slope = true;
            intercept = p.x;                    // x 절편 (기울기가 무한대)
        }
    }

    public static double floorToNearestEpsilon(double d) {
        int r = (int) (d / epsilon);
        return ((double) r) * epsilon;
    }

    public boolean isEquivalent(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }

    public boolean isEquivalent(Object o) {
        Line l = (Line) o;
        if (isEquivalent(l.slope, slope) &&
            isEquivalent(l.intercept, intercept) &&
            (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }
}

직선의 기울기를 계산할 때에는 주의해야 한다. 직선이 y축에 평행하여 y 절편이 존재하지 않는 경우 기울기는 무한대이다. 따라서 infinite_slop라는 별도 플래그를 두어 이를 추적할 수 있도록 했다. equals 메소드에서 이 플래그를 사용해 직선 일치 여부를 검사한다.

354쪽

21행 if 조건은 k
25행 주석문 제거.
26행 for 문에서 int i = 1을 int i = 0으로 변경

404쪽

페이지 마지막 줄의 O(N^3)을 O(3^N)으로 대체.

407쪽

getPath의 코드를 다음과 같이 변경.

public static boolean getPath(int x, int y, ArrayList path) {
    Point p = new Point(x, y);
    if (x == 0 && y == 0) {
        return true; // 경로 찾음
    }
    boolean success = false;
    if (x >= 1 && isFree(x - 1, y)) { // 왼쪽 시도
        success = getPath(x - 1, y, path); // 비어 있으므로 왼쪽으로 감
    }
    if (!success && y >= 1 && isFree(x, y - 1)) { // 위쪽 시도
        success = getPath(x, y - 1, path); // 비어 있으므로 위쪽으로 감
    }
    if (success) {
        path.add(p); // 올바른 길이므로 경로에 추가.
    }
    return success;
}
408쪽

getPath의 코드를 다음과 같이 변경

public static boolean getPath(int x, int y, ArrayList path, Hashtable cache) {
    Point p = new Point(x, y);
    if (cache.containsKey(p)) { // 이미 방문한 셀
        return cache.get(p);
    }
    if (x == 0 && y == 0) {
        return true; // 경로 찾음
    }
    boolean success = false;
    if (x >= 1 && isFree(x - 1, y)) { // 왼쪽 시도
        success = getPath(x - 1, y, path, cache); // 비어 있으므로 왼쪽으로 감
    }
    if (!success && y >= 1 && isFree(x, y - 1)) { // 위쪽 시도
        success = getPath(x, y - 1, path, cache); // 비어 있으므로 위쪽으로 감
    }
    if (success) {
        path.add(p); // 올바른 길이므로 경로에 추가
    }
    cache.put(p, success); // 결과를 캐시에 반영
    return success;
}
411쪽

페이지 맨 위쪽의 그림에서 밑줄이 쳐진 2를 3으로 변경

411페이지 설명에서 A[5] = 2라고 표기된 부분을 전부 A[5] = 3으로 변경

412쪽

맨 마지막 줄 “P(3)와 같이 표기한다”를 “P(n)”과 같이 표기한다”로 변경.

419쪽

소스코드 11-13행을 다음과 같이 수정.

set.add(s)

소스코드 16-18행을 다음과 같이 수정.

set.add("()" + str)
422쪽

422페이지 소스코드 21-23행을 다음과 같이 변경.

boolean paintFill(Color[][] screen, int x, int y, Color ncolor) {
    if (screen[y][x] == ncolor) return false;
    return paintFill(screen, x, y, screen[y][x], ncolor);
}
427쪽

아래쪽에서 다섯째 줄, “퀸을 (7, 3), (6, 7)에 둔 상태에서 8개의 퀸을 8X8 체스판에 배치하는 방법” 뒤에 있는 “+” 기호 제거.

428쪽

소스코드 12행 삭제.

436쪽

“카탈란의 수라고 한다.” 다음에 “여기서 n은 괄호 쌍의 개수이다.” 추가.

438쪽

소스코드 내의 주석문 (2-3라인) 잘못됨

int indexA = lastA - 1; /* 배열 a의 마지막 원소 첨자 */
int indexB = lastB - 1; /* 배열 b의 마지막 원소 첨자 */
445쪽

소스코드 3행 앞에 다음을 추가

if (first > last) return -1;
449쪽

첫 번째 문단 두 번째 줄 “같은 행에 속한 0부터 j사이에 있는”을 “같은 행에 속한 0부터 j-1까지의” 로 변경

456쪽

소스코드의 38행을 다음으로 변경

for (int i = 0; i < array.size(); i++) {
458쪽

페이지 하단 트리 앞에 다음 문장을 추가: “아래의 그림에서 괄호 안에 있는 숫자는 해당 노드의 왼쪽 부분 트리 안에 있는 노드 개수이다 (다른 말로 하면, 그 하위 트리에 상대적인, 해당 노드의 랭킹 값이다). ”

470쪽

11.3번 문제의 시작 부분을 “40억개의 정수”에서 “40억 개의 0을 포함하는 양의 정수”로 변경한다.

471쪽

소스코드 2행의 findOpenNumber2를 다음으로 변경

findOpenNumber
472쪽

첫 문단의 시작 부분을 “우리는 어떤 블록에 얼마나 많은 정수가 있어야 하는지 정확하게 알고 있다”에서 “중복되는 수가 없으므로, 우리는 각각의 블록에 얼마나 많은 수가 있는지 안다.”로 변경한다.

472쪽

위에서 세번째 줄에 있는 998을 999로 변경.

473쪽

소스코드 23행을 다음과 같이 변경

in = new Scanner(new FileReader("file.txt"));
478쪽

해법 첫 번째 문단의 “”400기가바이트””를 “”4테라바이트””로 변경.
세 번째 문단의 400GB를 4TB로 변경.
해법 #1 첫 번째 문단의 “”무더기 400개””를 “”무더기 4000개””로 변경. 해법 #2의 세번째, 네 번째 문단에 있는 400도 전부 4000으로 변경.

490쪽

위에서 여섯 번째 줄의 “y가 체스판 폭보다”를 “y가 체스판 높이보다”로 수정.

497쪽

해법의 두 번째 단략 첫 번째 줄 마지막 “처음에는 1부터 K까지의 행들이 이 배열에”를 “처음에는 0부터 K까지의 행들이 이 배열에”로 수정.

501쪽

소스코드 10행은 다음으로 수정

dest.ptr = (char *)malloc(strlen(src.ptr) + 1);

소스코드 11행은 다음으로 수정:

strcpy(dest.ptr, src.ptr);
507쪽

소스코드 6행의 SmarterPointer&는 다음과 같이 변경

SmartPointer<T>&
508쪽

소스코드 19-30을 다음과 같이 변경.

SmartPointer<T> & operator=(SmartPointer<T> & sptr) {
    if (this == &sptr) return *this;
    /* 이미 어떤 객체에 배정되어 있는 경우, 그에 대한 참조 감소. */
    if (*ref_count > 0) {
        remove();
    }
    ref = sptr.ref;
    ref_count = sptr.ref_count;
    ++(*ref_count);
    return *this;
}
510쪽

마지막 단락을 다음과 같이 수정.

(p+16)&11..1000을 (p+16)&11..10000으로 수정.

“즉, 주소 값의 마지막 세 비트를 000과 AND하면”을, “즉, 주소 값의 마지막 네 비트를 0000과 AND 하면”으로 변경.

510쪽

소스코드의 4행을 다음과 같이 수정

void* q = (void*) (((size_t)(p) + offset) & ~(alignment - 1));
517쪽

두 번째 소스 코드에서 3행을 다음과 같이 변경함.

String str = (String) vector.get(0)
518쪽

소스코드의 22행을 다음과 같이 변경

int f2 = foo2 -> val;
526쪽

소스코드의 1-3 행을 다음과 같이 변경.

SELECT BuildingName, ISNULL(Count, 0) as 'Count'
    FROM Buildings
    LEFT JOIN
532쪽

CourseEnrollment테이블에서 Grade의 타입을 integer에서 decimal로 변경.
따라서 531페이지의 마지막 줄 “성적 정보는 정수값으로 저장된다고 가정하겠다”는 삭제.

532쪽

532페이지 소스 코드를 다음과 같이 변경.

Microsoft SQL Server 제품의 TOP … PERCENT 함수를 사용하는 경우, 우선 다음과 같은 질의문을 만들어 볼 수 있을 것이다. (맞는 답은 아니다.)

SELECT TOP 10 PERCENT AVG(CourseEnrollment.Grade) AS GPA, CourseEnrollment.StudentID
    FROM CourseEnrollment
    GROUP BY CourseEnrollment.StudentID
    ORDER BY AVG(CourseEnrollment.Grade)

이 코드는 GPA 기준으로 정렬된 결과에서 순수하게 10% 만을 뽑아 낸다는 문제를 가지고 있다. 가령 100명의 학생이 있는데 그 중 최상위 15명의 학생이 전부 4.0 GPA를 받았다고 하더라도, 위 코드는 그 중 10명만 골라낸다. 따라서 동점자가 생기는 경우 그 학생도 전부 포함시키도록 개선해야 한다.

이 문제를 해결하기 위해 우선 ‘컷 오프(cut off)’ 기준 점수를 계산하는 도구부터 만들어보자.

DECLARE @GPACutOff float;
SET @GPACutOff = (SELECT min(GPA) as ‘GPAMin’
    FROM (
        SELECT TOP 10 PERCENT AVG(CourseEnrollment.Grade) AS GPA
            FROM CourseEnrollment
            GROUP BY CourseEnrollment.StudentID
            ORDER BY GPA desc)
    Grades);

@GPACutOff가 정의되고 나면, 그 점수 이상인 학생을 골라내는 건 단순한 작업이다.

SELECT StudentName, GPA
FROM (
    SELECT AVG(CourseEnrollment.Grade) AS GPA,
    CourseEnrollment.StudentID
        FROM CourseEnrollment
        GROUP BY CourseEnrollment.StudentID
        HAVING AVG(CourseEnrollment.Grade) >= @GPACutOff) Honors
    INNER JOIN Students ON Honors.StudentID = Student.StudentID
534쪽

세 번쨰 단락을 다음과 같이 수정: “쓰레드는 프로세스 안에 존재하며 프로세스의 자원 (힙 공간 등)을 공유한다. 같은 프로세스 안에 있는 쓰레드들은 같은 힙 공간을 사용하게 된다. 이는 다중 프로세스 환경과는 다른데, 프로세스는 다른 프로세스의 메모리를 직접 접근할 수 없다. 각각의 쓰레드는 별도의 레지스터와 스택을 갖지만, 힙 메모리는 서로 읽고 쓸 수 있다.”

547쪽

소스코드의 3-4행을 다음과 같이 수정:

public ReentrantLock lock1, lock2, lock3;
548쪽

소스코드 2-3행을 다음과 같이 수정.

public Semaphore sem1, sem2, sem3;
562쪽

두 번째 소스코드의 5번째 라인의 주석문을 다음과 같이 변경.

// if b >= 0, then 1 else 0
565쪽

소스코드의 49행을 다음과 같이 변경.

if (code >= 0 && frequencies[code] > 0 && guess.charAt(i) != solution.charAt(i)) {
567쪽

소스코드의 17행을 다음과 같이 수정:

for (int i = start - 1; i >= 0; i--) {
568쪽

소스코드의 39행 다음에 다음 코드를 추가.

if (min_index >= array.length) {
    return; // 이미 정렬됨
}
571쪽

해당 페이지 마지막 단락의 currentSum을 sum으로 수정. 다음 페이지의 currentSum도 sum으로 수정. 그 다음 단락의 currentSum도 sum으로 수정. 그 다음 단락의 currentSum도 sum 으로 수정. 역시 그 다음 단락의 currentSum도 sum으로 수정. 이런 식으로 소스코드 앞까지 나오는 모든 currentSum을 전부 sum으로 수정.

576쪽

페이지 마지막 줄에 등장하는 “그 결과를 10으로 나눈”은 “그 결과를 7로 나눈”으로 수정되어야 함.

602쪽

페이지 최상단의 가상 코드에서, 1행은 다음과 같이 수정되어야 함.

if x[d] = 2: count2sInRangeAtDigit(x, d) =

그리고 그 다음 세 줄의 가상 코드는 안쪽으로 들여쓰기되어야 함.

604쪽

아래에서 5행에 있는 리스트를 다음과 같이 변경.

list: {1a, 2a, 4b, 9a, 10b, 15a, 19b, 25a}

604쪽

페이지 맨 아래쪽에 다음의 한 줄을 추가한다.

“파일을 인덱싱하는 작업이 끝나고 나면 이 알고리즘은 O(p + k) 시간에 동작한다. 여기서 p와 k는 각 단어의 출현 횟수이다.”

622쪽

페이지 세 번째 줄의 공식을 다음과 같이 수정.

Val(x, y) = Val(x - 1, y) + Val(x, y - 1) - Val(x - 1, y - 1) + M[x][y]
633쪽

소스코드 7행을 다음과 같이 수정

return lookup.containsKey(s);

6 thoughts on “정오표

  1. 이병준

    507, 508 페이지 수정내용에 < > 기호가 있는 부분이 올바르게 표시가 되지 않은 문제가 있네요. 507쪽 교정내용은 SmartPointer<T>&가 되어야 할 것 같습니다. 508쪽 교정내용에도 마찬가지 오류가 있습니다.

      1. raccoony

        워드프레스의 pre 태그가 좀 이상하군요. 다시 반영하였습니다. ^^

  2. 첨벙

    오타가 너무 많아요 ㅠㅠ
    285쪽 첫째줄 우너소 -> 원소
    오타가 오나전 많네요.

    1. jogamza Post author

      보시는 데 불편을 드려 죄송합니다. 본문 확인 후 정오표에 반영하겠습니다.

Comments are closed.