[2/10] 2과목-1)데이터 입출력 구현

★이 파트는 무조건 꼼꼼히 다시 공부해야 함 자료구조 및 정렬 너무 어려워 특히 정렬 다시 공부하기★

01. 자료 표현 단위와 진법

• 10진수로 바꾸는 방법 알지? 십의자리수진수^(십의자리수-1) + 일의자리수진수^(일의자리수-1) + ....
• 자료 표현 방식 : 비트 > 니블 > 바이트 > 워드 > 필드 > 레코드 > 블록 > 파일 > 데이터베이스
• 10진수에서 각 진수로 바꾸는 방법?

02. 고정 소수점과 부동 소수점

• 1의 보수, 2의 보수 부호화 절대치 : 0이면 양수, 1이면 음수
• 고정 소수점 : 정수
• 부동 소수점 : 실수
• Widening : 정수형을 실수형으로 변환 시 정보의 손실이 없음
• Narrowing : 실수형을 정수형으로 변환 시 정보의 손실이 있음
• 저장 용량 단위 : 킬로 메가 기가 테라 P E Z Y !!!
  Peta Exa Zetta Yotta
• 속도 및 길이 단위 : deci(10^-1) centi(-2) milli(-3) micro(-6) / nano(-9) pico femto atto / zepto yocto(-24)

03. ★★★★★자료 구조

• 자료 구조 : 프로그램에서 쉽게 사용될 수 있도록 구성된 데이터 간의 논리적인 관계
• 선형리스트, 스택, 큐, 트리 ...
• 단순 구조 : int, float, double, char
• 선형 구조(1:1) : Stack, Queue, Deque, Linear List(연속 리스트, 연결 리스트), Linked List
• 비선형 구조(1:N, N:M) : Tree, Graph
• 파일 구조 : 순차 파일, 색인 파일

• 스택 :

• 큐 :

• 데크 :

• 선형 리스트 :

• 연결 리스트 :

• 트리 :

• 그래프 :

• 이진 트리 순회 3가지 방법 : P I PO
  Preorder : 근노드 -> 좌측 -> 우측
  Inorder : 좌측 -> 근노드 -> 우측
  Postorder: 좌측 -> 우측 -> 근노드

• 트리의 차수 : 자식 제일 많은 놈의 자식 수 / 단말 노드 : 제일 끝 놈

• 무방향 완전 그래프 간선 수 : n(n-1)/2

• 방향 완전 그래프 간선 수 : n(n-1)

04. 검색(탐색)

• 시간 복잡도 : O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3)
  0(1) : 알고리즘 수행시간이 입력 데이터 수와 관계없이 일정함
  0(log2n) : 이분검색, 이진트리검색
  0(n) : 수열, 선형(순차)검색
  0(nlog2n) : 퀵, 힙, 합병정렬
  0(n2) : 버블, 선택, 삽입정렬 (버, 선, 삽)
  0(n3) : 행렬 곱셈 알고리즘

• 선형 검색 : 처음부터 하나씩 비교하여 검색, 순서 상관 없음, 단순 느림, 0(n), 평균비교횟수 = (n+1)/2

• 이진 검색 : 전체자료를 이등분하면서 검색, 전체 자료수 알 때, 순서대로 정렬 필요, O(log2n)

• 보간 검색 : 찾고자 하는 자료의 위치값으로 검색, 일정한 규칙 있을 때, 전체 자료 수 알아야, 순서대로 정렬 필요, 순차 검색, 사전식 검색

• 블록 검색 : 그룹별로 블록화하여 인덱스로 만들어 검색, 순차 검색
  가장 이상적인 블록 개수 - 루트n개

• 이진 트리 검색 : 첫째 자료는 근노드, 근노드와 비교해서 작으면 왼쪽, 크면 오른쪽

• 해싱 검색 : 자료를 찾는 특별한 규칙(해싱 함수)으로 검색 대상의 자료를 저장하여 자료 찾기,

• 해싱 함수 종류 7개 (암기) : 제 제 폴댄스 숫기 의 기 소침 중 국감
  제산법, 제곱법, 폴딩법, 숫자분석법, 의사 무작위법, 기수 변환법, 중간 제곱법 / 충돌이 적어야 하고 계산이 쉬워야 함

• 해싱 용어 정리 :

• 그래프 탐색 : 그래프의 모든 정점을 방문하는 것, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

• B-Tree : DB나 파일에 사용되는 구조, 루트 노드, 리프 노드

05. 정렬(sort)

• 종류 : 버 선 삽 퀵 힙 쉘 이 버
  버블, 선택, 삽입, 퀵, 힙, 쉘, 이진 병합, 버킷 정렬

• 선택 정렬:

• 버블 정렬:

• 삽입 정렬:

• 쉘 정렬:

• 힙 정렬:

• 이진 병합 정렬:

• 버킷 정렬:

• 퀵 정렬:

• 재병화(합) : 재귀적함수호출은 병합정렬

• O(n2)는 버 선 삽

06. 모듈 구현

• 단위 모듈 구현시 : 응(집도)등이 높게, 결합도 낮게 / 항상 예외 처리 로직을 고려 / 화이트박스 테스트 기법 사용

• HTML 5 - Header, Div, Aside, Section, Nav, Article, Footer

• Responsive Web : 리액트, 뷰, 앵귤러 사용