[워밍업클럽4기-CS] 1주차 미션
컴퓨터 구조4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.입력 4개 AND입력 4개 OR입력 4개 NAND입력 4개 NOR입력 4개 XOR다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.A( (BB)’+ 0A) + (CC)' = A(B’ + 0) + C’ = AB’ + A0 + C’ = AB’ + C’(B’B’) + (AD’ + (CA)’)D = B’ + (AD’ + C’ + A’)D = B’ + C’D + A’D(A’B) + B(B1 + BC) = A’B +B(B(1+C)) = A’B + B = (A’+1)B = BB’(1C + BD) + DB = B’C + B’BD + DB = B’C +DB다음 2진수를 10진수로 변환해보세요.110111 = 32 + 16 + 4 + 2 + 1 = 5510000001 = 128 + 1 = 12911111100000 = 1024 + 512 +256 +128 +64 +32 = 2016101010 = 32 + 8 +2 = 42다음 10진수를 2진수로 변환해보세요.10 = 8 + 2 = 101027 = 16 +8 +2 +1 = 1101186 = 64 +16 + 4 + 2 = 1010110516 = 512 + 4 = 1000000100다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)(B’C) + (DB)(AB’) +CB’ + (DC’) + (DA’)자료구조와 알고리즘public class BinaryTree<T> { private T data; private BinaryTree<T> leftTree; private BinaryTree<T> rightTree; private int height; public BinaryTree(T data) { this.data = data; this.leftTree = null; this.rightTree = null; this.height = 1; } public T getData() { return this.data; } public void setData(T data) { this.data = data; } public int getHeight() { return this.height; } public void setHeight(int height) { this.height = height; } public BinaryTree<T> getLeftSubTree() { return this.leftTree; } public void setLeftSubTree(BinaryTree<T> leftTree) { this.leftTree = leftTree; } public BinaryTree<T> getRightSubTree() { return this.rightTree; } public void setRightSubTree(BinaryTree<T> rightTree) { this.rightTree = rightTree; } public BinaryTree<T> removeLeftSubTree() { BinaryTree<T> deletingNode = this.leftTree; this.setLeftSubTree(null); return deletingNode; } public BinaryTree<T> removeRightSubTree() { BinaryTree<T> deletingNode = this.rightTree; this.setRightSubTree(null); return deletingNode; } // 전위순회 public void preOrderTraversal() { System.out.print(this.data + " "); if (this.leftTree != null) { this.leftTree.preOrderTraversal(); } if (this.rightTree != null) { this.rightTree.preOrderTraversal(); } } // 중위순회 public void inOrderTraversal() { if (this.leftTree != null) { this.leftTree.inOrderTraversal(); } System.out.print(this.data + " "); if (this.rightTree != null) { this.rightTree.inOrderTraversal(); } } // 후위순회 public void postOrderTraversal() { if (this.leftTree != null) { this.leftTree.postOrderTraversal(); } if (this.rightTree != null) { this.rightTree.postOrderTraversal(); } System.out.print(this.data + " "); } }public class AvlTree { private BinaryTree<Integer> root; public BinaryTree<Integer> getRoot() { return this.root; } public BinaryTree<Integer> searchCeil(int data) { BinaryTree<Integer> currentNode = this.root; BinaryTree<Integer> result = null; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } else if (currentNode.getData() < data) { currentNode = currentNode.getRightSubTree(); } else { result = currentNode; currentNode = currentNode.getLeftSubTree(); } } return result; } public Integer search(int data) { BinaryTree<Integer> currentNode = this.root; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode.getData(); } else if (currentNode.getData() > data) { currentNode = currentNode.getLeftSubTree(); } else { currentNode = currentNode.getRightSubTree(); } } return null; } public int getHeight(BinaryTree<Integer> node) { if (node == null) { return 0; } return node.getHeight(); } public void updateHeight(BinaryTree<Integer> node) { int leftChildHeight = this.getHeight(node.getLeftSubTree()); int rightChildHeight = this.getHeight(node.getRightSubTree()); node.setHeight(Math.max(leftChildHeight, rightChildHeight) + 1); } public int getBalanceFactor(BinaryTree<Integer> node) { if (node == null) { return 0; } return this.getHeight(node.getLeftSubTree()) - this.getHeight(node.getRightSubTree()); } public BinaryTree<Integer> rotateLeft(BinaryTree<Integer> node) { BinaryTree<Integer> childNode = node.getRightSubTree(); node.setRightSubTree(childNode.getLeftSubTree()); childNode.setLeftSubTree(node); this.updateHeight(node); this.updateHeight(childNode); return childNode; } public BinaryTree<Integer> rotateRight(BinaryTree<Integer> node) { BinaryTree<Integer> childNode = node.getLeftSubTree(); node.setLeftSubTree(childNode.getRightSubTree()); childNode.setRightSubTree(node); this.updateHeight(node); this.updateHeight(childNode); return childNode; } public BinaryTree<Integer> rotation(BinaryTree<Integer> targetNode, int data) { int balanceFactor = this.getBalanceFactor(targetNode); boolean isRootNode = false; if(targetNode == this.root) { isRootNode = true; } if (balanceFactor < -1 && data > targetNode.getRightSubTree().getData()) { targetNode = this.rotateLeft(targetNode); // LL }else if(balanceFactor > 1 && data < targetNode.getLeftSubTree().getData()) { targetNode = this.rotateRight(targetNode); // RR } else if (balanceFactor > 1 && data > targetNode.getLeftSubTree().getData()) { targetNode.setLeftSubTree(this.rotateLeft(targetNode.getLeftSubTree())); targetNode = this.rotateRight(targetNode); // LR } else if(balanceFactor < -1 && data < targetNode.getRightSubTree().getData()) { targetNode.setRightSubTree(this.rotateRight(targetNode.getRightSubTree())); targetNode = this.rotateLeft(targetNode); // RL } if (isRootNode) { this.root = targetNode; } return targetNode; } public BinaryTree<Integer> getUnBalanceNode(BinaryTree<Integer> targetRootNode, BinaryTree<Integer> unBalanceNode) { if (targetRootNode.getLeftSubTree() == null && targetRootNode.getRightSubTree() == null) { unBalanceNode = targetRootNode; return unBalanceNode; } int balanceFactor = this.getBalanceFactor(targetRootNode); if (balanceFactor > 0) { unBalanceNode = this.getUnBalanceNode(targetRootNode.getLeftSubTree(), unBalanceNode); } else if (balanceFactor < 0) { unBalanceNode = this.getUnBalanceNode(targetRootNode.getRightSubTree(), unBalanceNode); } else { unBalanceNode = targetRootNode.getRightSubTree(); } return unBalanceNode; } public BinaryTree<Integer> insert(BinaryTree<Integer> targetRootNode, int data) { if(targetRootNode == null) { targetRootNode = new BinaryTree<>(data); } if (this.root == null) { this.root = targetRootNode; } else if (targetRootNode.getData() == data) { return targetRootNode; } else if (targetRootNode.getData() > data) { targetRootNode.setLeftSubTree(this.insert(targetRootNode.getLeftSubTree(), data)); } else { targetRootNode.setRightSubTree(this.insert(targetRootNode.getRightSubTree(), data)); } this.updateHeight(targetRootNode); targetRootNode = this.rotation(targetRootNode, data); return targetRootNode; } public BinaryTree<Integer> remove(BinaryTree<Integer> targetRootNode, int data, BinaryTree<Integer> parentNode) { if (targetRootNode.getData() > data && targetRootNode.getLeftSubTree() != null) { targetRootNode.setLeftSubTree(this.remove(targetRootNode.getLeftSubTree(), data, targetRootNode)); } else if (targetRootNode.getData() < data && targetRootNode.getRightSubTree() != null) { targetRootNode.setRightSubTree(this.remove(targetRootNode.getRightSubTree(), data, targetRootNode)); } else if (targetRootNode.getData() == data) { targetRootNode = this.removeHelper(targetRootNode, data, parentNode); if (parentNode == null && targetRootNode != null) { this.updateHeight(targetRootNode); BinaryTree<Integer> unBalanceNode = this.getUnBalanceNode(targetRootNode, null); targetRootNode = this.rotation(targetRootNode, unBalanceNode.getData()); } return targetRootNode; } this.updateHeight(targetRootNode); BinaryTree<Integer> unBalanceNode = this.getUnBalanceNode(targetRootNode, null); targetRootNode = this.rotation(targetRootNode, unBalanceNode.getData()); return targetRootNode; } private BinaryTree<Integer> removeHelper(BinaryTree<Integer> deletingNode, int data, BinaryTree<Integer> parentNode) { BinaryTree<Integer> fakeParentRootNode = new BinaryTree<>(0); fakeParentRootNode.setRightSubTree(this.root); if (parentNode == null) { parentNode = fakeParentRootNode; } BinaryTree<Integer> deletingNodeChild = null; if (deletingNode.getLeftSubTree() == null && deletingNode.getRightSubTree() == null) { if (parentNode.getLeftSubTree() == deletingNode) { parentNode.removeLeftSubTree(); } else { parentNode.removeRightSubTree(); } } else if (deletingNode.getLeftSubTree() == null || deletingNode.getRightSubTree() == null) { if (deletingNode.getLeftSubTree() != null) { deletingNodeChild = deletingNode.getLeftSubTree(); } else { deletingNodeChild = deletingNode.getRightSubTree(); } if (parentNode.getLeftSubTree() == deletingNode) { parentNode.setLeftSubTree(deletingNodeChild); } else { parentNode.setRightSubTree(deletingNodeChild); } } else { BinaryTree<Integer> replacingNode = deletingNode.getLeftSubTree(); BinaryTree<Integer> replacingNodeParent = deletingNode; while (replacingNode.getRightSubTree() != null) { replacingNodeParent = replacingNode; replacingNode = replacingNode.getRightSubTree(); } deletingNode.setData(replacingNode.getData()); if (replacingNodeParent.getLeftSubTree() == replacingNode) { replacingNodeParent.setLeftSubTree(replacingNode.getLeftSubTree()); } else { replacingNodeParent.setRightSubTree(replacingNode.getLeftSubTree()); } deletingNodeChild = deletingNode; } if (fakeParentRootNode.getRightSubTree() != this.root) { this.root = fakeParentRootNode.getRightSubTree(); } return deletingNodeChild; } }public class GarbageCollector { private final AvlTree avlTree; public GarbageCollector() { this.avlTree = new AvlTree(); } public void insertFreeMemory(int size) { this.avlTree.insert(this.avlTree.getRoot(), size); } public BinaryTree<Integer> searchFreeMemory(int size) { return this.avlTree.searchCeil(size); } public void releaseFreeMemory(int size) { this.avlTree.remove(this.avlTree.getRoot(), size, null); } public static void main(String[] args) { GarbageCollector gc = new GarbageCollector(); System.out.println("================= 빈 메모리 영역 초기화 ================="); gc.insertFreeMemory(64); gc.insertFreeMemory(48); gc.insertFreeMemory(87); gc.insertFreeMemory(13); gc.insertFreeMemory(102); gc.insertFreeMemory(34); gc.insertFreeMemory(61); gc.insertFreeMemory(40); gc.insertFreeMemory(6); BinaryTree<Integer> freeMemory1 = gc.searchFreeMemory(64); // 64 System.out.println("Found: " + (freeMemory1 != null ? freeMemory1.getData() : "null")); if (freeMemory1 != null) { gc.releaseFreeMemory(freeMemory1.getData()); } BinaryTree<Integer> freeMemory2 = gc.searchFreeMemory(42); // 48 System.out.println("Found: " + (freeMemory2 != null ? freeMemory2.getData() : "null")); if (freeMemory2 != null) { gc.releaseFreeMemory(freeMemory2.getData()); } BinaryTree<Integer> freeMemory3 = gc.searchFreeMemory(150); // X System.out.println("Found: " + (freeMemory3 != null ? freeMemory3.getData() : "null")); if (freeMemory3 != null) { gc.releaseFreeMemory(freeMemory3.getData()); } } } 첨부파일: https://jeongburgger.notion.site/20538ccc08b98012b5a7c6dd7ddf388d?pvs=73https://inf.run/4sVHg (그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편))https://inf.run/yFzxT (만들면서 쉽게 배우는 컴퓨터 구조)
