CS 1주차 발자국&미션

1주차 발자국

학습

알고리즘

• 비선형 자료구조 - 트리 (Tree) : 노드와 링크로 구성

  • 포화 이진 트리 : 터미널 노드가 아닌 내부 노드들은 모두 2개의 자식 노드를 갖고 있음

  • 완전 이진 트리 : 포화 이진 트리에서 터미널 노드중 오른쪽 노드가 없는 트리

• 이진 탐색 (Binary Search) : 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색, O(logN)

• 이진 트리의 탐색

  • 전위순회 PreOrderTraversal ( 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 )

  • 중위순회 InOrderTraversal (왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 )

  • 후위순회 PostOrderTraversal ( 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 )

• 이진 탐색 트리 (Binary Search Tree) 규칙

  • 왼쪽 자식 노드는 부모 노드 보다 작은 값

  • 오른쪽 자식 노드는 부모 노드 보다 큰 값

  • 서브트리도 이진탐색트리 유지

  • 중복안됨

• 탐색, 추가, 삭제 시 루트노드부터 비교시작해서 내려감

• 삭제 case

  • 자식 노드가 없는 터미널 노드일 경우

  • 자식 노드 1개

  • 자식 노드 2개

1주차 미션

컴퓨터 구조

1. 4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.

2. 다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.

1. A( (BB)’+ 0A) + (CC)' = (AB’) +C

   
   A( (B)' + 0) + (C)' = (AB') + C
   A(B') + C' = (AB') + C
   AB' + C' = AB' + C
   

    

2. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’)
   (B') + AD'D + (CA)'D = B' + (DC') + (DA')
   B' + A0 + (CA)'D = B' + (DC') + (DA')
   B' + (CA)'D = B' + (DC') + (DA')
   B' + (C' + A')D = B' + (DC') + (DA')
   B' + C'D + A'D = B' + DC' + DA'

   
   
   

3. (A’B) + B(B1 + BC) = B
   (A’B) + B(B + BC) = B
   (A’B) + BB + BBC = B
   (A’B) + B + BC = B
   (A’B) + B = B
   A’B + B = B
   B = B
   

    

4. B’(1C + BD) + DB = (B’C) + (DB)
   B’(C + BD) + DB = (B’C) + DB
   B’C + B’BD + DB = B’C + DB

   
   B’C + 0D + DB = B’C + DB
   B’C + DB = B’C + DB

   
   

3. 다음 2진수를 10진수로 변환해보세요.

1. 110111 = (2^5) * 1 + (2^4) * 1 + (2^3) * 0 + (2^2) * 1 + (2^1) * 1 + (2^0) * 1 = 55

2. 10000001 = (2^7) * 1 + (2^6) * 0 + (2^5) * 0 + (2^4) * 0 + (2^3) * 0 + (2^2) * 0 + (2^1) * 0 + (2^0) * 1 = 129

3. 11111100000 = (2^10) * 1 +(2^9) * 1 +(2^8) * 1 + (2^7) * 1 + (2^6) * 1 + (2^5) * 1+ (2^4) * 0 + (2^3) * 0 + (2^2) * 0 + (2^1) * 0 + (2^0) * 0 = 2016

4. 101010 = (2^5) * 1 + (2^4) * 0 + (2^3) * 1 + (2^2) * 0 + (2^1) * 1 + (2^0) * 0 = 42
   

4. 다음 10진수를 2진수로 변환해보세요. ( 각 수를 2로 계속 나누어 나머지를 기록하여 거꾸로 읽기 )

1. 10 = 0 -> 1 -> 0 -> 1 = 1010

    

2. 27 = 1 -> 1 -> 0 -> 1 -> 1 = 11011

    

3. 86 = 0 -> 1 -> 1 -> 0 -> 1 -> 0 - > 1 = 1010110

    

4. 516 = 0 -> 0 -> 1 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 1 = 1000000100
   

5. 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)

1. (B’C) + (DB)
   

2. (AB’) +C
   

3. B’ + (DC’) + (DA’)
   

   .circ 파일 링크 연결