CS 1주차 발자국 및 미션

CS 1주차 발자국 및 미션

미션 - 컴퓨터 구조 및 자료구조

Zip 파일을 개인 노션에 링크로 연결해두었습니다.
구성 : 컴퓨터 구조 문제해결 - 엑셀파일 및 cicr 파일 / 자료구조 - mjs 파일 3개

Notion Link

https://royal-fox-5e2.notion.site/CS-2053a46c075380d8be7cf08aacdac274?source=copy_link

미션 - 풀이과정

컴퓨터 구조 1번 문제

AND는 모든 인자가 1인 경우만 T를 반환한다. 이 점을 이용하여 모든 경우의 수 중 모두 1를 제외하고 0를 반환
OR는 인자 중 1개라도 1인 경우 T를 반환한다. 이 점을 이용하여 모든 경우의 수 중 모두 0를 제외하고 1를 반환
NAND, NOR는 AND,OR의 반전이라는 사실을 이용하여 작성
XOR는 1인 인자의 개수가 홀수 개일 경우만 1를 반환 나머지는 모두 0를 반환

컴퓨터 구조 2번 문제

분배,결합,흡수 법칙들을 사용하여 풀이 , 항등원의 원리 함께 사용
'(NOT) 연산은 AND->OR OR->AND 원리 사용
if문의 T/F 조건 작성과 비슷하여 쉽게 풀었음

컴퓨터 구조 3~4번 문제

2진법에서 10진법으로 변환하는 원리는 각 자리수가 2의 제곱수를 의미하므로

(1 또는 0)*1 + (1 또는 0)*2 + (1 또는 0)*4 ... 방식으로 모두 더하면 결과 나옴
10진법에서 2진법도 마찬가지로 10진수를 2로 반복적으로 나눈 나머지를 역순으로 작성하면 됨

컴퓨터 구조 5번 문제

제일 재밌게 풀었던 문제로 연산 우선순위를 생각해서 각 부품들을 연결하여 품

자료구조 문제

개인적으로 자바스크립트 문법를 하나도 몰라서 작성할 때 힘들었던 문제
(AVLTree 코드에 주석을 작성하며 분석하여 감을 잡고 작성)
(다음엔 시간을 조금 더 사용하여 C/C++로 작성해보고 변환해야겠다)
삽입 부분은 기존의 AVL의 Insert를 활용하면 균형을 유지한 상태로 삽입 가능
제거 부분도 삽입과 동일하게 Remove를 활용하면 균형을 유지하면서 제거 가능
탐색 부분이 생각보다 고려해야하는 요소가 많아서 힘들었다.
해제하려는 메모리의 크기가 트리의 구성요소랑 정확히 같을 경우 그냥 반환해준다.
해제하려는 메모리의 크기가 현재 노드보다 작다면 왼쪽 자식들을 재귀적으로 탐색하고
만약 크다면 오른쪽 자식들을 재귀적으로 탐색하여 최적의 크기를 찾아서 반환한다.

    searchFreeMemory(size) {

        let resultNode = this.freeMemoryTree.search(size);

        if (resultNode != null) {
            return resultNode; 
        }

        let current = this.freeMemoryTree.root;
        let candidate = null;

        while (current != null) {
            if (current.getData() >= size) {
                candidate = current;
                current = current.getLeftSubTree();
            } else {
                current = current.getRightSubTree();
            }
        }

        return candidate; 
    }

미션 - 느낀점

컴퓨터 구조 미션은 개인적으로 쉬웠는데 왜냐하면 C/C++를 위주로 게임프로그래밍을 공부를 했기 때문에

비트마스크와 비트쉬프트를 활용하여 오브젝트의 태크나 레이어를 설정하기 때문에 진법 문제와 GATE 문제를

쉽게 풀 수 있었다.
회로도는 생소 했지만 강의를 보고 실습을 해보니 금방 적응하여 풀 수 있었다.
자료구조는 언어만 생소하였고 논리적 흐름을 이해하니 GC의 문제도 트리에서 요소를 탐색하여 가져오고

삭제하는 부분은 어렵지 않게 구현할 수 있었다.

