[워밍업클럽4기-CS] 1주차 미션

[워밍업클럽4기-CS] 1주차 미션

avraskio 15일 전

컴퓨터 구조

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

    1. 입력 4개 AND

      image

    2. 입력 4개 ORimage

    3. 입력 4개 NANDimage

    4. 입력 4개 NORimage

    5. 입력 4개 XORimage

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

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

    2. (B’B’) + (AD’ + (CA)’)D = B’ + (AD’ + C’ + A’)D = B’ + C’D + A’D

    3. (A’B) + B(B1 + BC) = A’B +B(B(1+C)) = A’B + B = (A’+1)B = B

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

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

    1. 110111 = 32 + 16 + 4 + 2 + 1 = 55

    2. 10000001 = 128 + 1 = 129

    3. 11111100000 = 1024 + 512 +256 +128 +64 +32 = 2016

    4. 101010 = 32 + 8 +2 = 42

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

    1. 10 = 8 + 2 = 1010

    2. 27 = 16 +8 +2 +1 = 11011

    3. 86 = 64 +16 + 4 + 2 = 1010110

    4. 516 = 512 + 4 = 1000000100

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

    1. (B’C) + (DB)image

    2. (AB’) +Cimage

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

자료구조와 알고리즘

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://inf.run/4sVHg (그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편))

https://inf.run/yFzxT (만들면서 쉽게 배우는 컴퓨터 구조)

댓글을 작성해보세요.

채널톡 아이콘