CS 3주차 발자국 및 미션

학습 내용 정리컴퓨터 구조 명령어 PC를 통해 명령어를 인출하면 우리는 스탭 카운터를 통해 명령어 한개의 세부단계를 파악할 수 있다. 예를 들어 ADD는 CO, MI -> RO, II, CE -> IO, MI -> RO, BI-> EO,AI, FI 로 총 5단계로 이루어진 걸 파악할 수 있다. 어셈블리어기계어를 사람이 다루기 쉬운 언어체계로 만든 것으로 어셈블리어 명령줄은 기본적으로 RAM의 용량과 동일하다. 예를 들어 16Byte RAM이라면 16줄로 명령어와 데이터 영역을 나누어 작성해야 한다. 자료구조_알고리즘 - TrieHashTable를 활용한 자료구조로 검색엔진의 자동완성 기능을 구현할 때 사용한다.최대 힙을 활용하여 검색 수가 많은 검색어부터 사용자에게 보이도록 만들 수 있다.검색시 첫 글자가 HashTable의 Key값을 의미하며 테이블에 존재할 경우 연결된 노드로 계속이동하고특정 문자열("*")의 키값을 얻게 되면 종료되고 Words 리스트에 추가하는 방식이다. - Graph그래프는 트리보다 폭넓은 자료구조를 의미한다.트리는 그래프에서 사이클을 제거하고 연결되지 않은 정점이 존재하지 않으며 계층 구조를 이룬 것을 말한다.그래프는 무방향,방향 그래프로 나뉘고 둘의 차이점은 양방향,단방향의 차이이다. A-B 라고 하면 A와 B는 연결되어 있다. / A->B 라고 하면 A는 B와 연결되어 있지만 B는 A와 연결되지 않음탐색에는 두가지 방법이 있으면 상황에 따라 선택하면 된다.첫번째로 DFS로 깊이 우선 탐색이다.한 노드를 기점으로 끝까지 탐색한다. 사이클이 형성되어 있을 경우 무한 반복하기 때문에 탐색한 노드는 무시한다.두번째는 BFS로 너비 우선 탐색이다.큐를 활용하여 인접한 정점을 모두 탐색하고 끝나면 큐에 있는 다음 정점의 간접정점을 모두 탐색하는 방식이다. 다익스트라 알고리즘 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 직통으로 가는 거리와 경유해서 가는 거리 중 짧은 거리를 테이블에 등록하여 구하는 알고리즘이다. 조금 더 개량된 버전은 A* 알고리즘이 있다. 라우팅 테이블이나 , 네비게이션, 게임 AI의 길찾기 알고리즘 등 많은 분야에서 활용된다. 프림 알고리즘 다익스트라 알고리즘과 유사하지만 모든 간선의 길이가 최단거리가 되도록 만드는 알고리즘이다. 경유해서 가는 거리를 계산에 포함하지 않고 직접적으로 연결되는 거리만 계산한다. 학습하면서 깨달은 점 , 느낀 점세상에 많은 알고리즘들과 자료구조들이 있지만 그것들을 이해하기 위해 기초적인 부분을 많이 공부해야 겠다고 느꼈다.특히 자료구조와 알고리즘을 단단하게 알고있다면 다른 프로그램들을 개발할 때 큰 힘이 될것 같다. 미션 과정 및 느낀점마지막 허프만 코딩 미션이 어려웠다. 생각해야하는 부분이 많고 개념을 충분히 숙지해도 구현하는게 어려웠다.이번 강의들을 통해 배운 내용들을 조금더 탄탄하게 만들 필요가 있다고 느꼈다. 앞으로 좋은 개발자가 되기 위해 열심히 공부해야 겠다. 스스로 칭찬모든 과정을 모두 수료했다는 것에 대해 칭찬하고 싶다.

CS 2주차 발자국 및 미션

