컴퓨터 구조

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

XOR은 1의 개수가 홀수일 때 1, 짝수일 때 0

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 =
   → 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 1×2⁰
   → 32 + 16 + 0 + 4 + 2 + 1 = 55

2. 10000001 =
   → 1×2⁷ + 0×2⁶ + … + 0×2¹ + 1×2⁰
   → 128 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 129

3. 11111100000 =
   → 1×2¹⁰ + 1×2⁹ + 1×2⁸ + 1×2⁷ + 1×2⁶ + 1×2⁵ + 0×2⁴ + … + 0×2⁰
   → 1024 + 512 + 256 + 128 + 64 + 32 = 2016

4. 101010 =
   → 1×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰
   → 32 + 0 + 8 + 0 + 2 + 0 = 42

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

1. 10 = 1010

10 ÷ 2 = 5 → 나머지 0

5 ÷ 2 = 2 → 나머지 1

2 ÷ 2 = 1 → 나머지 0

1 ÷ 2 = 0 → 나머지 1

2. 27 = 11011

27 ÷ 2 = 13 → 나머지 1

13 ÷ 2 = 6 → 나머지 1

6 ÷ 2 = 3 → 나머지 0

3 ÷ 2 = 1 → 나머지 1

1 ÷ 2 = 0 → 나머지 1

3. 86 = 1010110

86 ÷ 2 = 43 → 나머지 0

43 ÷ 2 = 21 → 나머지 1

21 ÷ 2 = 10 → 나머지 1

10 ÷ 2 = 5 → 나머지 0

5 ÷ 2 = 2 → 나머지 1

2 ÷ 2 = 1 → 나머지 0

1 ÷ 2 = 0 → 나머지 1

4. 516 = 1000000100

516 ÷ 2 = 258 → 나머지 0

258 ÷ 2 = 129 → 나머지 0

129 ÷ 2 = 64 → 나머지 1

64 ÷ 2 = 32 → 나머지 0

32 ÷ 2 = 16 → 나머지 0

16 ÷ 2 = 8 → 나머지 0

8 ÷ 2 = 4 → 나머지 0

4 ÷ 2 = 2 → 나머지 0

2 ÷ 2 = 1 → 나머지 0

1 ÷ 2 = 0 → 나머지 1

5. 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.

circ파일링크

1.(B’C) + (DB)

2.(AB’) +C

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

자료구조와 알고리즘

문제

Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다. 여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)

풀이

내가 만든 AVLTree를 이용해서 풀어보았다

• key와 같거나 큰 값 중 가장 작은 노드를 찾아야 함

• 예: key = 42, 트리에 {6, 13, 34, 40, 48, 61, ...}이 있다면 → 48 반환해야 함

GarbageCollector.cpp

#include "AVLTree.h"

class GarbageCollector
{
public:
	void insertFreeMemory(int size)
	{
		tree.Insert(size);
	}

	void releaseFreeMemory(int size)
	{
		tree.Remove(size);
	}

    int searchFreeMemory(int size) {
        AVLTree::Node* node = tree.GetRoot();
        AVLTree::Node* result = nullptr;

        while (node) {
            if (node->key == size)
                return node->key;
            if (node->key > size) {
                result = node;
                node = node->left;
            }
            else {
                node = node->right;
            }
        }
        return result ? result->key : -1;
    }
    void printFreeMemory() {
        tree.printTree();
    }
private:
	AVLTree tree;
};

출력 결과

int main() {
	GarbageCollector gc;
	cout << "========== 빈 메모리 영역 초기화 ==========\n";
	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);

	gc.printFreeMemory();

	cout << "\n========== 메모리 요청: 64 ==========" << endl;
	int m1 = gc.searchFreeMemory(64);
	if (m1 != -1) {
		cout << "획득한 메모리: " << m1 << endl;
		gc.releaseFreeMemory(m1);
	}

	cout << "\n========== 메모리 요청: 42 ==========" << endl;
	int m2 = gc.searchFreeMemory(42);
	if (m2 != -1) {
		cout << "획득한 메모리: " << m2 << endl;
		gc.releaseFreeMemory(m2);
	}

	cout << "\n========== 남은 메모리 ==========" << endl;
	gc.printFreeMemory();
	return 0;
}