인프런 워밍업 클럽 CS4기_1주차 발자국

• 강의 수강

   

1. 컴퓨터 구조

(1) 컴퓨터 구성 요소

• CPU, 메모리, 데이터 저장장치 3가지 구조로 구성

• CPU : 중앙처리장치로 ALU(산술논리장치), 레지스터, 제어유닛으로 구성

• 메모리 : RAM(random acces memory) 휘발성 메모리로 프로그램 실행시 메모리를 적재, HDD 와 같은 데이터 저장장치보다 속도가 빠르다. ROM(Read Only Memory) 읽기전용 메모리로 비휘발성이며 Bios와 같은 OS 부팅시 사용된다.

   

• 데이터 저장장치 : HDD(Hard Dirve Disk) 용량이 매우 크지만 데이터 접근시 순회하기 때문에 읽기/쓰기 작업이 오래 걸린다. SSD(Solid State Disk) 장치로 속도가 더 빠른 데이터 저장장치로 있다.

(2) 컴퓨터 역사

• Compute + er의 합성어로 최초의 계산기 개념이 등장

• 주판 -> 펀치홀 방식 -> 진공관 -> 애니악 -> 현대의 컴퓨터 순서로 발전

• 오늘날의 컴퓨터 구조가 폰노이만에 의해서 완성 되었다.

(3) 불 대수

• 컴퓨터는 0과 1의 두가지 값으로 데이터를 인식

• 불 연산 : 0, 1의 연산에는 AND, OR, NOT, NAND, NOR, XOR, NOT XOR 등이 존재한다.

• 불 대수의 성질과 법칙 : 교환법칙, 결합법칙, 분배법칙

• 불 함수 : 여러 개의 불 값을 연산을 통해 하나의 불 값을 결정하는 함수, 진리표를 통해 불 함수를 만들어 낼 수 있으며 수식을 만족하는 불 함수는 여러가지가 될 수 있다.

• 진리표: 여러개의 불 값의 연산 결과를 정리해 놓은 표

• 카르노 맵 : 진리 표와 비슷하며 불 함수를 만족하는 카르노 맵을 만들어서 기존의 불 함수를 더 간결하게 만들 수 있다. 카르노 맵의 결과값을 만족하는 2n 승으로 최대한 길게 값을 묶으면 불 함수 수식을 알 수 있다.

(4) 비트

• 컴퓨터에서 데이트를 표현하는 방식으로 0과 1로 이루어져 있다.

• 컴퓨터는 8비트, 32비트, 64비트 체계 OS가 존재한다.

• 각 비트마다 자리수를 표현하며 8비트는 1바이트를 나타낸다.

• 진법에는 사람이 인식하기 쉬운 10진법과 컴퓨터에서 데이터를 표현하는 2진법이 존재

• 10진법에서 2진법 변환은 값을 2로 나눈후 그 몫을 역순으로 읽으면 된다.

• 2진수는 16진수로 변환이 가능하며 4비트 하나가 16진수로 변환 가능하다.

• 빅에디안 리틀에디안

  • 빅에디안 : 컴퓨터의 메모리 주소 체계에서 가장 큰 값을 순차적으로 저장하는 구조

  • 리틀에디안 : 컴퓨터의 메모리 주소 쳬계에서 가장 작은 값을 순차적으로 저장하는 구조

• 오버플로우와 인터럽트

  • 오버플로우 : 8비트 체계를 가진 컴퓨터에서 표현가능한 최대 숫자 범위를 넘어서 연산을 한 경우 그 값이 예상된 결과를 벗어나는 현상

  • 인터럽트 : 8비트 연산에서 255의 값에 1을 더할 경우 연산의 결과가 0이되면서 발생하는 1의 값

• 음수를 컴퓨터에서 표현하는 방법은 MSB 비트를 부호값으로 사용하여 표현하며 값의 범위는 부호가 없는 경우에 반만 표현 가능하다. 2진수 양수에서 음수를 구하는 방법은 2의 보수를 구하면 가능하다.

   

2. 자료 구조와 알고리즘

(1) 트리와 이진트리