학습 내용 정리 컴퓨터 구조 25/06/02 - MUX,디코더, 컨트롤 버퍼 MUX여러개의 입력 중 하나를 출력하는 장치로써 Selection Bit에 의해 출력을 결정함 (1,2,4,8 bit 등 많은 종류가 있음)1비트 : 2입력 의 예시로 입력핀 2개와 셀렉트 핀 1개 그리고 NAND 게이트 3개로 구성할 수 있다.8비트 인 경우도 1비트의 원리와 크게 다르지 않고 입력 핀 수와 비트에 따라 Selection Bit의 자릿수만 달라질 뿐이다.예시) 8비트 2입력 -> Selection 1bit / 8비트 4입력 -> Selection 2bit / 8비트 8입력 -> Selection 3bit 디코더N bit의 입력 중 2^N개의 비트 중 1개를 활성화 하는 장치 Selection bit와 Enable bit로 결정됨 (4bit->RAM에 활용)Enable bit가 1로 활성화 되어 있다면 Selection bit에 따라 출력 결정각 비트를 스플릿터를 활용해 쪼갠 이후 Not게이트와 AND 게이트를 활용하여 구성할 수 있다.예시) 000-> out0 / 001 -> out1 / 111 -> out7 컨트롤 버퍼정확한 입력에 따른 출력 값이 나올 수 있도록 입력을 넣을 건지 말 건지 결정하는 역할을 수행하는 장치입력값을 그대로 내보내거나, 연결을 끊어 어떤 값도 아닌 'U'(Undefined) 상태를 출력할 수 있다.사전 지식 : 5V -> logical 1 / 0V -> logical 0 / 0.8~2V -> 해석할 수 없는 값(노이즈)25/06/03 - ALU (반 가산기, 전 가산기 사용) 반가산기, 전가산기반 가산기는 최하위 1 비트의 덧셈을 가능하게 한다.하지만 자리올림 입력을 반영하지 못하여 여러 개의 비트를 더하려면 전가산기를 사용해야 한다.전 가산기는 반가산기 2개와 OR 게이트를 활용하여 만들 수 있다. ALUcpu에서 계산을 담당하는 역할을 수행한다. 전가산기를 활용하여 만든다.추가로 CU와 연결을 위해 여러가지 회로를 추가한다. (Zero Flag,Carry Flag, Enable Output) 25/06/04 - Latch (+ 조합,순차 논리회로) 조합,순차 논리회로조합 회로는 오직 입력값에 의해서만 출력값이 결정되는 회로로 대부분의 게이트,ALU가 대표적이다.ㅏ순차 회로는 출력 중 하나를 피드백 신호로 입력되어 상태를 기억할 수 있는 회로를 의미한다. Latch순차회로에서 1 비트의 정보를 저장하는 회로대표적인 종류로는 SR,D,JK Latch 가 있다. SR LatchSet-Reset의 줄임말로 두개의 입력에 따라 두개의 출력 값을 가지는 회로이다.출력 값을 Q,Q'라고 할 때 두 값을 서로 상보적이다. (1,0 / 0,1)따라서 만약 S,R 모두 1일 경우 논리적 모순으로 사용 불가하다. (NOR 게이트에서 동시에 0을 출력하기 때문)이 문제로 D 와 JK Latch 등장 D LatchData의 줄임말로 1비트의 정보를 저장하는 회로이다.입력을 1개로 줄임으로써 SR의 문제를 해결한다. JK LatchSR 회로의 단점을 보안한 회로 J,K 입력 모두 1,1이여도 출력에서 반전 시켜 준다.즉, 토글 기능이 가능하다. 25/06/05 - Ram (+ Register) 플립플롭1비트의 정보를 저장할 수 있는 순서회로 Ram사전 지식 (Register) - 1bit의 메모리 Latch에 연결된 여러비트를 저장하는 메모리Cpu가 사용할 정보를 저장하는 장치로써 주소+데이터로 이루어져 있다. 자료 구조_알고리즘 25/06/02~05 - RedBlackTree RedBlack TreeAVL 트리보다 삽입,삭제가 빠르지만 탐색속도는 느리다. (AVL 보다 균형을 느슨하게 체크하기 때문)노드마다 색깔이 있으며, 기본적인 높이랑 Black Height라는 높이를 활용하여 균형이 맞는지 체크한다. Heap , PriorityQueue 우선순위 큐는 힙를 이용하여 우선순위가 높은 노드 순으로 삽입,삭제 연산을 하는 자료구조이다. 힙은 (최소힙으로 가정) 루트 부터 시작하여 가장 작은 값이 부모 노드가 되는 구조의 완전 이진 트리이다. 학습하면서 깨달은 점 , 느낀 점1주차 자료구조 강의에 내용 중 어려운 부분은 50%만 이해하고 넘겼는데 이것이 나비효과가 되었다.2주차 강의에서 새로운 내용을 공부할 때 이해가 안가는 부분들이 대부분 이전 학습에서 이해하지 못한 부분이었다.따라서 미션을 하면서 하나하나 코드를 다시 이해하고 해결해야 상황이 와서 힘들었다.추가로 컴퓨터 구조는 Register, Ram 부분 부터 이해가 잘 안갔다. 어려운 점이 많아 미션할 때 힘들었다.다음 내용을 공부하기 전에 한번 더 복습하면서 70~80% 이해하면서 넘어가야 겠다. 다음주 학습 목표새로운 내용을 공부하기 전 복습하고 진행하기코드를 스스로 작성해보기 + 반복 작성 훈련 미션 과정 및 느낀점 자료구조 알고리즘의 경우는 삽입,삭제의 케이스들을 이해하면서 학습을 했다. 학습 내용을 바탕으로 우선순위에 따라 Dequeue가 가능하도록 구현했다. isBigPriority에서 첫번째 우선순위를 비교하고 동일하다면 두번째 우선순위를 비교하도록 작성했다.컴퓨터 구조의 경우 1~3은 회로의 수와 비트 수를 늘리고 그에 맞게 연결하여 풀었다. 4번 문제는 RAM, Register 이해를 해보려고 많이 노력해봤지만 쉽지 않았다. 또한 질문을 하고 싶어도 어떤 부분을 정확히 모르는지 나도 모르는 상태라서 더 답답했다.따라서 기존의 RAM 2개를 연결하면 되지 않을까 했지만 실패했다. 미션 난이도가 점점 쉽지 않다는 것을 느낀다. 스스로 칭찬1주차 글보다 조금 더 정돈된 글을 작성한 점 칭찬!2주차까지 포기하지 않고 강의를 끝까지 들은 점 칭찬!지난 주 목표를 모두 성공한 점 칭찬!

CS 1주차 발자국 및 미션

미션 - 컴퓨터 구조 및 자료구조 Zip 파일을 개인 노션에 링크로 연결해두었습니다.구성 : 컴퓨터 구조 문제해결 - 엑셀파일 및 cicr 파일 / 자료구조 - mjs 파일 3개 Notion Linkhttps://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일 동안 강의 들은 내용을 토,일에 정리하지 말고 그날 정리하고 작성하기조금 더 깔끔하게 정리하기