[워밍업클럽4기-CS] 3주차 미션 - 자료구조와 알고리즘

public class HuffmanNode { char data; int freq; HuffmanNode left; HuffmanNode right; public HuffmanNode(char data, int frequency) { this.data = data; this.freq = frequency; this.left = null; this.right = null; } public HuffmanNode(int freq, HuffmanNode left, HuffmanNode right) { this.data = '\0'; this.freq = freq; this.left = left; this.right = right; } public boolean isLeaf() { return this.left == null && this.right == null; } }public class HuffmanCoding { private Map huffmanCodes; public List> compress(String text) { Map frequencyMap = calculateFrequency(text); HuffmanNode root = buildHuffmanTree(frequencyMap); huffmanCodes = new HashMap(); generateHuffmanCodes(root, ""); return encodeText(); } private Map calculateFrequency(String text) { Map freqMap = new HashMap(); for (char ch : text.toCharArray()) { freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1); } return freqMap; } private HuffmanNode buildHuffmanTree(Map frequencyMap) { PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(n -> n.freq)); for (Map.Entry entry : frequencyMap.entrySet()) { pq.add(new HuffmanNode(entry.getKey(), entry.getValue())); } while (pq.size() > 1) { HuffmanNode left = pq.poll(); HuffmanNode right = pq.poll(); HuffmanNode merged = new HuffmanNode(left.freq + right.freq, left, right); pq.add(merged); } return pq.poll(); } private void generateHuffmanCodes(HuffmanNode node, String code) { if (node == null) return; if (node.isLeaf()) { huffmanCodes.put(node.data, code); return; } generateHuffmanCodes(node.left, code + "0"); generateHuffmanCodes(node.right, code + "1"); } private List> encodeText() { List> result = new ArrayList(huffmanCodes.entrySet()); result.sort(Comparator.comparing(Map.Entry::getKey)); // 알파벳 순 정렬 (옵션) return result; } }public class Main { public static void main(String[] args) { HuffmanCoding huffman = new HuffmanCoding(); String str = "Lorem ipsum dolor sit amet consectetur adipiscing elit. Consectetur adipiscing elit quisque faucibus ex sapien vitae. Ex sapien vitae pellentesque sem placerat in id. Placerat in id cursus mi pretium tellus duis. Pretium tellus duis convallis tempus leo eu aenean."; List> result = huffman.compress(str); for (Map.Entry entry : result) { System.out.printf("[ '%s', '%s' ]\n", entry.getKey(), entry.getValue()); } } } ======================================================================== [ ' ', '110' ] [ '.', '100011' ] [ 'C', '00111110' ] [ 'E', '00111111' ] [ 'L', '10001001' ] [ 'P', '0010011' ] [ 'a', '0101' ] [ 'b', '0010010' ] [ 'c', '11110' ] [ 'd', '00101' ] [ 'e', '011' ] [ 'f', '10001000' ] [ 'g', '0011110' ] [ 'i', '000' ] [ 'l', '0100' ] [ 'm', '10000' ] [ 'n', '11111' ] [ 'o', '00110' ] [ 'p', '10110' ] [ 'q', '001000' ] [ 'r', '10111' ] [ 's', '1110' ] [ 't', '1010' ] [ 'u', '1001' ] [ 'v', '001110' ] [ 'x', '1000101' ]

[워밍업클럽4기-CS] 2주차 미션 - 자료구조와 알고리즘

package DataStructure.cpu; public class BinaryTree { private T data; private BinaryTree leftTree; private BinaryTree rightTree; private BinaryTree parentTree; public BinaryTree(T data) { this.data = data; this.leftTree = null; this.rightTree = null; this.parentTree = null; } public T getData() { return this.data; } public void setData(T data) { this.data = data; } public BinaryTree getLeftSubTree() { return this.leftTree; } public void setLeftSubTree(BinaryTree leftTree) { this.leftTree = leftTree; } public BinaryTree getRightSubTree() { return this.rightTree; } public void setRightSubTree(BinaryTree rightTree) { this.rightTree = rightTree; } public BinaryTree removeLeftSubTree() { BinaryTree deletingNode = this.leftTree; this.setLeftSubTree(null); return deletingNode; } public BinaryTree removeRightSubTree() { BinaryTree 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 BinaryTree getParentTree() { return this.parentTree; } public void setParentTree(BinaryTree parentTree) { this.parentTree = parentTree; } public static void main(String[] args) { BinaryTree tree1 = new BinaryTree(1); BinaryTree tree2 = new BinaryTree(2); BinaryTree tree3 = new BinaryTree(3); BinaryTree tree4 = new BinaryTree(4); BinaryTree tree5 = new BinaryTree(5); BinaryTree tree6 = new BinaryTree(6); BinaryTree tree7 = new BinaryTree(7); tree1.setLeftSubTree(tree2); tree1.setRightSubTree(tree3); tree2.setLeftSubTree(tree4); tree2.setRightSubTree(tree5); tree3.setLeftSubTree(tree6); tree3.setRightSubTree(tree7); tree1.preOrderTraversal(); System.out.println(); tree1.inOrderTraversal(); System.out.println(); tree1.postOrderTraversal(); } }package DataStructure.cpu; public class Heap> { public BinaryTree root; public BinaryTree lastInsertedNode; public Heap() { this.root = null; this.lastInsertedNode = null; } public void insert(T data) { if (this.lastInsertedNode == null) { this.lastInsertedNode = new BinaryTree(data); this.root = this.lastInsertedNode; return; } BinaryTree insertingParent = this.getInsertingParent(); BinaryTree newNode = new BinaryTree(data); if (insertingParent.getLeftSubTree() == null) { insertingParent.setLeftSubTree(newNode); } else if (insertingParent.getRightSubTree() == null) { insertingParent.setRightSubTree(newNode); } newNode.setParentTree(insertingParent); this.lastInsertedNode = newNode; while (newNode.getParentTree() != null) { if (this.isBigPriority(newNode.getData(), newNode.getParentTree().getData())) { T tempData = newNode.getParentTree().getData(); newNode.getParentTree().setData(newNode.getData()); newNode.setData(tempData); newNode = newNode.getParentTree(); } else { break; } } } private boolean isBigPriority(T first, T second) { return first.compareTo(second) getInsertingParent() { if (this.lastInsertedNode.getParentTree() == null) { // 1번 케이스 return this.lastInsertedNode; } else { if (this.lastInsertedNode == this.lastInsertedNode.getParentTree().getLeftSubTree()) { // 2번 케이스 return this.lastInsertedNode.getParentTree(); } else { // 3번 케이스 BinaryTree current = this.lastInsertedNode; BinaryTree firstRightSibling = null; while (current.getParentTree().getParentTree() != null) { current = current.getParentTree(); firstRightSibling = this.getRightSibling(current); if (firstRightSibling != null) { break; } } if (firstRightSibling != null) { while (firstRightSibling.getLeftSubTree() != null) { firstRightSibling = firstRightSibling.getLeftSubTree(); } return firstRightSibling; } else { current = this.root; while(current.getLeftSubTree() != null) { current = current.getLeftSubTree(); } return current; } } } } private BinaryTree getRightSibling(BinaryTree node) { if (node.getParentTree().getRightSubTree() != node) { return node.getParentTree().getRightSubTree(); } return null; } private BinaryTree getLeftSibling(BinaryTree node) { if (node.getParentTree().getLeftSubTree() != node) { return node.getParentTree().getLeftSubTree(); } return null; } public BinaryTree remove() { BinaryTree deletedNode; if (this.lastInsertedNode == this.root) { deletedNode = this.root; this.root = null; this.lastInsertedNode = null; return deletedNode; } BinaryTree prevLastInsertedNode = this.getNewLastInsertedNode(); T tempData = this.root.getData(); this.root.setData(this.lastInsertedNode.getData()); this.lastInsertedNode.setData(tempData); if (this.lastInsertedNode.getParentTree().getLeftSubTree() == this.lastInsertedNode) { this.lastInsertedNode.getParentTree().setLeftSubTree(null); } else { this.lastInsertedNode.getParentTree().setRightSubTree(null); } this.lastInsertedNode.setParentTree(null); deletedNode = this.lastInsertedNode; this.lastInsertedNode = prevLastInsertedNode; BinaryTree current = this.root; do { BinaryTree higherChild = this.getHigherPriorityChild(current.getLeftSubTree(), current.getRightSubTree()); if (higherChild == null) { break; } else if (!this.isBigPriority(current.getData(), higherChild.getData())) { T tempData2 = current.getData(); current.setData(higherChild.getData()); higherChild.setData(tempData2); current = higherChild; } else { break; } } while (current.getLeftSubTree() != null || current.getRightSubTree() != null); return deletedNode; } private BinaryTree getHigherPriorityChild(BinaryTree left, BinaryTree right) { if (left == null) { return right; } else if (right == null) { return left; } else if (this.isBigPriority(left.getData(), right.getData())) { return left; } else { return right; } } private BinaryTree getNewLastInsertedNode() { BinaryTree prevLastInsertedNode; if (this.lastInsertedNode == this.lastInsertedNode.getParentTree().getLeftSubTree()) { // 1 케이스 BinaryTree current = this.lastInsertedNode; BinaryTree firstLeftSibling = null; while (current.getParentTree().getParentTree() != null) { current = current.getParentTree(); firstLeftSibling = this.getLeftSibling(current); if (firstLeftSibling != null) { break; } } if (firstLeftSibling != null) { // a 케이스 while (firstLeftSibling.getRightSubTree() != null) { firstLeftSibling = firstLeftSibling.getRightSubTree(); } prevLastInsertedNode = firstLeftSibling; } else { // b 케이스 current = this.root; while (current.getRightSubTree() != null) { current = current.getRightSubTree(); } prevLastInsertedNode = current; } } else { // 2 케이스 prevLastInsertedNode = this.lastInsertedNode.getParentTree().getLeftSubTree(); } return prevLastInsertedNode; } }package DataStructure.cpu; public class CpuScheduler> { private Heap heap; public CpuScheduler() { this.heap = new Heap(); } public void scheduleTask(T task) { this.heap.insert(task); } public T executeNextTask() { return this.heap.remove().getData(); } }package DataStructure.cpu; public record Process( String name, int cpuReturnCount, int executionCount ) implements Comparable { @Override public int compareTo(Process o) { if(this.executionCount == o.executionCount) { return Integer.compare(o.cpuReturnCount, this.cpuReturnCount); } return Integer.compare(this.executionCount, o.executionCount); } }public class Main { public static void main(String[] args) { CpuScheduler cpuScheduler = new CpuScheduler(); cpuScheduler.scheduleTask(new Process("수치계산프로그램", 4, 0)); cpuScheduler.scheduleTask(new Process("뮤직플레이어", 11, 10)); cpuScheduler.scheduleTask(new Process("웹브라우저", 27, 25)); cpuScheduler.scheduleTask(new Process("터미널1", 34, 2)); cpuScheduler.scheduleTask(new Process("터미널2", 93, 2)); System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask()); System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask()); System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask()); System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask()); System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask()); } } ========================= 터미널 ========================= 다음 실행할 프로세스: Process[name=수치계산프로그램, cpuReturnCount=4, executionCount=0] 다음 실행할 프로세스: Process[name=터미널2, cpuReturnCount=93, executionCount=2] 다음 실행할 프로세스: Process[name=터미널1, cpuReturnCount=34, executionCount=2] 다음 실행할 프로세스: Process[name=뮤직플레이어, cpuReturnCount=11, executionCount=10] 다음 실행할 프로세스: Process[name=웹브라우저, cpuReturnCount=27, executionCount=25]

[워밍업클럽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 { private T data; private BinaryTree leftTree; private BinaryTree 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 getLeftSubTree() { return this.leftTree; } public void setLeftSubTree(BinaryTree leftTree) { this.leftTree = leftTree; } public BinaryTree getRightSubTree() { return this.rightTree; } public void setRightSubTree(BinaryTree rightTree) { this.rightTree = rightTree; } public BinaryTree removeLeftSubTree() { BinaryTree deletingNode = this.leftTree; this.setLeftSubTree(null); return deletingNode; } public BinaryTree removeRightSubTree() { BinaryTree 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 root; public BinaryTree getRoot() { return this.root; } public BinaryTree searchCeil(int data) { BinaryTree currentNode = this.root; BinaryTree result = null; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } else if (currentNode.getData() 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 node) { if (node == null) { return 0; } return node.getHeight(); } public void updateHeight(BinaryTree node) { int leftChildHeight = this.getHeight(node.getLeftSubTree()); int rightChildHeight = this.getHeight(node.getRightSubTree()); node.setHeight(Math.max(leftChildHeight, rightChildHeight) + 1); } public int getBalanceFactor(BinaryTree node) { if (node == null) { return 0; } return this.getHeight(node.getLeftSubTree()) - this.getHeight(node.getRightSubTree()); } public BinaryTree rotateLeft(BinaryTree node) { BinaryTree childNode = node.getRightSubTree(); node.setRightSubTree(childNode.getLeftSubTree()); childNode.setLeftSubTree(node); this.updateHeight(node); this.updateHeight(childNode); return childNode; } public BinaryTree rotateRight(BinaryTree node) { BinaryTree childNode = node.getLeftSubTree(); node.setLeftSubTree(childNode.getRightSubTree()); childNode.setRightSubTree(node); this.updateHeight(node); this.updateHeight(childNode); return childNode; } public BinaryTree rotation(BinaryTree targetNode, int data) { int balanceFactor = this.getBalanceFactor(targetNode); boolean isRootNode = false; if(targetNode == this.root) { isRootNode = true; } if (balanceFactor targetNode.getRightSubTree().getData()) { targetNode = this.rotateLeft(targetNode); // LL }else if(balanceFactor > 1 && data 1 && data > targetNode.getLeftSubTree().getData()) { targetNode.setLeftSubTree(this.rotateLeft(targetNode.getLeftSubTree())); targetNode = this.rotateRight(targetNode); // LR } else if(balanceFactor getUnBalanceNode(BinaryTree targetRootNode, BinaryTree 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 insert(BinaryTree 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 remove(BinaryTree targetRootNode, int data, BinaryTree parentNode) { if (targetRootNode.getData() > data && targetRootNode.getLeftSubTree() != null) { targetRootNode.setLeftSubTree(this.remove(targetRootNode.getLeftSubTree(), data, targetRootNode)); } else if (targetRootNode.getData() unBalanceNode = this.getUnBalanceNode(targetRootNode, null); targetRootNode = this.rotation(targetRootNode, unBalanceNode.getData()); } return targetRootNode; } this.updateHeight(targetRootNode); BinaryTree unBalanceNode = this.getUnBalanceNode(targetRootNode, null); targetRootNode = this.rotation(targetRootNode, unBalanceNode.getData()); return targetRootNode; } private BinaryTree removeHelper(BinaryTree deletingNode, int data, BinaryTree parentNode) { BinaryTree fakeParentRootNode = new BinaryTree(0); fakeParentRootNode.setRightSubTree(this.root); if (parentNode == null) { parentNode = fakeParentRootNode; } BinaryTree 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 replacingNode = deletingNode.getLeftSubTree(); BinaryTree 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 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 freeMemory1 = gc.searchFreeMemory(64); // 64 System.out.println("Found: " + (freeMemory1 != null ? freeMemory1.getData() : "null")); if (freeMemory1 != null) { gc.releaseFreeMemory(freeMemory1.getData()); } BinaryTree freeMemory2 = gc.searchFreeMemory(42); // 48 System.out.println("Found: " + (freeMemory2 != null ? freeMemory2.getData() : "null")); if (freeMemory2 != null) { gc.releaseFreeMemory(freeMemory2.getData()); } BinaryTree 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 (만들면서 쉽게 배우는 컴퓨터 구조)