정오표

12쪽 예제-5 해답

따라서 n = O(n2)이며 c = 2, …이다.

따라서 n = O(n)이며 c = 1, …이다.

 

25쪽 문제-22 점화식 복잡도 해답

T(n) = 2^n – (2n – 1)

T(n) = 1

T(n) = 2^n – (2^n – 1)

T(n) = 1

 

——- 아래 내용은 2쇄에 반영되었습니다. ——-

148쪽 밑에서 2번째 줄

O(n제곱)

O(n^2)

177쪽 코드 다음과 같이 정정

void PostOrderNonRecursive(BinaryTreeNode root) {
LLStack S = new LLStack();
while(1) {
if(root != null) {
S.push(root);
root = root.getLeft();
}
else {
if(S.isEmpty()) {
System.out.println(“Stack is Empty”);
return;
}
else
if(S.top().getRight() == null) {
root = S.pop();
System.out.println(root.getData());
while (!S.isEmpty() && root == S.top().getRight()) {
root = S.pop();
System.out.println(root.getData());
}
}

if(!S.isEmpty())
root = S.top().getRight();
else root = null;
}
}
S.deleteStack();
}

396쪽 코드 다음과 같이 정정
void shellSort(int[] A) {
int i, j, h, v;
for (h = 1; h < A.length / 9; h = 3 * h + 1) ;

for (; h > 0; h = h / 3) {
for (i = h; i < A.length; i++) {
v = A[i];
j = i;
while (j >= h && A[j – h] > v) {
A[j] = A[j – h];
j -= h;
}
A[j] = v;
}
}
}

549쪽 문제-11 코드 다음과 같이 정정

void RremoveAdjacentPairs(char[] str, int len) {
int j = 0;
for(int i=1; i <= len; i++) {
while((str[i] == str[j]) && (j >= 0)){
// 쌍을 삭제한다.
i++;
j–;
}
str[++j] = str[i];
}
return;
}

567쪽 맨 마지막 코드 다음과 같이 정정

HuffmanCodingAlgorithm(int A[], int n) {
// 우선순위 큐인 PQ를 초기화하여 A의 항목들을 저장한다.
Heap PQ = new Heap();
BinaryTreeNode *temp;
for(i = 1; i<n; i++) {
temp = new BinaryTreeNode();
temp.setLeft(PQ.deleteMin());
temp.setRight(PQ.deleteMin());
temp.setData(temp.getLeft().getData() + temp.getRight().getData());
PQ.insert(temp);
}
return PQ;
}

 

8 thoughts on “정오표

  1. 강경구

    오탈자 신고 부분은 여기에다 해야되나요? 우측에 “오탈자 신고” 메뉴가 있어 거기다 했는데 피드백이 없어서 문의 드립니다.

    1. jogamza Post author

      안녕하세요, 강경구 님!
      오탈자 관리 계정을 확인해서 연락드리겠습니다.
      고맙습니다.

    2. jogamza Post author

      오탈자 관리 계정에 문제가 생겨서 메일이 도착하지 않았습니다.
      죄송하지만 다시 한 번 보내 주시면 바로 확인 후 회신드리겠습니다.

  2. 책보고 공부하는 중

    P.396의 쉘 정렬 구현
    void ShellSort(int A[], int array_size){
    int i, j, h, v;
    for(h = 1; h = array_size/9; h = 3*h+1); //이해불가
    for(; h > 0; h = h/3){
    for(i = h+1; i = array_size; i += 1){ //이해불가
    v = A[i];
    j = i;
    while(j > h && A[j-h] > v){
    A[j] = A[j-h];
    j -= h;
    }
    A[j] = v;
    }
    }
    }

    조건에 맞는건가요?

    완전이진트리쪽 구현에서도 형변환쪽이 제대로 설명과 구현이 되지 않은 것 같은데?
    소스에 대한 다른 문제는 없나요?

    1. wooil Post author

      안녕하세요. 불편을 끼쳐 죄송합니다. 코드가 다음과 같이 정정되어야 합니다.

      void shellSort(int[] A) {
      int i, j, h, v;
      for (h = 1; h < A.length / 9; h = 3 * h + 1) ; for (; h > 0; h = h / 3) {
      for (i = h; i < A.length; i++) { v = A[i]; j = i; while (j >= h && A[j – h] > v) {
      A[j] = A[j – h];
      j -= h;
      }
      A[j] = v;
      }
      }
      }

  3. RossSong

    p25, 문제-22, 점화식 복잡도 해답
    T(n) = 1 바로 윗줄에서
    T(n) = 2^n – (2n – 1) 틀렸음
    T(n) = 2^n – (2^n – 1) 임.
    [ ] 안에 있는 2^n-1 + 2^n-2 + … + 2^0 = 2^n 이 아니라
    p19에 나오는 등비수열에 따라 2^n – 1 임.
    그래서 T(n) = 2^n – (2^n -1) 이 되어
    T(n) = 1 이 됨.

    1. june Post author

      역자께 확인했습니다. 정오표에 반영하겠습니다. 지적 감사합니다.

Comments are closed.