• 개념

  • 노드 : 트리에서 표현되는 하나의 값

  • 루트 노드 : 트리에서 최상위 값

  • 터미널 노드 : 자식트리가 없는 노드

  • 트리 : 데이터 구조를 부모 자식형태로 나타낸 형태이며 부모 노드에 여러개의 자식 노드가 있을 수 있다.

  • 이진 트리 : 트리 형태를 가지면서 부모 노드의 자식 노드가 최대 2개를 넘지 않는다. 부모 노드의 왼쪽 자식 노드로는 더 작은 값의 노드만 올수 있으며 오른쪽 자식노드로는 더 큰 값만 올 수 있다.

  • 포화 이진 트리 : 이진 트리이면서 부모에 자식 노드가 모두 존재하는 트리

  • 완전 이진 트리 : 이진 트리이면서 부모의 자식 노드로 자식노드가 하나만 있거나 없는 트리

  (2)이진 탐색 트리

• 이진 탐색 알고리즘 : 원하는 값을 찾기위해 매번 범위를 반으로 줄여가면서 찾아가는 알고리즘, 데이터가 정렬되지 않은 경우 최대 n의 반복회수가 필요하므로 속도가 매우 느리다.

• 이진 탐색 트리

  • 개념 : 이진 탐색 알고리즘의 단점을 보완, 데이터 구조가 이진 트리를 만족하는 형태

  • 삽입, 검색, 삭제 중 삭제시에 시간이 올래 걸리고 복잡하다.

  • 조건 : 중복된 노드가 없어야 한다, 이진트리의 조건을 자식트리도 만족해야한다.

  • 단점 : 데이터 삽입시 이진 트리 구조가 깨진다면 데이터 검색속도는 n의 반복횟수가 되며 장점이 없어지게 된다.

(3)AVL 트리

• 이진 탐색 트리의 단점을 보완, 데이터 삽입시 이진 트리의 구조를 깨지 않기 위해 왼쪽 자식 트리의 높이와 오른쪽 자식 트리의 높이 차가 최대 2를 넘지 않도록 조건을 만족하는 값을 구한다.

  
  

  3. 회고

   

• 컴퓨터 공학을 전공했기에 대부분 알고 있는 내용이라고 생각했지만 강의를 수강하면서 깊게 알지 못했던 내용들을 다시 한 번 되짚어 부족했던 지식을 채우는 계기가 되었던 것 같습니다. 한 주동안 수강하면서 금방 이해 할 수 있을 거라고 보았지만 중간중간 강의를 다시 보아야 할 만큼 이해하기 어려운 부분들이 있다는 것을 보면서 스스로 부족한 부분들이 아직도 많다는 것을 깨닫게 되었습니다. 지난 한주동안 공부한 내용을 요약하면서도 남들에게 공유할 만큼의 지식을 갖추지 못한 것 같아 갈 깊이 아직 먼 것 같습니다.

   

• 다음 주에는 좀 더 강의에 집중하면서 많은 분들에게 지식 공유를 할 만큼 더 알기 쉽고 잘 정리된 강의 노트를 작성해 볼 예정입니다.

   

   

미션

1. 미션 해결 과정

• 모르는 부분은 강의에서 해당 부분을 찾아서 다시 한 번 복습하는 식으로 해결하였습니다. 풀이하는 방법은 여러가지가 있을 수 있지만 해결한 값의 정답은 GPT를 통해서 검증하였습니다.

   

   

   

• 자료구조와 알고리즘 1주차 미션 문제의 경우 강의에서 제공하는 AVL 트리 구현을 참고해서 필요한 메소드만 새로 추가하는 방식으로 처리하였습니다. 검증시 Tree자체가 이진 트리 구조로 잘 구성되었을 경우에만 Search함수가 정상 동작하는 문제가 있을 것 같습니다.

   

  2. 회고

• 아직 강의 초반부분임에도 불구하고 미션 해결과정에서 어려움을 느꼈습니다. 좀 더 강의 내용을 깊게 학습하고 복습하면서 어려운 문제에도 문제없이 풀 수 있도록 준비를 해야 할 것 같습니다. 미션에 정답은 하나이지만 풀의 방식은 각자가 다를 것이라고 보고 서로 간의 풀이 과정도 공유하면 유익한 강의가 될 것 같습니다.

• AVL 트리 구조의 경우 다소 난이도가 있어서 이해하고 구현하는데 많은 시간이 걸려서 다시 한 번 복습해야 할 듯 싶습니다.