자료구조와 알고리즘

• P-NP 개념

  • P: 결정론적 튜링기계로 다항시간 내 풀수 있는 문제

  • NP: 비결정론적 튜링기계로 다항시간 내 풀수 있는 문제

    • NP-complete : 다른 NP문제를 환원한 결과인 NP 문제

    • NP-hard : 비결정론적 튜링기계로도 다항시간 내 풀 수 있음이 증명되지 않은 문제

  • P=NP가 증명된다면 존재하는 모든 문제는 결정론적 튜링기계로 해결 가능하다.

• 이진 트리

  • 자식 노드를 최대 두 개만 가지는 트리 자료구조

  • 모든 자식노드가 2개라면 포화 이진 트리, 왼쪽부터 채워진다면 완전 이진 트리

• 이진탐색트리

  • 이진 트리 중 각 서브트리의 루트가 왼쪽 자식노드 보다는 크고 오른쪽 자식노드 보다는 작은 트리

  • 균형을 보장하지 않으므로 최악의 경우 탐색에 O(n) 소요

• AVL트리

  • 삽입,제거로 인해 균형이 깨질 경우 회전을 통해 스스로 균형을 맞추는 트리

컴퓨터 구조

• 개요 - 블랙박스, 컴퓨터의 역사, 프로그램 동작 원리

  • 블랙박스 : 인풋에 따른 아웃풋은 예상 가능하나, 내부 동작 원리는 이해할 수 없음 -> 모듈화에 활용

• CPU / 메모리 / 주변장치 / bit

  • 접근속도 : 하드디스크 < RAM/ROM < 캐시메모리 < 레지스터

  • 저장용량 : 하드디스크 > RAM/ROM > 캐시메모리 > 레지스터

• 불 대수 / 진리표

  • 1(true)/0(false)를 활용한 대수 연산

  • 진리표 : 불 대수 연산의 결과표

• 하드웨어 시뮬레이터를 활용한 게이트 구현

   

회고

• 인강 수강에 출퇴근 시간 활용이 생각보다 더 효율적임을 알게되었다.

• 인강 수강과 별개로 금주는 개인 일정 등으로 저녁에 복습을 위해 가진 시간이 많지 않았던 점이 아쉽다.

  • 출퇴근 시간에 수강할 수 있는 인강의 양이 예상보다 더 많음을 확인했으니 차주는 출퇴근 시간 활용으로 벌어둔 저녁 시간을 더 활용하면 좋을 것 같다.