학습 내용 정리 및 느낀 점
내용을 정리하기 앞서 아직 어떻게 정리해야 이쁘고 보기 좋게 정리 할 수 있는지 몰라서 서툰 면이 있다.
또한 zip파일로 묶어서 업로드 할 수 있을 줄 알았는데 링크로만 올릴 수 있다는 점을 처음 알아서

다음에는 링크로 할 수 있게 블로그에 미션을 풀고 걸어야 겠다.
다음 주에는 조금 더 보기 좋게 정리하기 위해서 노력해보고 싶다.

다음주 목표

자료구조 C/C++로 작성이후 자바스크립트로 변환
공부 내용 정리해서 더 깔끔하게 작성해보기

모르는 내용을 중심으로 정리

P - NP 문제

P 문제란 결정론적 튜링머신을 사용하여 다항 시간 내 정답을 구할 수 있는 문제를 말하며

여기서 결정론적 튜링머신은 현재 상태에서 다음 상태로 넘어갈 때 그 상태가 유일하여 단방향으로 진행한다.

NP문제란 비결정론적 튜링머신을 사용하여 다항 시간 내 정답을 구할 수 있는 문제를 의미하며

여기서 비결정론적 튜링머신은 현 상태에서 다음 상태로 넘어갈 때 그 상태가 유일하지 않아 다방향으로 진행한다.

NP-Hard는 NP 문제들을 다항 시간 내에 A문제로 치환 가능한 문제를 의미하며

NP-Complete는 NP-Hard이면서 NP에 속하는 문제를 뜻한다.

이진 탐색 트리

모든 데이터가 정렬되었다는 가정 하에 log N의 속도를 보여주는 이진 탐색을 기반으로 한 트리로

루트 노드의 왼쪽은 작은 값 오른쪽은 큰값으로 정렬되어 있는 트리이다. 장점으로 빠른 탐색,삽입,삭제가 가능하지만

단점으로 경사트리가 될 경우 시간 복잡도는 N으로 떨어지게 된다. 또한 균형을 쉽게 유지할 수 없다는 단점을 가지고 있다.

AVL 트리

이진 탐색 트리의 단점은 없애고 장점만 취하기 위해 개발된 구조 왼쪽과 오른쪽의 높이가 2이상 차이가 나면 균형이 무너졌다고 판단하여 LL,RR,LR,RL 회전으로 균형을 맞추어 경사트리가 되지 않도록 균형을 유지한다.

카르노 맵

F = AB+A'B+A'B' 라고 가정 할 때 각 항이 1이 될 때의 상황을 표로 나타내여 큰 영역으로 묶어서 표현하면 식을 간소화할 수 있도록 도와주는 맵이다. 이를 통해 복잡한 공식이나 법칙을 사용하지 않더라도 식을 간단하게 만들 수 있다는 장점이 있다.

빅 엔디안, 리틀 엔디안

빅 엔디안은 상위 바이트를 먼저 저장하여 기록하는 방식이며 리틀 엔디안은 하위 바이트를 먼저 저장하는 방식이다.

빅 엔디안은 사람이 읽기 편하다는 장점이 있고 네트워크에서 사용하는 방식이기도 하다. (TCP/IP) 리틀 엔디안은

사람이 읽기 조금 불편하지만 CPU가 연산하기 편하게 구성된다는 장점이 있다.

스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점

칭찬 하고 싶은 점

현장강의가 아닌 온라인 강의를 집중있게 듣는 것을 힘들어 하는데 그럼에도 불구하고 끝까지 들었다는 점
자바스크립트라는 새로운 언어로 자료구조를 공부했음에도 코드에 잘 적응해서 미션을 수행 했던 점

아쉬운 점

아직은 필기하는 습관이 잡혀있지 않아서 정리가 깔끔하지 못한 점
어떤 관점에서 해결하고 어떤 생각을 했는지 쉽게 정리하지 못한 점 (직관적으로 계산하고 공부한 점)

보안하고 싶은 점

5일 동안 강의 들은 내용을 토,일에 정리하지 말고 그날 정리하고 작성하기
조금 더 깔끔하게 정리하기